中国象棋的计算机博弈

中国象棋计算机博弈关键技术分析

徐心和  王骄

东北大学人工智能与机器人研究所教育部暨辽宁省流程工业自动化重点实验室  辽宁沈阳  110004

【摘要】机器博弈被认为是人工智能领域最具挑战性的研究方向之一．国际象棋的计算机博弈已经有了很长的历史，并且经历了一场波澜壮阔的“搏杀”，“深蓝”计算机的胜利也给人类留下了难以忘怀的记忆．中国象棋计算机博弈的难度绝不亚于国际象棋，不仅涉足学者太少，而且参考资料不多．在国际象棋成熟技术的基akL，结合在中国象棋机器博弈方面的多年实践，总结出一套过程建模、状态表示、着法生成、棋局评估、博弈树搜索、开局库与残局库开发、系统测试与参数优化等核心技术要点，最后提出了当前研究的热点与方向．

1  引言

博弈问题无所不在，小到孩童的游戏与争论、各种场合下的讨价还价，大到商家的竞争、各种突发事件(恐怖、灾害)的应急处理、国家的外交、流血的和不流血的战争，只要局中的双方主体存在某种利益冲突，博弈便成为矛盾表现和求解的一种方式．博弈与对策将成为一类智能系统研究的焦点问题．

象棋是从两军对阵中抽象出来的一种智力游戏，因此它是博弈的一个标准问题．下棋的双方无时不在调动自己的一切智能，充分发挥逻辑思维、形象思维和灵感思维的能力．所以，在人工智能领域始终将棋类的机器博弈作为最具挑战性的研究方向之一．

早在半个多世纪之前，信息论的创始人C．E香侬教授就提出了为象棋博弈编程的方案，成为机器博弈的创始人．半个世纪以来，国际象棋的计算机博弈十分活跃，而且确实经历了一场惊心动魄的激烈搏杀

1958年，IBM704成为第一台能同人下棋的计算机，名为“思考”，思考速度每秒200步．到了60年代中期，科学家德里夫斯依然断言，计算机将无法击败一位年仅10岁的棋手．

1973年，CHESS4．0被B．SlateandAtkin开发出来，成为未来程序的基础．1979年，国际象棋软件4．9达到专家级水平．

1981年，CRAYBLITZ新的超级计算机拥有特殊的集成电路，预言可以在1995年击败世界棋王．

1983年，KenThompson开发了国际象棋硬件BEI．LE，达到了大师水平．

80年代中期，美国的卡内基梅隆大学开始研究世界级的国际象棋计算机程序——“深思”．1987年，“深思”首次以每秒钟75万步的思考速度露面，它的水平相当于拥有国际等级分为2450的棋手．1988年，“深思”击败丹麦特级大师拉尔森．

1989年，“深思”已经有6台信息处理器，每秒思考速度达200万步，但在与世界棋王卡斯帕罗夫进行的“人机大战”中，以0比2败北．

1993年，“深思”二代击败了丹麦国家队，并在与世界优秀女棋手小波尔加的对抗中获胜．

1995年，IBM"深蓝“更新程序，新的集成电路将其思考速度提高到每秒300万步．1996年，“深蓝”在向卡斯帕罗夫的挑战赛中，以2比4败北．

1997年，由1名国际特级大师，4名电脑专家组成的“深蓝”小组研究开发出“更深的蓝”，它具有更加高级的“大脑”，通过安装在RS／6000S大型计算机上的256个专用处理芯片，可以在每秒钟计算2亿步，并且存储了百年来世界顶尖棋手的10亿套棋谱，最后“超级深蓝”以3．5比2．5击败了卡斯帕罗夫．卡斯帕罗夫要求重赛，但没有得到回应．

时至今日，尽管新的硬件、软件系统层出不穷，但国际象棋的机器博弈和人机大战仍然持续不断．因为人们总在不断地挑战自我，况且计算机在人机大战中仍然没有占据绝对优势．卡斯帕罗夫也仅仅输给“超级深蓝”那一次．

中国象棋是世界上历史最为悠久的棋类，早在2000多年前的战国时代就已经有了关于象棋的记载．然而中国象棋的计算机博弈却开展的不尽人意，成了“被爱情遗忘的角落”．缺少学者的关注，寥寥无几的参与者，匮乏的参考文献，沉寂的计算机博弈氛围，使得中国象棋的计算机博弈在中国大陆难有作为，只是成为一些商家的游戏软件和教学载体．这便是当前我们所面临的艰难局面．

国际象棋棋盘8行8列总计64格，中国象棋l0行9列总计90个交点，显然中国象棋的运子空间更大．相比之—下，中国象棋的着法更为特殊(如蹩马脚、压象眼等)，棋局变化也更加复杂，这都是对中国象棋的计算机博弈提出的困难和挑战．

随着计算机博弈在Othello、Checker和国际象棋三种棋类上的成功，全世界的学者又把目光投到更为复杂的中国象棋(ChineseChess)、日本将棋(Shogi)、围棋(Go)上面．几种棋类遍历搜索的复杂度对比见表1—2，表中的数字为复杂度的自然对数值．显然，这更是对中国学者提出的严峻挑战．

面对如此富于挑战性的局面，东北大学人工智能与机器人研究所从2003年便开始了中国象棋计算机博弈课题的研究．在认真借鉴国际象棋开发成果的基础上，突破了系列关键技术，开发出具有相当棋力的博弈软件系统，并在2004年成立了“棋天大圣”代表队，准备在中象棋机器博弈领域开创新的局面。本文便是针对系列关键技术的总结和归纳．接下来的各节分别论述了过程建模、状态表示、着法生成、棋局评估、博弈树搜索、开局库建立、残局库开发、系统测试与参数优化等核心技术要点，最后提出了当前研究的难点．

