中国象棋人机博弈系统的设计和实现.docx

班级031221学号0312本科毕业设计论文题目中国象棋人机博弈系统设计和实现学 院 计算机学院 专 业 网络工程 学生姓名 李盼舒 摘要中国象棋发展至今已经有了几千年历史，是中华民族灿烂文化瑰宝，它含有浓厚趣味性，规则简单明了，在中国已经成为了一项普遍棋类运动，是其它棋类远远无法比拟，而且现在，中国象棋正在往国外发展。为了使中国象棋愈加含有趣味性，我们在象棋博弈中加入了人机交互,实现了一个中国象棋人机博弈系统，这个系统是将计算机和人工智能结合起来一个电脑游戏。本文研究了中国象棋在电脑上局面表示，走棋过程中走法生成和局面评定、博弈树搜索等一系列问题。经过visual 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 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 that 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-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 intelligence 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第四章 系统设计和实现154.1 系统整体计划154.2 象棋界面实现154.3 对弈功效实现164.4 悔棋和还原功效174.5 文件保留和读取功效184.6 着法显示功效184.7 程序说明184.8 系统测试及试验结果19第五章 总结和展望23致 谢25参考文件27第一章绪论1.1选题背景和意义近几十年来，伴随计算机硬件和软件技术飞速发展，电脑游戏产业展现出了蓬勃发展势头，已经变成和音乐、影视等并驾齐驱娱乐产业。大家也开始对计算机是否能够战胜人脑产生了爱好。从二十世纪八十年代起，电脑人工智能开始向人类智能提出了挑战，到1997年，IBM研究超级电脑击败了当初国际象棋冠军，成为人类人工智能发展史上关键标志。人类对于人工智能探索是从棋类开始，研究人工智能学者们曾经表示：假如我们要想深入了解人类智能关键技术，我们就必需掌握棋类本质。中国象棋从古代流传至今有了几千年历史，是一个古老文化，集人类科学、文化、艺术为一体，有利于开发人智力，培养人思维，锻炼人毅力，使人更含有竞争意识。而且相比较于国际象棋，中国象棋更为复杂，所以对中国象棋人机博弈问题进行研究更有意义。怎样让机器变得智能，能够和人类智力进行竞技，是本文研究一个关键问题，经过本文研究，掌握人工智能搜索、知识表示、计算，在人工智能领域进行一个深度探索。1.2 中国外棋类博弈发展现实状况人类对于机器棋类博弈研究最早是开始于国际象棋，美国数学家香农经过几十年研究，找到了编写国际象棋程序方法，她提出了经过一个函数评定局面优劣，函数关键考虑通常棋手会考虑到部分问题，比如：棋子棋力、棋子在棋盘上位置、棋子间相互制约和棋子机动性等等。香农是国际象棋博弈理论先驱。当国际象棋博弈已经发展到一个比较成熟阶段，对中国象棋博弈研究才刚刚开始。直到1981年，张耀腾发表了第一篇研究中国象棋人机博弈文章人造智慧在电脑象棋上应用。她在她文章中以残局做试验，提出了局面评定函数是静态子力值、棋子机动性、棋子位置、威胁和保护等之和，不过缺乏对全局把握。1982廖嘉成发表利用计算机象棋试验，其中包含对开局、中局和残局研究。1983年周玉龙、黄少龙一起开发象棋排局系列软盘系统，实现了电脑和人对弈。这些研究结果为象棋软件发展奠定了基础。到了九十年代，中国象棋软件开始发展起来了，出现了部分比较著名象棋软件，如中国象棋、将族、象棋水浒战、象棋巫师等，不过当初象棋软件没有布局库，水平上比较弱。进入二十一世纪以后，中国象棋人机博弈研究受到越来越多关注，而且伴随计算机硬件和软件水平不停提升，象棋软件得到了很大水平上提升。现在象棋软件比较厉害是新天机、台风引擎、象棋名手、新小虫等，这些象棋软件基础上全部有计算能力强，审局比较深入等优点，这也是现在中国象棋计算机博弈正在进行深入研究地方。1.3 论文关键工作本文关键工作是将人工智能和中国象棋结合在一起，经过MFC文档视图体系结构和Visual C+开发工具，设计并实现一个中国象棋人机博弈系统。关键部分是象棋界面实现部分和博弈引擎部分。界面拥有友好人机交互，关键包含棋盘、菜单、功效按钮，提供部分悔棋、还原或走法显示之类功效。引擎部分关键是数据结构、走法生成、局面评定和搜索算法，是程序关键部分。第二章中国象棋介绍2.1 介绍中国象棋历史悠久，起源于山西沁县。战国时期，已经有了相关象棋正式记载，如：说苑载：“雍门子周以琴见孟尝君，说：足下千乘之君也，燕则斗象棋而舞郑女。”。楚辞招魂中有“蓖蔽象棋，有六簿些；分曹并进，遒相迫些；成枭而牟,北周象戏，呼五白些。”。所以在战国时期，象棋就开始在贵族中流传。中国象棋发展到唐朝时候，发生了巨大改变，由原先战国时期盛行文博象棋发展到了有4个兵种，分别是“将、马、车、卒”，刚开始，和国际象棋一样，中国象棋棋盘也是由黑白相间64个方格组成。后又变成和围棋一样90个网格点。经过不停传承和演变至宋代，中国象棋才完全定型。增加了“炮”“象”、“士”这三个兵种。记载于宋代事林广记象棋棋谱是中国现在所能看到最早象棋谱，比西方15世纪出现国际象棋谱早200多年。推翻了“中国象棋起源于印度”言论。到了明代，可能为了方便下棋和记忆，才将首先“将”改为“帅”，变得和现代中国象棋一样了。中国象棋是一个两人对抗游戏，比赛方法类似于古代打仗。两军对战，排列两边，有兵、马、车、炮，还有将军和士兵。兵、马、车、炮作为关键力量，将（帅）只待在军帐中指挥，还有卫兵保护她。棋子在网格交叉点上移动，将对方棋子“吃掉”，占领对方交叉点，或直接进行移动全部算走了一着，直到将对方“将”或“帅”擒住，分出胜、负、和，完成对局。2.2 棋盘和棋子中国象棋有三十二个棋子，分为红黑棋子两组，红子十六个、黑子十六个，对弈双方各一组，棋子兵种是一样，分为七个兵种：红方分为：帅（一个）、仕（两个）、相（两个）、车（两个）、马（两个）、炮（两个）、兵（四个）；黑方分为将（一个）、士（两个）、象（两个）、车（两个）、马（两个）、炮（两个）、卒（四个）。为了区分红黑棋子，方便记忆，有四组兵种名字是不一样，其中帅=将、仕=士、相=象、兵=卒，不过它们两两间作用完全相同。“棋盘”是棋子活动场所，就一方来说，棋面由五条横线和九条直线交叉组成。中间中间有一条空白横道，称为“楚河汉界”， “楚河汉界”将整个棋盘分为两部分，两部分经过河界相连，变成了横十竖九完整棋盘，拥有九十个交叉点，棋子就摆放在这些交叉点上。“河界”中间不标直线，棋子跨越“河界”，不管是直走横走或斜走均按有线行棋。棋盘上画“米”字形方格地方，叫做“九宫”，“九宫”是“将帅”王宫，开局时将就待在王宫最深处。2.3 走棋规则在中国象棋中多种棋子走法是不一样，全部有自己规则，规则以下：“帅”(将)每一着只许走一步，前进、后退、横走全部能够，但不能走出“九宫”。将和帅不准在同一直线上直接对面，如一方已先占据，另一方必需回避。“士”(仕)每一步只能够沿对角线方向移动一点，可进不可退，而且只能在王宫内移动，它是将帅贴身护卫。“象”（相)不能越过河界，每一招斜走两步，可进不可退，称为“象飞田”。另外，假如在移动过程中“田”中间有棋子，那么象是不能移动，称为“塞象眼”。“马”只能先水平或垂直移动一个交叉点，然后再像对角线方向移动（假如第一步水平移动时，只能往移动方向对角线移动；假如第一部是垂直移动，则对角线移动方向不受约束），称为“马走日”。另外，在理想情况下，马能够随意移动到四面八个点，故有八面威风之说。不过假如在横向或竖向旁边交叉点上有别棋子挡住，马就无法往那个方向移动，称为“蹩马腿”。“车”能够在水平或着垂直方向移动任意个点，不过不能够跨子移动。一个车能够横向和纵向工控制十七个点，故有“一车十子寒”之说。“炮”移动方法和车很差不多，但它必需越过一个棋子来吃掉敌方一个棋子，称为“炮打隔子”。“兵”（卒）在过楚河汉界之前，只能向前面移动一点。不过过了楚河汉界以后，兵除了不许可往后移动之外，它能够往左右移动了，故有“过河卒子顶半个车”之说。第三章 系统分析3.1 MFC介绍本文用到开发工具是Visual C + 6.0,简称VC或VC6. 0，是微软推出一款 C 编译器，将“高级语言”翻译为“机器语言（低级语言)”程序。Visual C是一个功效强大可视化软件开发工具。同时我们用到是Visual C+下MFC文档视图体系结构，下面我们对MFC做一个简单介绍。CObjectCDocumentCCmdTargetCWinThreadCWndCWinAPPCDialog及控件CFrameWndCViewCMiniFrameWndCMDIchildWndCMDIFrameWnd首先MFC是一个基础类库，这个库中封装了很多WinAPI函数，它类层次结构图3.1：图3.1 MFC类层次结构图因为C+能够继承类，支持虚函数，和MFC消息映射机制，程序员能够经过对类继承和扩展来实现特定功效。 其次MFC也是由多种类组成一个应用程序框架，在VC+下建立一个新MFC工程话，Microsoft Visua C+经过AppWizard自动生成很多文件，这些文件组成了一个框架，是用户接口标准实现方法，程序员需要做就是经过生成接口在这个轮廓当中加入应用程序要实现关键内容。程序员能够经过资源编辑器设计用户界面和接口，也能够经过ClassWizard向框架文件中添加代码。同时MFC也能够对工程文件进行封装，简单方便。3.2 棋局表示计算机要下棋首先是要读懂象棋，意思就是要让计算机知道目前棋盘局面（棋盘上棋子分布情况）。对于计算机来说，它能读懂就是由数据结构和算法所组成程序，所以我们首先要考虑是用什么样数据结构来统计棋子和棋子在棋盘上位置，用不一样数据结构来表示棋盘，程序会产生不一样时间、空间复杂度。采取109二维数组来存取棋盘信息，是中国象棋棋局最为简单一个表示方法。二维数组每个元素代表着棋盘上一个节点，元素值代表着这个节点上放置什么棋子或没有棋子。假如把棋盘看做是一个平面坐标系，我们能够经过数组元素横坐标和纵坐标知道每个棋子位置信息。而且在棋盘上最多32个棋子，所以能够用一个32个字节一维数组表示全部棋子位置，其中每个字节高4位表示该棋子横坐标，低4位表示棋子纵坐标。而已经被吃掉棋子用坐标范围以外数表示。这么棋盘信息就被装入这32个字节中。当然也能够把棋盘看作一维，每个元素保留直接位置信息。上面介绍两个棋盘表示方法，一个是基于棋盘数组，一个是基于棋子数组。棋盘数组中经过棋子位置能够在常数时间内取得棋子类型，但经过棋子类型取得棋子位置则需要遍历；在棋子数组中经过棋子类型能够在常数时间内取得棋子位置，但经过棋子位置取得棋子类型则很麻烦。假如将两种棋盘表示方法结合起来，那么我们既能够在常数时间内由棋子位置取得棋子类型，也能够在常数时间内由棋子类型取得棋子位置，这就大大提升了搜索时间这就是“棋子-棋盘联络数组”，这是很多改善棋盘基础。棋局表示是整个程序最基础部分，以后所做工作全部要建立在这个基础上。3.3 走法生成走法生成就是要经过遍历产生全部有效走法，计算机经过程序挑选出最有利走法，并判定人类棋手走子是否符合走棋规则。走法生成在博弈程序中是尤其复杂和花费时间部分，只能靠穷举来生成全部走法，同时为了方便搜索，要将全部生成走法存入一个队列，而且因为搜索层数不一样（我们这里将搜索深度定位1-3），还必需将走法所处层数也存入队列。依据实战统计，中国象棋每一步正当走法大约是五六十中，还能够经过良好数据结构和走法预生成来提升生成速度。走法预生成是为了提升走法产生效率，把每种棋子在某一位置最大可走步建成一个数据库，在产生走法时直接取出数据，然后依据具体棋局去除不正当走法，即以空间换时间优化。走法生成是搜索前提，优化走法生成很大程度上能够提升博弈速度。3.4 局面评定对于整个中国象棋博弈程序来说，假如说搜索算法是程序心脏，那么局面评定就是程序大脑，这两个部分全部是整个程序关键。在这里，局面评定作用是经过象棋知识评价目前棋局进行好坏评价，经过一个函数将棋局局面进行量化，得到一个估值。，正所谓：“象棋似布阵，点子如点兵”，中国象棋知识错综复杂，不过在中国象棋博弈系统中我们要考虑到棋类知识关键有四点：子力价值和子力总和：子力价值是指某一棋子本身所含有价值。棋子子力价值决定棋子能控制点位多少。比如，车是象棋中实力最强棋子，在棋盘上移动和进攻全部十分方便，所以假设车值为10，那比车实力小马值可能就为6，卒值可能就为2等等。不过各个子力价值只是参考，而真正能表现棋局优劣是所剩子力总和，单车胜不了士象全,而马炮能够对抗士象全，所以在评定局面时，首先要对双方子力总和进行一个对比。棋子位置：棋子位置是指棋子在棋盘上位置及可控区域，比如，过河卒、沉底炮、和车占士角等全部是很好棋子位置状态，而窝心马、将离开底线等则属较差棋子位置状态。棋子机动性：棋子机动性是指棋子灵活性。比如，刚开局时，车受到约束较大，移动性较差，下棋讲究车早出，故有“输棋只因出车迟”之说。一样被四面蹩脚马，它是不能移动，所以它机动性为0.棋子间关系：棋子间关系在棋局当中是很复杂。一个棋子和其它棋子之间关系往往不是一对一关系，比如，一个炮可能在攻击完对方车以后被对方马攻击。3.4.1 估值函数在程序中，估值函数作用是把局面质量量化成为直观数字，估值函数能够是简单，也能够是复杂，这取决于你在程序中加入知识数量。在中国象棋博弈程序中，估值函数就是多种棋类知识综合考虑计算以后所得到值。 对于棋子控制区域打分我们也能够依据已经定义好“控制区域价值表”，然后对其进行累加即可。对于子力打分，我们能够依据已经定义好“棋子价值表”。“棋子价值表”是由各个棋子紧要程度和走法综合考虑得到值。在估值函数中，我们能够用这么公式来计算一方棋子子力总和：sideValue（多种棋子总价值和）=sum(PieceNum（该种棋子价值）*PieceValue（某种棋子数量）)；对于棋子机动性打分，我们需要给棋子每种走法一个值，将每种走法估值相加，就能够得到每个棋子机动性得分。然后能够用下面表示式求某一方棋子机动性:Mobility（棋子灵活性分数）=Sum(MoveNum（某种棋子正当走法数量）*MoveValue（该种棋子每一走法价值）)；经过遍历棋盘，我们能够完成对控制区域打分、子力打分和机动性打分，我们再依据关系表来考察棋子相互关系，进行棋局棋子关系打分。分析棋子关系时，因为王特殊性，王一旦被攻击，那么整个游戏就结束了，所以我们要把王拿出来单独考虑。其次，对其它棋子，在分析棋子关系时，我们要考虑到：当攻击者子力价值小于被攻击者子力价值，攻击方将愿意换子。比如，一个马正受到一个兵攻击，那我被攻击方将能够直接放弃对马保护。或是多对多情况，攻击方子力总和被攻击方情况下，攻击方肯定是愿意直接换子。所以在程序中我们也考虑到要预防双方兑子过快，不过这里并没有考虑双方兑子后局面改变（要经过大量数据来研究重新考虑兑子过后局面是否有效），能够在以后研究中对引擎进行改善。3.4.2 估值函数和博弈性能通常来说博弈系统性能，速度，棋类知识满足下面关系：Performance(性能)=Speed(速度)Kowledge(知识)博弈系统性能基础上取决于估值速度和所加入知识量。不过从客观角度来说，并不是完全正相关关系。知识量上来说，知识越多，我们搜索时考虑愈加全方面，所以搜索结果也是比较优，博弈性能相对来说就好部分，不过当加入知识越多时，搜索速度就慢下来了，博弈性能可能就相对降低了。所以我们要想取得性能优异博弈程序，我们必需在速度和知识二者中间寻求一个平衡。当然，因为估值函数模块和其它程序模块耦合度并不高，我们能够考虑替换很多估值函数，最终给出估值，不过这么做效率比较低，我们应该寻求一个比很好估值函数来提升博弈性能。本文是终点估值，即抵达叶子节点时，使用估值函数对它进行估值，这种方法思绪清楚，轻易设计。3.4.3估值函数改善现在比较常见到估值函数改善方法是经过手工调整，就是进行大量测试，经过仔细比对，经过本身掌握棋类知识，比如，从经验上能够知道，一个车价值要比一个兵大，给车给予比兵大数值，马炮则给予在其间值;马和炮地位相当，给它们相当数值，以避免盲目换子；假如对弈中使用了部分优异战术配合，那么就给一定数值奖励，等等。将这些经验放进评定函数中反复对弈，然后不停修正参数，找出一组性能较高参数。本文中估值函数优化方法关键是手工调整方法，以后我们对程序改善能够从机器智能计算方面改善。3.5 搜索算法搜索算法是整个程序关键部分，相当于程序心脏，驱动着整个程序运行。中国象棋博弈树十分巨大，所以搜索算法好坏很大程度上会影响到计算机下棋水平（搜索速率越快，我们能够搜索深度就越深）。现在，计算机博弈搜索算法通常是图搜索策略，分为两类：盲目搜索：又称无信息搜索或穷尽搜索，它包含宽度优先搜索、深度优先搜索和等代价搜索。这种搜索方法会遍历整个博弈树（假如是无限图话，那么搜索则永远不会终止），然后才能找到最优路径，只适适用于求解简单问题。这种搜索方法代表是极大极小值搜索算法。启发式搜索：又称为有信息搜索河有序搜索。启发式搜索是将部分具体领域知识作为启发信息，对博弈树上节点进行有选择查找，以简化搜索过程。3.5.1 极大极小值搜索算法 极大极小值算法算法是一个最小化对手最大得益算法（即一方要做出对自己最有利选择）。这种算法通常见在围棋、五子棋、象棋等棋类程序。结局有三种可能：胜利、失败和平局。这个算法对战双方所考虑角度是不一样，一方总是选择对自己最为有利局面，为另一方总是选择对对方最为不利局面，其输赢总和为0（有点像能量守恒，就像本身两个玩家全部有1点，最终输家要将她1点给赢家，但整体上还是总共有2点）。中国象棋博弈树很大，假如用极大极小值算法来进行搜索，我们将必需遍历整个博弈树，这么搜索效率会很低，搜索量也会很巨大，这个过程是不切实际，不过假如毫无选择降低搜索范围，又会影响到搜索结果，所以我们要考虑用什么方法对博弈树进行合适裁剪，来降低搜索数量，这就能够选择Alpha-Beta剪枝算法，Alpha-Beta剪枝算法能够在不影响搜索精度条件下大幅降低搜索数目。3.5.2 Alpha-Beta剪枝搜索Alpha-Beta算法是和极大极小值算法很相同算法，AlphaBeta剪枝方法是对Minimax方法优化，它们产生结果是完全相同，只不过运行效率不一样。通常来说，下棋双方对棋局肯定有着相同认知，那就是你认为对你很糟糕局面，在你对手看来则是对她很有利局面，那么一些局面有可能造成很糟糕局面节点，你根本就没有考虑必需，它只会把你引向更坏局面，你应该放弃这个节点和它子节点，这么一来就能够缩小博弈树，提升搜索速度，这称为“树裁剪”。图3.2所表示极大极小树片段中，根据极大极小值搜索规则，从左路分枝 55795834MAX5MIN图3.2 裁剪树叶节点倒推得到第一层MAX节点值为5，可表示此时着法最好值，记为，显然此值可作为MAX方着法指标下界。在搜索中路分枝时，因为第二层着法选择是取第三层节点最小值，即取Min(8，3，“”)，而不管“”中为何值，全部不会比5大(最大为3)，故能够将“”表示节点及其后继节点剪掉，不再考虑此节点延伸。同理搜索右路分枝，也能够进行剪枝操作，这类剪枝称为-剪枝。55795834MINMAX 图3.2 裁剪树图3.2所表示极大极小树片段中，由左路分枝叶节点倒推得到第一层MIN节点值为n，可表示此时对方着法钳制值，记为。显然此值可作为MIN方可能实现着法指标上界。在搜索中路分枝时，因为第二层着法选择是取第三层节点最大值，即取MAX(5，12，“”)，而不管“”中为何值，全部不会比11小(最少为12)，故能够将“”表示节点及其后继节点剪掉，不再考虑此节点延伸。同理搜索右路分枝，进行剪枝操作。这类剪枝称为-剪枝。不过这个算法严重依靠于走法寻求次序。很显著，搜索空间大小和第一节点估价值相关。假如你最先搜到总是最坏节点，那么就不可能找到值比beta还要坏节点，就不会有任何裁剪，该算法会和极大极小值算法一样，遍历整个博弈树，搜索效率很低。不过假如我们最先搜到总是最好节点，这就是Alpha-Beta算法搜索效率最好情况。在数学角度来看，搜索效率能提升到原来平方根。在最好情况下，把搜索深度设为d，节点数量为极大极小值搜索算法二分之一。在最坏情况下，alpha-beta搜索算法和极大极小值搜索算法是一样。多大程度减小搜索空间取决于一个节点子节点在有序节点列表中怎样发展下去。为了提升搜索效率，能够调整子节点节点列表。这就要包含到启发式搜索了。3.5.3 启发式搜索及走法排序我们前面介绍alpha-beta剪枝搜索是极大极小值搜索改善，在一定程度上提升了效率，不过有着显著缺点（在上文中有介绍），假如要提升搜索深度和搜索效率，就要配合搜索过程中得到部分启发信息。利用启发信息来决定哪一个是下一步要做扩展节点，这种搜索总是选择“最有期望”节点来作为下一个被扩展节点。怎样快速找出那个“最有期望”节点，灵活利用启发信息，这就需要我们应用一些准则来重新排列节点列表中节点次序。依据这些搜索要求，我们出现了部分启发式搜索形式。这些策略加紧了搜索速度。以下：历史启发，在搜索过程中，很有可能会出现部分相同局面，这些局面可能是前面已经出现，我们能够对它用估值函数来给这些局面一个估值，但现在我们有一个愈加好措施能够快速判定这些局面是否还有继续下去可能性。历史启发这种搜索策略就是在搜索过程中，假如产生比很好走法，那么假如以后产生相同局面，这些走法也是比很好，所以我们能够将这些走法存放下来，并给一个参数来统计它得分，称为历史得分，这些局面出现次数越多它历史得分就越高。当我们进行一个新局面评定时，我们要对它们进行排列，而且确保历史得分最高在前面，这么就能够立即进行alpha-beta裁剪，提升搜索速率。杀手启发，这种搜索策略是一个特殊历史启发，和历史启发不一样是杀手启发优先搜索造成每一层剪枝最多走法。在搜索 过程中，有部分走法很糟糕，它假如被搜索到就会被剪掉。将这些走法统计下来，当下一次搜索到同一层时，假如杀手走法是目前局面一个合理走法，那就优先搜索杀手节点，然后将其裁剪掉。置换表，这种搜索策略是将搜索过程中搜索信息统计下来。在以后搜索中，假如搜索到节点在统计表中已经有统计，那就能够直接引用统计。置换表搜索策略和以上两个搜索策略不一样地方是，这个搜索策略不需要清空统计表，而是一直保留，为以后所用。在本文文中，我们采取历史启发这个搜索策略。我们能够使用多种排序算法对于走法进行排序，在此程序中采取了归并排序。归并排序时间复杂度为O(nlog2n)，空间复杂度为O(n)，含有较高效率。第四章 系统设计和实现4.1 系统整体计划我们在对象棋博弈系统做了一个需求分析后进行了功效设计，这个象棋博弈系统应该含有功效是人机对战、残局保留和读取功效、悔棋和还原功效、走法显示功效。功效结构图图4.1所表示：用户界面人人对战人机对战悔棋还原保留读取走法显示图4.1 功效结构图4.2 象棋界面实现本文界面实现用是MFC类库，只需建立一个基于对话框MFC应用程序，然后添加或删掉部分菜单栏工具栏就能够了，很方便。 关键分布为两个部分：（1）界面初始化部分OnInitDialog()函数负责是对话框初始化，同时也能够把中国象棋博弈程序相关内容进行初始化。相关内容包含：对棋盘上棋子位置初始化；对程序辅助部分所用到部分变量初始化。包含对悔棋、还原队列清空，棋盘、棋子样式默认形式，下棋模式默认选择，和走法名称列表初始化等等。（2）界面绘图部分MakeBoard( )函数和MB_DrawStar( )函数是完成棋盘界面绘图，OnPaint( )函数是完成棋盘界面上棋子显示;这三个函数完成了程序界面棋盘、和走法名称显示。OnPaint()函数关键贴表示棋子位图；MakeBoard（）函数是画棋盘；MB_DrawStar（）是画星点（为MakeBoard调用）。不过位图只能是矩形，而棋子是圆形，直接使用话会留下白色背景框，所以我们要想经过部分“和”和“异或”操作来屏蔽掉棋子背景。棋盘和棋子经过数组连接起来，形成一个完整界面系统。4.3 对弈功效实现对弈功效是整个博弈系统最关键功效，本系统包含人人对战和人机对战功效。本系统对于人人对战实现是经过象棋规则定义和图形化棋子怎样在棋盘上移动来实现。Cango（）函数实现了对于棋子走法定义，依据棋子走法判定我们能够定义棋子是否是正确移动，判定棋子位置是不是正当，是由IsNormal（）函数实现。OnLButtonDown( )函数和OnLButtonUp( )函数是用户动作响应部分，实现了棋子在棋盘上移动。最终由FixManMap（）函数保留棋盘状态。当用户点击鼠标时，调用OnLButtonDown（）函数，第一个参数表示确定左键是否按下，第二个参数为左键按下时点位置坐标。当用户放开鼠标是，调用OnLButtonUp()函数，参数作用和OnLButtonDown函数是一样。OnLButtonDown函数里处理操作是：假如用户点击鼠标位置落在己方棋子上，表示用户选中了该棋子，下一步将移动该子进行走棋（也可能用户下一步将会选择己方另外棋子，总而言之这一操作会统计下用户所选将要走棋子）。OnLButtonUp函数处理操作是：假如之前用户已经点击了棋子，那么就能够移动棋子，这是用户一次走棋过程。在收到用户传达走棋信息后，可先判定该走法是否合理（是否符合中国象棋走棋规则），假如是合理，则实施之，假如不合理，则让棋子回到它原来位置。系统最终目标是要实现人机对战，人机对战关键就是人工智能，本文是经过上面第三章介绍技术实现人工智能。实现电脑走棋逻辑步骤图4.2所表示：走法生成局面评定搜索走法找到适宜走法图4.2 人工智能实现步骤图走法生成部分，EnumList（）函数列出了目前局面全部走法。估值函数部分，首先const int ManBPlus21211要求了各个位置价值，ManBaseValue32要求了棋子固定价值，然后经过估值函数Value（），对走法进行估值，判定那种走法价值最大，其中ContactV（）函数是Value（）子函数，计算各个棋子活跃度和棋子间关系值。搜索部分，经过搜索找到比很好走法，这里经过SubThink（）函数对着法进行搜索。做完以上部分后，经过Think（）函数找到最好走法。4.4 悔棋和还原功效实现悔棋和还原功效是象棋软件基础功效。要实现悔棋和还原功效，在博弈程序中，我们要建立一个走法栈（CStepList m_StepList）来保留每一回合棋局局面（棋子数组和棋子位置等等）。还原功效是在悔棋步骤实现以后才能被激活，博弈双方对战一个回合以后，假如没有进行悔棋，那么还原栈是要清空。在本文中，OnEditRedo（）函数实现了悔棋功效，OnEditUndo( )函数实现了还原功效。下面我们将介绍一下悔棋和还原功效步骤。悔棋功效实现步骤：下棋回合数减一；走法栈存放目前棋局信息，可用于还原步骤；把上一回合着法名称从走法栈中取出，然后将它显示成目前局面，并将最近走法从走法栈中删除掉;将列表框中最终一列着法名称存放到着法名称队列中，为还原所用。然后从列表框中删除它。还原功效实现步骤：下棋回合数加一；走法栈存放目前棋局信息，可用于悔棋步骤；从着法队列中取出最近一次存放着法名称，将这些信息恢复成棋局局面，并表示出来；从着法队列中取出最近一次存入着法名称，将其重新显示到列表框中，并在走法栈中存放。然后将其从着法名称队列中剔除。以上就是悔棋和还原全部步骤，在用户界面上能够经过添加了事件处理函数悔棋和还原按钮来实现。4.5 文件保留和读取功效实现MFC汉字件读取和存放使用是CFile和CFileDialog类。CFileDialog类中封装了windows常见文件对话框，这个类提供了一个简单和Windows标准相一致文件打开和文件存放对话框功效。在程序中经过CFileDialog结构一个对象以后，初始化对话框控件，然后调用DoModal组员函数显示对话框并使用户输入路径和文件。OnFileSave（）函数实现了棋谱文件存放，OnFileOpen（）函数实现了棋谱文件打开。4.6 着法显示功效实现每当用户或计算机走一步棋时，就会根据中国象棋棋子着法描述规范在棋盘界面上列表框控件（List Box）中显示棋子着法，比如：兵三进一（用户），炮8进4（电脑）等。在本文中编写了一个函数来取得着法名称，实现将被移动棋子兵种和棋子起始坐标、终点坐标经过一定计算转换成标准中国象棋着法名称。我们经过GetStepName( )函数取得走法名称，然后显示在ListBox中。当列表框中显示数目超出了显示范围，列表框会自动加一个滚动条。4.7 程序说明ChessDlg.h是象棋相关定义，其中包含棋盘局面和着法表示。BaseClasses.h是棋局初始化。BaseDef.h是着法生成器，生成目前局面某一方全部正当着法。CoolButton.h是用于绘制主界面右下角四个按钮。Resource.h是资源管理。StepList.h是走法生成存放。Thinkdef.h是历史启发，Alpha-Beta搜索之补充，以提升搜索效率。Thinker.h是着法排序，经过启发信息对节点列表中节点进行排序，以提升搜索效率。ThinkOptionDlg.h是局面评定，为某一特定局面进行评分。MoveList.是搜索部分，使用搜索求出最好着法。4.8 系统测试及试验结果 系统测试属于黑盒类测试，是依据需求文档对软件功效和性能进行测试，它不包含程序代码部分，只是经过不一样硬件和外设条件进行兼容性测试，经过测试用例测试功效是否满足需求文档，经过测试软件对软件进行压力测试等等。 我们这里关键是在软件程序完成时，在windows 7系统环境下测试棋子走法是否是根据中国象棋走子规则是否能够实现人机对弈，是否能够对参数进行设置，是否保留和读取棋谱等等。 测试用例设计，我们能够这么进行设计，如表4.1：表 4.1 测试用例 功效点 前置条件 动作 预期结果 测试结果 文件保留 / 点击保留棋谱文件存放到电脑棋谱文件存放到电脑 文件读取电脑有正确棋谱文件 点击打开选择棋谱文件读取棋谱文件并显示棋局读取棋谱文件并显示棋局 文件读取 / 点击打开选择其它文件无法打开文件无法打开文件 棋子走棋棋盘上有棋子根据正确方法走棋棋子能够移动棋子能够移动 棋子走棋棋盘上有棋子根据不正确方法走棋 棋子不能够移动 棋子不能够移动 悔棋 已经走棋点击悔棋按钮棋局回到上一个局面棋局回到上一个局面 还原悔棋已实现点击还原按钮棋局回到悔棋前局面棋局回到悔棋前局面经过不停调试和修改，我们将中国象棋博弈程序实现出来了。而且经过系统测试，该中国象棋博弈