中国象棋人机博弈系统的设计与实现

1、班级031221学号03122014本科毕业设计论文题目中国象棋人机博弈系统的设计与实现学 院 计算机学院 专 业 网络工程 学生姓名 李盼舒 摘要中国象棋发展至今已经有了几千年的历史，是中华民族灿烂的文化瑰宝，它具有浓厚的趣味性，规则简单明了，在中国已经成为了一项普遍的棋类运动，是其他棋类远远无法比拟的，并且目前，中国象棋正在往国外发展。为了使中国象棋更加具有趣味性，我们在象棋博弈中加入了人机交互,实现了一个中国象棋人机博弈系统，这个系统是将计算机和人工智能结合起来的一种电脑游戏。本文研究了中国象棋在电脑上的局面表示，走棋过程中走法生成和局面评估、博弈树搜索等一系列的问题。通过visual

2、C+开发平台和MFC文档视图体系结构实现了一个包括人人对战、人机对战、残局保存、读取残局、悔棋、还原等功能模块的中国象棋人机博弈系统。本系统为象棋爱好者提供了一个平台，满足了玩家对中国象棋的基本需求。关键词：中国象棋人工智能博弈树搜索算法 估值函数ABSTRACTChinese chess is a gorgeous cultural treasure of Chinese nation with thousands of years history. It has a keen interest and simple rules which has been a popular chess

3、game in china that cant be matched by any other kinds of chess. Whats more, nowadays, Chinese chess is rapid development in foreign countries. In order to advancing the interest of Chinese chess, we add human-computer interaction into chess-playing system, making a human-computer interaction game th

4、at is a kind of computer game which has a combination of computer and artificial intelligence. This paper studies the problem of board position of Chinese chess, move generation and situation assessment. It reaches a Chinese chess game system with a variety of functional modules which involves “man-

5、man battle”, “man-machine battle”, the keeping and reading of the end-game, undoing and restoring through Visual C+ platform and MFC. This system provides a platform for the Chinese chess enthusiasts. It can meet the basic needs of players towards Chinese chess.Keywords: Chinese chess artificial int

6、elligence game playing tree algoritjm evaluate function目录第一章 绪论11.1选题的背景和意义11.2 国内外棋类博弈的发展现状11.3 论文的主要工作2第二章 中国象棋简介32.1 简介32.2 棋盘和棋子32.3 走棋规则4第三章 系统分析53.1 MFC简介53.2 棋局表示53.3 走法生成63.4 局面评估73.4.1 估值函数83.4.2 估值函数和博弈性能83.4.3估值函数的改进93.5 搜索算法93.5.1 极大极小值搜索算法103.5.2 Alpha-Beta剪枝搜索103.5.3 启发式搜索及走法排序12第四章 系统

7、设计与实现154.1 系统的整体规划154.2 象棋界面的实现154.3 对弈功能的实现164.4 悔棋和还原功能174.5 文件保存和读取功能184.6 着法显示功能184.7 程序说明184.8 系统测试及实验结果19第五章 总结与展望23致 谢25参考文献27第一章绪论1.1选题的背景和意义近几十年来，随着计算机硬件和软件技术的飞速发展，电脑游戏产业展现出了蓬勃发展的势头，已经变成与音乐、影视等并驾齐驱的娱乐产业。人们也开始对计算机是否可以战胜人脑产生了兴趣。从二十世纪八十年代起，电脑人工智能开始向人类智能提出了挑战，到1997年，IBM研究的超级电脑击败了当时的国际象棋冠军，成为人类人

8、工智能发展史上的重要标志。人类对于人工智能的探索是从棋类开始的，研究人工智能的学者们曾经表示：如果我们要想深入的了解人类智能的核心技术，我们就必须掌握棋类的本质。中国象棋从古代流传至今有了几千年的历史，是一种古老的文化，集人类科学、文化、艺术为一体，有助于开发人的智力，培养人的思维，锻炼人的毅力，使人更具有竞争意识。并且相比较于国际象棋，中国象棋更为复杂，因此对中国象棋人机博弈问题进行研究更有意义。如何让机器变得智能，可以和人类智力进行竞技，是本文研究的一个重要的问题，通过本文的研究，掌握人工智能的搜索、知识表示、计算，在人工智能领域进行一个深度的探索。1.2 国内外棋类博弈的发展现状人类对于

