博弈在棋类竞技中的应用及暗棋致胜策略(共6页)

1、基于博弈思想的象棋(xingq)暗棋致胜策略模型摘要(zhiyo)： 机器博弈被认为是人工智能(rn n zh nn)领域最具挑战性的方向之一。“深蓝”对阵世界棋王卡斯帕罗夫的胜利也给人们留下无尽的记忆和思考。近些年来IT行业发展极快，计算机的运算能力远胜以往，国内外棋类竞技中的博弈算法也日趋成熟。本文以此为背景，概括地介绍了一般棋类竞技软件博弈算法的主要思想和实现方式，并将博弈的思想创造性地应用在中国象棋变体“暗棋”上，尝试性地提出一种策略模型。关键词：不完全信息博弈；中国暗棋；概率；估值函数；博弈树搜索1引言博弈问题无所不在，小到孩童的游戏与争论、各种场合下的讨价还价,大到商家的竞争、各种

2、突发事件的应急处理、国家的外交、流血的和不流血的战争，只要局中的双方主体存在某种利益冲突，博弈便成为矛盾表现和求解的一种方式。博弈与对策将成为一类智能系统研究的焦点问题。象棋是从两军对阵中抽象出来的一种智力游戏，因此它是博弈的一个标准问题。下棋的双方无时不在调动自己的一切智能，充分发挥逻辑思维、形象思维和灵感思维的能力。所以，在人工智能领域始终将棋类的机器博弈作为最具挑战性的研究方向之一，到现在也已取得了一定的成果1。1997年IBM的超级计算机“深蓝”战胜“世界棋王”卡斯帕罗夫，更是给世界带来了巨大的震撼，掀起了“人机对战”的研究狂潮。无论是国际象棋还是中国象棋，从博弈的角度来说都属于完全信

3、息的动态博弈12，且局面的数量在数学意义上是有限的。因此，理论上只要计算机的速度够快，是可以穷举出所有可能并择一最优解或近似最优解。而暗棋则不同，虽然规则简单，但是具有一定的随机因素，所以决策空间尽管易于遍历，却难以择出最优解，属于一类不完全信息的动态博弈10。本文旨在将博弈思想体现在暗棋对弈之中，列出一些可能的想法和模型，并不奢求提出完备的算法流程。2中国暗棋暗棋是一个利用象棋棋盘与棋子来进行的棋类游戏，它的规则没有象棋般复杂，走棋在上，被吃子在下，虽然暗棋看起来如此的简单，但却一直受到大众的喜爱。游戏一开始需先将所有棋子盖上，布置在4x8的空格上。由其中一人先翻开棋盘中一子，该棋子的颜色（

4、红或黑），就是该名玩家在本局使用的棋，而另一人则是操纵另一个颜色的棋子，双方各拥有16个棋子。游戏的目的就是要把对方的棋子全部吃掉。暗棋是一种“等级”棋，根据棋子(qz)等级的大小实现对抗。具体规则为：帅（将）：帅和将可以(ky)吃除兵和卒以外(ywi)的任何棋子。仕（士）：仕（士）可以吃除帅和将以外的任何棋子。相（象）：相（象）可以吃除仕、士、帅和将以外的任何棋子。车：可以吃除相、象、仕、士、帅和将以外的任何棋子。马：可以吃马、炮、兵或卒。炮：可以吃任何棋子，但是中间必须隔一个子。兵（卒）：只能吃对方的帅（将）或兵（卒）。除炮在吃子时可以按竖线或横线走动多格，其他子每次走动只能按竖线或横线走

5、动一格。对局中，出现下列情况之一，本方算输，对方赢；自己宣布认输。自己的子被对方全部吃掉。出现以下情况，算和局；一方轮走时，提议作和，对方同意。双方走棋出现循环反复达三次，符合“不变作和”的规定，双方又不愿变着时。3机器博弈的基本思想人工智能的先驱者们曾认真地表明：如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中。计算机象棋对弈是一种双人完备信息的博弈过程2，即没有随机因素的博弈在两个人之间进行，在任一时刻，一方失去的利益即为另一方得到的利益，不会出现“双赢”的局面，而且在任何时刻，博弈的双方都明确的知道每一个

6、棋子是否存在和存在于哪里。假设有甲、乙二人对弈，现在轮到甲下棋，他面对的是一个局面1，从这个局面出发可以有N种符合规则的下法。局面2，3，N+1。假设甲选择了形成局面2的下法，轮到乙下棋。乙面对局面2，又可以有M种可能的下法，形成M种新的局面K+1，K+2，K+M。如果甲选择形成局面3，.4，N+1的下法，乙方都对应有若干种下法。这样甲乙双方轮流交替下棋，棋盘局面的发展变化就形成一棵树的形状，通常称为博弈树。计算机博弈的核心思想并不复杂，实际上就是对博弈树节点的估值过程和对博弈树搜索过程的结合3。博弈程序的任务就是对博弈树进行搜索找出当前最优的一步走棋。对博弈树进行极大极小搜索，可以达到这一目

