面向中国象棋的人机博弈系统研究

面向中国象棋的人机博弈系统研究

１４

湖南农业大学学报（社会科学版?素质教育研究）

?ＪｏｕｒｎａｌｏｆＨｕｎａｎＡｇｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔｙ（ＳｏｃｉａｌＳｃｉｅｎｃｅｓＲｅｓｅａｒｃｈｏｎＱｕａｌｉｔｙＥｄｕｃａｔｉｏｎ）

面向中国象棋的人机博弈系统研究

高建良

（华东理工大学信息科学与工程学院

摘

上海

２００５４０）

要：主要研究了以下搜索算法，负极大值法，Ａｌｐｈａ－Ｂｅｔａ法，使用历史启发和置换表的Ａｌｐｈａ－Ｂｅｔａ法等。估值是象棋人工智能的重

要组成部分，估值函数的评估标准要看几个方面：棋子的基本价值，棋子的灵活性还有棋子的威胁性和攻击性。

关键词：中国象棋；搜索算法；Ａｌｐｈａ－Ｂｅｔａ法；估值一、研究背景

深蓝”与当时的国际象棋１９９７年，ＩＢＭ公司的超级计算机“

世界冠军卡斯帕罗夫进行了一场大肆渲染的比赛，这次被卡斯帕罗夫称作“终于来临的一天”的比赛以卡氏的失败而告终。ＩＢＭ公司将“深

第一文库网

蓝”的获胜称作是人工智能领域的一个里程碑。

人类对机器博弈的研究衍生了大量的研究成果，这些成果不但对人工智能的其它领域产生了重要影响，而且由此衍生而来的多种应用，在诸如航空调度、天气预报、资源勘探、军事博弈，金融／经济调控等领域，也取得了大量引人瞩目的成就。

在我国，中国象棋有着深厚的群众基础，能把这项古老的国粹和现代计算机技术相结合，编制出超过人类智慧的中国象但由于中棋软件，是许多研究中国象棋软件人梦寐以求的目标。

国象棋在计算机实现方面比国际象棋更加复杂，而且中国象棋博弈技术研究落后于国际象棋，所以中国象棋软件还远未达到世界冠军水平。但近年来通过许多中国象棋软件编程爱好者和多个象棋开发团队的努力，使中国象棋软件水平有长足的进步，慢棋已达到业余大师水平，快棋可以和象棋大师对抗。

件实现更加复杂。

现有的计算机的运算能力仍然十分有限。不可能３．估值。

一直搜索到分出输赢的那一步，在有限搜索深度的末端，我们可利用以下几种静态的方法，来估计局面的优劣：

（１）棋子的基本价值。棋子的价值评估，简单的说就是评估

双方都有哪些棋子在棋盘上。根据经验，可以让一个车价值为

１０００，一个马价值为５００，一个兵价值为１００等等。将的价值为

无限大（通常用一个远大于其他棋子的数）。一方的棋子总值就是棋盘上存活的该方棋子乘以棋子价值的和。

（２）棋子的位置。根据棋子所处的位置进行估值。比如说，

过河兵的价值会远远大于没有过河的兵，当头炮一般来说会更有威胁。

（３）棋子的灵活性。棋子的灵活性是指棋子的活动范围，通

常是越大越好。一匹不能动的马很难在棋局中发挥重要作用；同样，一个蹲在角落里的车也是价值不高的。

（４）棋子的关系评估。棋子间的关系也是估值的重要内容

之一，我们可以将某个棋子被对方棋子威胁看成是一个不利的因素。

１．棋盘表示。棋盘表示就是使用一种数据结构来描述棋

一个典型的中国盘及棋盘上的棋子，通常是使用一个二维数组。

象棋棋盘是使用９×每一个元素代表棋盘上１０的二维数组表示。的一个交点。一个没有棋子的交点所对应的元素是０，一个黑帅对应的元素是１，黑士则用２表示等等，依此类推，棋盘的数据表示直接影响到程序的时间及空间复杂度。

（５）象棋专业知识加权。一个优秀的估值还可以对特别的

情形加权。比如空心炮和三子归边等情形可以得到额外的加分。

４．搜索技术。对于计算机来说，直接通过棋盘信息判别走

法的好坏并不精确。除了输赢这样的局面可以可靠地判别外，其他的判断都只能做到大致估计。判别两种走法孰优孰劣的一个好方法就是察看棋局走下去的结果。也就是向下搜索若干步，然后比较发展下去的结果。为了避免差错，我们假定对手的思考也和我们一样，也就是，我们想到的内容，对手也想到了。这就是极大极小搜索算法的基本原则，极大极小搜索算法是本书中所有

２．走法产生。博弈的规则决定了哪些走法是合法的，走法

