智能中国象棋系统的设计与实现
摘要
人工智能(AI)中国象棋系统是将计算机知识和中国象棋知识结合起来的一种新型的游戏方式。智能中国象棋系统在此基础上实现人与机器的对弈，突破了以往传统象棋游戏只能人与人对战的限制，使中国象棋这一古老的游戏形式焕发出蓬勃朝气。
本文结合在中国象棋机器博弈方面的实践经验，在分析了中国象棋游戏需求基础上，设计并实现了智能中国象棋系统。该系统包括人人对战、人机对战、制作棋谱、播放棋谱以及挑战英雄榜等功能模块。人人对战规则明确，包含了中国象棋所有的着法；人机对战中电脑棋力分为简单、中等、困难三个等级，方便了不同水平人群的选择；制作和播放棋谱模块容易操作，方便学习；挑战英雄榜则为象棋游戏增加了乐趣。
本系统的实现满足了人们对中国象棋的基本需求，解决了传统象棋游戏学习性差、棋谱不易保存、不易演示等问题。
关键词：计算机博弈，中国象棋，人机对战，制作棋谱，搜索算法
Intelligent Chinese Chess System Design and Implementation
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 game’s 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)
附录 ........................................................................................ 错误！未定义书签。
附录A：A INTRODUCTION ABOUT CHINESE CHESSA . 错误！未定义书签。
附录B：关于中国象棋的一些简要介绍 ............................... 错误！未定义书签。
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）
数据结构是一个程序的骨架，选择一种好的数据结构可以使程序的运行效率大大提