毕业论文-基于vc的智能中国象棋系统的设计与实现

武汉理工大学毕业设计（论文）基于VC的智能中国象棋系统的设计与实现学院（系）专业班级学生姓名指导教师智能中国象棋系统的设计与实现摘要人工智能AI中国象棋系统是将计算机知识和中国象棋知识结合起来的一种新型的游戏方式。智能中国象棋系统在此基础上实现人与机器的对弈，突破了以往传统象棋游戏只能人与人对战的限制，使中国象棋这一古老的游戏形式焕发出蓬勃朝气。本文结合在中国象棋机器博弈方面的实践经验，在分析了中国象棋游戏需求基础上，设计并实现了智能中国象棋系统。该系统包括人人对战、人机对战、制作棋谱、播放棋谱以及挑战英雄榜等功能模块。人人对战规则明确，包含了中国象棋所有的着法；人机对战中电脑棋力分为简单、中等、困难三个等级，方便了不同水平人群的选择；制作和播放棋谱模块容易操作，方便学习；挑战英雄榜则为象棋游戏增加了乐趣。本系统的实现满足了人们对中国象棋的基本需求，解决了传统象棋游戏学习性差、棋谱不易保存、不易演示等问题。关键词计算机博弈，中国象棋，人机对战，制作棋谱，搜索算法INTELLIGENTCHINESECHESSSYSTEMDESIGNANDIMPLEMENTATIONABSTRACTARTIFICIALINTELLIGENCEAICHINESECHESSSYSTEMISANEWGAMESWAYWHICHCOMBINESWITHCOMPUTERKNOWLEDGEANDCHINESECHESSKNOWLEDGEINTELLIGENTCHINESECHESSSYSTEMONTHEBASISOFITWHICHCOMPLETESTHEGAMEBETWEENHUMANANDCOMPUTER,BREAKINGTHETRADITIONALCHESSGAMESRESTRICTIONTHATONLYCANPLAYAGAINSTPEOPLESOTHATTHEANCIENTGAMEOFCHINESECHESSBECOMEPROSPERITYWITHTHEPRACTICALEXPERIENCEINCHINESECHESSCOMPUTERGAME,ADETAILEDANALYSISANDRESEARCHHASBEENDONEBASEDONTHOSE,IDESIGNEDANDIMPLEMENTEDTHEINTELLIGENTCHINESECHESSSYSTEMTHISSYSTEMINCLUDESTHEGAMEAGAINSTHUMAN,THEGMEBETWEENCOMPUTERANDHUMAN,MAKECHESSMANUAL,PLAYCHESSMANUALANDHEROLISTFUNCTIONSTHEGAMEAGAINSTHUMANFUNCTIONHASALLTHECHINESECHESSRULESANDTHEYAREVERYCLEARINTHEGAMEBETWEENCOMPUTERANDHUMANFUNCTION,COMPUTERTHINKINGDEPTHISDIVIDEDINTOSIMPLE,MEDIUMANDDIFFICULTYITFACILITATETHECHOICEOFDIFFERENTLEVELSMAKINGANDPLAYINGCHESSMANUALFUCTIONSAREEASYTOOPERATINGANDLEARNINGHEROLISTFUCTIONADDSMUCHFUNTOCHESSGAMETHISSYSTEMSATISFIEDTHEBASICDEMANDOFPEOPLETOCHINESECHESSANDSOLVEDTHESTUDYINGHARDANDTHETHEORETICALISNOTEASYTOMAKINGANDPLAYINGOFTHETRADITIONALCHESSGAMEKEYWORDSCOMPUTERGAME,CHINESECHESS,GAMEBETWEENHUMANANDCOMPUTER,MAKECHESSMANUAL,SEARCHTECNIQUES目录1绪论111选题的背景和意义112发展动态及研究现状113系统概述214本文的主要工作415论文结构42系统的分析和设计521数据结构（DATASTRUCTURE）5211棋盘的基本表示法（BOARDREPRESENTIONS）522着法生成（MOVEGENERATION）7221模板匹配法7222预置表法823局面评估8231估值函数（EVALUATIONFUNCTION）9232估值的速度与博弈性能10233估值函数的优化1024博弈树搜索技术12241基本搜索算法13242高级搜索算法1525开局库设计16251开局库的作用16252实现开局库的主要方法163系统的实现1931系统的整体规划1932象棋界面的实现1933对弈功能的实现2434制作和演示棋谱的实现2835象棋英雄榜的实现3136开局库的实现3237程序说明3238实验结果及分析32结论34致谢36参考文献37附录38附录AAINTRODUCTIONABOUTCHINESECHESSA38附录B关于中国象棋的一些简要介绍411绪论11选题的背景和意义在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。近几十年来，随着计算机硬件和软件技术的不断发展，人们开始对计算机能否战胜人脑这个话题产生了浓厚的兴趣。从1980开始，电脑博弈便开始逐渐大规模地向人类智能发起了挑战，到了1997年，IBM超级电脑DEEPERBLUE击败了当时的国际象棋冠军卡斯帕罗夫，成为了人工智能挑战人类智能发展的一个重要里程碑。许多学者认为，对于人工智能研究而言，象棋的重要作用不亚于遗传学研究中的果蝇。人类对机器博弈的研究衍生了大量的研究成果，这些成果对更广泛的领域产生了重要影响。人工智能的先驱们曾认真的表明如果能掌握下棋的本质，也许就掌握了人类智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中。因此对于中国象棋人机博弈问题的研究意义重大。而当今对中国象棋的研究也正如专家们所期望的那样在蓬勃地发展着。中国象棋不仅是中国传统智慧的体现，同时也具有着比国际象棋更高的复杂度，如何让机器具有智能,与人进行对弈成了本课题研究的一个重要问题。通过本课题的研究,掌握智能知识的表示与计算、搜索，不仅是对所学知识的锻炼，更是在人工智能领域的有意义的探索12发展动态及研究现状和国际象棋博弈系统相比，中国象棋博弈系统的研究起步比较晚，是八十年代开始的。在这个时候计算机国际象棋取得重大突破，1983年美国贝尔公司的电脑参加美国人类比赛，取得了不错的成绩，被授予大师称号。于是有专家学者想如何将国际象棋电脑技术移植到中国象棋上来，以带动中国象棋电脑较快的发展；同时中国象棋从技术研究进入理论研究，有关开局、中局、残局理论以及象棋对策相继建立起来，为中国象棋计算机博弈提供了理论基础。1981年张耀腾发表的人造智慧在电脑象棋上的应用，他提出审局函数为静态子力值，棋子位置值，棋子灵活度值，威胁与保护等四项之和。但该文主要以残局做实验，缺乏完整对局的考虑。1982年廖嘉成发表的利用计算机象棋的实验就进了一步，包括开局、中局、残局。1983年黄少龙、周玉龙合作制成象棋排局系列软盘专家系统与人对弈。到了90年代，中国象棋计算机博弈的应用开始发展起来，人们研究出了各种博弈软件。比较著名的软件有台湾的吴身润的中国象棋、光谱公司出品的将族、晟业编制的象棋水浒战、象棋武林帖。而且涉足这个领域比较早的是台湾的一些专家学者。近几年，在内地也涌现出一批对中国象棋人机博弈问题感兴趣的高校、单位及个人，而且进入21世纪以后，中国象棋计算机博弈的研究受到越来越多的学者的关注，比较著名的博弈软件如表1所示。表11著名中国象棋计算机博弈程序程序作者地区纵马奔流涂志坚广州中山大学谢谢象棋大师法国电脑公司法国ELP郑武尧、陈志吕台湾SHIGA（象棋世家）郑明政、颜士净台湾SHCC（神乎棋技）SAITEAM美国CYCLONE（象棋旋风）陈朝阳北京CONTEMPLATION千虑陈志昌、许舜钦台湾棋天大圣王骄东北大学象棋奇兵赵明阳中国每年也会有中国象棋计算机博弈的国际奥林匹克大赛，这其中有2003年的世界冠军“纵马奔流”，2004年的世界冠军“谢谢象棋大师”，2005年的世界冠军“象棋奇兵”，2006、2007年的世界冠军“棋天大圣”，2008年的世界冠军“倚天”。这些都体现了中国象棋的人机博弈的研究的受关注程度虽然如此，但中国象棋的人机博弈的研究比国际象棋还是晚了几十年，并且在搜索算法等方面的研究还与国际象棋相距甚远。13系统概述1、棋盘表示BOARDREPRESENTATIONS棋盘表示就是使用一种数据结构来描述棋盘及棋盘上的棋子，以方便计算机处理。中国象棋的棋盘表示还没有形成统一的或者公认的哪种为最佳的数据格式。最直观也是最典型的方式是使用10X9的二维棋盘数组表示，也有使用棋子数组，扩展棋盘棋子数组等，棋盘的数据表示直接影响到程序的时间及空间复杂度。2、着法生成MOVEGENERATION着法生成就是找到某个局面所有合法的走法。它与棋盘表示的数据结构密切相关，一般需要大量繁琐的判断，伴随着搜索进行，并且调用频繁，是相当复杂而且耗费运算时间。在一定程度上形成了程序的性能瓶颈。当前为了提高着法生成的效率通常采用以空间换时间的方法与先求出棋子的在某位置的所有走法。3、评估函数EVALUATIONFUNCTION评估函数就是对博弈过程中实际局面的好坏做出判断或打分，它影响着博弈局发展的趋势。目前象棋程序的静态评价函数主要有子力价值，子力灵活性，子力对棋盘的控制，和一些对棋局影响比较大的重要特征计算几部分组成。它与着法生成一样十分耗费运算时间，如何加速评估函数的速度十分关键。4、搜索技术SEARCHTECHNIQUES搜索技术与算法是象棋博弈系统程序的核心，是决定搜索效率的关键所在。再好的硬件也无法实现“象棋不败算法”。如何在成指数递增的状态空间中寻求最优解，是象棋博弈系统的一个重要的方向。“蛮力搜索”肯定是不可取的。如何有选择地搜索，既瞄准最有希望的方向局部加深，又不遗漏其它存在最优解的可能。目前主要是使用剪枝算法加上迭代深化、置换表、历史启发等策略的综合应用。5、开局库OPENINGBOOK把开局几步的走法建成数据库供程序直接取用。实践表明无论搜索引擎如何出色，在开局搜索过若干层后，得到的可能只是一些很笨拙的开局。直接从开局库中取就可以大大加快开局时的运行速度和提高开局的质量。开局库一般是采用ZOBRIST哈希技术加以实现。6、机器自学习MACHINELEARNING机器自学习之一是针对评估函数。对弈过程机器自动调整评估函数参数的权值进行优化，发现一些棋子之间潜在的联系之二是采用模式识别，学习的过程是通过对博弈过程的识别统计，自行丰富模式库中的内容，以提高程序的博弈性能。14本文的主要工作本文的主要工作是将博弈策略应用到中国象棋程序的设计与实现上，建立一个完整的中国象棋计算机博弈系统，研究工作主要集中在以下几个方面1、棋盘表示与走法生成从操作速度性能以及使用方便与否考虑，本象棋博弈系统从带位行位列信息的扩展棋盘棋子联系数组着手进行研究。然后根据棋盘表示获得所有棋子的走法预生成数组。在产生走法时直接从中取出数据，进行少量判断以得到该棋子的合法走步。2、估值函数如何快速有效的对一个局面进行评估需要从速度和知识的两个角度进行考虑一般知识越多估值越准确，但速度也慢下来。本系统采用通用的静态估值方式，同时在估值时结合走法预生成数组，使估值的速度有很大提升。3、搜索技术博弈树搜索技术它很大程度上独立于具体的计算机博弈程序。本文讨论了剪枝搜索算法及其各种增强手段包括窗口原则、置换表内存增强；历史启发表节点顺序调整；迭代深化时间控制等。如何把各种增强手段有机组合起来达到最优，文章对基于迭代加深、置换表、历史启发的NEGASCOUT算法进行改进。15论文结构第一章阐述了选题背景，课题的国内外研究现状及课题的主要工作和文章的章节安排。第二章第一部分首先介绍中国象棋程序的一些基本数据结构，着重研究了扩展的棋盘棋子联系数组棋盘；在此基础上实现所有棋子的走法预生成数组，以提高搜索过程中走法产生的效率。第二部分研究本系统的着法生成，包括预置表法和模板匹配法，进一步提高了搜索效率。第三部分描述本系统的评价函数架构，着重描述了静态估值方法，分析了其不足，并提出了解决之道。包括子力分数、子力灵活度评价、棋盘控制等并与走法预生成数组结合以提高估值速度。第四部分实现了博弈树的剪枝算法并简要介绍各种搜索策略。第五部分阐述了开局库的设计原理。第三章给出实验环境和程序实现。第四章是全文的总结及展望。2系统的分析和设计21数据结构（DATASTRUCTURE）数据结构是一个程序的骨架，选择一种好的数据结构可以使程序的运行效率大大提高。211棋盘的基本表示法（BOARDREPRESENTIONS）棋盘表示就是使用一种数据结构来描述棋盘上的信息，以便程序知道博弈的状态。棋盘的数据表示直接影响到程序的时间及空间复杂度。为了追求更高效率，研究人员针对中国象棋提出了多种不同的表示方法。中国象棋的棋盘表示中最典型的是用一个109的二维字节BYTE数组，数组中每个元素代表棋盘上的一个交点，其值表明这个交点上放置的是一个什么棋子或是没有棋子从棋子的角度考虑，如果把棋盘看成是一个平面坐标系，可以知道每一个棋子的位置信息小于10的横坐标和小于11的纵坐标又在棋盘上最多32个棋子，故可以用一个32个字节的一维数组表示所有32个棋子的位置，其中每个字节的高4位表示该棋子的横坐标，低4位表示棋子的纵坐标。而己被吃掉的棋子用坐标范围以外的数表示。这样棋盘信息就被装入这32个字节中。当然也可以把棋盘看作一维的，每个元素保存直接的位置信息。两种棋盘表示方法一是做一个棋盘数组；二是做一个棋子数组。棋盘数组中由棋子的位置获得棋子的类型可以在常数时间内完成，但由棋子的类型获得棋子的位置需要遍历；在棋子数组中由棋子的类型获得棋子的位置可以在常数时间内完成，但由棋子的位置获得棋子的类型操作繁琐。如果一个程序同时使用这两个数组，那么获得棋子的类型和棋子的位置都可以在常数时间内完成。这就是“棋盘棋子联系数组”，它的技术要点是L同时用棋盘数组和棋子数组表示一个局面，棋盘数组和棋子数组之间可以互相转换。2随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。在棋盘上删除一个棋子，需要做两个操作分别修改棋盘数组和棋子数组。同样，添加一个棋子时也需要两个操作。“棋盘棋子联系数组“最大的优势是对于着法产生过程，可以逐一查找棋子数组，如果该子没有被吃掉，就产生该子的所有合理着法，由于需要查找的棋子数组的数量每方只有16个棋子能走比棋盘格子的数量90个格子少得多，因此联系数组的速度要比单纯的棋盘数组快很多。同时“棋盘棋子联系数组”是很多改进的棋盘的基础。212改进型棋盘结构在计算机上面，位运算比一般的加减乘除及取余运算快得多。如果能在寻找棋子和定位棋子上使用位运算代替加减乘除和取余，这将很大程度上提高运算速度。所以，人们把“棋盘棋子联系数组“进行扩展把棋盘做成1616的大小，这样得到行号可以用16除，得到列号可以对16取余（和15进行运算），这比除以10和对9取余操作要快得多。如图21（红色格子都被标上“出界”的标志，目标格在这些格子上就说明着法无效）图21扩展的棋盘这种棋盘的更大的好处是1它可以防止棋子走出棋盘边界。由BOOL型棋盘数组（属于棋盘的位置为TRUE，否则为FALSE），判断棋子是否走出棋盘边界只要返回该数组对应的值即可，速度快。2对于是否在城池内可以用BOOL型城池数组判断，因为是否在城池内的判断会非常频繁，直接用该数组会很高效。3判断是否过河的方法非常简单只要设定特定的表达式，当表达式为假表示已过河，否则没过河。4还可以非常方便的判断棋子是否在己方。22着法生成（MOVEGENERATION）着法生成就是要产生所有有效的着法，让电脑棋手在这些着法中选择最好的着法，并判断人类棋手是否符合走棋规则。着法生成是博弈程序中一个相当复杂而且耗费运算时间的方面，要生成所有着法只能用穷举。中国象棋大约每一步可以有45个着法。通过良好的数据结构和走法预生成，可以显著地提高生成的速度。221模板匹配法当动子确定以后，其“落址”和“提址”的相对关系便确定下来了，这样可以为某些动子设计其着法生成的“模板”，只要匹配到提址，便可以迅速找到落址。图23给出了马的匹配模板。图22马的匹配模板将马对准提址，“O”表示符合“马走日”规则的落址，“X”表示“蹩马腿”的制约条件，通过查找模板匹配数组，实现“本方子则止，对方子则吃”，完成“提动落吃”内容的确定。对马的着法生成使用模板匹配法时，只要写出符合马行棋规则的模板匹配数组和马腿的模板匹配数组，在生成着法时通过查找这两个数组就可以实现。显然，这比扫描整个棋盘，通过计算得到合法落址要快速的多。同样的，可以对象、将、士、卒使用模板匹配生成着法。222预置表法它是把所有可能的着法预先存储起来，在生成着法时，用查表取代计算。中国象棋每种棋子的行棋规则不同，生成每种棋子的着法和整个棋盘棋子的分布密切相关，如果建立每种棋子最大可能着法的小型数据库，用查询取代复杂的判断，那么也可以在很大程度上加快着法生成的速度。预置表看起来似乎很大，但是只需在程序开始运行时初始化一次就可以了，这些耗费对整个程序的影响不大，但是对着法生成的作用却是非常明显的。图23即是以路向行向比特向量为索引的一个车的预置着法表的生成范例。图中显示，该车位于某行第4列，棋子分布的布尔向量形式为010100100，可以看出，此时车可能的吃子着法落址为010000100，非吃子着法的落址为F0010110001。把车的列号和该行棋子的布尔分布作为输入，把吃子落址和非吃子落址作为输出，将输入和输出的关系写入一个预置表中，在使用时通过查表，就可以快速构成可行着法，而且可以区分开吃子着法和非吃子着法。如图23所示图23车的着法预置表范例23局面评估局面估值就是通过既有的棋类知识来评估一个局面优劣的过程。从象棋的棋力上考虑，在搜索之外，局面估值是最重要的部分，因为对实际局面的评价的好坏，影响着今后局势发展的趋势。这一过程对具体的棋类知识依赖程度很深，但是仍有一般性的规律可循。目前在计算机象棋博弈中常用的估值方法主要采用静态估值方法。同时由于随着搜索层数的加深，叶子节点的数目迅速上升，估值函数被数以百万次的调用，花费大量的运算时间，如何提高估值函数的速度，也成了博弈性能改进的重要话题。下面分别从这两个方面及其关系介绍局面评估。231估值函数（EVALUATIONFUNCTION）本系统的估值函数包括棋子固定价值，棋子位置附加值，棋子灵活性，棋子对棋盘的控制，棋子间的关系几部分。棋子固定价值指的是对棋盘中的每一个棋子，根据它的重要性和走法的丰富程度赋予其一个特定的值。在棋盘上，棋子多者占优，棋子少者为劣。根据经验，可以让一个车价值为500，一个马价值为300，一个兵价值为100等等。在中国象棋的对弈中，由于一般以将死对方的将帅作为结束，因此，通常赋值的规则是为将帅赋予一个远大于其他棋子的子力之和的值。可以用下面的表达式求某一方的棋子固定值SIDEVALUESUMPIECENUMPIECEVALUE；其中PIECENUM是某种棋子的数量，PIECEVALUE是该种棋子的价值，SUM是对各种棋子的总价值求和。如果红色的棋子价值总和大于黑色的棋子价值总和，通常这意味着红方的局势优于黑方。而红黑双方的SIDEVALUE之差越大，红方的优势也就越大。同样的棋子在不同位置上起的作用是不同的，最明显的是兵卒过河之前与之后它的作用和攻击力以及对对方的威胁显然是不一样的，而当兵卒一旦到了底线附近，它对将帅的威胁度将大大下降。棋子灵活性描述的是棋子的活动范围，即棋子向各处调动的可能性大小。棋子的威力能否充分发挥，与灵活性直接相关。本方棋子可以走的点越多，说明本方棋子的灵活性越大。例如车在纵横线上遇到障碍物、马被周围棋子绊脚等，都降低了灵活性，也降低了威力的发挥，灵活性的计算是把棋子在棋盘上所能够移动到达的位置数作为灵活性计算，给予评分。可以用下面的表达式求某一方棋子灵活性MOBILITYSUMMOVENUMMOVEVALUE；其中，MOVENUM是某种棋子的合法走法数量，MOVEVALUE是该种棋子每一走法的价值，SUM是对所有棋子的灵活性价值求和。MOBILITY就是所有棋子的灵活性分数。一方对棋盘控制的棋盘区域越多，那么他就越具有主动性。在象棋中，如果一位置落在某方棋子的合法走步上，就可以认为被该方控制。如果某一位置同时落在双方的合法走步上，可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣。能控制更多位置的一方应在这项评分上占优。在中国象棋博弈中，每个棋子都不是孤立存在的，他们之间构成了各种相互关系。如棋子1下一步将被吃掉，则应该给一个负的附加值。而如果周围有己方棋子对其进行了保护，也就是说，对方在理智的情况下不会去吃棋子1，那么棋子L没有受到威胁，价值不变。棋子关系的评估应考虑到该谁走棋的问题。如果某个红马落在黑炮的合法走步之内，但此时轮到红方走棋，应认为红马受到的威胁较轻。而如果此时轮到黑方走棋，就应认为红马受到的威胁很大，应减去一个相对较大的值了。232估值的速度与博弈性能开发人员可以向估值函数加入大量的棋类知识，使之对于局面的评估更为精确。但是，博弈系统的性能，速度，棋类知识一般满足下面的关系PERFORMANCE性能SPEED速度KOWLEDGE知识且向估值函数加入越多的棋类知识，估值函数的速度也就越慢，因为所要进行的计算也相应增加。因此过于简单的估值函数和过于复杂的估值函数同样性能不佳。在同等的知识含量下，速度越快，性能越高。在同等速度之下，知识量越大性能越高。在速度和知识量二者的相互作用下，开发者要寻找的是一种平衡，是能够使性能最大化的速度和知识量。使用终点估值ENDPOINTENVALUATION，意思是当叶子节点到达时，使用估值函数对一个局面进行评估。这样的方法思路清晰，容易设计，而且模块间独立性高，同搜索算法的耦合度很低。可以轻易的更换估值函数，只改动极少的代码；你也可以随意使用任何估值方法来评估整个棋盘，最终给出估值，但这种方法的速度较慢。233估值函数的优化目前最长使用的是优化估值参数的方法是利用大量的测试局面进行手工调整，也是本文在优化评估函数时主要使用的手段。这种方法是利用人类的象棋经验知识来调整参数值，比如，从经验上可以知道，一个车的价值要比一个兵大，给车赋予比兵大的数值，马炮则赋予位于其间的值马和炮的地位相当，给予它们相当的数值，以避免盲目换子；如果对弈中使用了一些优秀的战术配合，那么就给予一定数值的奖励，等等。将这些经验放进评估函数中反复对弈，然后不断修正参数，找出一组性能较高的参数。1规格化NORMALIZE如果只是关心评价的顺序，而不怎么关心评价值，那么可以把每一项都乘以同样的常数。这就意味着，对某个特定的模块，例如兵的价值，可以硬性设一个值，其他值就可以表示成它们相当于多少个兵。这个做法可以减少一个需要设定的参数。2约束法DEDUCECONSTRAINTS通过考虑希望电脑作出怎样的判断，就可以确定一些参数。例如在对弈中即使赚到一个兵，用车换象或马还是坏的，但如果能赚到两个兵那还是好的，因为在考虑子力价值是要防止换单兵，鼓励换双兵。这样的条件越多，合适的权重组合就越少。在开始设定权重值的时候，这个方法通常可以得到合适的值，但是在后面仍然需要做一些调整。3交手法HANDTWEAKING这是调整评估函数时非常常用的方法，通过让程序对弈，来找到它的优势和弱点，猜测哪些参数会让程序更好，然后挑选新的参数。这个方法可以很快得到合理的结果，但是需要对棋类知识有足够的了解，便于根据程序的对局来做分析，从而知道程序的问题在哪里。手工调整是象棋引擎调整估值参数的主要手段之一，把人类的知识和经验尽量准确客观地“教授”给计算机，是提高棋力的普遍做法，虽然比较费时，但是很有效。通过不断的试验、修改参数值，可以得到不错的结果。但是人类的知识毕竟具有一定的局限性，评估函数也不能包含所有情况，参数之间往往又互相联系，调整某个参数可能解决了某类问题，但又可能给其它问题的解决带来麻烦，在这种情况下很难实现全局下的最优组合。还有一种主要的优化方法是机器自学习1爬山法HILLCLIMBING爬山法通过对参数进行小范围的试探来寻找最优解，一次只能对参数作一点小改变，然后测试博弈程序的性能是否提高了，仅当性能提高时才采纳这个改变，需要重复很多次。这种方法很慢，并且受初始采样值的限制，很容易陷入局部最优，即评价可能很差，但是任何很小的改变都会使评价更差。2模拟退火SIMULATEDANNEALING模拟退火是一种基于蒙特卡罗MONTECARLO算法的启发式随机搜索算法，它没有蒙特卡罗算法多次寻优的过程，也不像爬山法那样依赖初值。在优化参数时，类似于爬山法，模拟退火法也是对权重做改变来提高成绩，如果所做的改变没有提高成绩，也会根据一个随机的几率采纳这个改变，试图跳出局部最优。这个方法需要给定一些几率，从几率高、梯度大的条件开始，然后逐渐减小。模拟退火法比爬山法更慢，是最终可能得到比较好的值。3遗传算法GENETICALGORITHM，GA遗传算法是建立在自然选择和自然遗传学机理基础上的迭代自适应概率性全局优化算法，因其模仿生物的遗传机制而得名，最早由美国密执安大学JHHOLLAND于1975年提出，它通过染色体的复制，交叉，变异等操作，实现个体适应性的提高。遗传算法可以同时维护多组较好的参数，通过向其中添加一组新参数，通常是将从几组老参数中选出的值组合在一起作微小的变化，然后同几组老的参数比较孰优孰劣，将最坏的一组去除。遗传算法是从几组参数开始，而不是一组参数，具有很好的全局搜索能力，搜索速度也很快，而且此算法能将搜索重点集中于性能高的部分，能较快地求出最佳参数，鲁棒性也明显优于前两种算法，所以在计算机博弈中最有可能取得成功。24博弈树搜索技术中国象棋博弈树非常庞大，完全建立博弈树是不可能的，唯一的解决方法就是让博弈树扩展到计算机运算可以接受的深度，然后对没有分出胜负的叶子节点给出一个尽量准确的打分，表示此局面下取得胜利的可能性，这个打分是由评估函数计算给出的，将搜索树展开是着法生成的功能，而搜索引擎则是尽可能缩小树的规模，避免一切冗余的计算，这也是计算机博弈中搜索引擎研究的重点。根据搜索策略，目前应用于计算机博弈的搜索算法一般可分为三类L穷尽搜索EXHAUSTIVESEARCH，这种搜索是没有抛弃任何可能成为最佳路径的搜索，不存在风险，得到的最佳走法肯定是在现有评估函数下应该得到的，例如极大极小值搜索、剪枝搜索及其变种等。2选择性搜索SELECTIVESEARCH，即裁剪搜索，这种搜索略去对一些着法的搜索，冒着有可能漏掉最佳走法的风险，而换来局部更深的搜索深度。中国象棋中最常用裁剪算法是空着裁剪NULLMOVE等。3启发式搜索HEURISTICSEARCH利用象棋领域的知识启发信息设计搜索算法，着重对走法排序，以简化和加快搜索过程。中国象棋中的启发算法有历史启发、杀手启发、置换表等。241基本搜索算法极大极小值方法MINIMAXALGORITHM是解决博弈树问题的基本方法。香农教授早在1950年首先提出了“极大极小算法”，奠定了计算机博弈理论的基础。极大极小值算法的原则是博弈双方所要达到的目的相反，一方要寻找的利益是另一方失去的利益，博弈的一方总是希望下一步是子节点中取值最大者，而另一方希望下一步是子节点中取值最小者。在象棋博弈中，极大极小值算法体现在始终站在博弈一方的立场上给棋局估值，有利于这一方的棋局给予一个较高的价值分数，不利于这一方有利于另一方的给予一个较低的价值分数，双方优劣不明显的局面给予一个中间值分数。在这一方走棋的时候，选择价值最大的子节点走法，即实行“MAX搜索”，另一方走棋则选择价值最小的子节点走法，即实行“MIN搜索”，这就是象棋博弈中的一个极大极小过程。例如，如果红方为走棋方，它在偶数层的着法选择是要在其全部子节点中找到评估值最大的一个，实行“MAX搜索”，称为MAX方，而其敌对方即黑方在奇数层的着法选择则是在其全部子节点中要找到评估值最小的一个，实行“MIN搜索”，称为MIN方。图24表示了一个极大极小搜索过程，粗箭头为最佳路径片段。图24极大极小值算法示意图由于完整的博弈树过于庞大，程序不能也没有必要搜索整棵博弈树的所有节点，而需要像人类棋手一样有选择性地进行搜索，对于一些已经确定不佳的走步可以将以它根节点的子树剪掉CUTOFF/PRUNING，以提高单位时间内搜索的节点数。上述极大极小值搜索过程中，遍历了整个的博弈树，这样的搜索算法效率低，搜索量非常大，如果要减少搜索量，又可能影响搜索效果。但假如将叶节点的评估计算与树的展开同时进行，然后对博弈树进行必要的裁剪，就可能大量减少所需搜索的节点数目，并且保持搜索效果不变。这个技术叫剪枝搜索。它是一种基于搜索的深度优先搜索，是所有剪枝算法的基础，它是根据极大极小搜索规则进行的。图25和图26给出两个剪枝示意图MAXMINMAX图25剪枝示意图MINMAXMIN图26剪枝示意图在图25所示的极大极小树片段中，按照极大极小值搜索规则，从左路分枝的叶节点倒推得到第一层MAX节点的值为5，可表示此时的着法最佳值，记为，显然此值可作为MAX方着法指标的下界。在搜索中路分枝时，因为第二层着法的选择是取第三层节点的最小值，即取M州8，3，“”，而无论“”中为何值，都不会比5大最大为3，故可以将“”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。同理搜索右路分枝，也可以进行剪枝操作。此类剪枝称为剪枝。图25中通过剪枝，最后得到如粗箭头所示的最佳路径片断。图26所示的极大极小树片段中，由左路分枝的叶节点倒推得到第一层MIN节点的值为N，可表示此时对方着法的钳制值，记为。显然此值可作为MIN方可能实现着法指标的上界。在搜索中路分枝时，因为第二层着法的选择是取第三层节点的最大值，即取MAX5，12，“”，而无论“”中为何值，都不会比11小至少为12，故可以将“”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。同理搜索右路分枝，进行剪枝操作。此类剪枝称为剪枝。图27中通过剪枝，最后得到如粗箭头所示的最佳路径片断。剪枝搜索能够让我们省略许多节点的搜索，不只是节点本身，而且包括节点下面的子树，这样剪枝搜索需要遍历的节点数远少于极大极小算法所遍历的节点，也就节省了大量的时间开销，并且仍不失为穷尽搜索的本性，但剪枝的剪枝效果即搜索节点数与博弈树节点的搜索次序密切相关。242高级搜索算法极大极小值搜索是所有搜索算法的基础，而剪枝搜索是所有剪枝算法的基础。但在实际的博弈系统设计中，要提高程序的搜索速度和搜索深度，还必须利用搜中得到的一些启发式信息来加快搜索，目前己经有很多对基本搜索算法的增强算法。在剪枝搜索中，剪枝效率几乎完全取决于节点的排列顺序，如何调整待展开的走法的顺序，是提高搜索效率的关键。在搜索的过程中，往往有一些启发性的信息可以利用，如果利用这些信息在相似的局面下对走法进行优化排序，或者对相同的局面不再搜索，而直接返回以前搜索的结果，都会对搜索产生明显的加速作用。围绕着法排序，己经出现了许多优秀的搜索算法与举措，例如历史启发，杀手启发，置换表等等。历史启发HISTORYHEURISTIC实际上就是记录搜索过的好的走法，并在后续着法中优先搜索。根据经验，一些以前经过搜索认为最佳的走法，其后续走法仍然有很大可能成为最优的走法。在搜索过程中，每找到一个好的着法，就将与该走法相应的历史得分作一增量，一个多次被搜索并确认为好的走法的历史记录分值会较高，当搜索中间节点时，将走法根据其历史得分排序，以获得较佳的排列顺序。杀手启发KILLERHEURISTIC是基于这样的思想在搜索过程中，有许多走法一经搜索就引发了剪枝，且这些走法通常是同一个走法，这样，为每一层记录引发剪枝最多的走法即杀手走法，当下一次搜索到同样的深度时，如果杀手走法是该局的一个合法走法，就优先搜索杀手走法。杀手启发是一种特殊的历史启发，它不依赖于人类的知识，具有普遍性。置换表TRANSPOSILIONTABLE是用一张表把搜索过的信息记录下来，在后续的搜索中，察看记录在表中的这些信息，如果将要搜索的某个节点已经有记录，就直接利用记录下来的结果引入到当前的搜索中，以减少搜索。置换表不同于历史启发表和杀手表，不必在每次搜索之前都清空，而是一直维持这些数据，作为以后搜索的信息。另外，空着搜索NULLMOVE也是搜索算法中一种很有效的搜索策略，它的思想是放弃本方的走棋权利，让对方连续走棋，如果得到的分数还大于原来的值，就可以简单地返回值，在此分枝下的搜索意义不大，免于搜索。空着搜索明显降低了搜索的数量，导致搜索深度显著提高，并且危险性比较小，实现较为简单。25开局库设计中国象棋的开局变化极多，每一种走法都能产生出一种新的变化，单就中炮对屏风马、中炮对反宫马、中炮对左三步虎等数十种变化，其格个开局又都有自身的变化，这些开局都遵循开局的规律“明车”，即车路要通“活马”，即马与兵阵的配合合理，使马能有活动的空间“好炮位”，即炮要占住子力疏密适中的要点，封锁对方进攻路线，配合其他子力展开进攻。另外当进行快棋赛时，棋手还会选择一些冷门开局，使局面很快“脱谱”，迅速进入到中、残局。所以中国象棋开局阶段是整个对弈过程中变化最多的阶段，开局的好坏对之后的中、残局意义重大。251开局库的作用象人们记住开局招数一样，博弈程序使用一个数据库，里面储存了开局谱着和局面，于是当对局（开局）中的棋步在开局库中能找到时，它就可以立即取出来走，不用计算。无庸多说，这对于程序节省思考时间有重大帮助。这对于整个博弈系统来说有三点好处一是防止战略性错误；二是形成较为稳妥和有利的局面；三是节省了大量的搜索时间。但另一方面，如果开局库本身不好或部分不好，程序也可能被盲目引到劣势的局面甚至很快失利。所以如何设置一个比较好的开局库，就成了程序设计中不可或缺的部分。252实现开局库的主要方法实现开局库的方法一般有两种一种是用FEN的形式表示的开局库；另一种是哈希值表示的开局库。用FEN串表示开局库的方法比较简单，该方法仅仅是将开局库中的存储的棋盘状态与当前棋盘的状态进行比较，若相同，则程序根据库中的走法走一步。下面我们来看看什么是FEN串。1FENFEN就是“福斯夫爱德华兹记号法”（FORSYTHEDWARDSNOTATION），这是一种使用ASCII码字符描述国际象棋局面的标准。FEN是建立在19世纪由报社记者SD福斯夫设计的记录局面的标准基础上的。后来为了适合象棋软件的需要，由爱德华兹对此做了少许修改。一份标准的局面记号对需要大量交换共享局面数据的国际象棋程序设计等工作具有尤其重要的作用。2结构描述一个FEN记录使用长度可不同的一行来表示，由六个区域组成。单纯的FEN记录文件后缀应该是“FEN”，比如KK1FEN，在中国象棋开局库的FEN串形式的开局库文件后缀为DAT。FEN描述了棋子位置、轮走棋方、易位可行性、吃过路兵目标格、半步计数、以及总回合数。所有这一切用一行文字符号表示就行了而且非常容易读。看看一个FEN的五个区域及其含义，以中国象棋为例RNBAKABNR/9/1C5C1/P1P1P1P1P/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNRW01这就是每盘常规对局的最初局面，一个子都没有动，如图27图27象棋初始局面3棋子位置数值区域（PIECEPLACEMENTDATA）就是表示双方棋子各在棋盘哪个格子上的。规则是从第10横线开始顺序数到第1横线红方在下，从上数到下，从A线开始顺次数到H线；红方棋子以大写字母“RNBAKABNR”功表示，黑方棋子以小写“RNBAKABNR”表示，这是英文表示法，每个字母代表的意义与常规规定相同。数字代表一个横线上的连续空格，反斜杠“”表示结束一个横线的描述。上面的那P1PLP1PLP，就是表示黑方在第7横线上排有5只兵；后面那两个数字9，就是表示从第6到第5横线，双方一个棋子都不在，是空格；9个反斜杠“”将第一区域分成8段，因为棋盘有10条横线；其它的照着图完全可以类推。4轮走棋方（ACTIVECOLOR）表示目前局面谁该走棋。小写“W”表示红方走棋；小写“B”表示黑方走棋；因为起初局面是红先，所以上面就是“W”5吃过路兵目标格（ENPASSANTTARGETSQUARE）如果没有，就用“”表示。如果有，就用具体完成吃过路兵的那个格子坐标表示，显然对于白兵被吃只可能在第3横线，对于黑兵被吃只可能在第6横线。而且，这个标记是且只是在该局面紧接的上一步棋是某方刚走兵推进两格的情况下出现。6半回合数（HALFMOVECLOCK）用一个非负数表示自从上一次动兵或吃子之后目前走了的半回合数。这个是为了适应50步和棋规则而定。7回合数（FULLMOVENUMBER）当前要进行到的回合数。不管红还是黑，第一步时总是以1表示，以后黑方每走一步数字就加1。用哈希值开局库的文件的后缀通常为“BIN”。这种方法是使用置换表来统计开局库中的一些走法的优劣。与搜索引擎中的置换表类似，开局库也是用表示局面的哈希值除以开局库的大小作为索引，而表示局面的哈希值作为校验。虽然二者查询的形式完全相同，但是存储的内容却大不相同。置换表存储的内容主要用于搜索，开局库存储的内容主要是走法的权重、输赢比率，用于选择最佳的走法。它只存放某局面的一个哈希值以及对应的走法。这也意味着ZOBRIST哈希所要使用的随机数组，不能临时产生，而要包含在开局库当中。对于当前局面，查询数据库的函数使用库中的随机数组计算出其哈希值，然后在库中察看是否有此值所代表的局面。此种开局库的实现方法A查询当前局面开局库中存储的哈希值表示的是当前局面，查询到开局库中所储存的各种走法，并在各种走法中随机提取一个走法执行，走法选择的几率与其权重成正比。B查询后续局面这种开局库查询是与搜索结合在一起的，并不是查询当前局面是否在开局库中，而是展开根节点的所有走法，也就是当前局面下所有可能走法。3系统的实现31系统的整体规划整个智能象棋系统将要实现的主要功能是人人对战、人机对战、制作棋谱、演示棋谱、挑战英雄榜等，而其中的各个功能又分为几个小功能模块，该系统的功能结构图如图31所示用户界面对弈制作棋谱演示棋谱挑战英雄榜人人对战人机对战保存自动播放上一步下一步输入姓名并保存悔棋图31功能结构图32象棋界面的实现本系统要实现一个象棋游戏系统，界面是必不可少的部分。界面的设计是供用户与电脑进行交互，无论是人机对战还是制作、演示棋谱都是在界面中实现的。运行完成的程序，本系统界面如图32所示图32象棋系统界面界面的实现分为棋盘的表示和棋子的表示两部分，棋盘和棋子通过数组连接起来，形成一个完整的界面系统。首先定义一个棋子类（CHESSPIECE），来获取棋子的颜色以及类别PUBLICCLASSCHESSPIECEEXTENDSJLABELSTRINGNAMECOLORBACKCOLORNULL,FORECOLORSTRING颜色类别NULLCHESSBOARDBOARDNULLINTWIDTH,HEIGHTPUBLICCHESSPIECESTRINGNAME,COLORFC,COLORBC,INTWIDTH,INTHEIGHT,CHESSBOARDBOARDTHISNAMENAMEFORECOLORFCBACKCOLORBCSETSIZEWIDTH,HEIGHTSETBACKGROUNDBCADDMOUSEMOTIONLISTENERBOARDADDMOUSELISTENERBOARDPUBLICVOIDPAINTGRAPHICSGGSETCOLORFORECOLORGFILLOVAL2,2,WIDTH2,HEIGHT2GSETCOLORCOLORWHITEGSETFONTNEWFONT“隶书“,FONTBOLD,28GDRAWSTRINGNAME,7,HEIGHT8GSETCOLORCOLORYELLOWGDRAWOVAL2,2,WIDTH2,HEIGHT2PUBLICINTGETWIDTHRETURNWIDTHPUBLICINTGETHEIGHTRETURNHEIGHTPUBLICSTRINGGETNAMERETURNNAMEPUBLICCOLOR获取棋子颜色RETURNFORECOLORPUBLICVOIDSET棋子类别STRING类别颜色类别类别PUBLICSTRING棋子类别RETURN颜色类别然后在棋盘类（CHESSBOARD）里定义棋盘的表示、棋子的类别、颜色以及棋子在棋盘上的位置表示/棋盘的表示/PUBLICVOIDPAINTCOMPONENTGRAPHICSGSUPERPAINTCOMPONENTGFORINTJ1JGENERATEPOSSIBLEMOVES/有效着法的生成LISTRETNEWARRAYLISTFORINTX0X9XFORINTY0Y10YINTCHESSMANCHESSBOARDXYIFCHESSMAN0IFISREDGOIFISREDGOSWITCHCHESSMANCASE7IFISVALIDMOVEX,Y,X,Y1RETADDNEWMOTIONCHESSMAN,X,Y,X,Y1,0IFISVALIDMOVEX,Y,X,Y1IFISVALIDMOVEX,Y,X1,YIFISVALIDMOVEX,Y,X1,YFORINTOPPJIANGY7OPPJIANGY10OPPJIANGYBREAKPUBLICCLASSSEARCHENGINE/AI搜索算法PUBLICSTATICFINALINTWIN54PUBLICCHESSBOARDSITUATION/棋盘的当前情况PUBLICMOTIONBESTMOTION/按最佳移动方法搜索PUBLICSTATICINTSEARCH_DEPTH5SEARCHENGINEINSTANCEINSTANCENEWSEARCHENGINENEWSITUATIONLONGSTARTTIMESYSTEMNANOTIMEINSTANCEBASICALPHABETASEARCHSEARCH_DEPTH,WIN,WIN/剪枝34制作和演示棋谱的实现为了满足用户更好的学习中国象棋的需要，本系统实现了制作和演示棋谱的功能。制作棋谱的功能是在MAKECHESSMANUAL类里来实现的PUBLICCLASSMAKECHESSMANUALEXTENDSJPANELIMPLEMENTSACTIONLISTENERPUBLICMAKECHESSMANUALCHESSBOARDBOARD,CHESSPOINTPOINTTHISBOARDBOARDTHISPOINTPOINTTEXTNEWJTEXTAREASCROLLNEWJSCRO