2  象棋博弈过程建模

人工智能的先驱者们曾认真地表明：如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中．

在各种棋牌博弈当中，象棋是一种完全知识博弈(Gamesofcompleteinformation)，即参与双方在任何时候都完全清楚每一个棋子是否存在，位于何处．

象棋博弈具有如下基本特征：

(1)规则简单明确，成功与失败的判定标准简单，不包含任何机会或偶然性；

(2)问题的状态(即局面)数量在数学意义上是有限的；

(3)问题的解决在认识意义上不需要过多的知识．

为了深入探讨机器博弈的原理与方法学问题，尤其要从系统论和博弈沦的角度研究问题的规律与求解方法，有必要分析象棋对弈的演化过程，建立相应的数学模型．图1给出了象棋博弈状态演化过程图．图中表明棋局状态是在着法算子作用下进行演化的，其对应的状态转移方程可以写成式中为象棋的初始局面，为第n+1步的着法算子，而S。+：为走完第n-I-1步后的棋局．于是，不难写出式中S，为终局，或红胜，或黑胜，或和棋．显然，着法序列Q＝<Q~q2q3…Q／}便是记载博弈过程的棋谱，其中单数项序列Q+＝{Qlg…)为红方系列着法，而偶数项序列Q。＝{Q：Q4…}便是黑方的系列着法．

着法便是弈棋者的决策．尽管每次只能走出一步，但弈棋者可能考虑过全部有价值的走法，并且通过前瞻若干步，才形成弈棋者的当前决策．图2便以状态演化流程框图的形式展示了计算机应该如何实现这样的“思维”过程．

在这里全部可能的走法是通过着法生成器给出的，由它生成了第j步的A种可行着法，根据状态演化方程(1)，在算子g㈠，j＝1…是的作用下所形成的第i步后的棋局便不是一个，而同样是是个紧后棋局状态，即S，．j，／＝1…是．显然，这便是决策树，亦称为博弈树的展开过程．弈棋者按照这样的思维方式，必然展开一棵规模庞大的、根在上而叶在下的博弈树，如图3所示．它与一般决策树的不同点则在于它的决策主体不是一方，而是相互对立的双方，即红方和黑方．图中方节点代表轮到红方走棋的状态(棋局)，圆节点代表轮到黑方走棋的状态．显然，方、圆节点间的连线便对应于一个个着法．如果说，一个优秀棋手可以前瞻四步，则表示在他的脑海中的是将这棵博弈树展开4层(D叩th)．

博弈树上的每一个节点都代表一个棋局，棋手就是要在众多的叶子节点上挑选一个最佳的局面作为自己的选择，从而反推到当前的着法．

中国象棋博弈树的庞大是可以想象的．如果按照每一步平均有45种可行着法，每局棋平均走90步，那从开始局面展开到分出胜负，则要考虑45’*匀10’‘*种局面。据说这一天文数字要比地球上原子数目还要多，即使用世界上最快的计算机进行计算，直到地球毁灭也无法算出第一步的着法．

3  棋局状态的表示

要让计算机下棋首先需要解决的就是棋盘和棋局的数字表示。棋盘上面有9路10行形成90个交叉点，它很容易用109的棋盘数偶矩阵M。表示与坐标的对应关系．

要表示棋局则首先要给棋子编码．应该说编码的方法是任意的，只要能够满足棋局表示的唯一性和可区分性，都是可行的编码．如果考虑和追求棋局处理的节俭与快捷，那么在编码上还是具有研究的余地．

“棋天大圣”的兵种(Arms)编码在表2中给出．红方和黑方兵种编码仅相差一个负号，这为棋局评估红黑双方保持对称性提供了方便．

仅有兵种的编码是不够的．为了跟踪棋子的挪动与拼杀，还需要进行棋子编码．我们的做法如表3所示．由此便可以根据棋局给出兵种状态矩阵S‘和棋子状态矩阵S”．式(3)(4)便给出了中象初始局面(图4)对应的状态矩阵．

为了避免从棋子状态矩阵中提取某棋子实时位置的搜索过程，还需要直接给出棋子位置矩阵：P^M=[P^M_i，j]_2*32,矩阵中第一行P^M_1，j表示编号为j的棋子在棋盘矩阵中的行号，矩阵中第2行P^M_2，j表示编号为j的棋子在棋盘矩阵中的列(路)号．对应于S俨则有初始棋子位置矩阵为

在着法生成过程中，时常只关心棋子的分布，而不关心是什么棋子，这时可以用比特棋盘表示棋局的某种状态，它其实是棋盘状态矩阵5的布尔表示．比特棋盘的定义为

根据计算过程的需要，还可以定义其它含义的各种单项比特矩阵或比特向量．如：红棋比特矩阵，中路比特向量等．通常我们使用状态集合S。来表示n时刻的棋局状态．

4  着法生成

棋手都知道中国象棋着法的表示方法，如：炮八平五，马8进?等等．看得出，这种着法是和当时的棋局有着不可分割的联系．我们称其为相对着法，用／来表示．而在机器博弈中所说的着法g，都是绝对着法，它由提—动—落—吃4部分内容组成．即

式中from为“提址”，即此着的出发位置，moved (chessman moved)为“动子”，即走动哪个棋子；to为“落址”，即着法的到达位置；killed (chessman killed)为“吃子”，即吃掉哪个棋子．显然，落址处有对方棋子，则形成吃子；落址处没有棋子，则“吃空”，仅走不吃；落址处为本方棋子，则为非法着法．

着法生成方法一般有棋盘扫描法、模板匹配法和预置表法，时常还结合使用．

4．1 棋盘扫描法

根据象棋规则，定义可行区域，如棋盘有效区域A={(i,j)|1 i 10,1 j

[1] [2] [3] 下一页