中国象棋游戏的设计与实现（程序代码+任务书+说明书+外文翻译+演示文稿）

I基于QT的中国象棋游戏界面设计与实现摘要象棋程序的实现可以被分为人工智能和界面程序辅助两大部分。人工智能部分主要体现计算机的下棋思路，既计算机如何进行思考并以最佳走法完成下一步，先由相应的搜索算法进行搜索，并对各种可能的走法进行估值，从中选择胜利面最大的一步；而界面及程序辅助部分主要便于用户通过以前的下棋步骤，更好地调整下棋思路，着法显示使用户能够清楚地知道下棋过程，更准确地把握整个局面。本文首先研究了中国象棋在计算机中的表示问题，接着讨论如何产生着法一系列相关内容。其次研究了博弈树的极小极大搜索技术及在此基础上发展起来的Alpha-Beta剪枝算法，使用GUI文档视图体系结构和qt开发工具，实现了一个具有一定棋力的中国象棋人机对弈程序。关键词：中国象棋；人工智能；博弈树；Alpha-Beta搜索IIDesignandimplementationQT-basedChinesechessgameinterfaceAbstractAchievechessprogramcanbedividedintoartificialintelligenceandinterfaceprogramsassistedtwoparts.AIchessideasembodiedsomeofthemajorcomputer,bothcomputerstothinkandhowbesttotakethelawtocompletethenextstep,firstsearchalgorithmtosearchappropriate,andthevaluationofthevariouspossiblemoves,choosevictorybiggeststepsurface;whilesomemajorinterfaceanduser-friendlyprogramassistedbyformerchessstepstobetteradjustchessideas,amethodtodisplayenablestheusertoknowtheprocessofchess,moreaccuratelygraspthewholesituation.Firstly,thattheproblemstudiedChinesechessinthecomputer,andthendiscusshowtogenerateaseriesoflawsrelatedcontent.SecondlystudiedminimaxgametreesearchtechnologyanddevelopedonthebasisofAlpha-Betapruningalgorithm,usingtheGUIdocumentviewarchitectureandQTdevelopmenttools,implementsaman-machinechessIIIChinesechessplayingstrengthofacertainprocedures.Keywords:ChineseChess；AI；gametree；Alpha-BetaSearch目录摘要.IAbstract.II绪论.1一、系统概述.31.1软件用途.31.2游戏特色.51.3系统开发过程.51.4AI代码阅读提示.5二、系统需求说明.62.1系统总体功能.62.2环境需求.62.3系统功能需求.6三、系统设计.83.1系统设计决策.83.2系统总体设计.93.2.1设计思想.93.2.2系统体系结构.103.2.3系统动态行为.183.3用户界面设计.183.4系统部件.203.5系统出错处理设计.333.6后续可能的更新.33总结.34参考文献.35致谢.36外文文献.37中文翻译.481绪论选题的意义中国象棋在中国拥有悠久的历史，这个游戏需要两个人进行对弈。由于中国象棋用具简单、趣味性强，成为流行极为广泛、老少皆宜的棋艺活动。中国象棋是一种古老的文化，它集文化、科学、艺术、竞技于一体，有利于开发人的智慧，锻炼人的思维，培养人的毅力，增强人的竞争意识。随着电脑技术及互联网的发展，人们下棋没有了地域限制，人们甚至可以跟电脑对战，于是就产生了人是否能够战胜电脑的疑问。从很早开始，人们就开始进行棋类博弈的游戏了，而在人工智能领域，机器博弈始终是一个重要的组成部分。人们对人工智能的窥探是从棋类博弈游戏开始的，人们在博弈游戏中，对战双方通过对游戏规则的掌握、丰富的经验和知识，使游戏的局面有利于自己，这就是人类的思维过程，于是棋类博弈就成了人工智能的实验品。对机器博弈的研究取得的成果不仅仅只用在棋类游戏上，而且也已广泛应用于军事、政治、经济等多个领域，给人类带来了极大的社会效益。国内外研究现状概述机器棋类博弈的研究最早是从国际象棋开始的，1950年美国著名数学家香农积几十年的研究，找到了编制国际象棋程序的原则方法。他提出以数的函数评价局面的优劣。函数的主题是通常一般实力的棋手都能考虑到的一些因素,诸如:棋子实力重叠兵孤立兵、落后兵的弱点以及车的通路和其他子力的活动性等等。香农还提出用简化的估计方法剔除次要的变化。他是计算机国际象棋理论的奠基人。在数学家和计算机专家的共同努力下20世纪50年代末终于试制出世界上第1台公开与棋手对弈的电子计算机。1974年，在瑞典的斯德哥尔摩举行了计算机国际象棋的第1届世界冠军赛，8个国家的13种弈棋程序按积分循环制进行比赛，结果苏联的“卡伊赛”程序获得冠军。最出名的是1997年,卡内基梅隆大学的“深蓝”小组研究开发出“更深的蓝”，挑战人类大师。最后在全世界目光的关注下，“超级深蓝”击败了棋王卡斯帕罗夫。成为人工智能历史上里程碑式的事件，也标志着机器博弈的重大成功。2和国际象棋相比，中国象棋机器博弈起步比较晚，八十年代才开始。1981年张耀腾发表的人造智慧在电脑象棋上的应用，是第一篇研究中国象棋机器博弈的文章。他在他的毕业论文中以残局做实验，提出审局函数为静态子力值，棋子位置值，棋子灵活度值，威胁与保护等四项之和。1982年廖嘉成发表的利用计算机象棋的实验就进了一步，包括开局、中局、残局。台湾大学的许舜钦教授被称为中国计算机象棋之父。在他1991年的两篇论文中，总结并介绍了到当时为止几乎所有的搜索算法，他在文中详细阐述了许多算法的不足之处并且解释了人们对这些算法的误解。这些研究成果为以后计算机象棋的发展做好了铺垫，至今仍在指导着人们进行计算机象棋的研究和实验工作。到了九十年代，中国象棋计算机博弈开始发展起来，人们研究出了各种博弈软件。比较有代表性的有台湾的吴身润的中国象棋、光谱公司出品的将族、晟业编制的象棋水浒战等等。主要研究内容文章主要是研究中国象棋的人机对弈，包括象棋的界面和引擎部分。界面主要是方便人与电脑进行交互的可视化界面。界面包括棋盘区、菜单项和功能按钮区。主要实现棋子的移动、悔棋、记录棋谱、难度选择等选项功能。引擎部分主要包括，棋子棋盘的表示即数据结构，走法的生成，局面优劣的评估即评估函数，搜索算法及其优化和改进。文章设计是采用MFC的框架来实现界面部分,主要用到的MFC类有，CWnd：窗口，它是大多数“看得见的东西”的父类（Windows里几乎所有看得见的东西都是一个窗口，大窗口里有许多小窗口）。CDC设备文本。无论是显示器还是打印机，都是画图给用户看。这图就抽象为CDC。CDC与其他GDI（图形设备接口）一起，完成文字和图形、图像的显示工作。CDialog对话框类，CPen类，CBrush类等等。象棋对弈其实是一种零和博弈。双人对弈，轮流走步；信息完备，双方得到的信息都是一样的；零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或无利的棋。所以内核代码的思路要用到博弈算法。对每一个局面所有可能的着法进行考虑，每一步着法会形成新的局面，这样就形成了一颗博弈树。机器博弈就是要从这颗博弈树中找到最优的分支，即要用到搜索算法对整棵树进行搜索。而中国象棋的博弈树是一个庞大的集合，如果一毫微秒走一步，也要需要10的一百多次方年才能搜索出必赢的第一步，所以博弈树是不可能穷举的。人在思索下棋的时候也不可能对棋局所有的可能计算完全，人往往是凭自己的经验、知识对棋面的好坏进行评估。通过这种思路我们可以给每个局面打一个分数来表示棋局对自己的有利程3度。如果轮到自己落子的时候，一定会选择使局面分数最高的着法，如果轮到对手落子，他一定会选择使你得分最低的局面。这就是我们经常听到的极大极小值搜索，而对局面进行估分的函数就是评估函数。极大极小值搜索就是在轮到自己落子的时候选择分数最大的局面，轮到对手落子的时候选择得分最小的局面，这样就使得搜索可以进行，而由于估分的存在我们就可以在搜索进行到可以接受的时间范围内时结束它。一、系统概述1.1软件用途提供了一个PC端的中国象棋游戏。同时发布了GUI版与CLI版。其中CLI版为象棋AI部分开发过程中用作测试。但已经具有完整的人机对弈功能与相对友好的界面。考虑到有些用户可能相对GUI更偏向命令行操作方式,因此与GUI版本一起发布。4CLI版本只有人机对弈功能,默认黑方(AI)先走。AI原理与GUI版相同,以下文档只对GUI版作出说明。如无特殊说明,提到”软件”时,所指均为GUI版本。软件具有两种模式,双人对弈与人机对弈。若选择双人对弈,因为此版本暂未开发联机对弈功能,只能双人共用一台PC,红方先走,黑方后走,有一方被将死,即无棋可走时,电脑会自动判定胜负。若选择人机对弈,默认用户执红子,AI执黑子。软件可自动判定胜负。软件在ubuntu13。04、windows7、windowsXP平台下测试性能良好。此版本未实现的功能:长将判负。即假定红方只剩5个兵与一个将,且全部过河。黑方只剩一个将与一个车。则黑方基本不可能将死红方。但红方必定可在有限步之后将死黑方。则黑方为自保,最优策略是每一步都用车将红方的军,但无法将其将死。此时游戏会陷入循环。在正式象棋比赛中,任何情况下,长将判负。考虑到主要是面向人机对弈,和棋功能无意义,亦未开发。此AI与软件作者对弈,目前AI保持不败战绩。与其他测试者对弈，也是胜多败少。与作者ipad上的象棋app对弈,互有胜负,但软件AI胜少败多游戏截图：进场画面如下图所示：5图1.1进场界面游戏界面：图1.2游戏界面61.2游戏特色最大可达可接受时间内7层搜索深度,AI具有较高棋力。游戏固定权值与棋盘位置分值相结合的评估函数。基于alpha-beta搜索,走法排序后PVS搜索策略。1.3系统开发过程软件作者为张哲源与刘豪。张哲源负责开发系统的AI部分,即局面表示,走法生成,局面评估,Alpha-Beta搜索,搜索策略优化。刘豪负责系统GUI的设计与实现。部分GUI设计张哲源亦有参与。开发过程:先实现了一个无GUI的搜索策略为alpha-beta剪枝的命令行版本。再实现了一个基本的GUI版本。接下来GUI部分开始开发regret/restart/搜索进度条等工作。AI部分则着重于搜索策略的优化。六月份开始进行优化,一共经历过两次优化,一次走法栈生成时的自动排序使得Alpha-Beta的可接受搜索深度(在10s左右完成搜索)由depth=5提升到depth=6。搜索时引入PVS算法,使得可接受的搜索深度增加为7。文档的GUI部分为刘豪负责写作，AI部分由张哲源负责写作1.4AI代码阅读提示AI部分代码在kernel文件夹中，建议用户先阅读global.h，了解声明了哪些全局变量。则其余代码的算法都不复杂，应当较容易阅读。7二、系统需求说明2.1系统总体功能可以实现双人对弈与人机博弈.AI会检查走子的有效性.AI会自动判定胜负具有悔棋功能.但软件作者一致认为君子有所为有所不为,落子无悔才是值得提倡的.因此对用户悔棋功能设置了一些障碍.用户需连续点击弹出的对话框10次之后,同时接受AI的冷嘲热讽.才允许悔棋.若用户终于决定放弃悔棋.关闭对话框即可.若选择人机对弈,用户被AI吃子后会提示被吃了哪个子.可以restart,即棋局进行到中局或是一局终了,用户想要重新玩一局,可点击restart.若用户被将军,则必须应将,若不应将,则会弹出对话框提醒用户.人机对战模式中,AI会在被将死之前就认输,即当AI检测到它几步之后必然会被将死,就会提前认输.可接受的时间内搜索深度可达7层alpha-beta搜索.但是一开始就采用7步搜索无必要.因而设定前5回合(十步)进行5层搜索,5回合之后到25回合(50步)采用6步搜索.若之后用户仍未被将死.将采用7步搜索.人机对弈模式中，界面右下方会以进度条显示AI已搜索结点的比例。2.2环境需求AI部分与GUI部分由两人分工完成.(一)开发环境AI部分:TOSHIBAC600D-01L笔记本电脑.AMDAthlon(tm)IIP320Dual-CoreProcessor,Ubuntu13.04操作系统,使用vim编写,测试程序使用g+4.7.4编译.8AI部分测试功能正确后,交由高楠进行GUI的实现.GUI开发环境:AcerAspire4736ZG笔记本电脑.Pentium（R）Dual-CoreCPUT4500，Windows7企业版32位操作系统，使用QtCreator4.8编写(二)运行环境在ubuntu13.04及windows7、winXP操作系统下可流畅运行.作者测试游戏所用CPU较为低端,游戏运行仍较为流畅.用户所用CPU性能不错的话,可以考虑一开始就将搜索深度设为6或者7.2.3系统功能需求可选的对战模式_双人对弈或人机对弈启动游戏后,点击相应button,即可选择相应对战模式。双人对弈：若选择双人对弈功能,则可双方交替走子.系统会自动检测走子的有效性,不合规则的走子无法走出.若一方胜利,则系统会弹出对话框告知“black_lose”或是”redlose”.人机对弈:选择人机对弈模式之后,默认用户执红子先走.同样会检测走子有效性,同时还会检测红黑双方是否被将军,若被将军,则必须应将,不应将的走法时无效的.即红黑双方的将在游戏过程中并不会真正的被吃掉,只要一方的将被将死,则系统会判定胜负.AI会在被将死之前几步就检测出自己会被将死而无可补救,此时AI会认输.退出功能:点击exit按钮,可以退出程序.restart功能:点击restart按钮,可重新开始棋局.悔棋功能:9点击regret按钮,弹出对话框劝用户不要悔棋,用户执意悔棋,则撤销之前两步的走法(红方与黑方的).注意：悔棋是撤销两步走法，因此若是在双人对弈模式，A、B两人对弈，A走出之后要悔棋，必需在B走完之后才能成功。将军提醒:用户被将军而不应将时,系统会作出提醒.进度条:选择人机对战模式时,机器思考时,界面下方会有进度体啊显示机器搜索的程度.三、系统设计3.1系统设计决策AI10系统设计时,将AI与GUI分开设计.AI根据当前局面进行搜索/决策,产生最优走法,将走法传递给GUI,GUI刷新界面.GUI部分在用户界面设计部分会有详细说明,此处介绍AI的设计.用户可以通过运行CLI版本的游戏了解AI的整体架构.AI设计策略:一切以程序的运行速度为优先考量.为了说明采用这种编码方式的理由,可以先看一下AI设计完成之后,作者做的一组统计:开局第一步,共有44种走法,作者统计了不同搜索策略走第一步棋时搜索到的叶结点数目,这里的叶结点数是指真正会去做局面评估的叶结点.被剪枝的叶结点不在其中.未经走法排序的Alpha-Beta搜索各搜索深度实际搜索叶节点数如下表表3.1Alpha-Beta节点数搜索深度1234567结点数441131277713080466844627速度无法接受速度无法接受经过走法排序后的Alpha-Beta搜索各搜索深度实际搜索叶节点数如下表：表3.2实际搜索叶节点数搜索深度1234567结点数4484166013653136914970891速度无法接受经过走法排序后采用PVS算法的搜索策略各搜索深度实际搜索叶节点数如下表：表3.3pvs11搜索深度1234567结点数44841660120901140808894126482373将上表中走法排序后再reverse一次后的PVS搜索策略各搜索深度实际搜索叶节点数如下表：表3.4reverse一次后的PVS搜索策略各搜索深度实际搜索叶节点数搜索深度1234567结点数48206372295151964014700791速度无法接受速度无法接受注:PVS算法为先用小窗口的alpha-beta试探,若试探失败,则重新进行搜索.所以排序排的不好,可能访问结点数大于实际结点数,如第三张表中搜索深度为1时,实际有44中走法,却访问了48个结点.上表中各种搜索策略文档后面会详述,但是用户可以很直观的感受到:(1)不同搜索策略搜索效率差别很大,甚至可以是数量级上的差异.(2)搜索量随搜索深度指数上升.因而AI部分属于高计算量的程序,微小的速度差异会在大量的计算过程中被放大.AI的实质是数学上的决策过程.因而在AI部分编码过程中,没有采用面向对象的设计风格。因为AI思考的过程本质上是计算过程而非事件直接消息传递的模型。同时,具体实现上,大量的采用辅助数组等冗余数据结构，以空间换时间。函数的参数通过全局变量传递/引用传递而非值传递传递.分支结构尽量采用switch-case结构而非if-else结构.12GUIGUI部分的设计包括一个进场画面，选择对战模式，以及实际游戏的棋盘。进场画面选择了一个战争的场面，因为象棋是模拟战争的游戏。棋盘没有采用一般的象棋的木质拟物设计，而是自己手绘设计了棋盘。棋子也经过重新设计。红方采用瘦金体，而黑方则采用颜体楷书。进场画面为游戏三国策壁纸，棋盘采用ipad上的app“Paper”绘制。3.2系统总体设计3.2.1设计思想AI与GUI部分分别完成,通过接口实现通信.AI部分AI部分采用bottom-up的方法设计,包括局面表示/走法生成/局面评估/将军检测/搜索算法.AI部分代码在kernel文件夹中.kernel文件夹中代码的组织与AI的结构同构.表征局面的数据结构以及其他一些全局变量在global.h中声明,在define_global.cpp中定义.move文件夹中为走法生成的函数.check文件夹中为将军检测函数.eval文件夹中为局面评估函数.search文件夹中为搜索函数.每个文件夹中都有test.cpp及makefile,为相应函数的测试代码.用户可到相应文件夹中运行make,然后执行可执行文件查看测试结果(makefile在linux环境下写成)AI部分概述:以长度为256的一维数组表示棋盘,其中90个数字表征棋盘,其余部分为冗余数据,置零.棋盘的表示还有相关冗余数据结构.棋子以数字编码.走法生成函数生成走法,搜索算法调用评估函数,给出局面估值及最佳走法.搜索基于alpha-beta剪枝算法.剪枝效率与遍历走法栈的顺序关系很大,因此生成走法时按照一定规则对走法栈排序.还采用了PVS算法对alpha-beta算法进行优化.GUI部分/*/3.2.2系统体系结构分为AI部分，AI部分没有使用面向对象的方法，只以文字说明。GUI部分有类图等描述13(一)局面表示建议用户阅读global.h头文件.其他文件中的代码大抵知道函数功能即可.表征局面/走法等的数据结构均在global.h中声明,在define_global.cpp中定义.其中shortside表示当前走棋一方,side=0,表示红方,side=1,表示黑方.局面的表征主要通过两个数组，棋盘数组board和棋子数组piece，这两个数组是等价的，在AI思考过程中保持同步。之所以设置两个数组，是因为不同情况下使用不同数组更加方便或者运算速度更高。采用shortboard256表征棋盘,非棋盘位置0.棋盘上无棋子的位置也为0.采用256长度的数组,可以方便的像使用二位数组那样使用一维数组,如想要表征第三行第四列,只需使用board0x34即可.对每一个棋子,有一个(对兵来说,有两个,红黑有别)合法位置数组,也是长256的一维数组.若棋盘上的一个位置是该棋子的合法位置,则为1,否则则为0.棋子在board数组中位置为board数组元素下标。棋盘为9*10，因此是嵌在board数组中。如图所示3.1：图3.1棋子14对于棋子，用不同数字表示不同棋子，一个编码数字与一枚棋子一一对应，编码如下表：表3.5棋子编码红方帅仕相马车炮兵表示数1617,1819,2021,2223,2425,2627,28,29,30,31黑方将士象马车炮卒表示数3233,3435,3637,3839,4041,4243,44,45,46,47如此，譬如红方将一开始是在上图中c7位置处，则有board0xc7=16。这样编码的好处：令side_tag=(side=0?16:32)则红方编码&16=16,红方编码&32=0,黑方编码&16=0,黑方编码&32=32,则可非常方便快速的判定棋子颜色.生成走法栈时,经常需要遍历所有棋子,遍历棋盘数组上10*9的棋盘是非常不经济的.因此在棋盘数组之外引入一个等价的冗余数组棋子数组shortpiece48,其中下标015无意义.下标1631表征棋子编码为1631的棋子(即红方棋子)在棋盘上的位置.3247表征棋子编码为3247(即黑方)棋子在棋盘上的位置.如此，譬如红方将一开始是在上图中c7位置处，则有piece16=0xc7;piece数组初始化如下图:15图3.2piece数组board数组初始化如下图：图3.3bord数组初始化(二)走法生成中国象棋中，除了车和炮之外，其他棋子的走法都有棋盘上的固定增量(行增量，列增量)，因此比较容易处理。如红方过河的兵，有三个增量(-0x10,+0x01,-0x01)，分别对应向前、向右和向左。则对每一个棋子，设置增量数组，除兵以外的棋子红方黑方增量数组可以公用，除此之外，还要设置合法性数组，如将的合法区域只能在九宫格内。对于象和马，还要确定马腿、香眼的增量数组。先介绍相关数据定义，在介绍相关函数。首先定义了一个mov的class,表征一个走法，在global.h中。如下图所示：16图3.4定义Shortfrom为走法起始的棋盘位置,即棋子在board的下标.to为走法目的地址对应棋盘位置.capture为该走法所吃子的棋子编码,若走法未吃子,则capture等于0.重载了大于号操作符,在生成vectorMove_array时会调用sort函数排序.至于为何排序,以何种依据排序,排序的目的与好处,将会在介绍评估函数与搜索结点策略时再讲到.定义了走法生成时每个棋子的辅助数组,因为数组结构相似,只以马和兵为例进行说明.其他棋子的辅助数组可阅读global.h。马的辅助数组定义如下图所示：图3.5马constshortHorse_direction8:倘使已知一个马在board数组中的位置,则它一共有八个可走的方向,8个方向存在Horse_directoin数组中,举个例子,马要向上走两格后向右走一格(走一个日字形,方向为由红方向黑方),在棋子数组上,向上走两格为-0x20,向右走一17格为+01,则新的位置可如下计算:new_pos=now_pos-0x1f.Horse_direction中存的是马走到的新位置相对于旧位置的偏移量.Horse_leg:理解了Horse_direction之后,Horse_leg数组的定义也容易理解,即马腿位置相对于当前位置的偏移量.Horse_leg的下标与Horse_direction的下标一一对应,即Horse_legi是Horse_directioni这一走法对应的马腿位置.Horse_legal数组为马在棋盘上的合法位置,马可以踏遍整个棋盘,因而整个棋盘都是合法位置.兵的辅助数组如下图所示:图3.6兵数组的意义与马的数组名意义相同,一个为direction数组,一个为legal数组.不同的是,兵的红黑双方数组不同,红方只能向黑方走,黑方只能向红方走,因而定义了一个二维数组.接下来讲述相关函数的作用：Move.cpp中定义了两个函数:voidSave_move(shortfrom,shortto,vector&Move_array)函数.此函数接受两个整数表示的位置值,生成一个mov类型的变量,检测这个走法是否会造成本方(通过side判断)被将军.若不会被将军,则将这个mov类型的变量push进Move_array中.18VoidGen_All_Move(vector&Move_array)函数,接受一个vector&的变量,生成当前局面当前方的所有合法且不会被将军的走法,所有走法保存进Move_array中,在按照classmov定义中重载的大于号操作符对Move_array进行排序.move文件夹中其他代码文件,为特定棋子的走法生成函数,如chariot_move.cpp,就是生成当前局面当前方的车的所有可能走法,并push进Move_array中去.Gen_All_Move函数就是通过调用这些函数来完成走法生成功能.(三)将军检测将军检测功能的相关函数在check文件夹中.checkmate.cpp调用check文件夹中的其他函数,检测当前方(检查side)/当前局面(检查地方的攻击性棋子)是否本方被将军.若是返回true,否则返回false.可以造成将军的棋子有对方的车/对方的马/对方的兵/对方的炮,另外,有不能对将的规定.因而对general/chariot/cannon/horse/soldier这五类棋子各写了一个检测函数,它们都被checkmate.cpp中的boolcheckmate()调用.(四)局面评估局面评估函数是一个象棋AI的核心,直接决定AI的智能程度,如曾经战胜卡斯帕罗夫的IBM的”深蓝”计算机,它的国际象棋博弈程序的评估函数有4000多个参数.毫无疑问,评估函数越复杂,AI就越智能,但是在搜索过程中,对搜索到的叶结点会做局面评估,局面评估函数越复杂,搜索速度就越慢,搜索层数就越少.因此必须在搜索速度与评估函数智能程度之间作出权衡.本程序采用棋子固定权值结合棋子位置权值的评估策略.棋子固定权值即依照经验为不同的棋子设定一个固定的权值,在global.h中定义const数组piece_weight存储,数组长度48,前16位无意义,之后数组下标与跟下标编码相同的棋子一一对应.piece_weight定义如下:19图3.7pieceweight定义棋子将仕象马车炮兵权值10000200200400900450100在classmov的定义中,重载的大于号操作符就是判断两个走法的被吃子的权值比较.棋子位置分值为认定不同棋子在棋盘不同位置的价值是不一样的,一个显而易见的例子是,兵到了对方的九宫格内之后,价值会大大增加.对每种棋子,设置长256的pos_weight数组表征其位置分值.其中,将/仕/象/红黑双方数组可共用,兵/车/马/炮需要为红黑双方各设置一个位置分值数组.以将/马为例,其他数组用户可自行阅读global.h将的位置分值如下图：图3.8将红马的位置分值:20图3.9红马可以看出,靠近黑方九宫格的位置,权值较高黑马的位置分值:图3.9黑马通过以上辅助数组,我们现在可以评估一个局面,遍历piece数组中的棋子,对每个棋子,其分值为固定分值加上位置分值,进一步将红方棋子分值求和,黑方棋子分值求和,若side=0,则返回(red_value-black_value),若side=1,则返回(black_value-red_value).21(五)Alpha-Beta搜索采用深度优先搜索,配合Alpha-Beta剪枝策略.相关代码在search文件夹中,包括Alpha-Beta.cpp/PVS.cpp/try_move.cppAlpha-Beta.cpp中定义了intsearch(shortdepth,intalpha,intbeta)根据传入参数搜索深度进行搜索,给出当前局面搜索后的评分,但是并不产生最优走法.Alpha-Beta搜索的剪枝效率对搜索的顺序十分敏感,若走法栈中好的走法排在前面,则剪枝效率高,因此在走法生成部分对走法按照被吃子的固定权值进行了排序.明显提高了剪枝效率.try_move.cpp中定义了voidMake_move(movmv)与Un_move(movmv)函数,分别是根据当前局面与传入的mov类型的走法数据,执行一步走法,更改board数组与piece数组.voidUn_make(movmv)则是撤销一步走法.最优走法的生成在PVS.cpp中定义的intPVS(shortdepth,intalpha,intbeta)函数中产生.其基本思想是这样的:走法经过排序后,可以假设最优走法出现在走法栈的起始位置处,则在对Move_array进行遍历/搜索时,可以先假定Move_array0就是最优走法.则对其他的走法,先进行一个窗口宽度为0的alpha-beta搜索(search(depth-1,-alpha-1,-alpha),根据返回的结果判定假设是否成立,若假设不成立,则再进行一次正常的alpha-beta搜索.PVS算法根据当前局面,返回对当前方(根据side判断)的局面评分,并更改一个声明在global.h中的全局变量movbest_move.best_move被GUI程序调用,即机器要作出的走法.(六)GUI部分类图描述如下图：22图3.10类图主要的类有Choose，info和MainWindow三个，分别继承自QDialog，QDialog和QMainwindow。其中MainWindow是最为主要的一个类，具体介绍见后文的“主要的类”。3.2.3系统动态行为顺序图如下图所示（以人机对弈为例）23图3.11顺序图对应的状态图为：模式选择窗口主界面选择模式窗口关闭清空棋局等待用户走棋判断走棋是否合法以及是否分出胜负允许悔棋电脑行棋显示result窗口无人输棋分出胜负用户走棋不合法分出胜负点击悔棋点击restart点击Exit无人输棋点击restart点击Exit图3.12状态图3.3用户界面设计用户界面如下图所示：24图3.13主界面此为程序打开的第一个界面，两个按钮来选择对战模式。选择模式后进入下图所示的主界面:图3.14界面主程序界面主要包括这样几部分：棋盘，棋盘背景，棋子，三个功能按钮和一个提示消息。另外在走棋过程中，为了方便观察AI行棋，给出了用于定位走法的边框。如果出现吃子，将在走棋提示的文字下方显示被吃掉的棋子。若用户的走法为非法，则不予执行，同时，若对方将军，则必须应将。3.4系统部件AI部分AI部分没有采用面向对象的方法,走法栈生成/局面评价/搜索剪枝均通过相关函数的定义来实现.通过改变全局变量board数组与全局变量piece数组来刷新棋盘.以下为相关函数的详述:25kernel/board.cpp中:定义了两个函数,stringget_piece(short&piece_num)/voiddisplay(),用于CLI版本的游戏中打印棋盘,只是相当于打印board数组而已,无技术含量,不讲.kernel/define_global.cpp:global.cpp中声明的全局变量均在此处定义.走法生成分为3部分,每个棋子的走法生成函数/走法保存函数/走法栈生成函数.对应棋盘上当前走棋方的所有棋子,调用其棋子走法生成函数,生成走法并保存人走法栈.下面介绍马的走法生成函数Horse_move()/Save_move/Gen_All_Move()这三个函数,其他棋子的走法生成函数与马的走法生成函数相类似.Horse_move():函数参数:马的当前位置pos,表征当前走棋方的Side_tag,/*Side_tag=(side=0?16:32)*/走法栈向量的引用vector&Move_array输出:无返回值输出,将走法(mov类型变量push进Move_array中)伪代码:对马的8个可走方向:leg=pos+Horse_legi;next=pos+Horse_directioni;如果next是合法位置:如果没有马腿:26如果next位置上没有本方的棋子保存走法;/#Save_move()函数参数:整数类型的走法起始位置from;整数类型的走法终点位置to;走法栈引用vector函数输出:无返回值输出;改变Move_array;伪代码:capture=boardto/确定被吃棋子的编码;movmv=from,to,capture;/定义一个mv变量,对应传入的走法Make_move(mv)/*走一步这个走法,更新board数组与piece数组,同时side=1-side(因为一方走棋后轮到另一方走棋,side也会变*/side=1-side/将side改回本方check=checkmate()/检查这一步走出后是否会将军side=1-side/再次更改sideUnmove(mv)/撤销走法,更新board数组,piece数组,更改side如果没有被将军:27Move_array.push_back(mv);#Gen_all_move()函数参数:走法栈向量引用vector全局变量side/board/piece/函数输出:无返回值输出.更新Move_array;伪代码:对本方的每一个棋子:如果该棋子还在棋盘上没有被吃掉:生成该棋子走法;对生成的走法栈排序;将军检测将军检测部分的代码在kernel/check文件夹中。包括对将、兵、车、马、炮的检查函数。最后在checkmate.cpp中定义的boolcheckmate()函数调用这些检测函数。下面给出checkmate()和马的检测函数check_horse()的伪代码。将、兵、车、炮的算法用户可自行阅读源代码。checkmate()函数输入：无参数传入。函数输出：若当前方被将军，则返回true，否则返回false.28伪代码代码本身太简单，直接贴代码吧。check_horse()函数输入：无，检查side以及board数组，piece数组。函数输出：若当前方被对方马将军，则返回true，否则返回false.伪代码：my_general=(side=0?piece16:piece32);/确定己方将的位置。enemy_horse2=piece5+(side=0?32:16),piece6+(side=0?32:16);/确定敌方马的位置，piece的下标与棋子的编码一一对应。for(i=0;ialpha，则更新alpha，搜索过程中搜索到了大于beta的值，则剪枝。alpha-beta搜索的伪代码如下：函数形式：intsearch(shortdepth,intalpha,intbeta);输入：搜索深度depth，alpha,beta;输出:最佳走法对应的走法估值，并不更新全局变量movbest_move;伪代码：if(depth=0)return局面评估值定义走法栈vectorMove_array;定义评估值intvalue;生成所有走法;若走法栈为空返回负无穷;/*说明已经被将死*/对每一种走法，遍历：执行走法;value=-1*search(depth-1,-beta,-alpha);撤销走法;if(value=beta)returnbeta;if(valuealpha)alpha=value;returnalpha;32alpha-beta搜索的效率高低取决于剪枝的效率。剪枝的条件是value=beta，估值越高，越有可能引起剪枝，因此，在走法生成时，按照被吃子的固定权值对走法排序。大大提高了剪枝效率，使得可接受的搜索深度由5提高到6。search调用时，alpha取负无穷，beta取正无穷。PVS搜索算法：在走法生成时，走法已经经过排序，以提高剪枝的效率。我们可以如下假设，经过排序后，第一个走法就刚好是最好的走法。假定最初的(alp