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

基于QT的中国象棋算法设计与实现摘要中国象棋发展至今已有数千年的历史了，它是中华民族智慧的结晶。在我国，中国象棋的普及程度是其它棋类无法比拟的，大至国际、国内比赛，小至社区街道。本文章在研究分析对局树的基础上,先后运用极大极小查找和-修剪对查找下一步的算法进行了改进,并对中国象棋的对弈过程进行了有益的探讨。最后在此基础上,运用面向对象的技术,综合结构化程序设计方法,将所有的操作逻辑封装于类,实现基于对局树算法的中国象棋游戏系统。系统使用QT开发工具，实现了一个具有一定棋力的中国象棋人机对弈和双人对战程序。关键词：中国象棋人工智能博弈树Alpha-Beta搜索iWiththeimplementationofChinesechessalgorithmdesignbasedonQTAbstractChinesechessdevelopmenthasbeenseveralthousandyearsofhistory,anditisthewisdomoftheChinesenation.InChina,thepopularityofChinesechessboardisunmatchedbyotherlargetointernationalanddomesticcompetitions,smallcommunitystreets。Thisarticleisbasedonresearchandanalysisonthegametree,hastofindanduseMinimax-pruningalgorithmforfindingthenextimprovement,theprocessofChinesechessandchessforausefuldiscussion.Finally,onthisbasis,theuseofobject-orientedtechnology,integratedstructuredprogrammingmethod,alloftheoperatinglogicencapsulatedinaclass-basedsystemtoachieveChinesechessgamegametreealgorithm.ThesystemusesQTdevelopmenttoolstoachievehuman-computerchessandChinesechessprogramthathasadoublebattleofchess.Keywords:Chinesechess;artificialintelligence;gametree;Alpha-Betasearch目录摘要.iAbstract.ii1绪论.11.1中国象棋游戏设计背景和研究意义.11.2国内外象棋软件发展概况.11.3中国象棋游戏设计研究方法.11.4本文的主要工作.22系统的分析和设计.32.1棋盘和棋子的表示.32.2着法生成.53博弈程序的实现.73.1搜索算法.73.2估值函数（EvaluationFunction）.113.2.1估值函数简介.113.2.2估值函数的优化.123.2.3着法排序.133.3局面评估.164走棋程序的实现.204.1悔棋和还原功能的实现.204.2着法名称显示功能的实现.224.3主要函数.264.4将军检测.305系统实现.315.1系统的整体规划.315.2对弈功能的实现.32总结.38参考文献.39致谢.40外文原文.41中文翻译.4801绪论1.1中国象棋游戏设计背景和研究意义中国象棋游戏流传至今已经有数千年的历史了，是一种古老的文化，它集文化、科学、艺术、竞技于一体，有利于开发人的智慧，锻炼人的思维，培养人的毅力，增强人的竞争意识。自从计算机发明，向各个领域发展，到成为我们现在每天工作和生活必不可少的一部分的这个过程中，电子游戏也逐步渗入我们每个人的娱乐活动中。在计算机已经普及的今天，对于可以用计算机进行程序编辑的人来说，开发属于自己的游戏，已经不再是梦想，中国象棋历史悠久不仅源远流长，而且基础广泛，作为一项智力运动更成为我们游戏开发的首选对象。中国象棋是一项智力游戏，以往都是人和人下棋，现在有了计算机我们可以和计算机竞技，人可以与计算机进行对弈。控制计算机的是人类，而人工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。因此，对游戏开发过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向。1.2国内外象棋软件发展概况最早的象棋软件是一副可以外出携带的电子棋盘，后来升级到电视游戏机。开始出现的一些容量很小的象棋软件如：DOS界面将族、WIN31程序的中国象棋等等，与其说人类下不过电脑，倒不如说是没有耐性等待电脑程序慢吞吞的搜索算法，有时甚至怀疑软件是否在搜索中死掉了。后来，网络上先后出现了真正的WINDOWS窗口界面的象棋专业高级软件棋隐、象棋世家、象棋参谋、象棋奇兵等。总而言之，各类象棋软件既有自身的优点，也存在共通性的缺陷，如：中局审势不够智能化，走不出弃子取势的人性化佳构，残局时智力明显低于人脑，难以走出残局例胜的必然着法等。放眼未来，象棋软件已经走完了一波持续上涨的行情，有可能出现逐步降温的滑坡趋势。1.3中国象棋游戏设计研究方法本系统主要用VisualC+进行开发，里面的MFC类库，使游戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生成，从而完善整个游戏的功能。该象棋人机博弈系统实现的功能主要包括：1、选手选择（人或电脑）；2、人机对弈（人与电脑竞技）；3、悔棋、还原；4、着法名称显示（象棋走棋规范名称）。11.4本文的主要工作第一部分主要介绍了中国象棋游戏开发的背景及意义、国内外象棋软件的发展概况和象棋游戏的设计研究方法；第二部分介绍了棋局表示方法和着法生成；第三部分介绍了走棋和博弈程序的实现；第四部分介绍了系统的实现。22系统的分析和设计2.1棋盘和棋子的表示棋盘表示就是使用一种数据结构来描述棋盘上的信息，以便程序知道博弈的状态。棋盘的数据表示直接影响到程序的时间及空间复杂度。为了追求更高效率，研究人员针对中国象棋提出了多种不同的表示方法。中国象棋的棋盘表示中最典型的是用一个109的二维字节(byte)数组，数组中每个元素代表棋盘上的一个交点，其值表明这个交点上放置的是一个什么棋子或是没有棋子从棋子的角度考虑，如果把棋盘看成是一个平面坐标系，可以知道每一个棋子的位置信息:小于10的横坐标和小于11的纵坐标;又在棋盘上最多32个棋子，故可以用一个32个字节的一维数组表示所有32个棋子的位置，其中每个字节的高4位表示该棋子的横坐标，低4位表示棋子的纵坐标。而己被吃掉的棋子用坐标范围以外的数表示。这样棋盘信息就被装入这32个字节中。当然也可以把棋盘看作一维的，每个元素保存直接的位置信息。两种棋盘表示方法：一是做一个棋盘数组；二是做一个棋子数组。棋盘数组中由棋子的位置获得棋子的类型可以在常数时间内完成，但由棋子的类型获得棋子的位置需要遍历；在棋子数组中由棋子的类型获得棋子的位置可以在常数时间内完成，但由棋子的位置获得棋子的类型操作繁琐。如果一个程序同时使用这两个数组，那么获得棋子的类型和棋子的位置都可以在常数时间内完成。这就是“棋盘棋子联系数组”，它的技术要点是:(1)同时用棋盘数组和棋子数组表示一个局面，棋盘数组和棋子数组之间可以互相转换。(2)随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。在棋盘上删除一个棋子，需要做两个操作(分别修改棋盘数组和棋子数组)。同样，添加一个棋子时也需要两个操作。“棋盘棋子联系数组“最大的优势是：对于着法产生过程，可以逐一查找棋子数组，如果该子没有被吃掉，就产生该子的所有合理着法，由于需要查找的棋子数组的数量(每方只有16个棋子能走)比棋盘格子的数量(90个格子)少得多，因此联系数组的速度要比单纯的棋盘数组快很多。同时“棋盘棋子联系数组”是很多改进的棋盘的基础。对于中国象棋棋盘局面的表示可采用传统而简单的“棋盘数组”。即用一个9*10的数组来存储棋盘上的信息，数组的每个元素存储棋盘上是否有棋子。这种表示方法简单易行。按此方法棋盘的初始情形如下所示：BYTECChessBoard910=R,0,0,P,0,0,p,0,0,r,H,0,C,0,0,0,0,c,0,h,E,0,0,P,0,0,p,0,0,e,A,0,0,0,0,0,0,0,0,a,K,0,0,P,0,0,p,0,0,k,A,0,0,0,0,0,0,0,0,a,E,0,0,P,0,0,p,0,0,e,3H,0,C,0,0,0,0,c,0,h,R,0,0,P,0,0,p,0,0,r;给所有棋子定义一个值：#defineR_BEGINR_KING#defineR_ENDR_PAWN#defineB_BEGINB_KING#defineB_ENDB_PAWN#defineNOCHESS0/没有棋子黑方：#defineB_KING1/黑帅#defineB_CAR2/黑车#defineB_HORSE3/黑马#defineB_CANON4/黑炮#defineB_BISHOP5/黑士#defineB_ELEPHANT6/黑象#defineB_PAWN7/黑卒红方：#defineR_KING8/红将#defineR_CAR9/红车#defineR_HORSE10/红马#defineR_CANON11/红炮#defineR_BISHOP12/红士#defineR_ELEPHANT13/红相#defineR_PAWN14/红兵判断颜色：#defineIsBlack(x)(x=B_BEGIN&x=R_BEGIN&x#include#include#include#include#include#include#include#include#include#include4#include#includekernel/global.h#includeinformation.husingnamespacestd;classMainWindow:publicQMainWindowQ_OBJECTpublic:MainWindow(QWidget*parent=0);voidrefresh(short*);voidcompmove();voidend();intPVS(short,int,int);publicslots:voidslotregret();voidslotrestart();voidselectregret();private:QLabel*labelMousePos;QLabel*red;QLabel*black1;QLabel*black2;QLabel*chess32;QLabel*eat;info*anticheck;QPushButton*exit;QPushButton*restart;QPushButton*regret;QProgressBar*progress;QPixmappic34;shortvoidmousePressEvent(QMouseEvent*e);voidpaintEvent(QPaintEvent*);/*/*/#endif/MAINWINDOW_H有了对棋盘局面和着法的表示之后，程序才能够完成以下操作：生成所有合法着法；执行着法、撤销着法；针对某一局面进行评估。因而，棋局表示好比是整个程序（计算机下棋引擎部分）的地基，之后所有的操作都将建立在其基础上。2.2着法生成在着法生成器中，采用的基本思想就是遍历整个棋盘（一个接一个地查看棋盘上的每个位置点），当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型而相应地找出其所有合法着法并存入着法队列。这里谈到的“合法着法”包括以下几点：1、各棋子按其行子规则行子。诸如马跳“日”字、象走“田”字、士在九宫内斜行等等（这里需要特别注意的是卒（兵）的行子规则会随其所在位置的不同而发生变化过河后可以左右平移）。2、行子不能越出棋盘的界限。当然所有棋子都不能走到棋盘的外面，同时某些特定的棋子还有自己的行棋界限，如将、士不能出九宫，象不能过河。53、行子的半路上不能有其它子阻拦（除了炮需要隔一个子才能打子之外）以及行子的目的点不能有本方的棋子（当然不能自己吃自己了）。4、将帅不能碰面（本程序中只在生成计算机的着法时认为将帅碰面是非法的，而对用户所走的导致将帅碰面的着法并不认为其非法，而只是产生败局罢了）。产生了着法后要将其存入着法队列以供搜索之用，由于搜索会搜索多层（即考虑双方你来我往好几步，这样才有利于对局面进行评估以尽可能避免“目光短浅”），所以在把着法存入着法队列的时候还要同时存储该着法所属的搜索层数。因此可以将着法队列定义为二维数组m_MoveList870，其中第一个数组下标为层数，第二个数组下标为每一层的全部着法数。关于搜索层数，设定为4，实际使用的是1到3（在界面中将其限定为13）。搜索层数的增加会显著提高电脑的下棋水平（当然计算机的棋力在很大程度上也依赖于局面评估）。在配置为1.5G，512M内存的计算机上最多只能搜索3层，再多将导致搜索时间达到令人无法容忍的地步（这里还需要特别说明的是，搜索的速度也和着法生成的效率以及局面评估的复杂度有关，因为每分析一个结点都要执行这两种操作）。对于每一层的着法数，也就是当前下棋方针对当前局面的所有可选的合法着法，据有关数据统计在象棋实战中一般最多情况下也就五六十种。定义第二个数组下标为70，应当可以保证十分的安全。63博弈程序的实现3.1搜索算法中国象棋博弈树非常庞大，完全建立博弈树是不可能的，唯一的解决方法就是让博弈树扩展到计算机运算可以接受的深度，然后对没有分出胜负的叶子节点给出一个尽量准确的打分，表示此局面下取得胜利的可能性，这个打分是由评估函数计算给出的，将搜索树展开是着法生成的功能，而搜索引擎则是尽可能缩小树的规模，避免一切冗余的计算，这也是计算机博弈中搜索引擎研究的重点。根据搜索策略，目前应用于计算机博弈的搜索算法一般可分为三类：(l)穷尽搜索(ExhaustiveSearch)，这种搜索是没有抛弃任何可能成为最佳路径的搜索，不存在风险，得到的最佳走法肯定是在现有评估函数下应该得到的，例如极大极小值搜索、-剪枝搜索及其变种等。(2)选择性搜索(SelectiveSearch)，即裁剪搜索，这种搜索略去对一些着法的搜索，冒着有可能漏掉最佳走法的风险，而换来局部更深的搜索深度。中国象棋中最常用裁剪算法是空着裁剪(NullMove)等。(3)启发式搜索(Heuristicsearch)利用象棋领域的知识(启发信息)设计搜索算法，着重对走法排序，以简化和加快搜索过程。中国象棋中的启发算法有历史启发、杀手启发、置换表等。搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏，驱动着整个程序。搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着计算机的下棋水平。因为，计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多）。关于棋类对弈程序中的搜索算法，已有成熟的Alpha-Beta搜索算法以及其它一些辅助增强算法（还有众多基于Alpha-Beta算法的派生、变种算法）。我们在程序中直接借鉴了Alpha-Beta搜索算法并辅以历史启发。本节先介绍Alpha-Beta搜索算法：在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是吃掉对方的将或帅，或者避免自己的将或帅被吃。图3-1博弈图7又此，可以用一棵“博弈树”来表示下棋的过程树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的结点），如此不断进行下去直到再无可选择的走法，即到达叶子结点（棋局结束）。中国象棋的博弈树的模型大概，可以把其中连接结点的线段看作是着法，不同的着法自然产生不同的局面。该树包含三种类型的结点：1、奇数层的中间结点（以及根结点），表示轮到红方走棋；2、偶数层的中间结点，表示轮到黑方走棋；3、叶子结点，表示棋局结束。现在让计算机来下中国象棋，它应当选择一步对它最有利的着法（最终导致它取胜的着法）。获得最佳着法的方法就是“试走”每一种可能的着法，比较它们所产生的不同后果，然后从中选出能够产生对自己最有利的局面的着法。结合上面所讲的博弈树，若给每个结点都打一个分值来评价其对应的局面（这一任务由后面所讲的局面评估来完成），那么可以通过比较该分值的大小来判断局面的优劣。假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。如此，当轮到甲走棋时他会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到博弈树上，即如果假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。那么由于甲方希望棋盘上的分值尽可能大，则在偶数层上会挑选分值最大的结点偶数层的结点是甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。同样道理，由于乙方希望棋盘上的分值尽可能小，那么在奇数层上会选择分值最小的结点。这是“最小-最大”（Minimax）的基本思想。这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的着法。然而不幸的是，博弈树相当庞大（它会成指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作其时间复杂度为O(bn)。其中b是分枝因子，即针对各种局面的合法着法的数目的平均值，n是搜索的深度。对于中国象棋而言，在中盘时平均着法数目大约是40种左右，那么搜索4层需要检查250万条路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线！Alpha-Beta搜索能在不影响搜索精度的前提下大幅减少工作量。因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向（假定下棋双方对棋局有着同样的认知，即你认为对你很糟糕的局面，在你的对手看来则是对他很有利的局面），那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时（确切地说这里的“很糟糕”是与之前分析的情况相比较而言的），你应当立刻停止对其剩余子结点的分析不要对它再抱任何幻想了，如果你选择了它，那么你必将得到那个很糟糕的局面，甚至可能更糟。这样一来便可以在很大程度上减少搜索的工作量，提高搜索效率，这称为“树的裁剪”。下面用图来进一步说明“树的裁剪”。为了简便起见，将博弈树进行了简化每个结点只有三个分支，实际情况中，刚才讲过在盘中应有大约40个分支。假定棋盘上的局面发展到了结点A，现在轮到你走棋了，你是“最大的一方”即你希望棋局的分值尽可能的高。用搜索两层来看一看“树的裁剪”对提高搜索效8率的帮助。图中表示该结点要取子结点中的最大值；表示该结点要取子结点中的最小值。图3-2树的裁剪首先，考察结点A的子结点B。结点B所属的这一层是轮到你的对手“最小者”来走棋了，目的是使得棋局的分值尽可能的小。依次考察结点B的各个子结点，查看它们的分值（因为事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。结点B的第一个子结点（从左到右算起）返回-8，第二个子结点返回了-2，第三个子结点返回了2。由于结点B这层是你的对手来做选择，假设他一定会做出明智的选择（你不能寄希望于你的对手会走出一步“昏招”），那么他会选择返回值为-2的那个结点。-2最终也就成了从结点B传递回的值，即倘若你（现在位于结点A）选择了产生结点B的走法，使得局面发展到了结点B。那么下一步，你的对手的选择就会使得棋局发展成为分值为-2的那个结点所表示的局面。再来分析结点A的第二个子结点C，结点C与结点B同属一层，它依然是轮到你的对手作选择。依次查看结点C的各个子结点的分值，其第一个子结点返回了2。采用“裁剪”方法。不必再继续考察结点C的剩余子结点了，因为结点C已经够糟糕的了，不管结点C的剩余子结点有怎样的分值，它最多只能传回-8（有可能其剩余子结点中还有分值更小的结点，因而结点C还有可能传回更小的值）。而与前面已经分析过的结点B所传回-2相比较，作为“最大一方”的你显然更不愿意看到2的局面。所以，你当然不会选择相应的着法使得局面发展成为结点C。因为那样的话，下一步你的对手就会带给你一个分值不高于2的局面。由此，在不影响搜索质量的前提下避免了搜索“无价值的”结点C的剩余子结点的大量工作，从而节省了宝贵时间，为在同样机器配置下搜索更多的层数提供了可能。“最小-最大”的思想再加上“对树的裁剪”，这就是Alpha-Beta搜索算法的核心。最基本的Alpha-Beta算法的代码如下：intAlphaBeta(intdepth,intalpha,intbeta)if(depth=0)/如果是叶子节点（到达搜索深度要求）returnEvaluate();/则由局面评估函数返回估值GenerateLegalMoves();/产生所有合法着法while(MovesLeft()/遍历所有着法9MakeNextMove();/执行着法intval=-AlphaBeta(depth-1,-beta,-alpha);/递归调用UnmakeMove();/撤销着法if(val=beta)/裁剪returnbeta;if(valalpha)/保留最大值alpha=val;returnalpha;在kernel/search文件夹中定义了相关的搜索算法。try_move.cpp中定义了执行走法与撤销走法的函数。Alpha_Beta.cpp中定义了基本的Alpha_Beta搜索算法。PVS.cpp中定义了优化搜索的PVS搜索算法。相关函数详述及伪代码：首先介绍极大极小搜索算法，我们现在假定评估函数并非返回局面对当前方的优势，而是返回对红方的优势，则此值越大，对红方越有利，此值越小，对黑方越有利。图3-3搜索算法第一层结点是红方走，第二层结点是黑方走，则第二层结点处，黑方会选择局面估值小的结点作为走法。则黑方选择的估值作为此黑方结点的估值。则父节点(红方)要选择黑方估值最大的结点，作为红方父节点的估值。这就是最大最小搜索。最大最小搜索需要定义两个函数，最大搜索与最小搜索。我们采用最大最小搜索的变种：负极大值搜索。将评估函数定义为返回局面对当前方的优势。对黑方的优势为x，则对红方的优势即为-x，因此，整个搜索采用递归的深度有限搜索，对子节点调用搜索算法，返回对子节点的优势，返回值乘以-1后传给父节点，父节点在所有子节点的返回值中选取最大值，作为父节点的返回值，这样，总是进行最大值选择。其本质仍然是极大极小搜索。Alpha-Beta搜索。图3-4Aipha-Beta10其原理如图所示，此图适用于极大极小搜索，对于负极大值，原理是一样的。估值为1的叶节点被搜索到之后，其他的叶节点就可以被剪去不必再搜索。搜索应当如下展开，划定一个搜索区间(alpha,beta),对子节点搜索，若返回的valuealpha，则更新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;alpha-beta搜索的效率高低取决于剪枝的效率。剪枝的条件是value=beta，估值越高，越有可能引起剪枝，因此，在走法生成时，按照被吃子的固定权值对走法排序。大大提高了剪枝效率，使得可接受的搜索深度由5提高到6。search调用时，alpha取负无穷，beta取正无穷。3.2估值函数（EvaluationFunction）3.2.1估值函数简介本系统的估值函数包括：棋子固定价值，棋子位置附加值，棋子灵活性，棋子对棋盘的控制，棋子间的关系几部分。棋子固定价值指的是对棋盘中的每一个棋子，根据它的重要性和走法的丰富程度赋予其一个特定的值。在棋盘上，棋子多者占优，棋子少者为劣。根据经验，可以让一个车价值为500，一个马价值为300，一个兵价值为100等等。在中国象棋的对弈中，由于一般以将死对方的将(帅)作为结束，因此，通常赋值的规则是为将(帅)赋予一个远大于其他棋子的子力之和的值。可以用下面的表达式求某一方的棋子固定：SideValue=sum(PieceNum*PieceValue)；其中PieceNum是某种棋子的数量，PieceValue是该种棋子的价值，sum是对各种棋子的总价值求和。如果红色的棋子价值总和大于黑色的棋子价值总和，通常这意味着红方的局势优于黑方。而红黑双方的SideValue之差越大，红方的优势也就越大。同样的棋子在不同位置上起的作用是不同的，最明显的是兵(卒)过河之前与之后11它的作用和攻击力以及对对方的威胁显然是不一样的，而当兵卒一旦到了底线附近，它对将(帅)的威胁度将大大下降。棋子灵活性描述的是棋子的活动范围，即棋子向各处调动的可能性大小。棋子的威力能否充分发挥，与灵活性直接相关。本方棋子可以走的点越多，说明本方棋子的灵活性越大。例如车在纵横线上遇到障碍物、马被周围棋子绊脚等，都降低了灵活性，也降低了威力的发挥，灵活性的计算是把棋子在棋盘上所能够移动到达的位置数作为灵活性计算，给予评分。可以用下面的表达式求某一方棋子灵活性：Mobility=Sum(MoveNum*MoveValue)；其中，MoveNum是某种棋子的合法走法数量，MoveValue是该种棋子每一走法的价值，sum是对所有棋子的灵活性价值求和。Mobility就是所有棋子的灵活性分数。一方对棋盘控制的棋盘区域越多，那么他就越具有主动性。在象棋中，如果一位置落在某方棋子的合法走步上，就可以认为被该方控制。如果某一位置同时落在双方的合法走步上，可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣。能控制更多位置的一方应在这项评分上占优。在中国象棋博弈中，每个棋子都不是孤立存在的，他们之间构成了各种相互关系。如棋子1下一步将被吃掉，则应该给一个负的附加值。而如果周围有己方棋子对其进行了保护，也就是说，对方在理智的情况下不会去吃棋子1，那么棋子l没有受到威胁，价值不变。棋子关系的评估应考虑到该谁走棋的问题。如果某个红马落在黑炮的合法走步之内，但此时轮到红方走棋，应认为红马受到的威胁较轻。而如果此时轮到黑方走棋，就应认为红马受到的威胁很大，应减去一个相对较大的值了。3.2.2估值函数的优化目前最长使用的是优化估值参数的方法是利用大量的测试局面进行手工调整，也是本文在优化评估函数时主要使用的手段。这种方法是利用人类的象棋经验知识来调整参数值，比如，从经验上可以知道，一个车的价值要比一个兵大，给车赋予比兵大的数值，马炮则赋予位于其间的值;马和炮的地位相当，给予它们相当的数值，以避免盲目换子；如果对弈中使用了一些优秀的战术配合，那么就给予一定数值的奖励，等等。将这些经验放进评估函数中反复对弈，然后不断修正参数，找出一组性能较高的参数。(1)规格化(Normalize)如果只是关心评价的顺序，而不怎么关心评价值，那么可以把每一项都乘以同样的常数。这就意味着，对某个特定的模块，例如兵的价值，可以硬性设一个值，其他值就可以表示成它们相当于多少个兵。这个做法可以减少一个需要设定的参数。(2)约束法(DeduceConstraints)通过考虑希望电脑作出怎样的判断，就可以确定一些参数。例如在对弈中即使赚到一个兵，用车换象或马还是坏的，但如果能赚到两个兵那还是好的，因为在考虑子力价值是要防止换单兵，鼓励换双兵。这样的条件越多，合适的权重组合就越少。在开始设定权重值的时候，这个方法通常可以得到合适的值，但是在后面仍然需要做一些调整。(3)交手法(HandTweaking)这是调整评估函数时非常常用的方法，通过让程序对弈，来找到它的优势和弱点，猜测哪些参数会让程序更好，然后挑选新的参数。这个方法可以很快得到合理的结果，12但是需要对棋类知识有足够的了解，便于根据程序的对局来做分析，从而知道程序的问题在哪里。手工调整是象棋引擎调整估值参数的主要手段之一，把人类的知识和经验尽量准确客观地“教授”给计算机，是提高棋力的普遍做法，虽然比较费时，但是很有效。通过不断的试验、修改参数值，可以得到不错的结果。但是人类的知识毕竟具有一定的局限性，评估函数也不能包含所有情况，参数之间往往又互相联系，调整某个参数可能解决了某类问题，但又可能给其它问题的解决带来麻烦，在这种情况下很难实现全局下的最优组合。还有一种主要的优化方法是机器自学习：(1)爬山法(Hill-Climbing)爬山法通过对参数进行小范围的试探来寻找最优解，一次只能对参数作一点小改变，然后测试博弈程序的性能是否提高了，仅当性能提高时才采纳这个改变，需要重复很多次。这种方法很慢，并且受初始采样值的限制，很容易陷入局部最优，即评价可能很差，但是任何很小的改变都会使评价更差。(2)模拟退火(SimulatedAnnealing)模拟退火是一种基于蒙特卡罗(MonteCarlo)算法的启发式随机搜索算法，它没有蒙特卡罗算法多次寻优的过程，也不像爬山法那样依赖初值。在优化参数时，类似于爬山法，模拟退火法也是对权重做改变来提高成绩，如果所做的改变没有提高成绩，也会根据一个随机的几率采纳这个改变，试图跳出局部最优。这个方法需要给定一些几率，从几率高、梯度大的条件开始，然后逐渐减小。模拟退火法比爬山法更慢，是最终可能得到比较好的值。(3)遗传算法(GeneticAlgorithm，GA)遗传算法是建立在自然选择和自然遗传学机理基础上的迭代自适应概率性全局优化算法，因其模仿生物的遗传机制而得名，最早由美国密执安大学J.H.Holland于1975年提出，它通过染色体的复制，交叉，变异等操作，实现个体适应性的提高。遗传算法可以同时维护多组较好的参数，通过向其中添加一组新参数，通常是将从几组老参数中选出的值组合在一起作微小的变化，然后同几组老的参数比较孰优孰劣，将最坏的一组去除。遗传算法是从几组参数开始，而不是一组参数，具有很好的全局搜索能力，搜索速度也很快，而且此算法能将搜索重点集中于性能高的部分，能较快地求出最佳参数，鲁棒性也明显优于前两种算法，所以在计算机博弈中最有可能取得成功。3.2.3着法排序Alpha-Beta搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率，它的效率将在很大程度上取决于树的结构如果搜索了没多久就发现可以进行“裁剪”了，那么需要分析的工作量将大大减少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此时“裁剪”也已经失去了它原有的价值（因为你已经分析了所有情况，这时的Alpha-Beta搜索已和“最小-最大”搜索别无二致了）。因而，要想保证Alpha-Beta搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。采用深度优先搜索,配合Alpha-Beta剪枝策略.相关代码在search文件夹中,包括Alpha-Beta.cpp/PVS.cpp/try_move.cppAlpha-Beta.cpp中定义了intsearch(shortdepth,intalpha,intbeta)根据传入参数搜索深度进行搜索,给出当前局面搜索后的评分,但是并不产生最优走13法。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程序调用,即机器要作出的走法.在走法生成时，走法已经经过排序，以提高剪枝的效率。我们可以如下假设，经过排序后，第一个走法就刚好是最好的走法。假定最初的(alpha,beta)=(-100,100)，第一个结点返回的value值为30，则此时(alpha,beta)=(30,100)。若假设成立，则之后的结点的搜索值都不会大于30。则我们以(30,31)作为搜索区间试探。返回值value可能有3中情况：value=100说明返回值比原有的beta还大，应该剪枝30alpha&value=beta)returnvalue;if(valuealpha)14alpha=value;pv_flag=true;if(depth=max_depth)/max_depth为全局变量。best_move=Move_arrayi;returnalpha;可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。由J.Schaeffer所提出的“历史启发”（HistoryHeuristic）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。对于着法的排序可以使用各种排序算法，在程序中采用了归并排序。归并排序的空间复杂度为O(n)，时间复杂度为O(nlog2n)，具有较高的效率。中国象棋中，除了车和炮之外，其他棋子的走法都有棋盘上的固定增量(行增量，列增量)，因此比较容易处理。如红方过河的兵，有三个增量(-0x10,+0x01,-0x01)，分别对应向前、向右和向左。则对每一个棋子，设置增量数组，除兵以外的棋子红方黑方增量数组可以公用，除此之外，还要设置合法性数组，如将的合法区域只能在九宫格内。对于象和马，还要确定马腿、香眼的增量数组。先介绍相关数据定义，在介绍相关函数。首先定义了一个mov的class,表征一个走法，在global.h中。分为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是合法位置:如果没有马腿:如果next位置上没有本方的棋子保存走法;/Save_move()函数参数:整数类型的走法起始位置from;整数类型的走法终点位置to;15走法栈引用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如果没有被将军:Move_array.push_back(mv);Gen_all_move()函数参数:走法栈向量引用vector全局变量side/board/piece/函数输出:无返回值输出.更新Move_array;伪代码:对本方的每一个棋子:如果该棋子还在棋盘上没有被吃掉:生成该棋子走法;对生成的走法栈排序;3.3局面评估局面估值就是通过既有的棋类知识来评估一个局面优劣的过程。从象棋的棋力上考虑，在搜索之外，局面估值是最重要的部分，因为对实际局面的评价的好坏，影响着今后局势发展的趋势。这一过程对具体的棋类知识依赖程度很深，但是仍有一般性的规律可循。目前在计算机象棋博弈中常用的估值方法主要采用静态估值方法。同时由于随着搜索层数的加深，叶子节点的数目迅速上升，估值函数被数以百万次的调用，花费大量的运算时间，如何提高估值函数的速度，也成了博弈性能改进的重要话题。下面分别从这两个方面及其关系介绍局面评估。AI部分采用bottom-up的方法设计,包括局面表示/走法生成/局面评估/将军检测/搜索算法.AI部分代码在kernel文件夹中.kernel文件夹中代码的组织与AI的结构同构.表征局面的数据结构以及其他一些全局变量在global.h中声明,在define_global.cpp中定义.move文件夹中为走法生成的函数.check文件夹中为将军检测函数.eval文件夹中为局面评估函数.search文件夹中为搜索函数.