9、机器棋类博弈的研究最早是开始于国际象棋，美国数学家香农通过几十年的研究，找到了编写国际象棋程序的方法，他提出了通过一个函数评估局面的优劣，函数主要考虑一般棋手会考虑到的一些问题，例如：棋子的棋力、棋子在棋盘上的位置、棋子间的相互制约和棋子的机动性等等。香农是国际象棋博弈理论的先驱。当国际象棋博弈已经发展到一个比较成熟的阶段，对中国象棋博弈的研究才刚刚开始。直到1981年，张耀腾发表了第一篇研究中国象棋人机博弈的文章人造智慧在电脑象棋上的应用。他在他的文章中以残局做实验，提出了局面评估函数是静态子力值、棋子机动性、棋子的位置、威胁和保护等之和，但是缺乏对全局的把握。1982廖嘉成发表的利用计算机

10、象棋的实验，其中包括对开局、中局和残局的研究。1983年周玉龙、黄少龙一起开发的象棋排局系列软盘系统，实现了电脑与人的对弈。这些研究成果为象棋软件的发展奠定了基础。到了九十年代，中国象棋软件开始发展起来了，出现了一些比较著名的象棋软件，如中国象棋、将族、象棋水浒战、象棋巫师等，但是当时的象棋软件没有布局库，水平上比较弱。进入21世纪以后，中国象棋人机博弈的研究受到越来越多的关注，并且随着计算机硬件和软件水平的不断提高，象棋软件得到了很大水平上的提升。目前象棋软件比较厉害的是新天机、台风引擎、象棋名手、新小虫等，这些象棋软件基本上都有计算能力强，审局比较深入等优点，这也是现在中国象棋计算机博弈的

11、正在进行进一步研究的地方。1.3 论文的主要工作本文的主要工作是将人工智能和中国象棋结合在一起，通过MFC文档视图体系结构和Visual C+开发工具，设计并实现一个中国象棋人机博弈系统。主要的部分是象棋的界面实现部分和博弈引擎部分。界面拥有友好人机交互，主要包括棋盘、菜单、功能按钮，提供一些悔棋、还原或者走法显示之类的功能。引擎部分主要是数据结构、走法生成、局面评估和搜索算法，是程序的核心部分。第二章 中国象棋简介5第二章中国象棋简介2.1 简介中国象棋历史悠久，起源于山西沁县。战国时期，已经有了关于象棋的正式记载，如：说苑载：“雍门子周以琴见孟尝君，说：足下千乘之君也，燕则斗象棋而舞郑女。

12、”。楚辞·招魂中有“蓖蔽象棋，有六簿些；分曹并进，遒相迫些；成枭而牟,北周象戏，呼五白些。”。因此在战国时期，象棋就开始在贵族中流传。中国象棋发展到唐朝的时候，发生了巨大的变化，由原先的战国时期盛行的文博象棋发展到了有4个兵种，分别是“将、马、车、卒”，刚开始，和国际象棋一样的，中国象棋的棋盘也是由黑白相间的64个方格组成。后又变成和围棋一样的90个网格点。经过不断的传承和演变至宋代，中国象棋才完全定型。增加了“炮”“象”、“士”这三个兵种。记载于宋代的事林广记的象棋棋谱是中国目前所能看到的最早的象棋谱，比西方15世纪出现的国际象棋谱早200多年。推翻了“中国象棋起源于印度”的言论。

13、到了明代，可能为了方便下棋和记忆，才将一方面的“将”改为“帅”，变得和现代中国象棋一样了。中国象棋是一种两人对抗游戏，比赛方法类似于古代打仗。两军对战，排列两边，有兵、马、车、炮，还有将军和士兵。兵、马、车、炮作为主要的力量，将（帅）只待在军帐中指挥，还有卫兵保护他。棋子在网格的交叉点上移动，将对方的棋子“吃掉”，占领对方的交叉点，或者直接进行移动都算走了一着，直到将对方的“将”或“帅”擒住，分出胜、负、和，完成对局。2.2 棋盘和棋子中国象棋有三十二个棋子，分为红黑棋子两组，红子十六个、黑子十六个，对弈双方各一组，棋子的兵种是一样的，分为七个兵种：红方分为：帅（一个）、仕（两个）、相（两个）

14、、车（两个）、马（两个）、炮（两个）、兵（四个）；黑方分为将（一个）、士（两个）、象（两个）、车（两个）、马（两个）、炮（两个）、卒（四个）。为了区分红黑棋子，方便记忆，有四组兵种的名字是不一样的，其中帅=将、仕=士、相=象、兵=卒，但是它们两两间的作用完全相同。“棋盘”是棋子的活动场所，就一方来说，棋面由五条横线和九条直线交叉组成。中间中间有一条空白横道，称为“楚河汉界”， “楚河汉界”将整个棋盘分为两部分，两部分通过河界相连，变成了横十竖九的完整棋盘，拥有九十个交叉点，棋子就摆放在这些交叉点上。“河界”中间不标直线，棋子跨越“河界”，无论是直走横走或斜走均按有线行棋。棋盘上画“米”字形方格

