计算机下棋
Author: 博一 Date: 1991-01-01
计算机下棋采用的方法主要是搜索法，也就是对某一棋局，检查所有可能的走步，看哪一走步对自己最有利，这是一件既费时间又费存贮空间的事情。以下国际象棋为例，在对方走完第一步后，接着该计算机走。这时，计算机最多有35种选择，每种选择对应于搜索树上的一个结点，每个结点对应于棋局上的一种状态。计算机走了其中任何一步后，就应考虑对方会走哪一步。这时，对方最多也有35种选择。因此，计算机要同时考虑352个选择，搜索树有352指数个分枝。分枝不断向下扩展，直至到达某个目标状态。假设一盘棋双方共下50回合，那么这棵搜索树就有100层，总结点数为约3599个。若用目前最快的计算机以每秒十亿结点的速度来处理这棵树，则让计算机下一步棋的时间为3599/109≈3590数年!望而生畏的天文数字告诉我们，用耗尽式方法搜索树是不可能实现计算机与人对弈的。所以必须研究别的减少搜索次数的方法(称为启发式搜索)，这方面的研究已取得了一些成果，但仍需计算机工作者作更多的努力。