7、的。极大极小搜索，是因为博弈双方所要达到的目的相反，一方要寻找的利益恰是一方失去的利益，所以博弈的一方总是希望下一走棋是儿子节点中取值最大者，而另一方恰恰相反。这便形成了极大极小过程4。整棵的博弈树非常庞大，且不同棋类有所不同，分支因子大的如围棋的博弈树显然要比分支因子小的如国际象棋的博弈树要大得多，所以，不能也没有必要做到搜索整棵博弈树的所有节点，对于一些己经确定为不佳的走步可以将以它为根节点的子树剪掉。而且，搜索也不必真的进行到分出胜负的棋局，只需要在一定深度范围内对局面进行评估即可。只有搜索空间缩小到一定程度，搜索才可以真正的进行。当搜索进行到一定深度，用局面评估机制来评估棋盘局面，按照

8、极大极小的原则选出最优，向上回溯，给出这一局面的父节点的估值，然后再继续向上回溯，一直到根节点，最佳走棋就是这样搜索出来的。在这个过程中，最为重要的是搜索算法，高效的搜索算法可以保证用尽量少的时间和空间损耗来达到寻找具有最佳值的走步。但是真的想要提高博弈程序的棋力，还必须有一个好的局面评估机制，即估值算法作后盾。就是说，用这个估值算法评估的局面价值必须是客观的、正确的，可以确凿的评估局面的优劣以及优劣的程度。根据上面的计算机博弈基本思想，可以确定一个计算机博弈系统的一般构成5。暗棋作为中国象棋的变体，也具有一般棋类的特征(tzhng)，在博弈过程上是相似的。局中人一次走一步棋，局面更新一次。两

9、位棋手交替走棋，局面不断更新，至最终分出胜负或和棋。暗棋与象棋的不同之处，除了规则上的差别以外，主要在于暗棋棋子有“明暗(mn n)”的属性。棋子在开局时都是“暗棋”，而暗棋只具有(jyu)“翻棋”成为“明棋”这一种方法。因此，整个棋局由“暗”转“明”是博弈的第一阶段。第一阶段的博弈十分关键，局中人对“翻暗棋”还是“走明棋”的决策，直接关系到后续局面的展开，而且由于信息不完全，第一阶段的决策是存在随机因素的。第二阶段是“明棋”阶段，即所有棋子均已由暗转明。此时博弈已经变成了和象棋类似的完全信息的动态博弈。这一阶段可以通过建立博弈树，然后以一定搜索算法找到最优解来实现决策。4核心策略显而易见，一

10、个计算机博弈软件的优劣，关键就在于它的估值函数和搜索算法。下面就这两个方面介绍一般象棋博弈程序的构成，同时提出暗棋在概率特征下对这两大模块的改进设想。 4.1 估值函数估值函数综合了中国象棋的相关知识。通常情况下，估值函数所包含的知识越多，搜索的速度越慢，包含的知识越少，搜索的速度越快，在速度与知识的衡上，包含知识的多少是设计估值函数的重要考虑方面。但是，在和人下象棋的时候，估值函数所包含的只是应当越多越好，这样不容易让人找到搜索中的漏洞。中国象棋博弈技术中的估值函数一般包括：一是固定子力值；二是棋子位置值；三是棋子灵活度和配合值；四是威胁与保护值；五是动态调整值。具体的估值函数一般是子力值、

11、灵活度和配合值、威胁与保护值的有权值的线性函数。例如，最简单的估值函数是一个子力值之和的函数，即对博弈一方所拥有的棋子的子力值进行简单求和，然后反馈到搜索函数中6。文献7的作者是著名弈棋软件“棋天大圣”的设计者，这篇文献简单介绍了该软件的组成和一些算法。“棋天大圣”的估值函数考虑5个方面，分别是：棋子价值评估值、棋子位置评估值、棋子灵活度评估值、棋子配合评估值以及将帅安全评估值。而这5个指标之和就是总的评估值，也就是博弈树各节点的包含值。国际象棋和中国象棋在估值函数考虑因素方面是大致相同的。但是由于国际象棋的特殊规则（王车易位、吃过路兵、升变），在评估棋子价值的时候需要特殊计算。而中国暗棋作为