15、的地方，叫做“九宫”，“九宫”是“将帅”的王宫，开局时将就待在王宫的最深处。2.3 走棋规则在中国象棋中各种棋子的走法是不一样的，都有自己的规则，规则如下：“帅”(将)每一着只许走一步，前进、后退、横走都可以，但不能走出“九宫”。将和帅不准在同一直线上直接对面，如一方已先占据，另一方必须回避。“士”(仕)每一步只可以沿对角线方向移动一点，可进不可退，而且只能在王宫内移动，它是将帅的贴身护卫。“象”（相)不能越过河界，每一招斜走两步，可进不可退，称为“象飞田”。另外，如果在移动的过程中“田”中间有棋子，那么象是不能移动的，称为“塞象眼”。“马”只能先水平或垂直移动一个交叉点，然后再像对角线的方向

16、移动（如果第一步水平移动时，只能往移动方向的对角线移动；如果第一部是垂直移动，则对角线的移动方向不受约束），称为“马走日”。另外，在理想的状况下，马可以随意移动到四周的八个点，故有"八面威风"之说。但是如果在横向或者竖向旁边的交叉点上有别的棋子挡住，马就无法往那个方向移动，称为“蹩马腿”。“车”可以在水平或着垂直方向移动任意个的点，但是不可以跨子移动。一个车可以横向和纵向工控制十七个点，故有“一车十子寒”之说。“炮”移动的方式和车很差不多，但它必需越过一个棋子来吃掉敌方的一个棋子，称为“炮打隔子”。“兵”（卒）在过楚河汉界之前，只能向前面移动一点。但是过了楚河汉界之后，兵除

17、了不允许往后移动之外，它可以往左右移动了，故有“过河的卒子顶半个车”之说。第三章 系统分析和设计13第三章 系统分析3.1 MFC简介本文用到的开发工具是Visual C + 6.0,简称VC或者VC6. 0，是微软推出的一款 C 编译器，将“高级语言”翻译为“机器语言（低级语言)”的程序。Visual C是一个功能强大的可视化软件开发工具。同时我们用到的是Visual C+下的MFC文档视图体系结构，下面我们对MFC做一个简单的介绍。CObjectCDocumentCCmdTargetCWinThreadCWndCWinAPPCDialog及控件CFrameWndCViewCMiniFram

18、eWndCMDIchildWndCMDIFrameWnd首先MFC是一个基础类库，这个库中封装了很多的WinAPI函数，它的类的层次结构如图3.1：图3.1 MFC类层次结构图由于C+可以继承类，支持虚函数，和MFC的消息映射机制，程序员可以通过对类的继承和扩展来实现特定的功能。 另一方面MFC也是由各种类构成的一个应用程序框架，在VC+下建立一个新的MFC工程的话，Microsoft Visua C+通过AppWizard自动生成许多的文件，这些文件构成了一个框架，是用户接口的标准实现方法，程序员需要做的就是通过生成的接口在这个轮廓当中加入应用程序要实现的核心内容。程序员可以通过资源编辑器设

19、计用户界面和接口，也可以通过ClassWizard向框架文件中添加代码。同时MFC也可以对工程文件进行封装，简单方便。3.2 棋局表示计算机要下棋首先是要读懂象棋，意思就是要让计算机知道当前棋盘局面（棋盘上棋子的分布情况）。对于计算机来说，它能读懂的就是由数据结构和算法所组成的程序，所以我们首先要考虑的是用什么样的数据结构来记录棋子和棋子在棋盘上的位置，用不同的数据结构来表示棋盘，程序会产生不同时间、空间复杂度。采用10×9的二维数组来存取棋盘信息，是中国象棋棋局最为简单的一种表示方法。二维数组的每个元素代表着棋盘上的一个节点，元素的值代表着这个节点上放置什么棋子或者没有棋子。如果把

20、棋盘看做是一个平面坐标系，我们可以通过数组元素的横坐标和纵坐标知道每个棋子的位置信息。并且在棋盘上最多32个棋子，所以可以用一个32个字节的一维数组表示所有棋子的位置，其中每个字节的高4位表示该棋子的横坐标，低4位表示棋子的纵坐标。而已经被吃掉的棋子用坐标范围以外的数表示。这样棋盘信息就被装入这32个字节中。当然也可以把棋盘看作一维的，每个元素保存直接的位置信息。上面介绍的两个棋盘表示方法，一个是基于棋盘的数组，一个是基于棋子的数组。棋盘数组中通过棋子的位置可以在常数时间内获得棋子类型，但通过棋子的类型获得棋子的位置则需要遍历；在棋子数组中通过棋子的类型可以在常数时间内获得棋子的位置，但通过棋