产生是博弈程序中一个相当复杂而且耗费运算时间的方面。

在中国象棋中，一般情况下每一局面有２０～６０种走法，平均４０种走法，而国际象棋平均只有３５种走法，所以中国象棋软

参考文献：

［１］钟建玲．非英语专业新生英语自主学习现状分析与思考［Ｊ］．惠州学院

学报，２００６，（１）：１１０～１１４．

外语教育出版社，２００４．

大学英语课堂教学要求（试行）》［Ｊ］．外语界，２００５，（２）：［５］夏纪梅．解读《

１２－１４．

［２］罗立胜．理工科学生外语学习行为模式的探讨［Ｊ］．外语与外语教

学，２００１，（９）：３１～３３．

作者简介：

钟建玲（１９７３－），女，广西昭平人，讲师，研究方向：应用语言学，大学英语教学。

［３］朱菊芬．非英语专业新生英语学习现状调查［Ｊ］．外语界，２００３，（１）：

４０～４７．

［４］教育部高等教育司．大学英语课程教学要求（试行）［Ｍ］．上海：上海

２００７年１１月高等教育

湖南农业大学学报（社会科学版?素质教育研究）

?ＪｏｕｒｎａｌｏｆＨｕｎａｎＡｇｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔｙ（ＳｏｃｉａｌＳｃｉｅｎｃｅｓＲｅｓｅａｒｃｈｏｎＱｕａｌｉｔｙＥｄｕｃａｔｉｏｎ）

１５

搜索算法的基础。在过去的几十年中，一些相当成功的改进大大提高了极大极小搜索的效率。Ａｌｐｈａ－Ｂｅｔａ剪枝、置换表、历史启发等手段的综合应用将搜索效率提高了几个数量级。

二、主流搜索算法

—极大极小算法。假定我们有一个函１．最基本的算法——

数可以为每一局面的优劣评分。例如甲胜为＋∞；乙胜为－∞；和局为０；其他的情形依据双方剩余棋子的数量及位置评定－∞～＋这样我们可以建立一棵固定深度的搜索树，∞之间的具体分数。

其叶子节点不必是终了状态，而只是固定深度的最深一层的节点，其值由上述函数评出；对于中间节点，甲方取子节点的最大值，乙方取子节点的最小值。

几乎所有的人在使用基本的极大极小算法时都选择了深度优先搜索方法。这样可以在搜索过程中的任何时候仅仅生成整棵树的一小部分，搜索过的部分被立即删去。显然，这个算法对内存的要求极低，往往在内存只有几千字节的机器上也可以实现。并且同其他的选择相比，速度上也并不逊色。深度优先搜索极大极小树的过程，可以表示为一个递归的形式。

差已达７０倍之多。

置换表的效率随层次加深而提高，在搜索深度为３层时，

Ａｌｐｈａ－Ｂｅｔａ＋置换表同基本的Ａｌｐｈａ－Ｂｅｔａ搜索中评估的叶节点

数目相差约２０％，到６层时此数目则相差达３倍。

随着层数的加深，置换表的命中率逐渐提高，Ａｌｐｈａ－Ｂｅｔａ＋置换表的速度从第４层开始超过基本的'Ａｌｐｈａ－Ｂｅｔａ。而

ＮｅｇａＳｃｏｕｔ＋置换表＋历史启发也从第５层开始超越Ａｌｐｈａ－Ｂｅｔａ＋

历史启发的速度。到第６层时其速度已是Ａｌｐｈａ－Ｂｅｔａ＋历史启发的２．２倍。

历史启发表现出了极高的性能。同置换表相比，历史启发占用的运算时间极少。就单项增强手段看来显著地优于其他方法。

三、估值函数实现

１．估值基础

（１）棋子的价值评估。棋子的价值评估，简单的说就是评估

双方都有哪些棋子在棋盘上。根据我们的经验，可以让一个车价值为５００，一个马价值为３００，一个兵价值为１００等等。将的价值为无限大（通常用一个远大于其他棋子的数）。一方的棋子总值就是棋盘上存活的该方棋子乘以棋子价值的和。如果红色的棋子价值总和大于黑色的棋子价值总和，通常这意味着红方的局势优于黑方。

还可以加入一些其他的明显规律，使估值函数的知识水平提高。例如，兵在棋局中的作用与其过河与否有很大的关系。一个过河兵的作用比未过河的兵对局势的影响要大得多。显然，我们可以把兵的价值根据其过河与否结合其他具体位置信息设计成动态的。

２．负极大值算法。负极大值算法的核心在于：父节点的值