12、中国象棋的变体，规则上简化的许多，估值函数在考虑因素的数量上有所减少。按照笔者的想法，只需要考虑子力平衡、棋子相对位置和配合、安全性和暗棋最重要的一大因素概率。概率是暗棋得以流行的关键因素。概率的存在使得棋力有别的对弈双方胜负不再确定，使得局势更加莫测，也更加有趣。但是作为机器博弈算法的设计者，概率使得算法设计的难度大大增加，也可以说使得算法的优越性大大降低。概率的影响只存在于博弈第一阶段，是否“翻棋”作为一种可选的决策(juc)，应该纳入估值函数的考虑范围。但是，由于“翻棋”之后的结果完全无法预测，所以估值函数也就无从计算。也就是说，对于暗棋而言，仅仅使用估值函数来评价局势并不可行。笔者的看

13、法是，暗棋的决策应是“两段式”判断，即首先判断是否接受(jishu)“翻棋”，若接受(jishu)即结束决策；若拒绝则调用估值函数评估局势，再搜索出最优解。笔者对暗棋概率的思考还很有限，目前只是将其纳入“翻暗棋”的决策中：对一枚“明棋”S来说，假设S周围（定义为上下左右四格）存在暗棋，那么己方局中人是否翻开这枚暗棋就需要决策。由于棋盘可见，可以统计出已经出现的“明棋”数目，计算出“暗棋”中可能对S造成威胁的概率P。一种自然的想法就是，当P大于某阈值，就拒绝翻棋；当P小于某阈值，就接受翻棋。因此，可以将此概率P，纳入是否“翻棋”这一决策的考虑范围。当然，概率P绝不是唯一决定“翻棋”的因素，是否“

14、翻棋”还需将明棋P周围以及稍远一些的棋子纳入考虑，同时整个棋盘棋子分布也不能忽略。可以说，对是否“翻棋”的决策，也就是一次规模略小，但精度更高的估值过程。 4.2 搜索算法在博弈过程中，如果把某一棋盘局面作为一个节点，那么对于该节点，所有可能着法所形成的新局面就成为该节点的儿子节点，从儿子节点再走一步棋形成的局面就是孙子节点，以此类推，直到可以分出胜负或平局的局面，这样就可以构造出一棵博弈树。因此，尽量博弈树的节点数在数学意义上是有限的，但是由于其规模过于庞大，几乎无法在有限时间（如100万年）内得出最优解。所以为了使得博弈决策可行且高效，必须采用至少一种搜索算法。极大极小搜索，是机器博弈中最

15、早采用的算法。尽管其现在已被诸如负极大值算法8、Alpha-Beta剪枝法11等取代，极大极小搜索的核心思想仍然具有一定的指导意义。在讨论过程中，我们假设有两个博弈者甲方和乙方，可以认为甲方为计算机，乙方为对手。我们的任务是为甲方找到一步最佳走棋。首先，我们假定有一个函数F(pos)(即估值函数)可以对局势优劣程度进行评判它是从甲方立场出发的，估值越大对甲方越有利，估值越小对乙方越有利。即令:F(甲赢)= +，F(甲输)= -，F其它局面)为+到-之间的一个值。假设甲方先下，然后两个博弈者轮流下棋。因此，深度为奇数的节点，对应于甲方走了一步棋后的局面，即轮到乙方选择下法的局面，称为极小节点；深

16、度为偶数的节点，对应于乙方走了一步棋后的局面，即轮到甲方选择下法的局面，称为极大节点；博弈树的根节点深度为0。这样我们就可以建立一棵具有固定深度的博弈树，其叶子节点不必是终了状态，而只是固定深度的最深一层节点，其值由估值函数给出。对于中间节点，如果该节点所对应的局面轮到甲走棋，则该节点的值取其所有子节点中值最大的一个值；如果该节点所对应的局面轮到乙走棋，则该节点的值取其所有子节点中值最小的一个的值。一个最佳走步可以由极大极小搜索产生。甲方要为搜索树根结点O选择最佳走步，他肯定要选择一个能够导致具有最大值子节点的着法。因此，一个标有“甲”的节点的估值可以由它的标有“乙”的子节点的最大值确定。另一

17、方面，乙方从子节点开始选择时，由于估值越小对它越有利，因此必然选取估值最小的节点。因此，标有“乙”的节点估值可由它的标有“甲”的子节点的最小值确定。综合以上两方面，可从博弈树的叶子节点出发，一层一层倒推得到上一层的估值，直到得出根节点的估值，这样就可以确定从根节点出发的最佳走步。 4.3 暗棋特殊(tsh)策略(cl)“暗棋”与其他棋类（尤其是象棋）的不同，不仅仅在于概率的因素。暗棋规则的简化、棋盘规模的减小等等都可以用来改进(gijn)博弈算法，精确计算过程。4.3.1 不同的估值之前提到可以将“概率P”纳入翻棋决策的考虑，这是不完整的。应该说，暗棋的规则完全不同于象棋。暗棋的本质是一种“等