21、子的位置获得棋子的类型则很麻烦。如果将两种棋盘表示方法结合起来，那么我们既可以在常数时间内由棋子位置获得棋子类型，也可以在常数时间内由棋子类型获得棋子位置，这就大大提高了搜索的时间这就是“棋子-棋盘联系数组”，这是很多改进棋盘的基础。棋局的表示是整个程序最基础的部分，之后所做的工作都要建立在这个基础上。3.3 走法生成走法生成就是要通过遍历产生所有有效的走法，计算机通过程序挑选出最有利的走法，并判断人类棋手的走子是否符合走棋规则。走法生成在博弈程序中是特别复杂和耗费时间的部分，只能靠穷举来生成所有的走法，同时为了方便搜索，要将所有生成的走法存入一个队列，并且由于搜索的层数不同（我们这里将搜索深

22、度定位1-3），还必须将走法所处的层数也存入队列。根据实战统计，中国象棋每一步的合法走法大约是五六十中，还可以通过良好的数据结构和走法预生成来提高生成速度。走法预生成是为了提高走法产生的效率，把每种棋子在某一位置的最大可走步建成一个数据库，在产生走法时直接取出数据，然后根据具体的棋局去除不合法的走法，即以空间换时间的优化。走法生成是搜索的前提，优化走法生成很大程度上可以提高博弈速度。3.4 局面评估对于整个中国象棋博弈程序来说，如果说搜索算法是程序的心脏，那么局面评估就是程序的大脑，这两个部分都是整个程序的核心。在这里，局面评估的作用是通过象棋知识评价当前的棋局进行好坏的评价，通过一个函数将棋

23、局局面进行量化，得到一个估值。，正所谓：“象棋似布阵，点子如点兵”，中国象棋知识错综复杂，但是在中国象棋博弈系统中我们要考虑到的棋类知识主要有四点：子力价值和子力总和：子力价值是指某一棋子本身所具有的价值。棋子的子力价值决定棋子能控制的点位的多少。例如，车是象棋中实力最强的棋子，在棋盘上移动与进攻都十分方便，所以假设车的值为10，那比车实力小的马的值可能就为6，卒值可能就为2等等。但是各个子力价值只是参考，而真正能体现棋局优劣的是所剩的子力总和，单车胜不了士象全,而马炮可以对抗士象全，所以在评估局面时，首先要对双方的子力总和进行一个对比。棋子的位置：棋子的位置是指棋子在棋盘上的位置及可控的区域

24、，例如，过河卒、沉底炮、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差的棋子位置状态。棋子的机动性：棋子的机动性是指棋子的灵活性。例如，刚开局时，车的受到的约束较大，移动性较差，下棋讲究车早出，故有“输棋只因出车迟”之说。同样被四面蹩脚的马，它是不能移动的，所以它的机动性为0.棋子间的关系：棋子间的关系在棋局当中是非常复杂的。一个棋子和其它棋子之间的关系往往不是一对一的关系，例如，一个炮可能在攻击完对方的车之后被对方的马攻击。3.4.1 估值函数在程序中，估值函数的作用是把局面的质量量化成为直观的数字，估值函数可以是简单的，也可以是复杂的，这取决于你在程序中加入的知识的数

25、量。在中国象棋博弈程序中，估值函数就是各种棋类知识综合考虑计算之后所得到的值。 对于棋子控制区域的打分我们也可以根据已经定义好的“控制区域价值表”，然后对其进行累加即可。对于子力的打分，我们可以根据已经定义好的“棋子价值表”。“棋子价值表”是由各个棋子的紧要程度和走法综合考虑得到的值。在估值函数中，我们可以用这样的公式来计算一方棋子的子力总和：sideValue（各种棋子的总价值和）=sum(PieceNum（该种棋子的价值）*PieceValue（某种棋子的数量）)；对于棋子的机动性的打分，我们需要给予棋子每种走法一个值，将每种走法的估值相加，就可以得到每个棋子的机动性得分。然后可以用下面的

26、表达式求某一方棋子机动性:Mobility（棋子的灵活性分数）=Sum(MoveNum（某种棋子的合法走法数量）*MoveValue（该种棋子每一走法的价值）)；通过遍历棋盘，我们可以完成对控制区域的打分、子力打分和机动性打分，我们再根据关系表来考察棋子的相互关系，进行棋局棋子关系打分。分析棋子关系时，由于王的特殊性，王一旦被攻击，那么整个游戏就结束了，所以我们要把王拿出来单独考虑。其次，对其他的棋子，在分析棋子关系时，我们要考虑到：当攻击者子力价值小于被攻击者子力价值，攻击方将愿意换子。例如，一个马正受到一个兵的攻击，那我被攻击方将可以直接放弃对马的保护。或者是多对多的情况，攻击方的子力总和

