Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 关于电脑围棋程序的几点思考 
发信站: 哈工大紫丁香 (2002年04月21日11:00:46 星期天), 站内信件

 在人工智能领域内，搏弈是很重要的一个研究分支。通过对搏弈
的研究，可以解决很多实际问题，使电脑智能向人类智能迈进一大步。
    在搏弈问题中，围棋无疑是其中最有难度的问题。围棋程序的主
要困难在于一，状态点过多。在各种棋类中，围棋在每一步棋选择的
自由度要远远超过其他棋类。这是造成搜索困难的主要原因。二，棋
子间关系抽象化。懂得围棋的人知道，围棋中每一个棋子的影响是受
当前棋局决定的，从某种意义上说，每一个棋子的效率还将受到今后
棋局发展的影响。三，胜利条件复杂，围棋的胜利是靠双方所占目数
的多少决定的。在棋局过程中，一般业余棋手也很难点清（主要是确
定）双方目数，对于电脑就尤显复杂了。第二、三点决定了电脑围棋
程序的估价函数异常复杂。
    由于以上原因，限制了电脑围棋的发展，世界电脑围棋冠军程序
手谈（Handtalk）也只相当于业余2、3级水平。这就构成了一种压力
和机遇，毕竟电脑围棋前途不可限量。
    从原则上讲，博弈程序必然有最后的极限－－扩展全部博弈树。
这也是人脑无法比拟的。但由于围棋的上述特点，我认为现阶段电脑
围棋应从模拟人脑思维过程出发，利用电脑的高速度和准确庞大的记
忆弥补其他方面的不足。
    任何一种博弈程序都至少需要决策（搜索）系统、估价函数和数
据库。由于程序所耗时间主要在决策系统中，所以估价函数和数据库
都应根据决策的需要而改进，而决策也就理所当然的成为电脑围棋的
核心。
    以往的程序大多是在当前棋局下利用数据库选出一定数量的可选
点集合。对每个点进行几乎相同的搜索，然后选出权值最高的点作为
下一步棋输出。但我们知道，一般人们不是这样下棋的。人们往往通
过对棋局进行估计，决定决策方向（往哪下），再具体考虑落点（如
何下）。这样，对一些不在正确行棋方向上的选点，哪怕是局部的好
点，也不会进行过多的考虑。其次，限于电脑围棋水平，在同时有几
个好点时应该采取模糊方法选取，即在不同权值的点下随机选取。
    具体来说，当程序面临一个棋局时，应能将棋局分解为一个个棋
块，即相互紧密关联的棋子（包括黑白双方）。首先调用低级估价函
数。低级估价函数是以棋块为单位，分别与数据库中模型匹配，检验
在此棋块中是否有“急所”，如：未完成的定式，死活棋，待整形的
棋等。当与数据库中无法匹配时，在局部可做小范围的搜索。对找到
的急所可以按类似下面的高级估价函数进行全局范围的估价。低级估
价函数主要解决局部对抗，中盘战斗等问题。
    然后程序调用高级估价函数。高级估价函数把棋盘分为九个部分，
四个角、四个边和中腹。对每一部分分析双方成果，如计算实地目数、
外势影响、方向，征子问题等等，并适当修正本部分和其他部分结果，
最后将九个部分汇总得出全局估价结果并找出最能影响棋局均衡度的
部分。这一函数主要解决程序大局观问题，在序盘，对大场和打入的
选择尤为重要。
    当有了估价结果后，选出一个或几个（主要根据时间和当前棋局
进行情况）落点方向，再进行局部搜索。
    在其他方面如：一、对数据库要求较高，要便于程序匹配数据，
且对每一步应有详细的数值评价，如，取得实地、占有外势，能否脱
先、甚至对将来的影响等。二、适当加如感情参数，如在局面领先下
尽量选择平稳，否则尽量导入复杂。三、加入学习机制，使电脑不断
积累成果。
    以上是我对电脑围棋的大致想法，有很多不完善之处，如棋局抽
象问题，模式匹配问题等等。希望这篇文章能起到抛砖引玉的作用，
使各位同“志”多提建议，不胜感激。

--
当一个女孩儿觉得她不太容易了解那个男人的时候，她会爱他。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.32.57]