是各子节点的值的负数的极大值。如要这个算法正确运作，还要注意一点额外的东西。估值函数必须对谁走棋敏感，也就是说对于一个该红方走棋的局面返回正的估值的话，则对于一个该黑方走棋的局面返回负的估值。初看上去，负极大值算法比极大极在算小值算法稍难理解，但事实上负极大值算法更容易被使用。法的原理上，这两种算法完全等效。

３．Ａｌｐｈａ－Ｂｅｔａ搜索算法。将Ａｌｐｈａ剪枝和Ｂｅｔａ剪枝加入ｍｉｎｉｍａｘ搜索，就得到Ａｌｐｈａ－Ｂｅｔａ搜索算法。

Ａｌｐｈａ－Ｂｅｔａ搜索能够让我们忽略许多节点的搜索。对于每

一个被忽略的非叶子节点来说，这都意味着不仅节点本身，而且节点下面的子树也被忽略掉了。这就导致了Ａｌｐｈａ－Ｂｅｔａ搜索需要遍历的节点远远少于极大极小算法所遍历的节点。这也同时意味着对搜索同一棵树来说，Ａｌｐｈａ－Ｂｅｔａ搜索所花费的时间远远少于极大极小算法所花费的时间。

同极大极小搜索算法一样，Ａｌｐｈａ－Ｂｅｔａ搜索算法也有点繁琐，我们不仅要在奇数层进行ａｌ－ｐｈａ剪枝，而且还要在偶数层进行ｂｅｔａ剪枝。不过只要将负极大值的形式套用上去，这样在任何一层都只进行ｂｅｔａ剪枝，它就会同负极大值算法一样简洁。

随着搜索深度的增加，Ａｌｐｈａ－Ｂｅｔａ搜索同负极大值搜索在时间耗费上和搜索的叶节点数目上的差距在迅速增大。即使仅仅在第４层，二者在搜索效率上的差距也超过了２０倍。

（２）棋子的灵活性与棋盘控制。棋子的灵活性是指棋子的

活动范围，通常是越大越好。一匹不能动的马很难在棋局中发挥重要作用；同样，一个蹲在角落里的车也是价值不高的。

评估棋子的灵活性较为简单，将一个棋子的所有合法走法罗列出来，乘上该种棋子每一可走步的价值就行了。

与灵活性评估类似，还可以评估博弈双方对棋盘上位置的控制能力。在象棋中，如果某一位置落在某方棋子的合法走步上，就可以认为被该方控制。如果某一位置同时落在双方的合法走步上，我们可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣。能控制更多位置的一方应在这项评分上占优。

（３）棋子关系的评估。棋子间的关系也是估值的重要内容

之一，我们可以将某个棋子被对方棋子威胁看成是一个不利的因素。例如红车的位置在黑马的合法走步当中，此时我们可以把红车的价值减去一个值（例如２００）来刻画这种情形。而如果红马在黑车的合法走步之中，而红马同时也在红卒的合法走步之中，我们可以认为红马置于红卒的保护之下，没有受到威胁，价值不变。

棋子关系的评估应考虑到该谁走棋的问题。如果某个红马落在黑炮的合法走步之内，但此时轮到红方走棋，应认为红马受

４．使用历史启发和置换表的Ａｌｐｈａ－Ｂｅｔａ的搜索算法。在

各种增强手段当中，历史启发对于减少叶子节点数目有极大的作用。这也从另一方面证实了Ａｌｐｈａ－Ｂｅｔａ剪枝的效率对节点顺序的极度敏感。当置换表和历史启发共同作用时，节点数目进一步下降了。搜索的最大深度到达６层的时候，ＮｅｇａＳ－ｃｏｕｔ＋置换表＋历史启发同基本的Ａｌｐｈａ－Ｂｅｔａ搜索中评估的叶节点数目相

２００７年１１月高等教育

１６

湖南农业大学学报（社会科学版?素质教育研究）

?ＪｏｕｒｎａｌｏｆＨｕｎａｎＡｇｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔｙ（ＳｏｃｉａｌＳｃｉｅｎｃｅｓＲｅｓｅａｒｃｈｏｎＱｕａｌｉｔｙＥｄｕｃａｔｉｏｎ）

到的威胁较轻。而如果此时轮到黑方走棋，就应认为红马受到的威胁很大，应减去一个相对较大的值了。如果将被对方威胁，且轮到对方走棋，此时应结束估值返回失败的估值（通常是极大或极小值）。棋子间关系的评估可以在很大程度上提高估值的精度，通常是博弈估值的必备内容。

容易战胜；然而在考虑了棋子灵活性之后，就不会再出现孤炮进入敌群子中的冒进走法，估值比较完备，人工智能比较好。

２．不同搜索方式与搜索深度结果分析