27、<被攻击方的情况下，攻击方肯定是愿意直接换子的。所以在程序中我们也考虑到要防止双方兑子过快，但是这里并没有考虑双方兑子后局面的变化（要通过大量的数据来研究重新考虑兑子过后的局面是否有效），可以在以后的研究中对引擎进行改进。3.4.2 估值函数和博弈性能一般来说博弈系统的性能，速度，棋类知识满足下面的关系：Performance(性能)=Speed(速度)×Kowledge(知识)博弈系统的性能基本上取决于估值的速度和所加入的知识量。但是从客观的角度来说，并不是完全正相关的关系。知识的量上来说，知识越多，我们搜索时考虑的更加全面，所以搜索结果也是比较优的，博弈性能相对来说就好一些

28、，但是当加入的知识越多时，搜索的速度就慢下来了，博弈的性能可能就相对降低了。所以我们要想获得性能优异的博弈程序，我们必须在速度和知识二者中间寻求一个平衡。当然，由于估值函数模块和其他程序模块的耦合度并不高，我们可以考虑替换很多的估值函数，最终给出估值，但是这样做效率比较低，我们应该寻求一种比较好的估值函数来提高博弈性能。本文的是终点估值，即到达叶子节点时，使用估值函数对它进行估值，这种方法思路清晰，容易设计。3.4.3估值函数的改进目前比较常用到的估值函数的改进方法是通过手工调整，就是进行大量的测试，通过仔细的比对，通过自身掌握的棋类知识，比如，从经验上可以知道，一个车的价值要比一个兵大，给车

29、赋予比兵大的数值，马炮则赋予位于其间的值;马和炮的地位相当，给予它们相当的数值，以避免盲目换子；如果对弈中使用了一些优秀的战术配合，那么就给予一定数值的奖励，等等。将这些经验放进评估函数中反复对弈，然后不断修正参数，找出一组性能较高的参数。本文中的估值函数优化方法主要是手工调整的方法，以后我们对程序的改进可以从机器智能计算的方面改进。3.5 搜索算法搜索算法是整个程序的核心部分，相当于程序的心脏，驱动着整个程序的运行。中国象棋的博弈树十分巨大，因此搜索算法的好坏很大程度上会影响到计算机的下棋水平（搜索的速率越快，我们可以搜索的深度就越深）。目前，计算机博弈搜索算法一般是图搜索策略，分为两类：盲

30、目搜索：又称无信息搜索或者穷尽搜索，它包括宽度优先搜索、深度优先搜索和等代价搜索。这种搜索方法会遍历整个博弈树（如果是无限图的话，那么搜索则永远不会终止），然后才能找到最优的路径，只适用于求解简单的问题。这种搜索方法的代表是极大极小值搜索算法。启发式搜索：又称为有信息搜索河有序搜索。启发式搜索是将一些具体的领域知识作为启发信息，对博弈树上的节点进行有选择的查找，以简化搜索过程。3.5.1 极大极小值搜索算法 极大极小值算法算法是一种最小化对手最大得益的算法（即一方要做出对自己最有利的选择）。这种算法一般用在围棋、五子棋、象棋等棋类程序。结局有三种可能：胜利、失败和平局。这个算法对战双方所考虑的

31、角度是不一样的，一方总是选择对自己最为有利的局面，为另一方总是选择对对方最为不利的局面，其输赢的总和为0（有点像能量守恒，就像本身两个玩家都有1点，最后输家要将他的1点给赢家，但整体上还是总共有2点）。中国象棋的博弈树很大的，如果用极大极小值算法来进行搜索，我们将必须遍历整个博弈树，这样的搜索效率会很低，搜索量也会非常的巨大，这个过程是不切实际的，但是如果毫无选择的减少搜索的范围，又会影响到搜索的结果，所以我们要考虑用什么方法对博弈树进行适当的裁剪，来降低搜索的数量，这就可以选择Alpha-Beta剪枝算法，Alpha-Beta剪枝算法可以在不影响搜索精度的条件下大幅减少搜索数目。3.5.2

32、Alpha-Beta剪枝搜索Alpha-Beta算法是与极大极小值算法非常相似的算法，AlphaBeta剪枝方法是对Minimax方法的优化，它们产生的结果是完全相同的，只不过运行效率不一样。一般来说，下棋双方对棋局肯定有着相似的认知，那就是你觉得对你很糟糕的局面，在你的对手看来则是对他很有利的局面，那么某些局面有可能导致很糟糕的局面的节点，你根本就没有考虑的必要，它只会把你引向更坏的局面，你应该放弃这个节点和它的子节点，这样一来就可以缩小博弈树，提高搜索速度，这称为“树的裁剪”。如图3.2所示的极大极小树片段中，按照极大极小值搜索规则，从左路分枝 55795834MAX5MIN图3.2 裁剪

