毕业设计（论文）-基于QT的中国象棋算法设计与实现.doc

北京邮电大学毕业设计基于QT的中国象棋算法设计与实现摘要中国象棋发展至今已有数千年的历史了，它是中华民族智慧的结晶。在我国，中国象棋的普及程度是其它棋类无法比拟的，大至国际、国内比赛，小至社区街道。本文章在研究分析对局树的基础上先后运用极大极小查找和-修剪对查找下一步的算法进行了改进并对中国象棋的对弈过程进行了有益的探讨。最后在此基础上运用面向对象的技术综合结构化程序设计方法将所有的操作逻辑封装于类实现基于对局树算法的中国象棋游戏系统。系统使用QT开发工具，实现了一个具有一定棋力的中国象棋人机对弈和双人对战程序。关键词：中国象棋人工智能博弈树Alpha-Beta搜索北京邮电大学毕业设计WiththeimplementationofChinesechessalgorithmdesignbasedonQTAbstractChinesechessdevelopmenthasbeenseveralthousandyearsofhistoryanditisthewisdomoftheChinesenation.InChinathepopularityofChinesechessboardisunmatchedbyotherlargetointernationalanddomesticcompetitionssmallcommunitystreets。ThisarticleisbasedonresearchandanalysisonthegametreehastofindanduseMinimax-pruningalgorithmforfindingthenextimprovementtheprocessofChinesechessandchessforausefuldiscussion.Finallyonthisbasistheuseofobject-orientedtechnologyintegratedstructuredprogrammingalloftheoperatinglogicencapsulatedinaclass-basedsystemtoachieveChinesechessgamegametreealgorithm.ThesystemusesQTdevelopmenttoolstoachievehuman-computerchessandChinesechessprogramthathasadoublebattleofchess.Keywords:ChinesechessartificialintelligencegametreeAlpha-Betasearch北京邮电大学毕业设计目录摘要.iAbstract.ii1绪论.11.1中国象棋游戏设计背景和研究意义.11.2国内外象棋软件发展概况.11.3中国象棋游戏设计研究方法.11.4本文的主要工作.22系统的分析和设计.32.1棋盘和棋子的表示.32.2着法生成.53博弈程序的实现.73.1搜索算法.73.2估值函数（uationFunction）.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中文翻译.48北京邮电大学毕业设计1绪论1.1中国象棋游戏设计背景和研究意义中国象棋游戏流传至今已经有数千年的历史了，是一种古老的文化，它集文化、科学、艺术、竞技于一体，有利于开发人的智慧，锻炼人的思维，培养人的毅力，增强人的竞争意识。自从计算机发明，向各个领域发展，到成为我们现在每天工作和生活必不可少的一部分的这个过程中，电子游戏也逐步渗入我们每个人的娱乐活动中。在计算机已经普及的今天，对于可以用计算机进行程序编辑的人来说，开发属于自己的游戏，已经不再是梦想，中国象棋历史悠久不仅源远流长，而且基础广泛，作为一项智力运动更成为我们游戏开发的首选对象。中国象棋是一项智力游戏，以往都是人和人下棋，现在有了计算机我们可以和计算机竞技，人可以与计算机进行对弈。控制计算机的是人类，而人工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。因此，对游戏开发过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向。1.2国内外象棋软件发展概况最早的象棋软件是一副可以外出携带的电子棋盘，后来升级到电视游戏机。开始出现的一些容量很小的象棋软件如：DOS界面将族、WIN31程序的中国象棋等等，与其说人类下不过电脑，倒不如说是没有耐性等待电脑程序慢吞吞的搜索算法，有时甚至怀疑软件是否在搜索中死掉了。后来，网络上先后出现了真正的WINDOWS窗口界面的象棋专业高级软件棋隐、象棋世家、象棋参谋、象棋奇兵等。总而言之，各类象棋软件既有自身的优点，也存在共通性的缺陷，如：中局审势不够智能化，走不出弃子取势的人性化佳构，残局时智力明显低于人脑，难以走出残局例胜的必然着法等。放眼未来，象棋软件已经走完了一波持续上涨的行情，有可能出现逐步降温的滑坡趋势。1.3中国象棋游戏设计研究方法本系统主要用VisualC+进行开发，里面的MFC类库，使游戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生成，从而完善整个游戏的功能。该象棋人机博弈系统实现的功能主要包括：1、选手选择（人或电脑）；2、人机对弈（人与电脑竞技）；3、悔棋、还原；4、着法名称显示（象棋走棋规范名称）。北京邮电大学毕业设计1.4本文的主要工作第一部分主要介绍了中国象棋游戏开发的背景及意义、国内外象棋软件的发展概况和象棋游戏的设计研究方法；第二部分介绍了棋局表示方法和着法生成；第三部分介绍了走棋和博弈程序的实现；第四部分介绍了系统的实现。北京邮电大学毕业设计2系统的分析和设计2.1棋盘和棋子的表示棋盘表示就是使用一种数据结构来描述棋盘上的信息，以便程序知道博弈的状态。棋盘的数据表示直接影响到程序的时间及空间复杂度。为了追求更高效率，研究人员针对中国象棋提出了多种不同的表示方法。中国象棋的棋盘表示中最典型的是用一个109的二维字节(byte)数组，数组中每个元素代表棋盘上的一个交点，其值表明这个交点上放置的是一个什么棋子或是没有棋子从棋子的角度考虑，如果把棋盘看成是一个平面坐标系，可以知道每一个棋子的位置信息:小于10的横坐标和小于11的纵坐标又在棋盘上最多32个棋子，故可以用一个32个字节的一维数组表示所有32个棋子的位置，其中每个字节的高4位表示该棋子的横坐标，低4位表示棋子的纵坐标。而己被吃掉的棋子用坐标范围以外的数表示。这样棋盘信息就被装入这32个字节中。当然也可以把棋盘看作一维的，每个元素保存直接的位置信息。两种棋盘表示方法：一是做一个棋盘数组；二是做一个棋子数组。棋盘数组中由棋子的位置获得棋子的类型可以在常数时间内完成，但由棋子的类型获得棋子的位置需要遍历；在棋子数组中由棋子的类型获得棋子的位置可以在常数时间内完成，但由棋子的位置获得棋子的类型操作繁琐。如果一个程序同时使用这两个数组，那么获得棋子的类型和棋子的位置都可以在常数时间内完成。这就是“棋盘棋子联系数组”，它的技术要点是:(1)同时用棋盘数组和棋子数组表示一个局面，棋盘数组和棋子数组之间可以互相转换。(2)随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。在棋盘上删除一个棋子，需要做两个操作(分别修改棋盘数组和棋子数组)。同样，添加一个棋子时也需要两个操作。“棋盘棋子联系数组“最大的优势是：对于着法产生过程，可以逐一查找棋子数组，如果该子没有被吃掉，就产生该子的所有合理着法，由于需要查找的棋子数组的数量(每方只有16个棋子能走)比棋盘格子的数量(90个格子)少得多，因此联系数组的速度要比单纯的棋盘数组快很多。同时“棋盘棋子联系数组”是很多改进的棋盘的基础。对于中国象棋棋盘局面的表示可采用传统而简单的“棋盘数组”。即用一个910的数组来存储棋盘上的信息，数组的每个元素存储棋盘上是否有棋子。这种表示方法简单易行。按此方法棋盘的初始情形如下所示：BYTECChessBoard910=R00P00p00rH0C0000c0hE00P00p00eA00000000aK00P00p00kA00000000aE00P00p00e北京邮电大学毕业设计H0C0000c0hR00P00p00r给所有棋子定义一个值：#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=beta)裁剪returnbetaif(valalpha)保留最大值alpha=valreturnalpha在kernelsearch文件夹中定义了相关的搜索算法。try_move.cpp中定义了执行走法与撤销走法的函数。Alpha_Beta.cpp中定义了基本的Alpha_Beta搜索算法。PVS.cpp中定义了优化搜索的PVS搜索算法。相关函数详述及伪代码：首先介绍极大极小搜索算法，我们现在假定评估函数并非返回局面对当前方的优势，而是返回对红方的优势，则此值越大，对红方越有利，此值越小，对黑方越有利。图3-3搜索算法第一层结点是红方走，第二层结点是黑方走，则第二层结点处，黑方会选择局面估值小的结点作为走法。则黑方选择的估值作为此黑方结点的估值。则父节点(红方)要选择黑方估值最大的结点，作为红方父节点的估值。这就是最大最小搜索。最大最小搜索需要定义两个函数，最大搜索与最小搜索。我们采用最大最小搜索的变种：负极大值搜索。将评估函数定义为返回局面对当前方的优势。对黑方的优势为x，则对红方的优势即为-x，因此，整个搜索采用递归的深度有限搜索，对子节点调用搜索算法，返回对子节点的优势，返回值乘以-1后传给父节点，父节点在所有子节点的返回值中选取最大值，作为父节点的返回值，这样，总是进行最大值选择。其本质仍然是极大极小搜索。Alpha-Beta搜索。图3-4Aipha-Beta北京邮电大学毕业设计其原理如图所示，此图适用于极大极小搜索，对于负极大值，原理是一样的。估值为1的叶节点被搜索到之后，其他的叶节点就可以被剪去不必再搜索。搜索应当如下展开，划定一个搜索区间(alphabeta)对子节点搜索，若返回的valuealpha，则更新alpha，搜索过程中搜索到了大于beta的值，则剪枝。alpha-beta搜索的伪代码如下：函数形式：intsearch(shortdepthintalphaintbeta)输入：搜索深度depth，alphabeta输出:最佳走法对应的走法估值，并不更新全局变量movbest_move伪代码：if(depth=0)return局面评估值定义走法栈vectorMove_array定义评估值intvalue生成所有走法若走法栈为空返回负无穷说明已经被将死对每一种走法，遍历：执行走法value=-1search(depth-1-beta-alpha)撤销走法if(value=beta)returnbetaif(valuealpha)alpha=valuereturnalphaalpha-beta搜索的效率高低取决于剪枝的效率。剪枝的条件是value=beta，估值越高，越有可能引起剪枝，因此，在走法生成时，按照被吃子的固定权值对走法排序。大大提高了剪枝效率，使得可接受的搜索深度由5提高到6。search调用时，alpha取负无穷，beta取正无穷。3.2估值函数（uationFunction）3.2.1估值函数简介本系统的估值函数包括：棋子固定价值，棋子位置附加值，棋子灵活性，棋子对棋盘的控制，棋子间的关系几部分。棋子固定价值指的是对棋盘中的每一个棋子，根据它的重要性和走法的丰富程度赋予其一个特定的值。在棋盘上，棋子多者占优，棋子少者为劣。根据经验，可以让一个车价值为500，一个马价值为300，一个兵价值为100等等。在中国象棋的对弈中，由于一般以将死对方的将(帅)作为结束，因此，通常赋值的规则是为将(帅)赋予一个远大于其他棋子的子力之和的值。可以用下面的表达式求某一方的棋子固定：Sidue=sum(PieceNumPiecue)；其中PieceNum是某种棋子的数量，Piecue是该种棋子的价值，sum是对各种棋子的总价值求和。如果红色的棋子价值总和大于黑色的棋子价值总和，通常这意味着红方的局势优于黑方。而红黑双方的Sidue之差越大，红方的优势也就越大。同样的棋子在不同位置上起的作用是不同的，最明显的是兵(卒)过河之前与之后北京邮电大学毕业设计它的作用和攻击力以及对对方的威胁显然是不一样的，而当兵卒一旦到了底线附近，它对将(帅)的威胁度将大大下降。棋子灵活性描述的是棋子的活动范围，即棋子向各处调动的可能性大小。棋子的威力能否充分发挥，与灵活性直接相关。本方棋子可以走的点越多，说明本方棋子的灵活性越大。例如车在纵横线上遇到障碍物、马被周围棋子绊脚等，都降低了灵活性，也降低了威力的发挥，灵活性的计算是把棋子在棋盘上所能够移动到达的位置数作为灵活性计算，给予评分。可以用下面的表达式求某一方棋子灵活性：Mobility=Sum(MoveNumMovue)；其中，MoveNum是某种棋子的合法走法数量，Movue是该种棋子每一走法的价值，sum是对所有棋子的灵活性价值求和。Mobility就是所有棋子的灵活性分数。一方对棋盘控制的棋盘区域越多，那么他就越具有主动性。在象棋中，如果一位置落在某方棋子的合法走步上，就可以认为被该方控制。如果某一位置同时落在双方的合法走步上，可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣。能控制更多位置的一方应在这项评分上占优。在中国象棋博弈中，每个棋子都不是孤立存在的，他们之间构成了各种相互关系。如棋子1下一步将被吃掉，则应该给一个负的附加值。而如果周围有己方棋子对其进行了保护，也就是说，对方在理智的情况下不会去吃棋子1，那么棋子l没有受到威胁，价值不变。棋子关系的评估应考虑到该谁走棋的问题。如果某个红马落在黑炮的合法走步之内，但此时轮到红方走棋，应认为红马受到的威胁较轻。而如果此时轮到黑方走棋，就应认为红马受到的威胁很大，应减去一个相对较大的值了。3.2.2估值函数的优化目前最长使用的是优化估值参数的方法是利用大量的测试局面进行手工调整，也是本文在优化评估函数时主要使用的手段。这种方法是利用人类的象棋经验知识来调整参数值，比如，从经验上可以知道，一个车的价值要比一个兵大，给车赋予比兵大的数值，马炮则赋予位于其间的值马和炮的地位相当，给予它们相当的数值，以避免盲目换子；如果对弈中使用了一些优秀的战术配合，那么就给予一定数值的奖励，等等。将这些经验放进评估函数中反复对弈，然后不断修正参数，找出一组性能较高的参数。(1)规格化(Normalize)如果只是关心评价的顺序，而不怎么关心评价值，那么可以把每一项都乘以同样的常数。这就意味着，对某个特定的模块，例如兵的价值，可以硬性设一个值，其他值就可以表示成它们相当于多少个兵。这个做法可以减少一个需要设定的参数。(2)约束法(DeduceConstraints)通过考虑希望电脑作出怎样的判断，就可以确定一些参数。例如在对弈中即使赚到一个兵，用车换象或马还是坏的，但如果能赚到两个兵那还是好的，因为在考虑子力价值是要防止换单兵，鼓励换双兵。这样的条件越多，合适的权重组合就越少。在开始设定权重值的时候，这个方法通常可以得到合适的值，但是在后面仍然需要做一些调整。(3)交手法(HandTweaking)这是调整评估函数时非常常用的方法，通过让程序对弈，来找到它的优势和弱点，猜测哪些参数会让程序更好，然后挑选新的参数。这个方法可以很快得到合理的结果，北京邮电大学毕业设计但是需要对棋类知识有足够的了解，便于根据程序的对局来做分析，从而知道程序的问题在哪里。手工调整是象棋引擎调整估值参数的主要手段之一，把人类的知识和经验尽量准确客观地“教授”给计算机，是提高棋力的普遍做法，虽然比较费时，但是很有效。通过不断的试验、修改参数值，可以得到不错的结果。但是人类的知识毕竟具有一定的局限性，评估函数也不能包含所有情况，参数之间往往又互相联系，调整某个参数可能解决了某类问题，但又可能给其它问题的解决带来麻烦，在这种情况下很难实现全局下的最优组合。还有一种主要的优化方法是机器自学习：(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.cppPVS.cpptry_move.cppAlpha-Beta.cpp中定义了intsearch(shortdepthintalphaintbeta)根据传入参数搜索深度进行搜索给出当前局面搜索后的评分但是并不产生最优走北京邮电大学毕业设计法。Alpha-Beta搜索的剪枝效率对搜索的顺序十分敏感若走法栈中好的走法排在前面则剪枝效率高因此在走法生成部分对走法按照被吃子的固定权值进行了排序.明显提高了剪枝效率。try_move.cpp中定义了voidMake_move(movmv)与Un_move(movmv)函数分别是根据当前局面与传入的mov类型的走法数据执行一步走法更改board数组与piece数组.voidUn_make(movmv)则是撤销一步走法。最优走法的生成在PVS.cpp中定义的intPVS(shortdepthintalphaintbeta)函数中产生.其基本思想是这样的:走法经过排序后可以假设最优走法出现在走法栈的起始位置处则在对Move_array进行遍历搜索时可以先假定Move_array0就是最优走法.则对其他的走法先进行一个窗口宽度为0的alpha-beta搜索(search(depth-1-alpha-1-alpha)根据返回的结果判定假设是否成立若假设不成立则再进行一次正常的alpha-beta搜索.PVS算法根据当前局面返回对当前方(根据side判断)的局面评分并更改一个声明在global.h中的全局变量movbest_move.best_move被GUI程序调用即机器要作出的走法.在走法生成时，走法已经经过排序，以提高剪枝的效率。我们可以如下假设，经过排序后，第一个走法就刚好是最好的走法。假定最初的(alphabeta)=(-100100)，第一个结点返回的value值为30，则此时(alphabeta)=(30100)。若假设成立，则之后的结点的搜索值都不会大于30。则我们以(3031)作为搜索区间试探。返回值value可能有3中情况：value=100说明返回值比原有的beta还大，应该剪枝30alpha)北京邮电大学毕业设计alpha=valuepv_flag=trueif(depth=max_depth)max_depth为全局变量。best_move=Move_arrayireturnalpha可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。由J.Schaeffer所提出的“历史启发”（HistoryHeuristic）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。对于着法的排序可以使用各种排序算法，在程序中采用了归并排序。归并排序的空间复杂度为O(n)，时间复杂度为O(nlog2n)，具有较高的效率。中国象棋中，除了车和炮之外，其他棋子的走法都有棋盘上的固定增量(行增量，列增量)，因此比较容易处理。如红方过河的兵，有三个增量(-0 x10+0 x01-0 x01)，分别对应向前、向右和向左。则对每一个棋子，设置增量数组，除兵以外的棋子红方黑方增量数组可以公用，除此之外，还要设置合法性数组，如将的合法区域只能在九宫格内。对于象和马，还要确定马腿、香眼的增量数组。先介绍相关数据定义，在介绍相关函数。首先定义了一个mov的class表征一个走法，在global.h中。分为3部分每个棋子的走法生成函数走法保存函数走法栈生成函数.对应棋盘上当前走棋方的所有棋子调用其棋子走法生成函数生成走法并保存人走法栈.下面介绍马的走法生成函数Horse_move()Save_moveGen_All_Move()这三个函数其他棋子的走法生成函数与马的走法生成函数相类似.Horse_move():函数参数:马的当前位置pos表征当前走棋方的Side_tagSide_tag=(side=016:32)走法栈向量的引用vector&Move_array输出:无返回值输出将走法(mov类型变量push进Move_array中)伪代码:对马的8个可走方向:leg=pos+Horse_leginext=pos+Horse_directioni如果next是合法位置:如果没有马腿:如果next位置上没有本方的棋子保存走法Save_move()函数参数:整数类型的走法起始位置from整数类型的走法终点位置to北京邮电大学毕业设计走法栈引用vector&Move_array函数输出:无返回值输出改变Move_array伪代码:capture=boardto确定被吃棋子的编码movmv=fromtocapture定义一个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&Move_array全局变量sideboardpiece函数输出:无返回值输出.更新Move_array伪代码:对本方的每一个棋子:如果该棋子还在棋盘上没有被吃掉:生成该棋子走法对生成的走法栈排序3.3局面评估局面估值就是通过既有的棋类知识来评估一个局面优劣的过程。从象棋的棋力上考虑，在搜索之外，局面估值是最重要的部分，因为对实际局面的评价的好坏，影响着今后局势发展的趋势。这一过程对具体的棋类知识依赖程度很深，但是仍有一般性的规律可循。目前在计算机象棋博弈中常用的估值方法主要采用静态估值方法。同时由于随着搜索层数的加深，叶子节点的数目迅速上升，估值函数被数以百万次的调用，花费大量的运算时间，如何提高估值函数的速度，也成了博弈性能改进的重要话题。下面分别从这两个方面及其关系介绍局面评估。AI部分采用bottom-up的方法设计包括局面表示走法生成局面评估将军检测搜索算法.AI部分代码在kernel文件夹中.kernel文件夹中代码的组织与AI的结构同构.表征局面的数据结构以及其他一些全局变量在global.h中声明在define_global.cpp中定义.move文件夹中为走法生成的函数.check文件夹中为将军检测函数.文件夹中为局面评估函数.search文件夹中为搜索函数.每个文件夹中都有test.cpp及makefile为相应函数的测试代码.用户可到相应文件夹中运行make然后执行可执行文件查看测试结果(makefile在linux环境下写成)北京邮电大学毕业设计AI部分概述:以长度为256的一维数组表示棋盘其中90个数字表征棋盘其余部分为冗余数据置零.棋盘的表示还有相关冗余数据结构.棋子以数字编码.走法生成函数生成走法搜索算法调用评估函数给出局面估值及最佳走法.搜索基于alpha-beta剪枝算法.剪枝效率与遍历走法栈的顺序关系很大因此生成走法时按照一定规则对走法栈排序.还采用了PVS算法对alpha-beta算法进行优化.局面评估函数定义在kernelweight.cpp棋子的固定权值存在piece_weight数组中。棋子的位置权值存在各棋子的pos_value数组中。#includeglobal.h#includevoidMake_move(mov&mv)shortto=mv.toshortfrom=mv.fromshortcapture=mv.capturepieceboardfrom=topiececapture=0boardto=boardfromboardfrom=0side=1-sidevoidUn_move(mov&mv)shortto=mv.toshortfrom=mv.fromshortcapture=mv.captureboardfrom=boardtoboardto=capturepiececapture=topieceboardfrom=fromside=1-sidevectorhuman_movevectorhistoryshortpiece48=00000000000000000 xc70 xc60 xc80 xc50 xc90 xc40 xca0 xc30 xcb0 xa40 xaa0 x930 x950 x970 x990 x9b0 x370 x360 x380 x350 x390 x340 x3a0 x330 x3b0 x540 x5a0 x630 x650 x670 x690 x6bshortrepiece48=00000000000000000 xc70 xc60 xc80 xc50 xc90 xc40 xca0 xc30 xcb0 xa40 xaa0 x930 x950 x970 x990 x9b0 x370 x360 x380 x350 x390 x340 x3a0 x330 x3b0 x540 x5a0 x630 x650 x670 x690 x6bshortboard256=000000000000000000000000000000000000000000000000000393735333234363840000000000000000000000000410000042000000004304404504604700000000000000000000000000000000000000027028029030031000000002500000260000000000000000000000002321191716182022240000北京邮电大学毕业设计000000000000000000000000000000000000000000000000shortsidemax_depthmodeprogressinfointvaluemovbest_moveintWeight_value()伪代码：红方权值=0黑方权值=0；对红方每一个棋子：红方权值+=（该棋子固定权值+该棋子位置得分）对黑方每一个棋子：黑方权值+=（该棋子固定权值+该棋子位置的饭呢）if(side=0)return红方权值-黑方权值；if(side=1)return黑方权值-红方权值。前文已经讲过了棋局表示、着法生成、搜索算法（包括搜索辅助“历史启发”），在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。首先，先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素略有差异。在中国象棋中所要考虑的最基本的几个因素包括如下四点：1、子力总和子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如，车值10的话，那可能马值6，卒值2等等。所以在评估局面时，首先要考虑双方的子力总和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。2、棋子位置棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位置。例如，沉底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差的棋子位置状态。3、棋子的机动性棋子的机动性指棋子的灵活度（可移动性）。例如，起始位置的车机动性较差，所以下棋讲究早出车。同样四面被憋马腿的死马机动性也较差（对于一步也不能走的棋子，可以认为其机动性为零）。4、棋子的相互关系这一点的分析较为复杂，因为一个棋子与其它子之间往往存在多重关系。如：一个马可能在对方的炮的攻击之下同时它又攻击着对方的车。在程序中，估值函数最后返回的是每一方的总分的差值，而各方的总分就是上面所提到的四个因素的打分的总和。对于子力打分和控制区域打分，只要遍历棋盘，当遇到棋子时简单地去查事先定义好的“子力价值表”和“控制区域价值表”，取出相对应的值进行累加即可。对于机动性打分，需要求出各个子总共有多少种走法，然后根据各个子所不同的机动性价值每多一种走法就加一次相应的分数。北京邮电大学毕业设计对棋子间相互关系的打分，要用到以下几个数据：intm_Basue15存放棋子基本价值intm_FlexValue15存放棋子灵活性分值shortm_AttackPos109存放每一位置被威胁的信息BYTEm_GuardPos109存放每一位置被保护的信息BYTEm_FlexibilityPos109存放每一位置上棋子的灵活性分值intm_chessValue109存放每一位置上棋子的总价值其中计算机会进行所有棋子值的判断，AttackPos和GuardPos分别记录该棋子受到的威胁和被保护的值。当遍历一遍棋盘之后，子力打分、控制区域打分和机动性打分都可以完成，而关系表也可以填完。之后，再根据关系表来具体考察棋子的相互关系，进行关系打分。分析关系时，首先，对王的攻击保护应分离出来单独考虑，因为对王的保护没有任何意义，一旦王被吃掉整个游戏就结束了。其次，对一个普通子，当它既受到攻击又受到保护的时候要注意如下几个问题：1、攻击者子力小于被攻击者子力，攻击方将愿意换子。比如，一个车正遭受一个炮的攻击，那么任何对车的保护都将失去意义对方肯定乐意用一个炮来换一个车。2、多攻击单保护的情况，并且攻击者最小子力小于被攻击者子力与保护者子力之和，则攻击方可能以一子换两子。3、三攻击两保护的情况，并且攻击者子力较小的二者之和小于被攻击者子力与保护者子力之和，则攻击方可能以两子换三子。4、攻击方与保护方数量相同，并且攻击者子力小于被攻击者子力与保护者子力之和再减去保护者中最大子力，则攻击方可能以n子换n子。当然，上述四条只是覆盖了最常见的几种情况，覆盖并不全面。而且，在程序中并没有直接地重新考虑双方兑子之后的控制区域及机动性变化情况（之所以说没有“直接地重新考虑”，是因为搜索继续展开结点后仍会考虑这些因素，只是目前不知这样效果是否受影响考察这两种方法在效果上的差异需要一定数量的试验数据的支持）。所以，如果今后要对引擎进行改进，提高程序的下棋水平的话，还应当在此进行研究。北京邮电大学毕业设计4走棋程序的实现4.1悔棋和还原功能的实现悔棋和还原是棋类软件中较为基本的功能。要实现悔棋和还原功能，首先要明确哪些信息应当被保存以供悔棋和还原所使用。在程序中保存了如下信息：棋局表示中所定义的棋盘数组；各棋子的贴图位置；这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后当悔棋的时候，需要撤销着法；还原的时候，需要执行着法。然而，在编写自己的程序时一来考虑到程序的可读性和不易出错性，二来考虑到对当今的计算机的配置来说这点开销基本上不会对程序的效率产生什么影响。因此保存了全部棋子的信息。根据所要保存的数据定义了如下基本结构类型：typedefstructCHESSMOVEcmChessMoveshortnChessID被吃掉的棋子UNDOMOVE在对弈过程中，每一回合都将棋局信息（这里指前面所说的需要保存的信息）保存至走法队列，以供悔棋所用。还原功能是与悔棋功能相对应的，只有当产生了悔棋功能之后，还原功能才会被激活。一个回合的结束意味着前一次操作没有悔棋功能的产生，因此还原队列也应被清空。#includemainwindow.h#includekernelglobal.h#include#include#include#include#includevoidMainWindow:slotregret()北京邮电大学毕业设计QTextCodec:setCodecForTr(QTextCodec:codecForName(UTF-8)toregret=newinfo(this)toregret-setGeometry(550300300150)toregret-show()QStringsen11toregret-text-setText(sentimes)toregret-button-setGeometry(5010020030)toregret-button-setText；regret-setEnabled(false)if(timesbuttonSIGNAL(clicked()thisSLOT(slotregret()connect(toregret-buttonSIGNAL(clicked()toregretSLOT(close()times+elseconnect(toregret-buttonSIGNAL(clicked()SLOT(selectregret()connect(toregret-buttonSIGNAL(clicked()toregretSLOT(close()times=0voidMainWindow:slotrestart()shorti=0for(ishowMessage(round:+QString:number(history.size()2+1)regret-setEnabled(false)progress-setValue(0)red-hide()black1-hide()black2-hide()eat-hide()voidMainWindow:selectregret()voidUn_move(mov&mv)intninti=0if(history.size()=2)for(ishow()refresh(piece)history.pop_back()if(n=1)regret-setEnabled(false)progress-setValue(0)red-hide()black1-hide()black2-hide()statusBar()-showMessage(round:+QString:number(history.size()2+1)eat-hide()voidMainWindow:end()result=newinfo(this)result-show()result-setGeometry(500350300150)control=1controlregret-setEnabled(false)if(side=0)result-text-setText(tr(RedLose!)elseresult-text-setText(tr(BlackLose!)result-button-setText(tr(close)connect(result-buttonSIGNAL(clicked()resultSLOT(close()在悔棋中主要完成了以下任务：1、下棋回合数减一；2、将当前局面信息保存至走法队列，以供还原所用；3、从走法队列中取出上一回合的棋局信息，恢复到当前局面，然后将其从队列中剔除掉；4、将显示着法名称的列表框中的本回合的着法名称保存到一个着法名