Ａｌｐｈａ－Ｂｅｔａ搜索能够让我们忽略许多节点的搜索。对于每

一个被忽略的非叶子节点来说，这都意味着不仅节点本身，而且节点下面的子树也被忽略掉了。这就导致了Ａｌｐｈａ－Ｂｅｔａ搜索需要遍历的节点远远少于极大极小算法所遍历的节点。这也同时意味着对搜索同一棵树来说，Ａｌｐｈａ－Ｂｅｔａ搜索所花费的时间远远少于极大极小算法所花费的时间。

选择ＡｌｐｈａＢｅｔａＳｅａｒｃｈＥｎｇｉｎｅ，分别在１￣５层的深度上运行，与负极大值的搜索引擎比较，就会发现，在同样的深度下，

２．估值核心的优化

（１）估值函数的速度。在博弈树搜索的过程中，估值核心所

花费的运算时间，对于搜索的速度有着至关重要的影响。随着搜索层数的加深，叶子节点的数目迅速上升，估值函数被数以百万次的调用，花费了大量的运算时间。如何提高估值函数的速度，也成了博弈性能改进的重要话题。

（２）估值函数与博弈性能。在博弈程序的几大主要部分

里，估值函数是与具体的棋类知识紧密结合的一部分。可以说估值函数在很大程度上决定了博弈程序的棋力高低。显然，开发人员可以向估值函数加入大量的棋类知识，使之对于局面的评估更为精确，也可以使用简单的估值函数，以期能够使估值的过程简单而节省运算时间，期望通过更深层的搜索可以使棋力提高。

一般来说过于简单的估值函数和过于复杂的估值函数同样性能不佳。在同等的知识含量下，速度越快，性能越高。在同等速度之下，知识量越大性能越高。在速度和知识量二者的相互作用下，开发者要寻找的是一种平衡，是能够使性能最大化的速度和知识量。

四、结果分析

Ａｌｐｈａ－Ｂｅｔａ搜索引擎的搜索速度快得多。而且，对于同

样的局

面，在同样的搜索深度下，二者找到的最佳走法完全一样。

五、结束语

１．总结

本文对中国象棋的两个关键技术：搜索技术与估值函数进行了研究，并对不同的搜索技术与不同估值函数带来的不同结果进行了分析，通过分析得出了这些技术对中国象棋的适合程度。

２．需要继续研究及有待解决的问题

（１）估值函数。在开发的系统中估值函数考虑的因素还不

够全，很多看似细小的因素在实战中其实影响很大；估值方法中还没有引进历史知识，棋谱库没有建立，无法跟据棋谱中已有下法来调整估值结果；没有加入经验值，如空心炮等大家公认为有利的局面带来的附加值等等。

１．不同估值方式结果分析。如果将灵活性的赋值都归０，

并且将循环统计扫描的数据（有关威胁性）去掉，则估值函数很简单，下出的棋子很幼稚，现以当头炮走法为例，则电脑走法：红（人）炮二平五、黑（电脑）车１进１、红炮五进四、黑车１平２。

如果将灵活性的赋值都归０，而将循环统计扫描的数据（有关威胁性）加上，电脑智能一般，仍以当头炮为例，走法如下：红（人）炮二平五、黑（电脑）炮２进７、红炮五进四、黑马２进３。

如果将灵活性的因素考虑进去，并且将循环统计扫描的数据（有关威胁性）加上，电脑智能不错，仍以当头炮为例，走法如下：红（人）炮二平五、黑（电脑）马２进３。

通过上述３次改变的比较，我们可以看出只考虑棋子的基本价值，估值函数会漏洞很多，导致电脑人工智能很差；考虑了棋子的位置和威胁性，虽然比上一种进步许多，但是走招比较激进，只考虑了棋子威胁和全局的得分，不灵活，人工智能一般，很

（２）搜索算法。搜索算法在两个平台中没有得到很好的体

现，在系统的研究中因为搜索深度一般不是很大，搜索算法带来的影响很难通过实验得出精确结论；没有加入残局库，无法在某些应该有输赢结论的局面下得出完全正确的下法。

参考文献：

［１］王小春．ＰＣ游戏编程（人机博弈）［Ｍ］．重庆：重庆大学出版社，２００２．［２］陆汝钤．人工智能［Ｍ］．北京：科学出版社，１９９５．

［３］王永庆．人工智能原理与方法［Ｍ］．西安：西安交通大学出版社，１９９８．［４］何华灿．人工智能导论［Ｍ］．西安：西北工业大学出版社，１９８８．［５］杨祥金．人工智能［Ｍ］．重庆：科学技术文献出版社重庆分社，１９８８．

作者简介：

高建良（１９６３－），男，讲师，硕士，教研室主任。

２００７年１１月高等教育