33、树的叶节点倒推得到第一层MAX节点的值为5，可表示此时的着法最佳值，记为，显然此值可作为MAX方着法指标的下界。在搜索中路分枝时，因为第二层着法的选择是取第三层节点的最小值，即取Min(8，3，“”)，而无论“”中为何值，都不会比5大(最大为3)，故可以将“”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。同理搜索右路分枝，也可以进行剪枝操作，此类剪枝称为-剪枝。55795834MINMAX 图3.2 裁剪树如图3.2所示的极大极小树片段中，由左路分枝的叶节点倒推得到第一层MIN节点的值为n，可表示此时对方着法的钳制值，记为。显然此值可作为MIN方可能实现着法指标的上界。在搜索中路分枝时，因

34、为第二层着法的选择是取第三层节点的最大值，即取MAX(5，12，“”)，而无论“”中为何值，都不会比11小(至少为12)，故可以将“”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。同理搜索右路分枝，进行剪枝操作。此类剪枝称为-剪枝。但是这个算法严重依赖于走法的寻找顺序。很明显，搜索空间的大小和第一节点的估价值有关。如果你最先搜到的总是最坏的节点，那么就不可能找到值比beta还要坏的节点，就不会有任何裁剪，该算法会和极大极小值算法一样，遍历整个博弈树，搜索效率很低。但是如果我们最先搜到的总是最好的节点，这就是Alpha-Beta算法的搜索效率最好的情况。在数学的角度来看，搜索效率能提高到原来

35、的平方根。在最好的情况下，把搜索的深度设为d，节点的数量为极大极小值搜索算法的一半。在最坏的情况下，alpha-beta搜索算法和极大极小值搜索算法是一样的。多大程度的减小搜索空间取决于一个节点的子节点在有序的节点列表中如何发展下去。为了提高搜索的效率，可以调整子节点的节点列表。这就要涉及到启发式搜索了。3.5.3 启发式搜索及走法排序我们前面介绍的alpha-beta剪枝搜索是极大极小值搜索的改进，在一定程度上提高了效率，但是有着明显的缺点（在上文中有介绍），如果要提高搜索深度和搜索效率，就要配合搜索过程中得到的一些启发信息。利用启发信息来决定哪一个是下一步要做扩展的节点，这种搜索总是选择“

36、最有希望”的节点来作为下一个被扩展的节点。如何快速的找出那个“最有希望”的节点，灵活的运用启发信息，这就需要我们应用某些准则来重新排列节点列表中节点的顺序。根据这些搜索要求，我们出现了一些启发式搜索的形式。这些策略加快了搜索的速度。如下：历史启发，在搜索的过程中，很有可能会出现一些相似的局面，这些局面可能是前面已经出现的，我们可以对它用估值函数来给予这些局面一个估值，但现在我们有一种更好的办法可以快速判断这些局面是否还有继续下去的可能性。历史启发这种搜索策略就是在搜索的过程中，如果产生比较好的走法，那么如果以后产生相似的局面，这些走法也是比较好的，所以我们可以将这些走法存储下来，并给予一个参数

37、来记录它的得分，称为历史得分，这些局面出现的次数越多它的历史得分就越高。当我们进行一个新的局面评估时，我们要对它们进行排列，并且保证历史得分最高的在前面，这样就可以尽快的进行alpha-beta裁剪，提高搜索速率。杀手启发，这种搜索策略是一种特殊的历史启发，和历史启发不同的是杀手启发优先搜索造成每一层剪枝最多的走法。在搜索的 过程中，有一些走法很糟糕，它如果被搜索到就会被剪掉。将这些走法记录下来，当下一次搜索到同一层时，如果杀手走法是当前局面的一个合理走法，那就优先搜索杀手节点，然后将其裁剪掉。置换表，这种搜索策略是将搜索过程中的搜索信息记录下来。在以后的搜索中，如果搜索到的节点在记录表中已有

38、记录，那就可以直接引用记录。置换表搜索策略和以上两个搜索策略不同的地方是，这个搜索策略不需要清空记录表，而是一直保存，为以后所用。在本文文中，我们采用的历史启发这个搜索策略。我们可以使用各种排序算法对于走法进行排序，在此程序中采用了归并排序。归并排序的时间复杂度为O(nlog2n)，空间复杂度为O(n)，具有较高的效率。第四章 系统实现21第四章 系统设计与实现4.1 系统的整体规划我们在对象棋博弈系统的做了一个需求分析后进行了功能设计，这个象棋博弈系统应该具备的功能是人机对战、残局的保存和读取功能、悔棋和还原功能、走法显示功能。功能结构图如图4.1所示：用户界面人人对战人机对战悔棋还原保存读

