基于Qt的黑白棋游戏（程序代码+任务书+说明书+外文翻译+演示文稿）

基于Qt的黑白棋游戏摘要本文主要介绍黑白棋游戏的设计与开发流程,同时讨论黑白棋设计中不同搜索算法的原理以及特点,从博弈树搜索算法的进步来反映人工智能的发展。本程序是在Linux(Ubuntu12.04LTS)环境下使用面向对象的C+语言开发。有人人对弈，人机对弈，悔棋等功能。本论文首先指出了黑白棋游戏，Qt以及计算机博弈的发展现状，然后重点介绍了Qt开发工具的使用，黑白棋程序的设计流程（包含类图、用例图、时序图的设计），规则设计，算法设计。最后介绍了Linux桌面环境GUI和计算机博弈的发展趋势。本设计通过一个棋类游戏的开发，阐述了棋类游戏的开发过程，包括软件开发的逻辑分析，程序设计，软件实现和软件测试的几个步骤。关键词：黑白棋；人工智能；搜索算法；QtIReversigamebasedonQtAbstractThispaperdescribestheOthellogamedesignanddevelopmentprocessanddiscusseddifferentdesignprinciplesandfeaturesofthesearchalgorithm.Fromtheadvancementofgametreesearchalgorithmtoreflectadvancesinthedevelopmentofartificialintelligence.Thisprogramistheuseofobject-orientedC+languagedevelopmentunderLinux(Ubuntu12.04LTS)environment.Implementsthefollowingfunctions,man-machinetowar,multiplayer,undo,etc.InthisthesispointsoutthedevelopmentstatusofReversigame,Qtandcomputergame.ThenfocusesontheusageofQtdevelopmenttools,Othelloprogramdesignprocess(includingclassdiagrams,casediagram,sequencediagramdesignwith),rulesdesign,algorithmdesign.Finally,thedevelopmenttrendofLinuxdesktopenvironmentGUIandcomputergame.Bydevelopingachessgame,describesthedevelopmentprocessofboardgames.Severalstepsincludinglogicalanalysisofsoftwaredevelopment,programdesign,softwareimplementationandsoftwaretesting.Keywords:Othello;ArtificialIntelligence;SearchAlgorithm;QtII目录摘要.IAbstract.II1绪论.11.1前言.11.2黑白棋的发展.11.2.1黑白棋程式的发展.21.2.2游戏规则.21.2.3开局策略.21.3机器博弈与人工智能的发展概况.31.3.1机器博弈的基本思想.31.3.2机器博弈系统.41.3.3博弈搜索.41.3.4Min-Max搜索.41.3.5-剪枝搜索.41.3.6alpha-beta的增强算法介绍.51.3.7人工智能的发展状况.71.4主要研究内容.81.5相关实验环境.82工具及算法介绍.92.1Qt简介.92.2信号与槽.92.3Qt和MFC的比较.92.4核心算法介绍.103系统分析与设计.123.1黑白棋的需求分析.123.1.1用例图.123.1.2程序流程图.133.2模块设计.133.2.1主要模块简介.133.2.2类图.143.2.3棋盘数据结构设计.153.3设计系统的现实意义.174详细设计.184.1界面设计.184.2核心算法代码及注释.205系统测试.295.1白盒测试.295.2黑盒测试.30III5.3总结.325.4展望.33参考文献.34致谢.3501绪论1.1前言计算机博弈（ComputerGames），也称之为机器博弈，就是让计算机可以像人脑一样进行思维活动，最终可以下棋，下国际象棋、西洋跳棋、黑白棋、中国象棋、围棋等等。早在计算机诞生的前夜，著名的数学家和计算机学家阿伦图灵(AlanTuring)便设计了一个能够下国际象棋的纸上程序，并经过一步步的人为推演，实现了第一个国际象棋的程序化博弈。那些世界上最著名的科学家，如计算机创始人冯.诺依曼（JohnvonNeumann），信息论创始人科劳德.香农(ClaudeE.Shannon)，人工智能的创始人麦卡锡(JohnMcCarthy)等人都曾涉足计算机博弈领域，并做出过非常重要的贡献。从上世纪40年代计算机诞生，计算机博弈经过一代又一代学者的艰苦奋斗和坎坷历程，终于在上世纪的八、九十年代，以计算机程序战胜棋类领域的天才而享誉世界。其中最为著名的则是1997年5月IBM“深蓝”战胜世界棋王卡斯帕罗夫，成为计算机科学史上一个不朽的丰碑。在这之后，计算机博弈一天也没有停息过拼搏。由Science杂志评选的2007年十大科技突破中，就还包括了加拿大阿尔波特大学的科研成果解决了西洋跳棋(Checker)博弈问题，也就是说，在西洋跳棋的博弈中计算机将永远“立于不败之地”。计算机博弈原理与方法学既涉及到博弈论（对策论）、搜索原理等理论内容，又更多地涉及到数据结构、软件工程、程序设计方法学等方面的知识。计算机博弈属于计算机科学与应用学科的研究方向之一，又是人工智能领域的重要研究方向，应该属于智能科学与技术学科的一个分支。本文着重介绍了黑白棋的设计与开发，通过介绍博弈算法与程序设计的基本流程让您对计算机博弈原理与方法以及程序设计有更深入的了解。1.2黑白棋的发展黑白棋是起源于英国19世纪末的一种棋盘类游戏,又叫反棋(Reversi)、奥塞罗棋(Othello)、苹果棋或翻转棋。游戏通过相互翻转对方的棋子，最后以棋盘上谁的棋子多来判断胜负。为什么以奥塞罗棋来命名黑白棋呢？上世纪70年代日本人GoroHasegawa借用莎士比亚名剧“奥塞罗”为黑白棋重新命名。在莎士比亚笔下的主角奥塞罗，是一位黑肤色的摩那人将军，他的妻子是一位白人贵族的女儿苔丝狄蒙娜(Desdemon)，因为受到小人伊阿古(Iago)的挑拨离间，怀疑自己的妻子不忠而亲手杀死了自己的妻子。真相大白后，由于内心充满后悔和愧疚而自杀身亡。就如同奥塞罗据中男女主角之间的爱恨纠葛一样，黑白棋在游戏的过程中黑子与白子必须不断翻动对手棋子，因此黑白棋就以Othello来命名。11.2.1黑白棋程式的发展上世纪90年代初，由于计算深度和尾局的准确性，黑白棋程式的棋力已经很强。这个时期的程式由人工加入行动力、位置策略等因素，所以程式的棋力依赖于程式员本身的棋力，导致程式中存在人类棋手的弱点。这一情况在1995年左右得到了突破性的发展，程式员MichaelBuro写出了能自我学习的黑白棋游戏Logistello。自此，程式员不在把人工策略写死在程式里，而是由程式自我学习，程式会纪录形状，自动调整下棋策略。具有先进算法，高效率和准确的编程，使黑白棋程式的棋力远远超过人类棋手。黑白棋算法的不断改进，体现了人工智能(AI)的发展。1.2.2游戏规则游戏开始时棋盘正中有交叉放置的四个棋子,两黑两白,黑棋总是先手。双方交替下棋。新落下的棋子与棋盘上已有同色棋子之间，被夹住得所有对方棋子都要翻转过来。且夹住位置上必须全部是对手的棋子，不能有空格。一步棋可以在数个方向上翻棋，任何被夹住得棋子必须被翻转过来。如果一方在棋盘上没有地方可以落子，则对手可以连续落子。双方都没有棋子可落时，棋局结束，棋子数目多的一方获胜。在棋盘还没有下满是，如果一方棋盘上没有棋子，则棋局结束。将对手棋子吃光的一方获胜。1.2.3开局策略黑白棋最常见的开局策略有以下几种:最多子策略(TheMaximumDiscStrategy)位置权重策略(TheWeightedSquareStrategy)行动能力策略(TheMobilityConsiderationStrategy)稳定子策略(TheStabilityDiscStrategy)这四种开局策略各有优缺点，以下会对其简单介绍：(1)最多子策略(TheMaximumDiscStrategy)此策略采用贪心算法，是最直接简单的一种策略。此策略在落子时，会判断在哪个位置落子可以造成己方棋子数目最多，即可以翻转对手棋子最多的位置，从而取得胜利。虽然使用此策略会在初期占据大量棋子并取得优势，但是占据的棋子并非不会再被对手所占据的稳定子，且让对手有更多落子的位置的选择。因此很容易被对方逆转局面，失去领先地位。(2)位置权重策略(TheWeightedSquareStrategy)棋盘上每个位置都有各自对整个盘面变化产生的价值,因此将每个位置不同的价值作为落子时考虑的权重,如图1-1所示在角落位置(*)因为对盘面有较大的影响力，因此也就拥有比其他位置较高的权重，一旦占领角落后，不仅此位置不会被对手再占领，且将可以此位置为锚，进而占领盘面上其他的位置，所以在位置权重策略上对角落位置给予较高权重。而在盘面上C与X被赋予较低的权重，因为落子在这些位置时有可能对盘面发展状况造成不利的影响，落子在C、X会让对手有机会占领角落，而让自己处于不利局面。此外在A、D位置会给予次高的权重，落子在这些位置时，将有可能让对手被迫落子在C、X位置，而陷于困境，因此A、D位置有次高权重。(3)行动能力策略(TheMobilityConsiderationStrategy)以合法步的数量来决定其行动能力的状态，如果是对手可下的合法步数量少得话，2将会使对手无合法步可以落子发生pass，或是被迫下在不利位置(如图1-1C、X位置)。(4)稳定子策略(TheStabilityDiscStrategy)落子时考虑落子的位置将会造成多少稳定子来决定该下在哪里，稳定子即无法再被对手所翻动的棋子。在上述的策略中,每一种策略都有其应用的情况,也有其不足之处,所以在一盘棋局中不能只采用一种策略,最好的方式应该是在面对不同的棋局情况时采用对应的策略。图1-1位置权重策略示意图1.3机器博弈与人工智能的发展概况1.3.1机器博弈的基本思想机器博弈的核心思想并不复杂，实际上就是对博弈树节点的估值过程和对博弈树搜索过程的结合。在博弈的任何一个中间阶段，站在博弈双方其中一方的立场上，可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推，构造整棵博弈树，直到可以分出胜负的棋局。整棵的博弈树非常庞大，且不同的棋类有所不同，分支因子大的如围棋的博弈树显然要比分支因子小的如国际象棋的博弈树要大得多。博弈程序的任务就是对博弈树进行搜索找出当前最优的一步行棋。对博弈树进行极大极小搜索，可以达到这一目的。极大极小搜索，是因为博弈双方所要达到的目的相反，一方要寻找的利益恰是一方失去的利益，所以博弈的一方总是希望下一走是儿子节点中取值最大者，而另一方恰恰相反。这便形成了极大极小过程。当然，程序不能也没有必要做到搜索整棵博弈树的所有节点，对于一些已经确定为不佳的走步可以将以它为根节点的子树剪掉。而且，搜索也不必真地进行到分出胜负的棋局，只需要在一定深度范围内对局面进行评价即可。只有搜索空间缩小到一定程度，搜索才可以真正的进行。当搜索进行到一定深度，用局面评价机制来评价棋局，按照极大极小的原则选出最优，向上回溯，给出这一局面的父亲节点的价值评价，然后再继续向上回溯，一直到根节点，最优走步就是这样搜索出来的。在这个过程中，最为重要的是搜索算法，高效的搜索算法可以保证用尽量少的时间和空间损耗来达到寻找高价值的走步。但是真的想要博弈程序棋力提高，还必须有3一个好的局面评价机制，即估值算法作后盾。就是说，用这个估值算法评价的局面价值必须是客观的、正确的，可以确凿的评价局面的优劣以及优劣的程度。1.3.2机器博弈系统根据机器博弈的基本思想，可以确定一个机器博弈系统的一般构成6。首先是知识表示的问题，选用一种合适的方法记录棋局。这时需要考虑在这种知识表示的数据结构之上将要进行的各种操作，知识表示应该使最经常进行的操作花费的时间和空间代价最小。其次，根据不同的棋类的不同规则集，要有一个相应的走法产生机制。它的作用是用来产生整棵博弈树，即处于博弈树的任何一个节点位置上，应该能够运用该机制产生这个节点的所有儿子节点，也就是接下来的所有合法走步。除了以上两个模块以外，就是博弈核心的搜索技术和与之配合的估值技术了。这四个部分相互配合运转起来，就可以实现机器博弈。1.3.3博弈搜索博弈搜索的基本思想已经提出半个多世纪，目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。也就是说，没有随机因素的博弈在两个人之间进行，在任何一个时刻，一方失去的利益即为另一方得到的利益，不会出现“双赢”的局面，而且在任何时刻，博弈的双方都明确的知道每一个棋子是否存在和存在于哪里。二人、零和、完备信息的博弈搜索理论已经很系统。极大极小算法是所有搜索算法的基础。在这个基础上，目前在这一领域的算法主要有两类，一类是作为主流的深度优先的alpha-beta搜索及其系列增强算法，另一类是最佳优先的系列算法。博弈搜索从搜索方向上可以分为宽度优先搜索(Breadth-firstsearch)和深度优先搜索(Depth-firstsearch)。前者能够保证在搜索树中找到一条通向目标节点的最短途径。但是巨大的时间和空间开销使得它在计算机博弈中很少采用。深度优先搜索的最大特点就是可以节省大量的节点存储空间。因为它通常是采用递归过程来遍历搜索树，即后序遍历，得到一个节点值，就对其子节点做递归，然后根据他们的俄返回值来决定自身的返回值，搜索过的底层节点也随即撤销，因此它所占用的动态空间十分有限。1.3.4Min-Max搜索在机器与人对弈的过程中，机器事先并不知道人的水平如何，因而机器只能假设人走的每一步都会为自己带来最小的收益，而机器走的每一步都要为自己争取最大的利益，这就是极大极小原理。如果我们把机器和人连接走的每一步画成树状结构（即博弈树），对于每一个节点，其子节点是下一步所有可能走的位置（有可能是对方走，也有可能是自己走），对于叶子节点我们运用一次估值函数得到叶子的权值，之后便一直向上反推，直到得到根节点的权值。我们把每一次机器要走的节点叫做Max节点，因为这个节点的值是其子节点所有值中的最大值，而把每一个人要走的节点叫做Min节点，因为这个节点的值是其子节点所有值中的最小值。这样得到的根节点的值，就是机器走这一步期望的最大收益。41.3.5-剪枝搜索-搜索实际上就是运用-剪枝优化后的Min-Max搜索，其基本的极大极小思想是不变的。首先引入两个变量、，表示当前节点在前面的搜索过程中，依据子节点的返回值来估计出的当前节点最后的结果的下限和上限。下面给出剪枝和剪枝的定义：1.如果当前节点是Min节点，当前节点的父节点是Max节点，那么当当前节点的一个子节点的值小于当前节点的值时，那么当前节点的其余子节点就不用搜索了，这个过程称为剪枝过程。2.如果当前节点是Max节点，当前节点的父节点是Min节点，那么当当前节点的一个子节点的值大于当前节点的值时，那么当前节点的其余子节点就不用搜索了，这个过程称为剪枝过程。图1-2Alpha剪枝示意图图1-3Beta剪枝示意图1.3.6alpha-beta的增强算法介绍1渴望搜索（AspirationSearch）在alpha-beta剪枝过程中，初始的的搜索窗口往往是从-（即初始的alpha值）到+（初始的beta值），在搜索进行中再不断缩小窗口，加大剪枝效果。渴望搜索就是渴望从一开始就使用小的窗口，从而在搜索初起，就可以进行大量的剪枝。这个初始窗口的选定很重要，如果选择准确，即所要寻找的走步就在这个窗口内，搜索便可以继续进行。如果第一步搜索的返回值证明最佳走步大于beta值，就5需要重新确定窗口。以原来的beta值为alpha值，以+为新的beta值重新搜索。相反如果第一步的返回值证明最佳走步小于alpha值，重新确定的窗口就是以-为alpha值，原来的alpha值为beta值了。可见第一次搜索猜测的窗口非常重要，如果猜测准确，搜索时间可以大大缩短，如果不准确，这一优势就不明显了。由于渴望搜索是一种基本的搜索方法，它在和后面叙述的遍历深化结合使用的时候，就可以借助前一次深度为depth的搜索的结果来猜测当前深度为depth+1搜索的窗口了。2极小窗口搜索（MinimalWindowSearch）极小窗口搜索，也被称为是主变量导向搜索（PrincipalVariationSearch），常常简称为PVS算法或者NegaScout算法。这个算法应用非常广泛。它的出发点是和渴望搜索大致相同的，即用极小的窗口来限制剪枝范围。它的过程是这样的：在根节点处，假定第一个儿子节点为主变量，也就是假定它为最佳走步，对它进行完整窗口(a,b)的搜索并得到一个返回值v，对后面的儿子节点依次用极小窗口（也被称为是零窗口）（v,v+1）来进行搜索，如果搜索返回值大于零窗口，则证明这一分支亦为主变量，对它进行窗口为（v+1,b）的搜索，可是如果返回值小于零窗口，这一分支就可以忽略，因为它的最佳走步还不如已有的走步。极小窗口搜索采用了极小的窗口，剪枝效率最高，并且只对主变量进行大窗口的搜索，所以大部分搜索动作是有效的，搜索产生的博弈树也很小。3置换表（TranspositionTable）在搜索进行中，查询所有的走步，经常会在相同的或者不同的路径上遇到相同的棋局，这样的子树就没有必要重复搜索，把子树根节点的估值、子树的最好走步和取得这个值的深度信息保存在一个称为置换表的数据结构中，下次遇到时直接运用即可。但是，对不同的情况要区别对待。对于固定深度的搜索，如果前一次保存的子树深度小于新节点要搜索的深度，还是要进行重新的搜索以保证所取得数据的准确程度。反之，如果置换表中保存的子树信息表明，子树的深度大于或者等于当前的新节点要求的搜索深度，它的信息就可以直接运用了。置换表增强如果和有效的alpha-beta搜索结合使用，结果就会使实际搜索的博弈树小于最小树。博弈树搜索的问题实际上是一个有向图的搜索。那些在置换表中被命中的节点，就是有向图中若干路径的交叉点。只有避免这些交点被重复搜索，搜索过程中生成的搜索树才有可能小于最小树。这也是后来证明深度优先的算法并不比最佳优先的算法差的原因之一。这个算法存在的问题是，置换表的构造，必须使对置换表的查找和插入操作不成为整个搜索的负担，才能提高效率。一般使用散列表来实现。4遍历深化（IterativeDeepening）遍历深化是因对博弈树进行多次遍历，又不断加深其深度而得名，有人还把它称为蛮力搜索。算法利用了alpha-beta算法对子节点排序敏感的特点。它希望通过浅层的遍历给出节点的大致排序，把这个排序作为深层遍历的启发式信息。另外，算法用时间控制遍历次数，时间一到，搜索立即停止，这也符合人类棋手的下棋特点。在关键的开局和残局，由于分支较少，也可以进行较深层次的搜索。6算法的过程是，对以当前棋局为根节点的博弈树进行深度为二的遍历，得出其儿子节点的优劣排序，接着再从根节点进行深度为三的遍历，这一次优先搜索上次遍历中得出的最优者，从而加大剪枝效果，以此类推，在进行第三次、第四次的遍历，一直达到限定时间为止。由于这个算法的每次遍历都从根节点开始，所以有人称其为蛮力搜索，但实际上由于每次都可以优先搜索相对好的节点，导致剪枝效率增大，其实算法效率是很高的，目前这一算法也得到了广泛的认可。5历史启发搜索（HistoryHeuristic）历史启发也是迎合alpha-beta搜索对节点排列顺序敏感的特点来提高剪枝效率的，即对节点排序，从而优先搜索好的走法。所谓好的走法即可以引发剪枝的走法或者是其兄弟节点中最好的走法。一个这样的走法，一经遇到，就给其历史得分一个相应的增量，使其具有更高的优先被搜索的权利。6杀手启发搜索(KillerHeuristic)杀手启发实际上是历史启发的特例。它是把同一层中，引发剪枝最多的节点称为杀手，当下次搜索时，搜索到同一层次，如果杀手走步是合法的话，就优先搜索杀手。7MTD(f)算法MTD(f)搜索的全称是MemoryenhancedTestDriverwithfandn。它是一个较新的算法，在1995左右年由AskePlaat等人提出。它不是单一的alpha-beta算法的增强，但也是alpha-beta算法的改进。在算法进行中多次调用了零窗口的alpha-beta搜索过程。在算法初起，要给定一个初始值f，一个上界和一个下界。初始值要尽可能的靠近最后要找到的最优走步值，上界和下界要保证能把这个最优走步包含在内。算法实际上就是不断的应用零窗口的alpha-beta搜索，缩小上界和下界，并移动初始值使其接近最优走步。以下使这个算法的伪代码。functionMTD(n,);g:=;+:=+;:=;repeatifg=then:=g+1else:=g;g:=alphabeta(n,-1,)ifg先获取当前窗口的高和宽，height（）和width（），必须在painterEvent事件中，因为在窗口发生变化时，重绘工作要重新获取宽和高的数值，才能准确画出棋盘；3for循环9次画线；3将棋盘中间的四个位置画上相应的棋子。其他位置绘制棋子就事先在此类的构造函数中将棋盘模拟成一个三维数组，用不同的枚举状态代表不同的颜色。然后这里进行数组遍历，根据不同颜色，在计算出四个棋子的相对坐标上将棋子（圆）画上去。双方棋子数目的显示：在另一模块中定义两个QLCDNumber对象，将其初始化后，用QHBoxLayout放入QWidget框架中。然后在用connect（）棋子的数目变化与display（）槽连接。当棋子数目发生变化时，发送信号使其显示棋子数。当点击开始按钮（QPushButton）时发射信号给自定义槽Init（），槽的功能则是将棋盘（数组）重新初始化为新一局棋盘，包括主要标志位，然后进行重绘。核心算法（人机对战）：此算法由事件mousepressEvent（QMouseEvent*e）函数来响应鼠标事件。当点击鼠标后进入该事件，首先获取鼠标点击出坐标x=e-x,()y=e-y(),计算x，y坐标对应的数组位置，即QPointpoint。当获取到棋盘坐标后，将其传入另一函数do_pressPoint(QPointpoint)中进行进一步处理。参数color代表当前方棋子的颜色，在11此分析函数将完成棋盘点击处八个方向的棋子是否可落子判断，八个方向则由i、j加减一来决定，这里只分析一个方向，其他方向雷同。如果坐标的下一格为空或着是与color值相同，则进入下一个方向判断。若上述条件不满足，进入while(-i0),若遇到color则记录坐标处到clor处的格数（count），退出循环。然后用for循环将刚才color间夹得子变成color。跳过：当人对人时，可随意跳过，人对机时要等到某方确实无法下子时，跳过才生效。主要是通过发射信号的方式来显示一个提示框，同时，已经改变同步标志位。胜负提示：当棋盘棋子总数为64或者单方棋子位0时显示提示框。123系统分析与设计在软件工程中,需求分析指的是在创建一个新的或改变一个现存的系统或产品时,确定新系统的目的、范围、定义和功能时所要做的所有工作。需求分析是软件工程中的一个关键过程。在这个过程中，系统分析员和软件工程师确定顾客的需要。只有在确定了这些需要后他们才能够分析和寻求新系统的解决方法。概要设计的主要任务是把需求分析得到的系统扩展用例图转换为软件结构和数据结构。设计软件结构的具体任务是：将一个复杂系统按功能进行模块划分、建立模块的层次结构及调用关系、确定模块间的接口及人机界面等。数据结构设计包括数据特征的描述、确定数据的结构特性、以及数据库的设计。3.1黑白棋的需求分析首先要界面简洁，具有黑、白棋子数目显示、倒数计时显示、功能键显示等。其次要界面友好，背景、组件大小等要协调，给用户一种和谐的感官。再次要实现游戏开始、暂停、退出、模式选择、悔棋、跳过等基本功能。最后要选择合适的算法来实现黑白棋的下棋规则功能和计算机自动下棋功能。3.1.1用例图User人人人人人人人人人人人人人人人人人人人人人人人人人人人人includeinclude图3-1用例图由参与者（Actor）、用例（UseCase）以及它们之间的关系构成的用于描述系统功能的静态视图称为用例图。用例图是被称为参与者的外部用户所能观察到的系统功能13的模型图，呈现了一些参与者和一些用例，以及它们之间的关系，主要用于对系统、子系统或类的功能行为进行建模。用例图用于对系统、子系统或类的行为进行可视化，使用户能够理解如何使用这些元素，并使开发者能够实现这些元素。用例图定义了系统的功能需求，它是从系统的外部看系统功能，并不描述系统内部对功能的具体实现。3.1.2程序流程图开始模式选择人机对战人人对战使用者落子产生盘面判断游戏是否结束计算机落子产生盘面No判断游戏是否结束No结束YesYes黑方落子产生盘面判断游戏是否结束白方落子产生盘面判断游戏是否结束NoYesNo图3-2程序流程图3.2模块设计3.2.1主要模块简介通过对程序流程图的分析,将采用以下模块来实现黑白棋游戏的开发与设计。(1)游戏界面模块本模块是用来绘制游戏主界面，包括黑白棋记数，时间显示，棋盘，以及实现各种子功能的按钮。该模块是由Qt设计师界面类实现，通过QtDesigner拖拽控件设计14主界面。(2)绘制棋盘模块绘制棋盘模块用来绘制8x8正方形棋盘以及黑、白色棋子。通过paintEvent(QPaintEvent*e)函数来实现绘图模块。(3)初始化棋盘模块根据黑白棋的游戏规则，每轮开局前，首先在8*8的棋盘上的中心位置，先放入4枚棋子，黑、白各两枚。初始化模块的作用就是开局以及游戏结束开始新游戏时复位棋盘。(4)黑白棋子记数及判断输赢模块本模块实现当棋盘下满时，根据黑白棋数目判断输赢及对当前黑白棋子数的显示。(5)倒计时及判断输赢模块本模块当倒计时小于5时，实现对玩家的提醒功能以及倒计时结束后对游戏输赢的判断。(6)人人对战模块本模块通过判断用户鼠标单击事件位置,获得棋盘落子坐标,根据下棋规则模块判断落子是否合法,判断为合法落子,则落子成功,并将落子权交给对方,否则将无法响应。(7)人机对战模块本模块通过人机对战时机器计算落子坐标，并根据坐标自动下棋，本模块是黑白棋游戏的核心模块，人机对战模块的核心算法决定了黑白棋游戏的落子效率以及黑白棋游戏的可玩性。该算法是人工智能在游戏领域的体现。本模块采用的是一个穷举的方法传统的博弈树搜索算法（极大-极小）。(8)下棋规则模块本模块是黑白棋游戏的基础，本模块负责判断哪些位置能落子，以及落子成功后翻转相应的棋子。本模块是由C+语言实现黑白棋游戏规则的逻辑。(9)跳过模块当根据游戏规则出现没有地方落子的情况时，通过本模块实现跳过功能，将落子权交给对方，从而继续进行游戏。(10)悔棋模块黑白棋项目是由堆栈来存储落子信息。通过落子信息的出栈、入栈实现悔棋功能。3.2.2类图类图(Classdiagram)是显示了模型的静态结构，特别是模型中存在的类、类的内部结构以及它们与其他类的关系等。类图由许多（静态）说明性的模型元素（例如类、包和它们之间的关系）组成。类图是最常用的UML图，显示出类、接口以及它们之间的静态结构和关系；它用于描述系统的结构化设计。类图最基本的元素是类或者接口。15QWidgetChessBoard+enumGridState+intblack_num+intwhite_num-intgrid-intstarx,stary-intgridNum-void*chessManInfo+ChessBoard()+SetChessManInfo()#paintEvent()#mousePressEvent()+pressPoint()+chessnum()Widget+QStackstack+intblackNumber+intwhiteNumber-ChessBoard*board-ChessBoard:GridStatecurrentRole-intchess-introw-init()-paintEvent()-chessRule()-chessOuto()-autochess()+do_pressPoint()+timerslot()+show_chessnum()+pressPoint()图3-3类图3.2.3棋盘数据结构设计Widget.cpp文件中包含了下棋的规则和棋盘的数据结构。要实现棋盘的数据结构，我们首先想到的是二维数组，但是二维数组的执行效率不高，我们将采用三维数组来实现棋盘的数据结构：intchess6488;三维数组第一个元素代表64个位置的落子状态，第二元素代表棋盘x坐标，第三元素代表棋盘y坐标。三维数组的存储情况如下所示：012345670xxxxxxxx0.71xxxxxxxx8.152xxxxxxxx16.233xxxxxxxx24.314xxxxxxxx32.395xxxxxxxx40.476xxxxxxxx48.557xxxxxxxx56.63图3-4落子位置示意图其中“x”表示棋盘上8x8个棋格，数字表示三维数组的下标。intdir82=1,0,1,-1,0,-1,-1,-1,-1,0,-1,1,0,1,1,1;dir数组表示“横竖撇捺”四个方向要位移的下标。例如：chessboardtemp_x+16dir00,temp_y+dir01;就是横方向向右移一位。chessboardtemp_x+dir10,temp_y+dir11;就是横方向向右移一位的同时纵方向向下移一位。棋盘数组上每一元素可以是：黑棋子、白棋子和空棋格3种情况：enumGridStateBlack,White,Empty;假设ChessBoard:GridStatecurrentRole=0;为黑色棋子。假如chessboardtemp_x+dir00,temp_y+dir01=ChessBoard:Empty，表示x位置横方向向右移一位是空棋格。假如chessboardtemp_x+dir00,temp_y+dir01=currentRole，表示x位置横方向向右移一位是黑色棋子。假如chessboardtemp_x+dir00,temp_y+dir01=!currentRole，表示x位置横方向向右移一位是白色棋子。其中，需要特别注意的是，构造的三维数组，可能会造成数组的越界，通过if语句加强判断，能有效地解决数组越界问题。从上面三位数组数据结构和枚举类型中，我们发现数据冗余量较大，Byte是一个字节8位，2的8次方等于256，可以代表256种情况，而我们只用存储黑、白、空三种情况所以存在大量数据冗余，所以在此我们可以尝试一种新的存贮方法按位存储棋子信息的数据结构。在本轮文将给出思路而不进行实现。具体的思路就是，使用两个64位的无符号整形数，一个保存黑棋的情况，另一个保存白棋的情况。64位刚好保存8x8的棋盘格子。#defineBitBoardUNSIGNEDLONGLONGBitBoardblack;BitBoardwhite;如果某格上为黑棋，那么BitBoardblack对应标志位为1，其余位为0；如果某格上为白棋，那么BitBoardwhite对应标志位为1，其余位为0。对应黑棋和白棋的情况，初始局面的位图情况如图3-5所示：17图3-5数据结构示意图3.3设计系统的现实意义黑白棋由于其规则简单,搜索规模较小等特点,特别适合于研究和测试算法使用。黑白棋编程被誉为博弈人工智能界的“果蝇”，可以在黑白棋的编程上试验各种各样的新的人工智能方面的研究的新技术与新方法。由于黑白棋只有64格，开局已经有四个棋子，按照游戏规则60步就可以下完一盘。人人队战2-3分钟可以下完一盘棋，如果设置双方都是计算机的自动队战模式，一分钟内可以下完。所以测试起来非常方便，能够方便地看到人工智能实现的效果。正是由于以上原因，一些算法和思想已经首先在黑白棋上得到验证，比如MPC搜索算法和基于统计和模板匹配的估值函数，对其他棋类也是有相当启发意义的。黑白棋在人工智能这一领域，相当于生物学中的果蝇和小白鼠，具有相当的研究和测试意义。184详细设计通过第3章的描述，黑白棋设计思路已经确定，现在要做的就是把设计结果翻译成专用的程序设计语言所书写的程序。编码是对设计的进一步具体化，本部分的质量取决于前期设计的质量，但是，所选设计语言的特点及