18、级为上”的棋类竞技，这类的棋有一大特征就是棋子的等级是决定胜负的关键。也就是说，对于暗棋来说，子力平衡无法像象棋那样做成“静态平衡”，它是动态的。举例来说：暗棋中，“将”的天敌只有“兵”，但是由于“兵”的极度脆弱，很可能中盘阶段就被全部消灭。那这时“将”的子力就变成了无穷大，基本上可以保持不败。因此，子力的动态平衡是暗棋估值函数必须考虑的一点。暗棋局面评估的另一不同在于棋子位置关系和配合。暗棋中，棋子一次只能行动一格，这就意味着局面变化缓慢。每种棋子的行动方式一致，即可预测。在这样的规则下，可能会一个“高级棋子”先发制人，杀死对方一片的情况。这就要求程序在棋子位置关系和配合这个方面做的极为精细

19、，难度较大。4.3.2 不同的搜索虽然暗棋规则比象棋简单，但是完全的博弈树遍历也是不可能实现的。而一般的博弈树搜索是通过一些类似“剪枝”的方法尽量缩小节点空间，达到提高效率的目的。象棋的每一着法背后可能隐含着很多步的预测，所以一般人下象棋时会犹豫会思考很久。而暗棋对弈的情况则完全不同，即使是刚刚学会暗棋的人也能迅速找到最优解。原因在于暗棋棋子的“等级”对局势的影响太大，这里面隐藏了一个类似于“强弱对比度”的概念。局中人发现自己的一枚高级棋子周围没有天敌，那他十有八九会利用这枚棋子“大杀四方”，这是十分自然的选择。因此在实际的博弈树搜索中，应该优选考虑这些“高级棋子”。值得一提的是，若对方是一位

20、聪明的棋手，在出现这种情况的时候，他应该及时的让自己的棋子有规律的撤退，同时自己的“高级棋子”去保护和迎战。若棋盘上没有可堪一战的棋子，就会“翻棋”一搏。所以，即使出现之前提到的情况，胜负也未可知。5可能的改进与总结极大极小搜索法已经很少在用，文献8和文献9都提到了Alpha-Beta剪枝法对前者的取代，同时也提到进一步优化的SS*、CSS*、Alpha-Beta*等搜索方法，这会使博弈树的搜索效率得到提升。文中提到的估值函数虽然各有不同，但均为静态估值，即各成分权重在博弈过程中保持不变。现代启发式算法的发展，使得可以通过人工神经网络或遗传算法将静态估值函数动态化13，即其在博弈中会自适应成分

21、的权重，达到最好的效果。暗棋虽然有随机的因素，但终究不如象棋复杂，更不用说至今无解的围棋。本文除了介绍一般棋类竞技程序的主要构成和提出暗棋策略的设想外，主要的目的是学习博弈思想在棋类竞技中的体现，同时尝试性的将其应用在实际的算法设计中，因此选择了较为简单的暗棋。参考文献1 Xu Xinhe , Analysis on the achievement milestones and limitations of Game Theory, HYPERLINK /xpl/mostRecentIssue.jsp?punumber=4588287 Control and Decision Conferen

22、ce, 2008. CCDC 2008. 2 陆汝铃.人工智能(rn n zh nn)，上册.科学(kxu)初版社，19893 David j. Eruglinski ，Scot Wingo & George ShePherd. Programming MicrosoftVisual C+.5th Edition，Microsoft Press，19994 Rivest，R.L. Game Tree Searching by MinMax Approximation，ArtificialIntelligence，1998，Vol.34，No. l5 肖齐英，王正志，博弈(b y)树搜索与静态估

23、值函数，计算机应用研究，1997,46 任志鸿, 基于象棋博弈问题中评价函数的分析与探讨,电脑与信息技术， 20（6）：2628、48，20127 徐心和,王骄, 中国象棋计算机博弈关键技术分析, 小型微型计算机系统，27（6）：961967，20068 孙伟，马绍汉，博弈树搜索算法设计和分析，计算机学报,16（5）：361369，19939 杨涛，博弈树函数及其优化，计算机学报，1988：828810 马骁，王轩，王晓龙，一类非完备信息的信息模型，计算机研究与发展，47（12）：21002109，201011 张幸儿，潘征宇，面向目标的最佳Alpha-Beta搜索策略及其在博弈问题中的应用，4（4）：2025,199312 HYPERLINK /search/searchresult.jsp?searchWithin=p_Authors:.QT.Aumann,%20R.J.QT.&newsearch=true Aumann, R.J.，Backward induction in games of perfect information， HYPERLINK /xpl/mostRecentIs