2017毕业论文-智能中国象棋系统的设计与实现.doc

智能中国象棋系统的设计与实现 摘 要 人工智能(AI)中国象棋系统是将计算机知识和中国象棋知识结合起来的一种新型的 游戏方式。智能中国象棋系统在此基础上实现人与机器的对弈，突破了以往传统象棋 游戏只能人与人对战的限制，使中国象棋这一古老的游戏形式焕发出蓬勃朝气。 本文结合在中国象棋机器博弈方面的实践经验，在分析了中国象棋游戏需求基础 上，设计并实现了智能中国象棋系统。该系统包括人人对战、人机对战、制作棋谱、 播放棋谱以及挑战英雄榜等功能模块。人人对战规则明确，包含了中国象棋所有的着 法；人机对战中电脑棋力分为简单、中等、困难三个等级，方便了不同水平人群的选 择；制作和播放棋谱模块容易操作，方便学习；挑战英雄榜则为象棋游戏增加了乐趣。 本系统的实现满足了人们对中国象棋的基本需求，解决了传统象棋游戏学习性差、 棋谱不易保存、不易演示等问题。 关键词：计算机博弈，中国象棋，人机对战，制作棋谱，搜索算法 Intelligent Chinese Chess System Design and Implementation Author：Wang Guiwei Tutor：Fang Miao Abstract Artificial Intelligence (AI) Chinese Chess System is a new games way which combines with computer knowledge and Chinese Chess knowledge. Intelligent Chinese Chess System on the basis of it which completes the game between human and computer , breaking the traditional chess games restriction that only can play against people. So that the ancient game of Chinese chess become prosperity . With the practical experience in Chinese chess computer game, a detailed analysis and research has been done .Based on those, I designed and implemented the Intelligent Chinese Chess System .This system includes the game against human ,the gme between computer and human ,make chess manual ,play chess manual and hero list functions .The game against human function has all the Chinese Chess rules and they are very clear.In the game between computer and human function ,computer thinking depth is divided into simple,medium and difficulty.It facilitate the choice of different levels. Making and playing chess manual fuctions are easy to operating and learning. Hero list fuction adds much fun to chess game. This system satisfied the basic demand of people to Chinese chess and solved the studying hard and the theoretical is not easy to making and playing of the traditional chess game. Key Words: Computer Game, Chinese Chess, Game between Human and Computer, Make Chess Manual, Search Tecniques 目目 录录 1 绪论.2 1.1 选题的背景和意义2 1.2 发展动态及研究现状2 1.3 系统概述3 1.4 本文的主要工作4 1.5 论文结构5 2 系统的分析和设计.5 2.1 数据结构（DATA STRUCTURE）.5 2.1.1 棋盘的基本表示法（Board Representions）6 2.2 着法生成（MOVE GENERATION）.8 2.2.1 模板匹配法.8 2.2.2 预置表法.8 2.3 局面评估 .9 2.3.1 估值函数（Evaluation Function） 9 2.3.2 估值的速度与博弈性能.11 2.3.3 估值函数的优化.11 2.4 博弈树搜索技术 .13 2.4.1 基本搜索算法.13 2.4.2 高级搜索算法.16 2.5 开局库设计 .17 2.5.1 开局库的作用.17 2.5.2 实现开局库的主要方法.17 3 系统的实现.19 3.1 系统的整体规划 .19 3.2 象棋界面的实现20 3.3 对弈功能的实现24 3.4 制作和演示棋谱的实现28 3.5 象棋英雄榜的实现32 3.6 开局库的实现 .32 3.7 程序说明 .33 3.8 实验结果及分析 .33 结论.35 致 谢.37 参考文献.38 附 录.39 附录 A：A INTRODUCTION ABOUT CHINESE CHESSA39 附录 B：关于中国象棋的一些简要介绍 42 1 绪论 1.1 选题的背景和意义 在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。近几十年来，随着 计算机硬件和软件技术的不断发展，人们开始对计算机能否战胜人脑这个话题产生了 浓厚的兴趣。从 1980 开始，电脑博弈便开始逐渐大规模地向人类智能发起了挑战，到 了 1997 年，IBM 超级电脑 Deeper Blue 击败了当时的国际象棋冠军卡斯帕罗夫，成为 了人工智能挑战人类智能发展的一个重要里程碑。 许多学者认为，对于人工智能研究而言，象棋的重要作用不亚于遗传学研究中的 果蝇。人类对机器博弈的研究衍生了大量的研究成果，这些成果对更广泛的领域产生 了重要影响。人工智能的先驱们曾认真的表明：如果能掌握下棋的本质，也许就掌握 了人类智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它 任何需要人类智能的活动中。因此对于中国象棋人机博弈问题的研究意义重大。 而当今对中国象棋的研究也正如专家们所期望的那样在蓬勃地发展着。中国象棋 不仅是中国传统智慧的体现，同时也具有着比国际象棋更高的复杂度，如何让机器具 有智能,与人进行对弈成了本课题研究的一个重要问题。通过本课题的研究,掌握智能知 识的表示与计算、搜索，不仅是对所学知识的锻炼，更是在人工智能领域的有意义的 探索 1.2 发展动态及研究现状 和国际象棋博弈系统相比，中国象棋博弈系统的研究起步比较晚，是八十年代开始 的。在这个时候计算机国际象棋取得重大突破，1983 年美国贝尔公司的电脑参加美国 人类比赛，取得了不错的成绩，被授予大师称号。于是有专家学者想如何将国际象棋 电脑技术移植到中国象棋上来，以带动中国象棋电脑较快的发展；同时中国象棋从技 术研究进入理论研究，有关开局、中局、残局理论以及象棋对策相继建立起来，为中 国象棋计算机博弈提供了理论基础。 1981 年张耀腾发表的人造智慧在电脑象棋上的应用 ，他提出审局函数为静态子 力值，棋子位置值，棋子灵活度值，威胁与保护等四项之和。但该文主要以残局做实 验，缺乏完整对局的考虑。1982 年廖嘉成发表的利用计算机象棋的实验就进了一 步，包括开局、中局、残局。1983 年黄少龙、周玉龙合作制成象棋排局系列软盘 专家系统与人对弈。 到了 90 年代，中国象棋计算机博弈的应用开始发展起来，人们研究出了各种博弈 软件。比较著名的软件有台湾的吴身润的中国象棋 、光谱公司出品的将族 、 晟业编制的象棋水浒战 、 象棋武林帖 。而且涉足这个领域比较早的是台湾的一些 专家学者。近几年，在内地也涌现出一批对中国象棋人机博弈问题感兴趣的高校、单 位及个人，而且进入 21 世纪以后，中国象棋计算机博弈的研究受到越来越多的学者的 关注，比较著名的博弈软件如表 1 所示。 表表 1-1 著名中国象棋计算机博弈程序著名中国象棋计算机博弈程序 程程序序 作作者者 地地区区 纵纵马马奔奔流流 涂涂志志坚坚 广广州州中中山山大大学学 谢谢谢谢象象棋棋大大师师 法法国国电电脑脑公公司司 法法国国 ELP 郑郑武武尧尧、陈陈志志吕吕 台台湾湾 SHIGA（象象棋棋世世家家） 郑郑明明政政、颜颜士士净净 台台湾湾 SHCC（神神乎乎棋棋技技） SAI team 美美国国 Cyclone（象象棋棋旋旋风风） 陈陈朝朝阳阳 北北京京 CONTEMPLATION 千千虑虑 陈陈志志昌昌、许许舜舜钦钦 台台湾湾 棋棋天天大大圣圣 王王骄骄 东东北北大大学学 象象棋棋奇奇兵兵 赵明阳赵明阳 中国中国 每年也会有中国象棋计算机博弈的国际奥林匹克大赛，这其中有 2003 年的世界 冠军“纵马奔流” ，2004 年的世界冠军“谢谢象棋大师” ，2005 年的世界冠军“象棋奇 兵” ，2006、2007 年的世界冠军“棋天大圣” ， 2008 年的世界冠军“倚天” 。 这些都 体现了中国象棋的人机博弈的研究的受关注程度;虽然如此，但中国象棋的人机博弈的 研究比国际象棋还是晚了几十年，并且在搜索算法等方面的研究还与国际象棋相距甚 远。 1.3 系统概述 1、棋盘表示(Board Representations) 棋盘表示就是使用一种数据结构来描述棋盘及棋盘上的棋子，以方便计算机处理。 中国象棋的棋盘表示还没有形成统一的或者公认的哪种为最佳的数据格式。最直观也 是最典型的方式是使用 10x9 的二维棋盘数组表示，也有使用棋子数组，扩展棋盘棋 子数组等，棋盘的数据表示直接影响到程序的时间及空间复杂度。 2、着法生成(Move Generation) 着法生成就是找到某个局面所有合法的走法。它与棋盘表示的数据结构密切相关， 一般需要大量繁琐的判断，伴随着搜索进行，并且调用频繁，是相当复杂而且耗费运 算时间。在一定程度上形成了程序的性能瓶颈。当前为了提高着法生成的效率通常采 用以空间换时间的方法:与先求出棋子的在某位置的所有走法。 3、评估函数(Evaluation Function) 评估函数就是对博弈过程中实际局面的好坏做出判断或打分，它影响着博弈局发 展的趋势。目前象棋程序的静态评价函数主要有子力价值，子力灵活性，子力对棋盘 的控制，和一些对棋局影响比较大的重要特征计算几部分组成。它与着法生成一样十 分耗费运算时间，如何加速评估函数的速度十分关键。 4、搜索技术(Search Techniques) 搜索技术与算法是象棋博弈系统程序的核心，是决定搜索效率的关键所在。再好 的硬件也无法实现“象棋不败算法” 。如何在成指数递增的状态空间中寻求最优解，是 象棋博弈系统的一个重要的方向。 “蛮力搜索”肯定是不可取的。如何有选择地搜索， 既瞄准最有希望的方向局部加深，又不遗漏其它存在最优解的可能。目前主要是使用 - 剪枝算法加上迭代深化、置换表、历史启发等策略的综合应用。 5、开局库(Opening Book) 把开局几步的走法建成数据库供程序直接取用。实践表明无论搜索引擎如何出色， 在开局搜索过若干层后，得到的可能只是一些很笨拙的开局。直接从开局库中取就可 以大大加快开局时的运行速度和提高开局的质量。开局库一般是采用 zobrist 哈希技术 加以实现。 6、机器自学习(Machine Learning) 机器自学习之一是针对评估函数。对弈过程机器自动调整评估函数参数的权值进行 优化，发现一些棋子之间潜在的联系:之二是采用模式识别，学习的过程是通过对博弈 过程的识别统计，自行丰富模式库中的内容，以提高程序的博弈性能。 1.4 本文的主要工作 本文的主要工作是将博弈策略应用到中国象棋程序的设计与实现上，建立一个完 整的中国象棋计算机博弈系统，研究工作主要集中在以下几个方面： 1、棋盘表示与走法生成 从操作速度(性能)以及使用方便与否考虑，本象棋博弈系统从带位行位列信息的扩 展棋盘棋子联系数组着手进行研究。然后根据棋盘表示获得所有棋子的走法预生 成数组。在产生走法时直接从中取出数据，进行少量判断以得到该棋子的合法走步。 2、估值函数 如何快速有效的对一个局面进行评估需要从速度和知识的两个角度进行考虑:一般 知识越多估值越准确，但速度也慢下来。本系统采用通用的静态估值方式，同时在估 值时结合走法预生成数组，使估值的速度有很大提升。 3、搜索技术 博弈树搜索技术它很大程度上独立于具体的计算机博弈程序。本文讨论了 - 剪 枝搜索算法及其各种增强手段：包括窗口原则、置换表(内存增强)；历史启发表(节点 顺序调整)；迭代深化(时间控制)等。如何把各种增强手段有机组合起来达到最优，文 章对基于迭代加深、置换表、历史启发的 Negascout 算法进行改进。 1.5 论文结构 第一章阐述了选题背景，课题的国内外研究现状及课题的主要工作和文章的章节 安排。 第二章第一部分首先介绍中国象棋程序的一些基本数据结构，着重研究了扩展的 棋盘棋子联系数组棋盘；在此基础上实现所有棋子的走法预生成数组，以提高搜 索过程中走法产生的效率。第二部分研究本系统的着法生成，包括预置表法和模板匹 配法，进一步提高了搜索效率。第三部分描述本系统的评价函数架构，着重描述了静 态估值方法，分析了其不足，并提出了解决之道。包括子力分数、子力灵活度评价、 棋盘控制等并与走法预生成数组结合以提高估值速度。第四部分实现了博弈树的 - 剪枝算法并简要介绍各种搜索策略。第五部分阐述了开局库的设计原理。 第三章给出实验环境和程序实现。 第四章是全文的总结及展望。 2 系统的分析和设计 2.1 数据结构（Data structure） 数据结构是一个程序的骨架，选择一种好的数据结构可以使程序的运行效率大大 提高。 2.1.1 棋盘的基本表示法（Board Representions） 棋盘表示就是使用一种数据结构来描述棋盘上的信息，以便程序知道博弈的状态。 棋盘的数据表示直接影响到程序的时间及空间复杂度。为了追求更高效率，研究人员 针对中国象棋提出了多种不同的表示方法。 中国象棋的棋盘表示中最典型的是用一个 109 的二维字节(byte)数组，数组中每 个元素代表棋盘上的一个交点，其值表明这个交点上放置的是一个什么棋子或是没有 棋子 从棋子的角度考虑，如果把棋盘看成是一个平面坐标系，可以知道每一个棋子的位 置信息:小于 10 的横坐标和小于 11 的纵坐标;又在棋盘上最多 32 个棋子，故可以用一 个 32 个字节的一维数组表示所有 32 个棋子的位置，其中每个字节的高 4 位表示该棋 子的横坐标，低 4 位表示棋子的纵坐标。而己被吃掉的棋子用坐标范围以外的数表示。 这样棋盘信息就被装入这 32 个字节中。当然也可以把棋盘看作一维的，每个元素保存 直接的位置信息。 两种棋盘表示方法：一是做一个棋盘数组；二是做一个棋子数组。棋盘数组中由 棋子的位置获得棋子的类型可以在常数时间内完成，但由棋子的类型获得棋子的位置 需要遍历；在棋子数组中由棋子的类型获得棋子的位置可以在常数时间内完成，但由 棋子的位置获得棋子的类型操作繁琐。如果一个程序同时使用这两个数组，那么获得 棋子的类型和棋子的位置都可以在常数时间内完成。这就是“棋盘棋子联系数组” ， 它的技术要点是: (l) 同时用棋盘数组和棋子数组表示一个局面，棋盘数组和棋子数组之间可以互相 转换。 (2) 随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。在 棋盘上删除一个棋子，需要做两个操作(分别修改棋盘数组和棋子数组)。同样，添加一 个棋子时也需要两个操作。 “棋盘棋子联系数组“最大的优势是：对于着法产生过程，可以逐一查找棋子数 组，如果该子没有被吃掉，就产生该子的所有合理着法，由于需要查找的棋子数组的 数量(每方只有 16 个棋子能走)比棋盘格子的数量(90 个格子)少得多，因此联系数组的 速度要比单纯的棋盘数组快很多。同时“棋盘棋子联系数组”是很多改进的棋盘 的基础。 2.1.2 改进型棋盘结构 在计算机上面，位运算比一般的加减乘除及取余运算快得多。如果能在寻找棋子 和定位棋子上使用位运算代替加减乘除和取余，这将很大程度上提高运算速度。所以， 人们把“棋盘棋子联系数组“进行扩展：把棋盘做成 1616 的大小，这样得到 行号可以用 16 除，得到列号可以对 16 取余（和 15 进行运算） ，这比除以 10 和对 9 取余操作要快得多。如图 2.1（红色格子都被标上“出界”的标志，目标格在这些格 子上就说明着法无效）： 图 2.1 扩展的棋盘 这种棋盘的更大的好处是： (1) 它可以防止棋子走出棋盘边界。由 bool 型棋盘数组（属于棋盘的位置为 true， 否则为 false） ，判断棋子是否走出棋盘边界只要返回该数组对应的值即可，速度快。 (2) 对于是否在城池内可以用 bool 型城池数组判断，因为是否在城池内的判断会非 常频繁，直接用该数组会很高效。 (3) 判断是否过河的方法非常简单：只要设定特定的表达式，当表达式为假表示已 过河，否则没过河。 (4) 还可以非常方便的判断棋子是否在己方。 2.2 着法生成（Move Generation） 着法生成就是要产生所有有效的着法，让电脑棋手在这些着法中选择最好的着法， 并判断人类棋手是否符合走棋规则。着法生成是博弈程序中一个相当复杂而且耗费运 算时间的方面，要生成所有着法只能用穷举。中国象棋大约每一步可以有 45 个着法。 通过良好的数据结构和走法预生成，可以显著地提高生成的速度。 2.2.1 模板匹配法 当动子确定以后，其“落址”和“提址”的相对关系便确定下来了，这样可以为 某些动子设计其着法生成的“模板” ，只要匹配到提址，便可以迅速找到落址。图 2.3 给出了马的匹配模板。 图 2.2 马的匹配模板 将马对准提址， “O”表示符合“马走日”规则的落址， “x”表示“蹩马腿”的制约 条件，通过查找模板匹配数组，实现“本方子则止，对方子则吃” ，完成“提动 落吃”内容的确定。 对马的着法生成使用模板匹配法时，只要写出符合马行棋规则的模板匹配数组和马 腿的模板匹配数组，在生成着法时通过查找这两个数组就可以实现。显然，这比扫描 整个棋盘，通过计算得到合法落址要快速的多。同样的，可以对象、将、士、卒使用 模板匹配生成着法。 2.2.2 预置表法 它是把所有可能的着法预先存储起来，在生成着法时，用查表取代计算。中国象 棋每种棋子的行棋规则不同，生成每种棋子的着法和整个棋盘棋子的分布密切相关， 如果建立每种棋子最大可能着法的小型数据库，用查询取代复杂的判断，那么也可以 在很大程度上加快着法生成的速度。预置表看起来似乎很大，但是只需在程序开始运 行时初始化一次就可以了，这些耗费对整个程序的影响不大，但是对着法生成的作用 却是非常明显的。 图 2.3 即是以路向行向比特向量为索引的一个车的预置着法表的生成范例。图中显 示，该车位于某行第 4 列，棋子分布的布尔向量形式为 010100100，可以看出，此 时车可能的吃子着法落址为010000100，非吃子着法的落址为f0010110001。把车 的列号和该行棋子的布尔分布作为输入，把吃子落址和非吃子落址作为输出，将输入 和输出的关系写入一个预置表中，在使用时通过查表，就可以快速构成可行着法，而 且可以区分开吃子着法和非吃子着法。如图 2.3 所示： 图 2.3 车的着法预置表范例 2.3 局面评估 局面估值就是通过既有的棋类知识来评估一个局面优劣的过程。从象棋的棋力上 考虑，在搜索之外，局面估值是最重要的部分，因为对实际局面的评价的好坏，影响 着今后局势发展的趋势。这一过程对具体的棋类知识依赖程度很深，但是仍有一般性 的规律可循。目前在计算机象棋博弈中常用的估值方法主要采用静态估值方法。同时 由于随着搜索层数的加深，叶子节点的数目迅速上升，估值函数被数以百万次的调用， 花费大量的运算时间，如何提高估值函数的速度，也成了博弈性能改进的重要话题。 下面分别从这两个方面及其关系介绍局面评估。 2.3.1 估值函数（Evaluation Function） 本系统的估值函数包括：棋子固定价值，棋子位置附加值，棋子灵活性，棋子对 棋盘的控制，棋子间的关系几部分。 棋子固定价值指的是对棋盘中的每一个棋子，根据它的重要性和走法的丰富程度 赋予其一个特定的值。在棋盘上，棋子多者占优，棋子少者为劣。根据经验，可以让 一个车价值为 500，一个马价值为 300，一个兵价值为 100 等等。在中国象棋的对弈中， 由于一般以将死对方的将(帅)作为结束，因此，通常赋值的规则是为将(帅)赋予一个远 大于其他棋子的子力之和的值。 可以用下面的表达式求某一方的棋子固定值 SideValue=sum(PieceNum*PieceValue)； 其中 PieceNum 是某种棋子的数量，PieceValue 是该种棋子的价值，sum 是对各种棋子 的总价值求和。如果红色的棋子价值总和大于黑色的棋子价值总和，通常这意味着红 方的局势优于黑方。而红黑双方的 SideValue 之差越大，红方的优势也就越大。 同样的棋子在不同位置上起的作用是不同的，最明显的是兵(卒)过河之前与之后它 的作用和攻击力以及对对方的威胁显然是不一样的，而当兵卒一旦到了底线附近，它 对将(帅)的威胁度将大大下降。 棋子灵活性描述的是棋子的活动范围，即棋子向各处调动的可能性大小。棋子的威 力能否充分发挥，与灵活性直接相关。本方棋子可以走的点越多，说明本方棋子的灵 活性越大。例如车在纵横线上遇到障碍物、马被周围棋子绊脚等，都降低了灵活性， 也降低了威力的发挥，灵活性的计算是把棋子在棋盘上所能够移动到达的位置数作为 灵活性计算，给予评分。 可以用下面的表达式求某一方棋子灵活性: Mobility=Sum(MoveNum*MoveValue)； 其中，MoveNum 是某种棋子的合法走法数量，MoveValue 是该种棋子每一走法的 价值，sum 是对所有棋子的灵活性价值求和。Mobility 就是所有棋子的灵活性分数。 一方对棋盘控制的棋盘区域越多，那么他就越具有主动性。在象棋中，如果一位置 落在某方棋子的合法走步上，就可以认为被该方控制。如果某一位置同时落在双方的 合法走步上，可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣。能控 制更多位置的一方应在这项评分上占优。 在中国象棋博弈中，每个棋子都不是孤立存在的，他们之间构成了各种相互关系。 如棋子 1 下一步将被吃掉，则应该给一个负的附加值。而如果周围有己方棋子对其进 行了保护，也就是说，对方在理智的情况下不会去吃棋子 1，那么棋子 l 没有受到威胁， 价值不变。棋子关系的评估应考虑到该谁走棋的问题。如果某个红马落在黑炮的合法 走步之内，但此时轮到红方走棋，应认为红马受到的威胁较轻。而如果此时轮到黑方 走棋，就应认为红马受到的威胁很大，应减去一个相对较大的值了。 2.3.2 估值的速度与博弈性能 开发人员可以向估值函数加入大量的棋类知识，使之对于局面的评估更为精确。但 是，博弈系统的性能，速度，棋类知识一般满足下面的关系： Performance(性能)=Speed(速度)Kowledge(知识) 且向估值函数加入越多的棋类知识，估值函数的速度也就越慢，因为所要进行的计 算也相应增加。因此过于简单的估值函数和过于复杂的估值函数同样性能不佳。在同 等的知识含量下，速度越快，性能越高。在同等速度之下，知识量越大性能越高。在 速度和知识量二者的相互作用下，开发者要寻找的是一种平衡，是能够使性能最大化 的速度和知识量。使用终点估值(endpoint envaluation)，意思是当叶子节点到达时， 使用估值函数对一个局面进行评估。这样的方法思路清晰，容易设计，而且模块间独 立性高，同搜索算法的耦合度很低。可以轻易的更换估值函数，只改动极少的代码； 你也可以随意使用任何估值方法来评估整个棋盘，最终给出估值，但这种方法的速度 较慢。 2.3.3 估值函数的优化 目前最长使用的是优化估值参数的方法是利用大量的测试局面进行手工调整，也是 本文在优化评估函数时主要使用的手段。这种方法是利用人类的象棋经验知识来调整 参数值，比如，从经验上可以知道，一个车的价值要比一个兵大，给车赋予比兵大的 数值，马炮则赋予位于其间的值;马和炮的地位相当，给予它们相当的数值，以避免盲 目换子；如果对弈中使用了一些优秀的战术配合，那么就给予一定数值的奖励，等等。 将这些经验放进评估函数中反复对弈，然后不断修正参数，找出一组性能较高的参数。 (1)规格化(Normalize) 如果只是关心评价的顺序，而不怎么关心评价值，那么可以把每一项都乘以同样的 常数。这就意味着，对某个特定的模块，例如兵的价值，可以硬性设一个值，其他值 就可以表示成它们相当于多少个兵。这个做法可以减少一个需要设定的参数。 (2)约束法 (Deduce Constraints) 通过考虑希望电脑作出怎样的判断，就可以确定一些参数。例如在对弈中即使赚到 一个兵，用车换象或马还是坏的，但如果能赚到两个兵那还是好的，因为在考虑子力 价值是要防止换单兵，鼓励换双兵。这样的条件越多，合适的权重组合就越少。在开 始设定权重值的时候，这个方法通常可以得到合适的值，但是在后面仍然需要做一些 调整。 (3)交手法 (Hand Tweaking) 这是调整评估函数时非常常用的方法，通过让程序对弈，来找到它的优势和弱点， 猜测哪些参数会让程序更好，然后挑选新的参数。这个方法可以很快得到合理的结果， 但是需要对棋类知识有足够的了解，便于根据程序的对局来做分析，从而知道程序的 问题在哪里。手工调整是象棋引擎调整估值参数的主要手段之一，把人类的知识和经 验尽量准确客观地“教授”给计算机，是提高棋力的普遍做法，虽然比较费时，但是 很有效。通过不断的试验、修改参数值，可以得到不错的结果。但是人类的知识毕竟 具有一定的局限性，评估函数也不能包含所有情况，参数之间往往又互相联系，调整 某个参数可能解决了某类问题，但又可能给其它问题的解决带来麻烦，在这种情况下 很难实现全局下的最优组合。 还有一种主要的优化方法是机器自学习： (1)爬山法(Hill-Climbing) 爬山法通过对参数进行小范围的试探来寻找最优解，一次只能对参数作一点小改变， 然后测试博弈程序的性能是否提高了，仅当性能提高时才采纳这个改变，需要重复很 多次。这种方法很慢，并且受初始采样值的限制，很容易陷入局部最优，即评价可能 很差，但是任何很小的改变都会使评价更差。 (2)模拟退火 (Simulated Annealing) 模拟退火是一种基于蒙特卡罗 (Monte Carlo)算法的启发式随机搜索算法，它没有 蒙特卡罗算法多次寻优的过程，也不像爬山法那样依赖初值。在优化参数时，类似于 爬山法，模拟退火法也是对权重做改变来提高成绩，如果所做的改变没有提高成绩， 也会根据一个随机的几率采纳这个改变，试图跳出局部最优。这个方法需要给定一些 几率，从几率高、梯度大的条件开始，然后逐渐减小。模拟退火法比爬山法更慢，是 最终可能得到比较好的值。 (3)遗传算法 (Genetic Algorithm，GA) 遗传算法是建立在自然选择和自然遗传学机理基础上的迭代自适应概率性全局优化 算法，因其模仿生物的遗传机制而得名，最早由美国密执安大学 J.H.Holland 于 1975 年提出，它通过染色体的复制，交叉，变异等操作，实现个体适应性的提高。遗传算 法可以同时维护多组较好的参数，通过向其中添加一组新参数，通常是将从几组老参 数中选出的值组合在一起作微小的变化，然后同几组老的参数比较孰优孰劣，将最坏 的一组去除。遗传算法是从几组参数开始，而不是一组参数，具有很好的全局搜索能 力，搜索速度也很快，而且此算法能将搜索重点集中于性能高的部分，能较快地求出 最佳参数，鲁棒性也明显优于前两种算法，所以在计算机博弈中最有可能取得成功。 2.4 博弈树搜索技术 中国象棋博弈树非常庞大，完全建立博弈树是不可能的，唯一的解决方法就是让博 弈树扩展到计算机运算可以接受的深度，然后对没有分出胜负的叶子节点给出一个尽 量准确的打分，表示此局面下取得胜利的可能性，这个打分是由评估函数计算给出的， 将搜索树展开是着法生成的功能，而搜索引擎则是尽可能缩小树的规模，避免一切冗 余的计算，这也是计算机博弈中搜索引擎研究的重点。 根据搜索策略，目前应用于计算机博弈的搜索算法一般可分为三类： (l)穷尽搜索 (Exhaustive Search)，这种搜索是没有抛弃任何可能成为最佳路径的搜 索，不存在风险，得到的最佳走法肯定是在现有评估函数下应该得到的，例如极大极 小值搜索、- 剪枝搜索及其变种等。 (2)选择性搜索 (Selective Search)，即裁剪搜索，这种搜索略去对一些着法的搜索， 冒着有可能漏掉最佳走法的风险，而换来局部更深的搜索深度。中国象棋中最常用裁 剪算法是空着裁剪(Null Move)等。 (3)启发式搜索 (Heuristic search)利用象棋领域的知识(启发信息)设计搜索算法，着 重对走法排序，以简化和加快搜索过程。中国象棋中的启发算法有历史启发、杀手启 发、置换表等。 2.4.1 基本搜索算法 极大极小值方法(Minimax Algorithm)是解决博弈树问题的基本方法。香农教授早 在 1950 年首先提出了“极大极小算法” ，奠定了计算机博弈理论的基础。 极大极小值算法的原则是:博弈双方所要达到的目的相反，一方要寻找的利益是另 一 方失去的利益，博弈的一方总是希望下一步是子节点中取值最大者，而另一方希望 下一步是子节点中取值最小者。在象棋博弈中，极大极小值算法体现在始终站在博弈 一方的立场上给棋局估值，有利于这一方的棋局给予一个较高的价值分数，不利于这 一方(有利于另一方)的给予一个较低的价值分数，双方优劣不明显的局面给予一个中 间值分数。在这一方走棋的时候，选择价值最大的子节点走法，即实行“Max 搜索” ， 另一方走棋则选择价值最小的子节点走法，即实行“Min 搜索” ，这就是象棋博弈中的 一个极大极小过程。例如，如果红方为走棋方，它在偶数层的着法选择是要在其全部 子节点中找到评估值最大的一个，实行“Max 搜索” ，称为 MAX 方，而其敌对方即黑 方在奇数层的着法选择则是在其全部子节点中要找到评估值最小的一个，实行“Min 搜索” ，称为 MIN 方。图 2.4 表示了一个极大极小搜索过程，粗箭头为最佳路径片段。 图 2.4 极大极小值算法示意图 由于完整的博弈树过于庞大，程序不能也没有必要搜索整棵博弈树的所有节点， 而需要像人类棋手一样有选择性地进行搜索，对于一些已经确定不佳的走步可以将以 它根节点的子树剪掉(cut-off/pruning)，以提高单位时间内搜索的节点数。 上述极大极小值搜索过程中，遍历了整个的博弈树，这样的搜索算法效率低，搜 索量非常大，如果要减少搜索量，又可能影响搜索效果。但假如将叶节点的评估计算 与树的展开同时进行，然后对博弈树进行必要的裁剪，就可能大量减少所需搜索的节 点数目，并且保持搜索效果不变。 这个技术叫 - 剪枝搜索。它是一种基于 - 搜索的深度优先搜索，是所有剪枝算法的 基础，它是根据极大极小搜索规则进行的。图 2.5 和图 2.6 给出两个剪枝示意图： MAX MIN MAX 图 2.5 剪枝示意图 MIN MAX MIN 图 2.6 剪枝示意图 在图 2.5 所示的极大极小树片段中，按照极大极小值搜索规则，从左路分枝的叶节 点倒推得到第一层 MAX 节点的值为 5，可表示此时的着法最佳值，记为 ，显然此 值可作为 MAX 方着法指标的下界。在搜索中路分枝时，因为第二层着法的选择是取 第三层节点的最小值，即取 M 州(8，3， “”)，而无论“”中为何值，都不会比 5 大(最大为 3)，故可以将“”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。 同理搜索右路分枝，也可以进行剪枝操作。此类剪枝称为 -剪枝。图 2.5 中通过剪枝， 最后得到如粗箭头所示的最佳路径片断。 图 2.6 所示的极大极小树片段中，由左路分枝的叶节点倒推得到第一层 MIN 节点 的值为 n，可表示此时对方着法的钳制值，记为 。显然此 值可作为 MIN 方可能实 现着法指标的上界。在搜索中路分枝时，因为第二层着法的选择是取第三层节点的最 大值，即取 MAX(5，12， “”)，而无论“”中为何值，都不会比 11 小(至少为 12)，故可以将“”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。同理搜 索右路分枝，进行剪枝操作。此类剪枝称为 -剪枝。图 2.7 中通过剪枝，最后得到如 粗箭头所示的最佳路径片断。 - 剪枝搜索能够让我们省略许多节点的搜索，不只是节点本身，而且包括节点下 面的子树，这样 - 剪枝搜索需要遍历的节点数远少于极大极小算法所遍历的节点， 也就节省了大量的时间开销，并且仍不失为穷尽搜索的本性，但 - 剪枝的剪枝效果 即搜索节点数与博弈树节点的搜索次序密切相关。 2.4.2 高级搜索算法 极大极小值搜索是所有搜索算法的基础，而 - 剪枝搜索是所有剪枝算法的基础。 但在实际的博弈系统设计中，要提高程序的搜索速度和搜索深度，还必须利用搜中得 到的一些启发式信息来加快搜索，目前己经有很多对基本搜索算法的增强算法。 在 - 剪枝搜索中，剪枝效率几乎完全取决于节点的排列顺序，如何调整待展开 的走法的顺序，是提高搜索效率的关键。在搜索的过程中，往往有一些启发性的信息 可以利用，如果利用这些信息在相似的局面下对走法进行优化排序，或者对相同的局 面不再搜索，而直接返回以前搜索的结果，都会对搜索产生明显的加速作用。围绕着 法排序，己经出现了许多优秀的搜索算法与举措，例如历史启发，杀手启发，置换表 等等。 历史启发(History Heuristic)实际上就是记录搜索过的好的走法，并在后续着法中优 先搜索。根据经验，一些以前经过搜索认为最佳的走法，其后续走法仍然有很大可能 成为最优的走法。在搜索过程中，每找到一个好的着法，就将与该走法相应的历史得 分作一增量，一个多次被搜索并确认为好的走法的历史记录分值会较高，当搜索中间 节点时，将走法根据其历史得分排序，以获得较佳的排列顺序。 杀手启发(Killer Heuristic)是基于这样的思想:在搜索过程中，有许多走法一经搜索 就引发了剪枝，且这些走法通常是同一个走法，这样，为每一层记录引发剪枝最多的 走法即杀手走法，当下一次搜索到同样的深度时，如果杀手走法是该局的一个合法走 法，就优先搜索杀手走法。杀手启发是一种特殊的历史启发，它不依赖于人类的知识， 具有普遍性。 置换表 (TransposilionTable)是用一张表把搜索过的信息记录下来，在后续的搜索中， 察看记录在表中的这些信息，如果将要搜索的某个节点已经有记录，就直接利用记录 下来的结果引入到当前的搜索中，以减少搜索。置换表不同于历史启发表和杀手表， 不必在每次搜索之前都清空，而是一直维持这些数据，作为以后搜索的信息。 另外，空着搜索(Null Move)也是搜索算法中一种很有效的搜索策略，它的思想是 放弃本方的走棋权利，让对方连续走棋，如果得到的分数还大于原来的 值，就可以 简单地返回 值，在此分枝下的搜索意义不大，免于搜索。空着搜索明显降低了搜索 的数量，导致搜索深度显著提高，并且危险性比较小，实现较为简单。 2.5 开局库设计 中国象棋的开局变化极多，每一种走法都能产生出一种新的变化，单就中炮对屏 风马、中炮对反宫马、中炮对左三步虎等数十种变化，其格个开局又都有自身的变化， 这些开局都遵循开局的规律:“明车” ，即车路要通;“活马” ，即马与兵阵的配合合理， 使马能有活动的空间;“好炮位” ，即炮要占住子力疏密适中的要点，封锁对方进攻路线， 配合其他子力展开进攻。另外当进行快棋赛时，棋手还会选择一些冷门开局，使局面 很快“脱谱” ，迅速进入到中、残局。所以中国象棋开局阶段是整个对弈过程中变化最 多的阶段，开局的好坏对之后的中、残局意义重大。 2.5.1 开局库的作用 象人们记住开局招数一样，博弈程序使用一个数据库，里面储存了开局谱着和局面， 于是当对局（开局）中的棋步在开局库中能找到时，它就可以立即取出来走，不用计 算。无庸多说，这对于程序节省思考时间有重大帮助。这对于整个博弈系统来说有三 点好处：一是防止战略性错误；二是形成较为稳妥和有利的局面；三是节省了大量的 搜索时间。但另一方面，如果开局库本身不好或部分不好，程序也可能被盲目引到劣 势的局面甚至很快失利。所以如何设置一个比较好的开局库，就成了程序设计中不可 或缺的部分。 2.5.2 实现开局库的主要方法 实现开局库的方法一般有两种：一种是用 FEN 的形式表示的开局库；另一种是哈 希值表示的开局库。 用 FEN 串表示开局库的方法比较简单，该方法仅仅是将开局库中的存储的棋盘状 态与当前棋盘的状态进行比较，若相同，则程序根据库中的走法走一步。下面我们来 看看什么是 fen 串。 (1) FEN FEN 就是“福斯夫-爱德华兹记号法” （Forsyth-Edwards Notation） ，这是一种使用 ASCII 码字符描述国际象棋局面的标准。FEN 是建立在 19 世纪由报社记者 SD福斯 夫设计的记录局面的标准基础上的。后来为了适合象棋软件的需要，由爱德华兹对此 做了少许修改。一份标准的局面记号对需要大量交换共享局面数据的国际象棋程序设 计等工作具有尤其重要的作用。 (2) 结构描述 一个 FEN 记录使用长度可不同的一行来表示，由六个区域组成。单纯的 FEN 记录 文件后缀应该是“.fen” ，比如:kk-1.fen，在中国象棋开局库的 fen 串形式的开局库文件 后缀为.DAT。FEN 描述了:棋子位置、轮走棋方、易位可行性、吃过路兵目标格、半 步计数、以及总回合数。所有这一切用一行文字符号表示就行了而且非常容易读。 看看一个 FEN 的五个区域及其含义，以中国象棋为例： Rnbakabnr/9/1C5C1/P1P1P1P1P/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w0 1 这就是每盘常规对局的最初局面，一个子都没有动，如图 2.7： 图 2.7 象棋初始局面 (3) 棋子位置数值区域（Piece placement data） 就是表示双方棋子各在棋盘哪个格子上的。规则是从第 10 横线开始顺序数到第 1 横线(红方在下，从上数到下)，从 a 线开始顺次数到 h 线；红方棋子以大写字母 “RNBAKABNR”功表示，黑方棋子以小写“rnbakabnr”表示，这是英文表示法， 每个字母代表的意义与常规规定相同。数字代表一个横线上的连续空格，反斜杠 “”表示结束一个横线的描述。 上面的那 P1PlP1PlP，就是表示黑方在第 7 横线上排有 5 只兵；后面那两个数字 9， 就是表示从第 6 到第 5 横线，双方一个棋子都不在，是空格；9 个反斜杠“”将第 一区域分成 8 段，因为棋盘有 10 条横线；其它的照着图完全可以类推。 (4) 轮走棋方（Active Color） 表示目前局面谁该走棋。小写“w”表示红方走棋；小写“b”表示黑方走棋； 因为起初局面是红先，所以上面就是“w”. (5) 吃过路兵目标格（En Passant Target Square） 如果没有，就用“-”表示。如果有，就用具体完成吃过路兵的那个格子坐标表 示，显然对于白兵被吃只可能在第 3 横线，对于黑兵被吃只可能在第 6 横线。而且， 这个标记是且只是在该局面紧接的上一步棋是某方刚走兵推进两格的情况下出现。 (6) 半回合数（Halfmove Clock） 用一个非负数表示自从上一次动兵或吃子之后目前走了的半回合数。这个是为了 适应 50 步和棋规则而定。 (7) 回合数（Fullmove Number） 当前要进行到的回合数。不管红还是黑，第一步时总是以 1 表示，以后黑方每走 一步数字就加 1。用哈希值开局库的文件的后缀通常为“.BIN” 。 这种方法是使用置换 表来统计开局库中的一些走法的优劣。与搜索引擎中的置换表类似，开局库也是用表 示局面的哈希值除以开局库的大小作为索引，而表示局面的哈希值作为校验。虽然二 者查询的形式完全相同，但是存储的内容却大不相同。置换表存储的内容主要用于搜 索，开局库存储的内容主要是走法的权重、输赢比率，用于选择最佳的走法。它只存 放某局面的一个哈希值以及对应的走法。这也意味着 Zobrist 哈希所要使用的随机数组， 不能临时产生，而要包含在开局库当中。对于当前局面，查询数据库的函数使用库中 的随机数组计算出其哈希值，然后在库中察看是否有此值所代表的局面。此种开局库 的实现方法: (a) 查询当前局面 开局库中存储的哈希值表示的是当前局面，查询到开局库中所储存的各种走法，并 在各种走法中随机提取一个走法执行，走法选择的几率与其权重成正比。 (b)查询后续局面 这种开局库查询是与搜索结合在一起的，并不是查询当前局面是否在开局库中，而是 展开根节点的所有走法，也就是当前局面下所有可