39、取走法显示图4.1 功能结构图4.2 象棋界面的实现本文的界面实现用的是MFC类库，只需建立一个基于对话框的MFC应用程序，然后添加或者删掉一些菜单栏工具栏就可以了，非常方便。 主要分布为两个部分：（1）界面初始化部分OnInitDialog()函数负责的是对话框的初始化，同时也可以把中国象棋博弈程序相关内容进行初始化。相关内容包括：对棋盘上棋子位置的初始化；对程序辅助部分所用到的一些变量的初始化。包括对悔棋、还原队列的清空，棋盘、棋子样式的默认形式，下棋模式的默认选择，以及走法名称列表的初始化等等。（2）界面绘图部分MakeBoard( )函数和MB_DrawStar( )函数是完成棋盘界面

40、的绘图，OnPaint( )函数是完成棋盘界面上棋子的显示;这三个函数完成了程序界面棋盘、和走法名称的显示。OnPaint()函数主要贴表示棋子的位图；MakeBoard（）函数是画棋盘；MB_DrawStar（）是画星点（为MakeBoard调用）。但是位图只能是矩形的，而棋子是圆形的，直接使用的话会留下白色的背景框，所以我们要想通过一些“与”和“异或”操作来屏蔽掉棋子的背景。棋盘和棋子通过数组连接起来，形成一个完整的界面系统。4.3 对弈功能的实现对弈功能是整个博弈系统最主要的功能，本系统包括人人对战和人机对战的功能。本系统对于人人对战的实现是通过象棋规则的定义和图形化的棋子如何在棋盘上移

41、动来实现的。Cango（）函数实现了对于棋子走法的定义，根据棋子走法判断我们可以定义棋子是否是正确的移动，判断棋子位置是不是合法，是由IsNormal（）函数实现的。OnLButtonDown( )函数和OnLButtonUp( )函数是用户动作响应部分，实现了棋子在棋盘上的移动。最后由FixManMap（）函数保存棋盘状态。当用户点击鼠标时，调用OnLButtonDown（）函数，第一个参数表示确定左键是否按下，第二个参数为左键按下时点的位置坐标。当用户放开鼠标是，调用OnLButtonUp()函数，参数的作用和OnLButtonDown函数是一样的。OnLButtonDown函数里处理的操

42、作是：如果用户点击鼠标的位置落在己方的棋子上，表示用户选中了该棋子，下一步将移动该子进行走棋（也可能用户下一步将会选择己方另外的棋子，总之这一操作会记录下用户所选的将要走的棋子）。OnLButtonUp函数处理的操作是：如果之前用户已经点击了棋子，那么就可以移动棋子，这是用户的一次走棋过程。在收到用户传达的走棋信息后，可先判断该走法是否合理（是否符合中国象棋的走棋规则），如果是合理，则执行之，如果不合理，则让棋子回到它原来的位置。系统最终的目的是要实现人机对战，人机对战的核心就是人工智能，本文是通过上面第三章介绍的技术实现人工智能的。实现电脑走棋的逻辑步骤如图4.2所示：走法生成局面评估搜索走

43、法找到合适的走法图4.2 人工智能实现流程图走法生成部分，EnumList（）函数列出了当前局面的所有走法。估值函数部分，首先const int ManBPlus21211规定了各个位置的价值，ManBaseValue32规定了棋子的固定价值，然后通过估值函数Value（），对走法进行估值，判断那种走法价值最大，其中ContactV（）函数是Value（）的子函数，计算各个棋子的活跃度和棋子间的关系值。搜索部分，通过搜索找到比较好的走法，这里通过SubThink（）函数对着法进行搜索。做完以上的部分后，通过Think（）函数找到最佳走法。4.4 悔棋和还原功能的实现悔棋和还原功能是象棋软件的基

44、本功能。要实现悔棋和还原的功能，在博弈程序中，我们要建立一个走法栈（CStepList m_StepList）来保存每一回合的棋局局面（棋子数组和棋子位置等等）。还原功能是在悔棋步骤实现之后才能被激活的，博弈双方对战一个回合之后，如果没有进行悔棋，那么还原栈是要清空的。在本文中，OnEditRedo（）函数实现了悔棋功能，OnEditUndo( )函数实现了还原功能。下面我们将介绍一下悔棋和还原功能的步骤。悔棋功能实现的步骤：下棋回合数减一；走法栈存储当前的棋局信息，可用于还原步骤；把上一回合的着法名称从走法栈中取出，然后将它显示成当前局面，并将最近的走法从走法栈中删除掉;将列表框中的最后一列

