基于qt的中国象棋游戏界面设计与实现

毕业设计（论文）任务书毕业设计（论文）题目基于QT的中国象棋游戏界面设计与实现毕业设计（论文）要求及原始数据（资料）1综述中国象棋的软件开发研究现状；2深入了解中国象棋软件开发的相关技术；3熟练掌握基于QT软件的应用与分析，训练编写程序的能力；4设计并实现中国象棋中有特色的界面；5深入分析中国象棋中的网格界面；6训练检索文献资料和利用文献资料的能力；7训练撰写技术文档与学位论文的能力。此处内容须和自己的设计一致，但最后两条必须包含。毕业设计（论文）主要内容1综述中国象棋的软件设计与开发；2了解基于QT的相关软件；3熟悉基于QT各类软件的开发环境；4设计中国象棋中各个棋子不同的走法算法；5深入分析中国象棋中棋子走法与设计流程；6熟练掌握基于QT平台关于中国象棋的语言编写；7设计与实现针对中国象棋的插件的程序。学生应交出的设计文件（论文）1内容完整、层次清晰、叙述流畅、排版规范的毕业设计论文；2包括毕业设计论文、源程序等内容在内的毕业设计电子文档及其它相关材料。此处为统一内容，无需修改。此处内容须和自己的设计一致此处内容须和自己的设计要一致主要参考文献（资料）1FANGHRCHINESECHESSENDGAMEDATABASEANDRELATEDAPPLICATIONS19962张红军计算机中国象棋界面和搜索引擎的设计与实现西安理工大学,20093于超博弈算法在中国象棋上的应用D中国海洋大学20114高强一种混合博弈树算法在中国象棋人机博弈中的应用研究D大连交通大学20075谢艳茹中国象棋计算机博弈数据结构与评估函数的研究和实现D西安理工大学20086任建敏中国象棋软件开局库和着法生成器的研究D燕山大学20127郭峰中国象棋计算机博弈中的判别剪枝搜索研究D河北大学20098CLAUDEESHANNONPROGRAMMINGACOMPUTERFORPLAYINGCHESSPHILOSOPHICALMAGAZINE19509CHENJRCHINESECHESSOPENGAMEDATABASEDESIGN1997专业班级软件1021班学生要求设计（论文）工作起止日期2014年3月17日2014年6月27日指导教师签字日期2014年3月17日教研室主任审查签字日期系主任批准签字日期这两个日期不要修改基于QT的中国象棋游戏界面设计与实现摘要象棋程序的实现可以被分为人工智能和界面程序辅助两大部分。人工智能部分主要体现计算机的下棋思路，既计算机如何进行思考并以最佳走法完成下一步，先由相应的搜索算法进行搜索，并对各种可能的走法进行估值，从中选择胜利面最大的一步；而界面及程序辅助部分主要便于用户通过以前的下棋步骤，更好地调整下棋思路，着法显示使用户能够清楚地知道下棋过程，更准确地把握整个局面。本文首先研究了中国象棋在计算机中的表示问题，接着讨论如何产生着法一系列相关内容。其次研究了博弈树的极小极大搜索技术及在此基础上发展起来的ALPHABETA剪枝算法，使用GUI文档视图体系结构和QT开发工具，实现了一个具有一定棋力的中国象棋人机对弈程序。关键词中国象棋；人工智能；博弈树；ALPHABETA搜索DESIGNANDIMPLEMENTATIONQTBASEDCHINESECHESSGAMEINTERFACEABSTRACTACHIEVECHESSPROGRAMCANBEDIVIDEDINTOARTIFICIALINTELLIGENCEANDINTERFACEPROGRAMSASSISTEDTWOPARTSAICHESSIDEASEMBODIEDSOMEOFTHEMAJORCOMPUTER,BOTHCOMPUTERSTOTHINKANDHOWBESTTOTAKETHELAWTOCOMPLETETHENEXTSTEP,FIRSTSEARCHALGORITHMTOSEARCHAPPROPRIATE,ANDTHEVALUATIONOFTHEVARIOUSPOSSIBLEMOVES,CHOOSEVICTORYBIGGESTSTEPSURFACEWHILESOMEMAJORINTERFACEANDUSERFRIENDLYPROGRAMASSISTEDBYFORMERCHESSSTEPSTOBETTERADJUSTCHESSIDEAS,AMETHODTODISPLAYENABLESTHEUSERTOKNOWTHEPROCESSOFCHESS,MOREACCURATELYGRASPTHEWHOLESITUATIONFIRSTLY,THATTHEPROBLEMSTUDIEDCHINESECHESSINTHECOMPUTER,ANDTHENDISCUSSHOWTOGENERATEASERIESOFLAWSRELATEDCONTENTSECONDLYSTUDIEDMINIMAXGAMETREESEARCHTECHNOLOGYANDDEVELOPEDONTHEBASISOFALPHABETAPRUNINGALGORITHM,USINGTHEGUIDOCUMENTVIEWARCHITECTUREANDQTDEVELOPMENTTOOLS,IMPLEMENTSAMANMACHINECHESSCHINESECHESSPLAYINGSTRENGTHOFACERTAINPROCEDURESKEYWORDSCHINESECHESS；AI；GAMETREE；ALPHABETASEARCH目录摘要IABSTRACTII绪论1一、系统概述311软件用途312游戏特色513系统开发过程514AI代码阅读提示5二、系统需求说明621系统总体功能622环境需求623系统功能需求6三、系统设计831系统设计决策832系统总体设计9321设计思想9322系统体系结构10323系统动态行为1833用户界面设计1834系统部件2035系统出错处理设计3336后续可能的更新33总结34参考文献35致谢36外文文献37中文翻译48绪论选题的意义中国象棋在中国拥有悠久的历史，这个游戏需要两个人进行对弈。由于中国象棋用具简单、趣味性强，成为流行极为广泛、老少皆宜的棋艺活动。中国象棋是一种古老的文化，它集文化、科学、艺术、竞技于一体，有利于开发人的智慧，锻炼人的思维，培养人的毅力，增强人的竞争意识。随着电脑技术及互联网的发展，人们下棋没有了地域限制，人们甚至可以跟电脑对战，于是就产生了人是否能够战胜电脑的疑问。从很早开始，人们就开始进行棋类博弈的游戏了，而在人工智能领域，机器博弈始终是一个重要的组成部分。人们对人工智能的窥探是从棋类博弈游戏开始的，人们在博弈游戏中，对战双方通过对游戏规则的掌握、丰富的经验和知识，使游戏的局面有利于自己，这就是人类的思维过程，于是棋类博弈就成了人工智能的实验品。对机器博弈的研究取得的成果不仅仅只用在棋类游戏上，而且也已广泛应用于军事、政治、经济等多个领域，给人类带来了极大的社会效益。国内外研究现状概述机器棋类博弈的研究最早是从国际象棋开始的，1950年美国著名数学家香农积几十年的研究，找到了编制国际象棋程序的原则方法。他提出以数的函数评价局面的优劣。函数的主题是通常一般实力的棋手都能考虑到的一些因素,诸如棋子实力重叠兵孤立兵、落后兵的弱点以及车的通路和其他子力的活动性等等。香农还提出用简化的估计方法剔除次要的变化。他是计算机国际象棋理论的奠基人。在数学家和计算机专家的共同努力下20世纪50年代末终于试制出世界上第1台公开与棋手对弈的电子计算机。1974年，在瑞典的斯德哥尔摩举行了计算机国际象棋的第1届世界冠军赛，8个国家的13种弈棋程序按积分循环制进行比赛，结果苏联的“卡伊赛”程序获得冠军。最出名的是1997年,卡内基梅隆大学的“深蓝”小组研究开发出“更深的蓝”，挑战人类大师。最后在全世界目光的关注下，“超级深蓝”击败了棋王卡斯帕罗夫。成为人工智能历史上里程碑式的事件，也标志着机器博弈的重大成功。和国际象棋相比，中国象棋机器博弈起步比较晚，八十年代才开始。1981年张耀腾发表的人造智慧在电脑象棋上的应用，是第一篇研究中国象棋机器博弈的文章。他在他的毕业论文中以残局做实验，提出审局函数为静态子力值，棋子位置值，棋子灵活度值，威胁与保护等四项之和。1982年廖嘉成发表的利用计算机象棋的实验就进了一步，包括开局、中局、残局。台湾大学的许舜钦教授被称为中国计算机象棋之父。在他1991年的两篇论文中，总结并介绍了到当时为止几乎所有的搜索算法，他在文中详细阐述了许多算法的不足之处并且解释了人们对这些算法的误解。这些研究成果为以后计算机象棋的发展做好了铺垫，至今仍在指导着人们进行计算机象棋的研究和实验工作。到了九十年代，中国象棋计算机博弈开始发展起来，人们研究出了各种博弈软件。比较有代表性的有台湾的吴身润的中国象棋、光谱公司出品的将族、晟业编制的象棋水浒战等等。主要研究内容文章主要是研究中国象棋的人机对弈，包括象棋的界面和引擎部分。界面主要是方便人与电脑进行交互的可视化界面。界面包括棋盘区、菜单项和功能按钮区。主要实现棋子的移动、悔棋、记录棋谱、难度选择等选项功能。引擎部分主要包括，棋子棋盘的表示即数据结构，走法的生成，局面优劣的评估即评估函数，搜索算法及其优化和改进。文章设计是采用MFC的框架来实现界面部分,主要用到的MFC类有，CWND窗口，它是大多数“看得见的东西”的父类（WINDOWS里几乎所有看得见的东西都是一个窗口，大窗口里有许多小窗口）。CDC设备文本。无论是显示器还是打印机，都是画图给用户看。这图就抽象为CDC。CDC与其他GDI（图形设备接口）一起，完成文字和图形、图像的显示工作。CDIALOG对话框类，CPEN类，CBRUSH类等等。象棋对弈其实是一种零和博弈。双人对弈，轮流走步；信息完备，双方得到的信息都是一样的；零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或无利的棋。所以内核代码的思路要用到博弈算法。对每一个局面所有可能的着法进行考虑，每一步着法会形成新的局面，这样就形成了一颗博弈树。机器博弈就是要从这颗博弈树中找到最优的分支，即要用到搜索算法对整棵树进行搜索。而中国象棋的博弈树是一个庞大的集合，如果一毫微秒走一步，也要需要10的一百多次方年才能搜索出必赢的第一步，所以博弈树是不可能穷举的。人在思索下棋的时候也不可能对棋局所有的可能计算完全，人往往是凭自己的经验、知识对棋面的好坏进行评估。通过这种思路我们可以给每个局面打一个分数来表示棋局对自己的有利程度。如果轮到自己落子的时候，一定会选择使局面分数最高的着法，如果轮到对手落子，他一定会选择使你得分最低的局面。这就是我们经常听到的极大极小值搜索，而对局面进行估分的函数就是评估函数。极大极小值搜索就是在轮到自己落子的时候选择分数最大的局面，轮到对手落子的时候选择得分最小的局面，这样就使得搜索可以进行，而由于估分的存在我们就可以在搜索进行到可以接受的时间范围内时结束它。一、系统概述11软件用途提供了一个PC端的中国象棋游戏。同时发布了GUI版与CLI版。其中CLI版为象棋AI部分开发过程中用作测试。但已经具有完整的人机对弈功能与相对友好的界面。考虑到有些用户可能相对GUI更偏向命令行操作方式,因此与GUI版本一起发布。CLI版本只有人机对弈功能,默认黑方AI先走。AI原理与GUI版相同,以下文档只对GUI版作出说明。如无特殊说明,提到”软件”时,所指均为GUI版本。软件具有两种模式,双人对弈与人机对弈。若选择双人对弈,因为此版本暂未开发联机对弈功能,只能双人共用一台PC,红方先走,黑方后走,有一方被将死,即无棋可走时,电脑会自动判定胜负。若选择人机对弈,默认用户执红子,AI执黑子。软件可自动判定胜负。软件在UBUNTU13。04、WINDOWS7、WINDOWSXP平台下测试性能良好。此版本未实现的功能长将判负。即假定红方只剩5个兵与一个将,且全部过河。黑方只剩一个将与一个车。则黑方基本不可能将死红方。但红方必定可在有限步之后将死黑方。则黑方为自保,最优策略是每一步都用车将红方的军,但无法将其将死。此时游戏会陷入循环。在正式象棋比赛中,任何情况下,长将判负。考虑到主要是面向人机对弈,和棋功能无意义,亦未开发。此AI与软件作者对弈,目前AI保持不败战绩。与其他测试者对弈，也是胜多败少。与作者IPAD上的象棋APP对弈,互有胜负,但软件AI胜少败多游戏截图进场画面如下图所示图11进场界面游戏界面图12游戏界面12游戏特色最大可达可接受时间内7层搜索深度,AI具有较高棋力。游戏固定权值与棋盘位置分值相结合的评估函数。基于ALPHABETA搜索,走法排序后PVS搜索策略。13系统开发过程软件作者为张哲源与刘豪。张哲源负责开发系统的AI部分,即局面表示,走法生成,局面评估,ALPHABETA搜索,搜索策略优化。刘豪负责系统GUI的设计与实现。部分GUI设计张哲源亦有参与。开发过程先实现了一个无GUI的搜索策略为ALPHABETA剪枝的命令行版本。再实现了一个基本的GUI版本。接下来GUI部分开始开发REGRET/RESTART/搜索进度条等工作。AI部分则着重于搜索策略的优化。六月份开始进行优化,一共经历过两次优化,一次走法栈生成时的自动排序使得ALPHABETA的可接受搜索深度在10S左右完成搜索由DEPTH5提升到DEPTH6。搜索时引入PVS算法,使得可接受的搜索深度增加为7。文档的GUI部分为刘豪负责写作，AI部分由张哲源负责写作14AI代码阅读提示AI部分代码在KERNEL文件夹中，建议用户先阅读GLOBALH，了解声明了哪些全局变量。则其余代码的算法都不复杂，应当较容易阅读。二、系统需求说明21系统总体功能可以实现双人对弈与人机博弈AI会检查走子的有效性AI会自动判定胜负具有悔棋功能但软件作者一致认为君子有所为有所不为,落子无悔才是值得提倡的因此对用户悔棋功能设置了一些障碍用户需连续点击弹出的对话框10次之后,同时接受AI的冷嘲热讽才允许悔棋若用户终于决定放弃悔棋关闭对话框即可若选择人机对弈,用户被AI吃子后会提示被吃了哪个子可以RESTART,即棋局进行到中局或是一局终了,用户想要重新玩一局,可点击RESTART若用户被将军,则必须应将,若不应将,则会弹出对话框提醒用户人机对战模式中,AI会在被将死之前就认输,即当AI检测到它几步之后必然会被将死,就会提前认输可接受的时间内搜索深度可达7层ALPHABETA搜索但是一开始就采用7步搜索无必要因而设定前5回合十步进行5层搜索,5回合之后到25回合50步采用6步搜索若之后用户仍未被将死将采用7步搜索人机对弈模式中，界面右下方会以进度条显示AI已搜索结点的比例。22环境需求AI部分与GUI部分由两人分工完成一开发环境AI部分TOSHIBAC600D01L笔记本电脑AMDATHLONTMIIP320DUALCOREPROCESSOR,UBUNTU1304操作系统,使用VIM编写,测试程序使用G474编译AI部分测试功能正确后,交由高楠进行GUI的实现GUI开发环境ACERASPIRE4736ZG笔记本电脑PENTIUM（R）DUALCORECPUT4500，WINDOWS7企业版32位操作系统，使用QTCREATOR48编写二运行环境在UBUNTU1304及WINDOWS7、WINXP操作系统下可流畅运行作者测试游戏所用CPU较为低端,游戏运行仍较为流畅用户所用CPU性能不错的话,可以考虑一开始就将搜索深度设为6或者723系统功能需求可选的对战模式_双人对弈或人机对弈启动游戏后,点击相应BUTTON,即可选择相应对战模式。双人对弈若选择双人对弈功能,则可双方交替走子系统会自动检测走子的有效性,不合规则的走子无法走出若一方胜利,则系统会弹出对话框告知“BLACK_LOSE”或是”REDLOSE”人机对弈选择人机对弈模式之后,默认用户执红子先走同样会检测走子有效性,同时还会检测红黑双方是否被将军,若被将军,则必须应将,不应将的走法时无效的即红黑双方的将在游戏过程中并不会真正的被吃掉,只要一方的将被将死,则系统会判定胜负AI会在被将死之前几步就检测出自己会被将死而无可补救,此时AI会认输退出功能点击EXIT按钮,可以退出程序RESTART功能点击RESTART按钮,可重新开始棋局悔棋功能点击REGRET按钮,弹出对话框劝用户不要悔棋,用户执意悔棋,则撤销之前两步的走法红方与黑方的注意悔棋是撤销两步走法，因此若是在双人对弈模式，A、B两人对弈，A走出之后要悔棋，必需在B走完之后才能成功。将军提醒用户被将军而不应将时,系统会作出提醒进度条选择人机对战模式时,机器思考时,界面下方会有进度体啊显示机器搜索的程度三、系统设计31系统设计决策AI系统设计时,将AI与GUI分开设计AI根据当前局面进行搜索/决策,产生最优走法,将走法传递给GUI,GUI刷新界面GUI部分在用户界面设计部分会有详细说明,此处介绍AI的设计用户可以通过运行CLI版本的游戏了解AI的整体架构AI设计策略一切以程序的运行速度为优先考量为了说明采用这种编码方式的理由,可以先看一下AI设计完成之后,作者做的一组统计开局第一步,共有44种走法,作者统计了不同搜索策略走第一步棋时搜索到的叶结点数目,这里的叶结点数是指真正会去做局面评估的叶结点被剪枝的叶结点不在其中未经走法排序的ALPHABETA搜索各搜索深度实际搜索叶节点数如下表表31ALPHABETA节点数搜索深度1234567结点数441131277713080466844627速度无法接受速度无法接受经过走法排序后的ALPHABETA搜索各搜索深度实际搜索叶节点数如下表表32实际搜索叶节点数搜索1234567深度结点数4484166013653136914970891速度无法接受经过走法排序后采用PVS算法的搜索策略各搜索深度实际搜索叶节点数如下表表33PVS搜索深度1234567结点数44841660120901140808894126482373将上表中走法排序后再REVERSE一次后的PVS搜索策略各搜索深度实际搜索叶节点数如下表表34REVERSE一次后的PVS搜索策略各搜索深度实际搜索叶节点数搜索深度1234567结点数48206372295151964014700791速度无法接受速度无法接受注PVS算法为先用小窗口的ALPHABETA试探,若试探失败,则重新进行搜索所以排序排的不好,可能访问结点数大于实际结点数,如第三张表中搜索深度为1时,实际有44中走法,却访问了48个结点上表中各种搜索策略文档后面会详述,但是用户可以很直观的感受到1不同搜索策略搜索效率差别很大,甚至可以是数量级上的差异2搜索量随搜索深度指数上升因而AI部分属于高计算量的程序,微小的速度差异会在大量的计算过程中被放大AI的实质是数学上的决策过程因而在AI部分编码过程中,没有采用面向对象的设计风格。因为AI思考的过程本质上是计算过程而非事件直接消息传递的模型。同时,具体实现上,大量的采用辅助数组等冗余数据结构，以空间换时间。函数的参数通过全局变量传递/引用传递而非值传递传递分支结构尽量采用SWITCHCASE结构而非IFELSE结构GUIGUI部分的设计包括一个进场画面，选择对战模式，以及实际游戏的棋盘。进场画面选择了一个战争的场面，因为象棋是模拟战争的游戏。棋盘没有采用一般的象棋的木质拟物设计，而是自己手绘设计了棋盘。棋子也经过重新设计。红方采用瘦金体，而黑方则采用颜体楷书。进场画面为游戏三国策壁纸，棋盘采用IPAD上的APP“PAPER”绘制。32系统总体设计321设计思想AI与GUI部分分别完成,通过接口实现通信AI部分AI部分采用BOTTOMUP的方法设计,包括局面表示/走法生成/局面评估/将军检测/搜索算法AI部分代码在KERNEL文件夹中KERNEL文件夹中代码的组织与AI的结构同构表征局面的数据结构以及其他一些全局变量在GLOBALH中声明,在DEFINE_GLOBALCPP中定义MOVE文件夹中为走法生成的函数CHECK文件夹中为将军检测函数EVAL文件夹中为局面评估函数SEARCH文件夹中为搜索函数每个文件夹中都有TESTCPP及MAKEFILE,为相应函数的测试代码用户可到相应文件夹中运行MAKE,然后执行可执行文件查看测试结果MAKEFILE在LINUX环境下写成AI部分概述以长度为256的一维数组表示棋盘,其中90个数字表征棋盘,其余部分为冗余数据,置零棋盘的表示还有相关冗余数据结构棋子以数字编码走法生成函数生成走法,搜索算法调用评估函数,给出局面估值及最佳走法搜索基于ALPHABETA剪枝算法剪枝效率与遍历走法栈的顺序关系很大,因此生成走法时按照一定规则对走法栈排序还采用了PVS算法对ALPHABETA算法进行优化GUI部分/322系统体系结构分为AI部分，AI部分没有使用面向对象的方法，只以文字说明。GUI部分有类图等描述一局面表示建议用户阅读GLOBALH头文件其他文件中的代码大抵知道函数功能即可表征局面/走法等的数据结构均在GLOBALH中声明,在DEFINE_GLOBALCPP中定义其中SHORTSIDE表示当前走棋一方,SIDE0,表示红方,SIDE1,表示黑方局面的表征主要通过两个数组，棋盘数组BOARD和棋子数组PIECE，这两个数组是等价的，在AI思考过程中保持同步。之所以设置两个数组，是因为不同情况下使用不同数组更加方便或者运算速度更高。采用SHORTBOARD256表征棋盘,非棋盘位置0棋盘上无棋子的位置也为0采用256长度的数组,可以方便的像使用二位数组那样使用一维数组,如想要表征第三行第四列,只需使用BOARD0X34即可对每一个棋子,有一个对兵来说,有两个,红黑有别合法位置数组,也是长256的一维数组若棋盘上的一个位置是该棋子的合法位置,则为1,否则则为0棋子在BOARD数组中位置为BOARD数组元素下标。棋盘为910，因此是嵌在BOARD数组中。如图所示31图31棋子对于棋子，用不同数字表示不同棋子，一个编码数字与一枚棋子一一对应，编码如下表表35棋子编码红方帅仕相马车炮兵表示数1617,1819,2021,2223,2425,2627,28,29,30,31黑方将士象马车炮卒表示数3233,3435,3637,3839,4041,4243,44,45,46,47如此，譬如红方将一开始是在上图中C7位置处，则有BOARD0XC716。这样编码的好处令SIDE_TAGSIDE01632则红方编码PIECE数组初始化如下图图32PIECE数组BOARD数组初始化如下图图33BORD数组初始化二走法生成中国象棋中，除了车和炮之外，其他棋子的走法都有棋盘上的固定增量行增量，列增量，因此比较容易处理。如红方过河的兵，有三个增量0X10,0X01,0X01，分别对应向前、向右和向左。则对每一个棋子，设置增量数组，除兵以外的棋子红方黑方增量数组可以公用，除此之外，还要设置合法性数组，如将的合法区域只能在九宫格内。对于象和马，还要确定马腿、香眼的增量数组。先介绍相关数据定义，在介绍相关函数。首先定义了一个MOV的CLASS,表征一个走法，在GLOBALH中。如下图所示图34定义SHORTFROM为走法起始的棋盘位置,即棋子在BOARD的下标TO为走法目的地址对应棋盘位置CAPTURE为该走法所吃子的棋子编码,若走法未吃子,则CAPTURE等于0重载了大于号操作符,在生成VECTORMOVE_ARRAY时会调用SORT函数排序至于为何排序,以何种依据排序,排序的目的与好处,将会在介绍评估函数与搜索结点策略时再讲到定义了走法生成时每个棋子的辅助数组,因为数组结构相似,只以马和兵为例进行说明其他棋子的辅助数组可阅读GLOBALH。马的辅助数组定义如下图所示图35马CONSTSHORTHORSE_DIRECTION8倘使已知一个马在BOARD数组中的位置,则它一共有八个可走的方向,8个方向存在HORSE_DIRECTOIN数组中,举个例子,马要向上走两格后向右走一格走一个日字形,方向为由红方向黑方,在棋子数组上,向上走两格为0X20,向右走一格为01,则新的位置可如下计算NEW_POSNOW_POS0X1FHORSE_DIRECTION中存的是马走到的新位置相对于旧位置的偏移量HORSE_LEG理解了HORSE_DIRECTION之后,HORSE_LEG数组的定义也容易理解,即马腿位置相对于当前位置的偏移量HORSE_LEG的下标与HORSE_DIRECTION的下标一一对应,即HORSE_LEGI是HORSE_DIRECTIONI这一走法对应的马腿位置HORSE_LEGAL数组为马在棋盘上的合法位置,马可以踏遍整个棋盘,因而整个棋盘都是合法位置兵的辅助数组如下图所示图36兵数组的意义与马的数组名意义相同,一个为DIRECTION数组,一个为LEGAL数组不同的是,兵的红黑双方数组不同,红方只能向黑方走,黑方只能向红方走,因而定义了一个二维数组接下来讲述相关函数的作用MOVECPP中定义了两个函数VOIDSAVE_MOVESHORTFROM,SHORTTO,VECTORNEXTPOSHORSE_DIRECTIONI如果NEXT是合法位置如果没有马腿如果NEXT位置上没有本方的棋子保存走法/SAVE_MOVE函数参数整数类型的走法起始位置FROM整数类型的走法终点位置TO走法栈引用VECTOR函数输出无返回值输出改变MOVE_ARRAY伪代码CAPTUREBOARDTO/确定被吃棋子的编码MOVMVFROM,TO,CAPTURE/定义一个MV变量,对应传入的走法MAKE_MOVEMV/走一步这个走法,更新BOARD数组与PIECE数组,同时SIDE1SIDE因为一方走棋后轮到另一方走棋,SIDE也会变/SIDE1SIDE/将SIDE改回本方CHECKCHECKMATE/检查这一步走出后是否会将军SIDE1SIDE/再次更改SIDEUNMOVEMV/撤销走法,更新BOARD数组,PIECE数组,更改SIDE如果没有被将军MOVE_ARRAYPUSH_BACKMVGEN_ALL_MOVE函数参数走法栈向量引用VECTOR全局变量SIDE/BOARD/PIECE/函数输出无返回值输出更新MOVE_ARRAY伪代码对本方的每一个棋子如果该棋子还在棋盘上没有被吃掉生成该棋子走法对生成的走法栈排序将军检测将军检测部分的代码在KERNEL/CHECK文件夹中。包括对将、兵、车、马、炮的检查函数。最后在CHECKMATECPP中定义的BOOLCHECKMATE函数调用这些检测函数。下面给出CHECKMATE和马的检测函数CHECK_HORSE的伪代码。将、兵、车、炮的算法用户可自行阅读源代码。CHECKMATE函数输入无参数传入。函数输出若当前方被将军，则返回TRUE，否则返回FALSE伪代码代码本身太简单，直接贴代码吧。CHECK_HORSE函数输入无，检查SIDE以及BOARD数组，PIECE数组。函数输出若当前方被对方马将军，则返回TRUE，否则返回FALSE伪代码MY_GENERALSIDE0PIECE16PIECE32/确定己方将的位置。ENEMY_HORSE2PIECE5SIDE03216,PIECE6SIDE03216/确定敌方马的位置，PIECE的下标与棋子的编码一一对应。FORI0IALPHA，则更新ALPHA，搜索过程中搜索到了大于BETA的值，则剪枝。ALPHABETA搜索的伪代码如下函数形式INTSEARCHSHORTDEPTH,INTALPHA,INTBETA输入搜索深度DEPTH，ALPHA,BETA输出最佳走法对应的走法估值，并不更新全局变量MOVBEST_MOVE伪代码IFDEPTH0RETURN局面评估值定义走法栈VECTORMOVE_ARRAY定义评估值INTVALUE生成所有走法若走法栈为空返回负无穷/说明已经被将死/对每一种走法，遍历执行走法VALUE1SEARCHDEPTH1,BETA,ALPHA撤销走法IFVALUEBETARETURNBETAIFVALUEALPHAALPHAVALUERETURNALPHAALPHABETA搜索的效率高低取决于剪枝的效率。剪枝的条件是VALUEBETA，估值越高，越有可能引起剪枝，因此，在走法生成时，按照被吃子的固定权值对走法排序。大大提高了剪枝效率，使得可接受的搜索深度由5提高到6。SEARCH调用时，ALPHA取负无穷，BETA取正无穷。PVS搜索算法在走法生成时，走法已经经过排序，以提高剪枝的效率。我们可以如下假设，经过排序后，第一个走法就刚好是最好的走法。假定最初的ALPHA,BETA100,100，第一个结点返回的VALUE值为30，则此时ALPHA,BETA30,100。若假设成立，则之后的结点的搜索值都不会大于30。则我们以30,31作为搜索区间试探。返回值VALUE可能有3中情况VALUE100说明返回值比原有的BETA还大，应该剪枝30ALPHAIFVALUEALPHAALPHAVALUEPV_FLAGTRUEIFDEPTHMAX_DEPTH/MAX_DEPTH为全局变量，主函数调用PVS时，就是以MAX_DEPTH为搜索深度BEST_MOVEMOVE_ARRAYIRETURNALPHAGUI部分系统开发过程中，算法和GUI的设计实现几乎是分开实现的，后期进行整合。在算法部分未使用面向对象的编程方法，大部分是以函数调用来实现。而GUI部分则较多的应用到了面向对象的方法，同时将某些算法中的函数纳入到了GUI的类中。以下介绍主要的类图317主要类INFO和CHOOSE继承自QDIALOG，分别用来实现弹出的提示窗口和进入程序的选择窗口。MAINWINDOW继承自QMAINWINDOW，为主窗口，程序的主要部分均在此实现。接下来介绍各个类的成员图317个各类CHOOSE类中包含有构造函数和两个槽，以及两个BUTTON用来选择模式。图318CHOOSE类INFO类中有一个用于关闭的按钮和一个用于显示信息的LABEL。图318INFO类以上为MAINWINDOW类的公有成员函数和槽，分别为，构造函数，刷新界面，电脑走棋，胜负判定的显示，以及PVS（原为算法中的函数，由于引进了进度条需要PVS中的数据对进度条修改，所以将PVS纳入MAINWINDOW类），以及负责完成悔棋和重新开局的槽。图319MAINWINDOW类以上为MAINWINDOW中的私有或保护成员。LABELMOUSEPOS为界面下方的提示字符（对于用户没有用处，早期调试时使用，正式提交可能会删除）。RED和BLACK1，BLACK2为提示棋子位置的边框，CHESS32为32个棋子，TIPS为右侧提示走棋方的文字，EAT提示被吃掉的棋子。OREGRET,RESULT,ANTICHECK分别为悔棋，显示胜负，提醒应将的对话框。EXIT,RESTART,REGRET三个按钮分别为位于屏幕右上方退出，重来和悔棋按钮。PIC34为程序中使用的图片。SIZE为每个格子的尺寸，FLAG为识别鼠标点击的标志。更新中添加了CONTROL变量，为了控制判定胜负后不允许再走棋。TRANS为记录用户当前走法的一个MOV型变量。MOUSEPRESSEVENT和PAINTEVENT分别为鼠标点击的响应函数和绘制图形的函数。主要函数GUI设计中的主要函数（未列举的函数较为简单，解释见代码注释）图320电脑走棋的函数该函数为电脑走棋的函数。为防止走棋过慢，对不同回合数采用了不同深度的搜索。此函数主要完成的功能有电脑走棋，图标跟踪，界面刷新，进度条显示。图321鼠标响应函数此函数为重定义的鼠标响应函数，其主要功能为响应鼠标在棋盘范围内的点击，通过标志FLAG来判断走法是否合法，并调用走棋和刷新界面等函数。更新中将IFM0改为IFM02ITISNEITHERSOSIMPLEASTOBETRIVIALNORTOODIFFICULTFORSATISFACTORYSOLUTION3CHESSISGENERALLYCONSIDEREDTOREQUIRE“THINKING“FORSKILFULPLAYASOLUTIONOFTHISPROBLEMWILLFORCEUSEITHERTOADMITTHEPOSSIBILITYOFAMECHANIZEDTHINKINGORTOFURTHERRESTRICTOURCONCEPTOF“THINKING“4THEDISCRETESTRUCTUREOFCHESSFITSWELLINTOTHEDIGITALNATUREOFMODERNCOMPUTERSTHEREISALREADYACONSIDERABLELITERATUREONTHESUBJECTOFCHESSPLAYINGMACHINESDURINGTHELATE19THCENTURY,THEMAELZELCHESSAUTOMATON,ADEVICEINVENTEDBYVONKEMPELEN,WASEXHIBITEDWIDELYASACHESSPLAYINGMACHINEANUMBEROFPAPERSAPPEAREDATTHETIME,INCLUDINGANANALYTICALESSAYBYEDGARALLANPOEENTITLEDMAELZELSCHESSPLAYERPURPORTINGTOEXPLAINITSOPERATIONMOSTOFTHEWRITERSCONCLUDED,QUITECORRECTLY,THATTHEAUTOMATONWASOPERATEDBYACONCEALEDHUMANCHESSMASTERTHEARGUMENTSLEADINGTOTHISCONCLUSION,HOWEVER,WEREFREQUENTLYFALLACIOUSPOEASSUMES,FOREXAMPLE,THATITISASEASYTODESIGNAMACHINEWHICHWILLINVARIABLYWINASONEWHICHWINSOCCASIONALLY,ANDARGUESTHATSINCETHEAUTOMATONWASNOTINVINCIBLEITWASTHEREFOREOPERATEDBYAHUMAN,ACLEARNONSEQUITURFORACOMPLETEACCOUNTOFTHEHISTORYOFTHEMETHODOFOPERATIONOFTHEAUTOMATON,THEREADERISREFERREDTOASERIESOFARTICLESBYHARKNESSANDBATTELLINCHESSREVIEW,1947AMOREHONESTATTEMPTTODESIGNACHESSPLAYINGMACHINEWASMADEIN1914BYTORRESYQUEVEDO,WHOCONSTRUCTEDADEVICEWHICHPLAYEDANENDGAMEOFKINGANDROOKAGAINSTKINGVIGNERON,1914THEMACHINEPLAYEDTHESIDEWITHKINGANDROOKANDWOULDFORCECHECKMATEINFEWMOVESHOWEVERITSHUMANOPPONENTPLAYEDSINCEANEXPLICITSETOFRULESCANBEGIVENFORMAKINGSATISFACTORYMOVESINSUCHANENDGAME,THEPROBLEMISRELATIVELYSIMPLE,BUTTHEIDEAWASQUITEADVANCEDFORTHATPERIODTHETHESISWEWILLDEVELOPISTHATMODERNGENERALPURPOSECOMPUTERSCANBEUSEDTOPLAYATOLERABLYGOODGAMEOFCHESSBYTHEUSEOFSUITABLECOMPUTINGROUTINEOR“PROGRAM“WHITETHEAPPROACHGIVENHEREISBELIEVEDFUNDAMENTALLYSOUND,ITWILLBEEVIDENTTHATMUCHFURTHEREXPERIMENTALANDTHEORETICALWORKREMAINSTOBEDONE2GENERALCONSIDERATIONSACHESS“POSITION“MAYBEDEFINEDTOINCLUDETHEFOLLOWINGDATA1ASTATEMENTOFTHEPOSITIONSOFALLPIECESONTHEBOARD2ASTATEMENTOFWHICHSIDE,WHITEORBLACK,HASTHEMOVE3ASTATEMENTASTOWHETHERTHEKINGANDROOKSHAVEMOVEDTHISISIMPORTANTSINCEBYMOVINGAROOK,FOREXAMPLE,THERIGHTTOCASTLEOFTHATSIDEISFORFEITED4ASTATEMENTOF,SAY,THELASTMOVETHISWILLDETERMINEWHETHERAPOSSIBLEENPASSANTCAPTUREISLEGAL,SINCETHISPRIVILEGEIFFORFEITEDAFTERONEMOVE5ASTATEMENTOFTHENUMBEROFMOVESMADESINCETHELASTPAWNMOVEORCAPTURETHISISIMPORTANTBECAUSEOFTHE50MOVEDRAWINGRULEFORSIMPLICITY,WEWILLIGNORETHERULEOFDRAWAFTERTHREEREPETITIONSOFAPOSITIONINCHESSTHEREISNOCHANCEELEMENTAPARTFROMTHEORIGINALCHOICEOFWHICHPLAYERHASTHEFIRSTMOVETHISISINCONTRASTWITHCARDGAMES,BACKGAMMON,ETCFURTHERMORE,INCHESSEACHOFTHETWOOPPONENTSHAS“PERFECTINFORMATION“ATEACHMOVEASTOALLPREVIOUSMOVESINCONTRASTWITHKRIEGSPIEL,FOREXAMPLETHESETWOFACTSIMPLYVONNEUMANNANDMORGENSTERN,1944THATANYGIVENPOSITIONOFTHECHESSPIECESMUSTBEEITHER1AWONPOSITIONFORWHITETHATIS,WHITECANFORCEAWIN,HOWEVERBLACKDEFENDS2ADRAWPOSITIONWHITECANFORCEATLEASTADRAW,HOWEVERBLACKPLAYS,ANDLIKEWISEBLACKCANFORCEATLEASTADRAW,HOWEVERWHITEPLAYSIFBOTHSIDESPLAYCORRECTLYTHEGAMEWILLENDINADRAW3AWONPOSITIONFORBLACKBLACKCANFORCEAWIN,HOWEVERWHITEPLAYSTHISIS,FORPRACTICALPURPOSES,OFTHENATUREOFANEXISTENCETHEOREMNOPRACTICALMETHODISKNOWNFORDETERMININGTOWHICHOFTHETHREECATEGORIESAGENERALPOSITIONBELONGSIFTHEREWERECHESSWOULDLOSEMOSTOFITSINTERESTASAGAMEONECOULDDETERMINEWHETHERTHEINITIALPOSITIONISAWON,DRAWN,ORLOSTFORWHITEANDTHEOUTCOMEOFAGAMEBETWEENOPPONENTSKNOWINGTHEMETHODWOULDBEFULLYDETERMINEDATTHECHOICEOFTHEFIRSTMOVESUPPOSINGTHEINITIALPOSITIONADRAWASSUGGESTEDBYEMPIRICALEVIDENCEFROMMASTERGAMES1EVERYGAMEWOULDENDINADRAWITISINTERESTINGTHATASLIGHTCHANGEINTHERULESOFCHESSGIVESAGAMEFORWHICHITISPROVABLETHATWHITEHASATLEASTADRAWINTHEINITIALPOSITIONSUPPOSETHERULESTHESAMEASTHOSEOFCHESSEXCEPTTHATAPLAYERISNOTFORCEDTOMOVEAPIECEATHISTURNTOPLAY,BUTMAY,IFHECHOOSES,“PASS“THENWECANPROVEASATHEOREMTHATWHITECANATLEASTDRAWBYPROPERPLAYFORINTHEINITIALPOSITIONEITHERHEHASAWINNINGMOVEORNOTIFSO,LETHIMMAKETHISMOVEIFNOT,LETHIMPASSBLACKISNOTFACEDWITHESSENTIALLYTHESAMEPOSITIONTHATWHITEHASBEFORE,BECAUSEOFTHEMIRRORSYMMETRYOFTHEINITIALPOSITION2SINCEWHITEHADNOWINNINGMOVEBEFORE,BLACKHASNONENOWHENCE,BLACKATBESTCANDRAWTHEREFORE,INEITHERCASEWHITECANATLEASTDRAWINSOMEGAMESTHEREISASIMPLEEVALUATIONFUNCTIONFPWHICHCANBEAPPLIEDTOAPOSITIONPANDWHOSEVALUEDETERMINESTOWHICHCATEGORYWON,LOST,ETCTHEPOSITIONPBELONGSINTHEGAMEOFNIMHARDYANDWRIGHT,1938,FOREXAMPLE,THISCANBEDETERMINEDBYWRITINGTHENUMBEROFMATCHESINEACHPILEINBINARYNOTATIONTHESENUMBERSAREARRANGEDINACOLUMNASTHOUGHTOADDTHEMIFTHENUMBEROFONESINEACHCOLUMNISEVEN,THEPOSITIONISLOSTFORTHEPLAYERABOUTTOMOVE,OTHERWISEWONIFSUCHANEVALUATIONFUNCTIONFPCANBEFOUNDFORAGAMEISEASYTODESIGNAMACHINECAPABLEOFPERFECTPLAYITWOULDNEVERLOSEORDRAWAWONPOSITIONANDNEVERLOSEADRAWNPOSITIONANDIFTHEOPPONENTEVERMADEAMISTAKETHEMACHINEWOULDCAPITALIZEONITTHISCOULDBEDONEASFOLLO