45、着法名称存储到着法名称队列中，为还原所用。然后从列表框中删除它。还原功能实现的步骤：下棋回合数加一；走法栈存储当前棋局信息，可用于悔棋步骤；从着法队列中取出最近一次存储的着法名称，将这些信息恢复成棋局局面，并表示出来；从着法队列中取出最近一次存入的着法名称，将其重新显示到列表框中，并在走法栈中存储。然后将其从着法名称队列中剔除。以上就是悔棋和还原的所有步骤，在用户界面上可以通过添加了事件处理函数的悔棋和还原按钮来实现。4.5 文件保存和读取功能的实现MFC中文件的读取和存储使用的是CFile与CFileDialog类。CFileDialog类中封装了windows常用的文件对话框，这个类提供了

46、一种简单的和Windows标准相一致的文件打开和文件存储对话框功能。在程序中通过CFileDialog构造一个对象之后，初始化对话框控件，然后调用DoModal成员函数显示对话框并使用户输入路径和文件。OnFileSave（）函数实现了棋谱文件的存储，OnFileOpen（）函数实现了棋谱文件的打开。4.6 着法显示功能的实现每当用户或者计算机走一步棋时，就会按照中国象棋棋子着法描述规范在棋盘界面上的列表框控件（List Box）中显示棋子着法，例如：兵三进一（用户），炮8进4（电脑）等。在本文中编写了一个函数来获得着法名称，实现将被移动的棋子的兵种以及棋子的起始坐标、终点坐标经过一定的计算转

47、换成标准的中国象棋着法名称。我们通过GetStepName( )函数取得走法名称，然后显示在ListBox中。当列表框中的显示数目超过了显示范围，列表框会自动加一个滚动条。4.7 程序说明ChessDlg.h是象棋相关定义，其中包括棋盘局面和着法的表示。BaseClasses.h是棋局初始化。BaseDef.h是着法生成器，生成当前局面某一方所有合法着法。CoolButton.h是用于绘制主界面右下角的四个按钮。Resource.h是资源管理。StepList.h是走法生成存储。Thinkdef.h是历史启发，Alpha-Beta搜索之补充，以提高搜索效率。Thinker.h是着法排序，通过启

48、发信息对节点列表中节点进行排序，以提高搜索效率。ThinkOptionDlg.h是局面评估，为某一特定局面进行评分。MoveList.是搜索部分，使用搜索求出最佳着法。4.8 系统测试及实验结果 系统测试属于黑盒类测试，是根据需求文档对软件的功能和性能进行测试，它不涉及程序的代码部分，只是通过不同的硬件和外设条件进行兼容性测试，通过测试用例测试功能是否满足需求文档，通过测试软件对软件进行压力测试等等。 我们这里主要是在软件程序完成时，在windows 7系统环境下测试棋子的走法是否是按照中国象棋的走子规则是否可以实现人机对弈，是否可以对参数进行设置，是否保存和读取棋谱等等。 测试用例的设计，我

49、们可以这样进行设计，如表4.1：表 4.1 测试用例 功能点 前置条件 动作 预期结果 测试结果 文件保存 / 点击保存棋谱文件存储到电脑棋谱文件存储到电脑 文件读取电脑有正确的棋谱文件 点击打开选取棋谱文件读取棋谱文件并显示棋局读取棋谱文件并显示棋局 文件读取 / 点击打开选取其他文件无法打开文件无法打开文件 棋子走棋棋盘上有棋子按照正确的方式走棋棋子可以移动棋子可以移动 棋子走棋棋盘上有棋子按照不正确的方式走棋 棋子不可以移动 棋子不可以移动 悔棋 已经走棋点击悔棋按钮棋局回到上一个局面棋局回到上一个局面 还原悔棋已实现点击还原按钮棋局回到悔棋前局面棋局回到悔棋前局面经过不断的调试与修改，

50、我们将中国象棋博弈程序实现出来了。并且经过系统测试，该中国象棋博弈系统完全满足需求文档中的功能和性能。首先最重要的功能是可以实现人机对弈，并且所有的棋子可以都按照标准的中国象棋走子规则移动，其次满足悔棋和还原的功能，也可以对参数进行设置，满足象棋残局文件的保存和读取。如图4.3是软件界面的截图，在界面上所有的功能都一目了然，界面包括棋盘区域、走法显示区域、悔棋按钮、还原按钮，但是可能还存在一些不足之处，如外观不够美观，没有音效。图4.3 中国象棋博弈系统用户界面截图图4.4 残局保存功能截图如图4.4是象棋博弈系统的残局保存功能，在这里我们可以看到我们可以将残局保存为棋谱类型，保存到电脑上，之后可以读取后再进行切磋。如图4.5是象棋博弈系统的棋谱读取功能，它只能正确读取棋谱文件，然后显示