当前位置:首页>> >>


基于Qt的黑白棋游戏.rar

收藏

资源目录
    文档预览:
    编号:20180913212649159    类型:共享资源    大小:1.52MB    格式:RAR    上传时间:2018-09-13
    尺寸:148x200像素    分辨率:72dpi   颜色:RGB    工具:   
    45
    金币
    关 键 词:
    基于 Qt 白棋 游戏
    资源描述:
    太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸I基于 Qt 的黑白棋游戏摘 要本文主要介绍黑白棋游戏的设计与开发流程,同时讨论黑白棋设计中不同搜索算法的原理以及特点,从博弈树搜索算法的进步来反映人工智能的发展。本程序是在Linux(Ubuntu12.04LTS)环境下使用面向对象的 C++语言开发。有人人对弈,人机对弈,悔棋等功能。本论文首先指出了黑白棋游戏,Qt 以及计算机博弈的发展现状,然后重点介绍了 Qt 开发工具的使用,黑白棋程序的设计流程(包含类图、用例图、时序图的设计) ,规则设计,算法设计。最后介绍了 Linux 桌面环境 GUI 和计算机博弈的发展趋势。本设计通过一个棋类游戏的开发,阐述了棋类游戏的开发过程,包括软件开发的逻辑分析,程序设计,软件实现和软件测试的几个步骤。关键词:黑白棋;人工智能;搜索算法;Qt太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸IIReversi game based on QtAbstractThis paper describes the Othello game design and development process and discussed different design principles and features of the search algorithm. From the advancement of game tree search algorithm to reflect advances in the development of artificial intelligence. This program is the use of object-oriented C + + language development under Linux (Ubuntu12.04LTS) environment. Implements the following functions, man-machine to war, multiplayer, undo, etc. In this thesis points out the development status of Reversi game, Qt and computer game. Then focuses on the usage of Qt development tools, Othello program design process (including class diagrams, case diagram, sequence diagram design with), rules design, algorithm design. Finally, the development trend of Linux desktop environment GUI and computer game.By developing a chess game, describes the development process of board games. Several steps including logical analysis of software development, program design, software implementation and software testing.Key words: Othello; Artificial Intelligence; Search Algorithm; Qt太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸III目录摘 要 ........................................................................................................................................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.4 Min-Max 搜索 ...............................................................................................41.3.5 α-β 剪枝搜索 ...............................................................................................41.3.6 alpha-beta 的增强算法介绍 ..........................................................................51.3.7 人工智能的发展状况 ....................................................................................71.4 主要研究内容 ...........................................................................................................81.5 相关实验环境 ...........................................................................................................82 工具及算法介绍 ..................................................................................................................92.1 Qt 简介 ......................................................................................................................92.2 信号与槽 ...................................................................................................................92.3 Qt 和 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 黑盒测试 .................................................................................................................30太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸IV5.3 总结 .........................................................................................................................325.4 展望 .........................................................................................................................33参考文献 ..................................................................................................................................34致谢 ..........................................................................................................................................35太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸11 绪论 1.1 前言计算机博弈(Computer Games) ,也称之为机器博弈,就是让计算机可以像人脑一样进行思维活动,最终可以下棋,下国际象棋、西洋跳棋、黑白棋、中国象棋、围棋等等。 早在计算机诞生的前夜,著名的数学家和计算机学家阿伦·图灵(Alan Turing)便设计了一个能够下国际象棋的纸上程序,并经过一步步的人为推演,实现了第一个国际象棋的程序化博弈。那些世界上最著名的科学家,如计算机创始人冯.诺依曼(John von Neumann) ,信息论创始人科劳德.香农(Claude E. Shannon) ,人工智能的创始人麦卡锡(John McCarthy)等人都曾涉足计算机博弈领域,并做出过非常重要的贡献。 从上世纪 40 年代计算机诞生,计算机博弈经过一代又一代学者的艰苦奋斗和坎坷历程,终于在上世纪的八、九十年代,以计算机程序战胜棋类领域的天才而享誉世界。其中最为著名的则是 1997 年 5 月 IBM“深蓝”战胜世界棋王卡斯帕罗夫,成为计算机科学史上一个不朽的丰碑。在这之后,计算机博弈一天也没有停息过拼搏。由《Science》杂志评选的 2007 年十大科技突破中,就还包括了加拿大阿尔波特大学的科研成果——解决了西洋跳棋(Checker) 博弈问题,也就是说,在西洋跳棋的博弈中计算机将永远“立于不败之地” 。计算机博弈原理与方法学既涉及到博弈论(对策论) 、搜索原理等理论内容,又更多地涉及到数据结构、软件工程、程序设计方法学等方面的知识。计算机博弈属于计算机科学与应用学科的研究方向之一,又是人工智能领域的重要研究方向,应该属于智能科学与技术学科的一个分支。本文着重介绍了黑白棋的设计与开发,通过介绍博弈算法与程序设计的基本流程让您对计算机博弈原理与方法以及程序设计有更深入的了解。1.2 黑白棋的发展黑白棋是起源于英国 19 世纪末的一种棋盘类游戏,又叫反棋(Reversi)、奥塞罗棋(Othello)、苹果棋或翻转棋。游戏通过相互翻转对方的棋子,最后以棋盘上谁的棋子多来判断胜负。为什么以奥塞罗棋来命名黑白棋呢?上世纪 70 年代日本人 Goro Hasegawa 借用莎士比亚名剧“奥塞罗”为黑白棋重新命名。在莎士比亚笔下的主角——奥塞罗,是一位黑肤色的摩那人将军,他的妻子是一位白人贵族的女儿——苔丝狄蒙娜(Desdemon),因为受到小人——伊阿古(Iago)的挑拨离间,怀疑自己的妻子不忠而亲手杀死了自己的妻子。真相大白后,由于内心充满后悔和愧疚而自杀身亡。就如同奥塞罗据中男女主角之间的爱恨纠葛一样,黑白棋在游戏的过程中黑子与白子必须不断翻动对手棋子,因此黑白棋就以 Othello 来命名。太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸21.2.1 黑白棋程式的发展上世纪 90 年代初,由于计算深度和尾局的准确性,黑白棋程式的棋力已经很强。这个时期的程式由人工加入行动力、位置策略等因素,所以程式的棋力依赖于程式员本身的棋力,导致程式中存在人类棋手的弱点。这一情况在 1995 年左右得到了突破性的发展,程式员 Michael Buro 写出了能自我学习的黑白棋游戏 Logistello。自此,程式员不在把人工策略写死在程式里,而是由程式自我学习,程式会纪录形状,自动调整下棋策略。具有先进算法,高效率和准确的编程,使黑白棋程式的棋力远远超过人类棋手。黑白棋算法的不断改进,体现了人工智能(AI)的发展。1.2.2 游戏规则游戏开始时棋盘正中有交叉放置的四个棋子,两黑两白,黑棋总是先手。双方交替下棋。新落下的棋子与棋盘上已有同色棋子之间,被夹住得所有对方棋子都要翻转过来。且夹住位置上必须全部是对手的棋子,不能有空格。一步棋可以在数个方向上翻棋,任何被夹住得棋子必须被翻转过来。如果一方在棋盘上没有地方可以落子,则对手可以连续落子。双方都没有棋子可落时,棋局结束,棋子数目多的一方获胜。在棋盘还没有下满是,如果一方棋盘上没有棋子,则棋局结束。将对手棋子吃光的一方获胜。1.2.3 开局策略黑白棋最常见的开局策略有以下几种:最多子策略(The Maximum Disc Strategy)位置权重策略(The Weighted Square Strategy)行动能力策略(The Mobility Consideration Strategy)稳定子策略(The Stability Disc Strategy)这四种开局策略各有优缺点,以下会对其简单介绍:(1)最多子策略(The Maximum Disc Strategy)此策略采用贪心算法,是最直接简单的一种策略。此策略在落子时,会判断在哪个位置落子可以造成己方棋子数目最多,即可以翻转对手棋子最多的位置,从而取得胜利。虽然使用此策略会在初期占据大量棋子并取得优势,但是占据的棋子并非不会再被对手所占据的稳定子,且让对手有更多落子的位置的选择。因此很容易被对方逆转局面,失去领先地位。(2)位置权重策略(The Weighted Square Strategy)棋盘上每个位置都有各自对整个盘面变化产生的价值,因此将每个位置不同的价值作为落子时考虑的权重,如图 1-1 所示在角落位置(*)因为对盘面有较大的影响力,因此也就拥有比其他位置较高的权重,一旦占领角落后,不仅此位置不会被对手再占领,且将可以此位置为锚,进而占领盘面上其他的位置,所以在位置权重策略上对角落位置给予较高权重。而在盘面上 C 与 X 被赋予较低的权重,因为落子在这些位置时有可能对盘面发展状况造成不利的影响,落子在 C、X 会让对手有机会占领角落,而让自己处于不利局面。此外在 A、D 位置会给予次高的权重,落子在这些位置时,将有可能让对手被迫落子在 C、X 位置,而陷于困境,因此 A、D 位置有次高权重。(3)行动能力策略(The Mobility Consideration Strategy)以合法步的数量来决定其行动能力的状态,如果是对手可下的合法步数量少得话,太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸3将会使对手无合法步可以落子发生 pass,或是被迫下在不利位置 (如图 1-1 C、X 位置)。(4)稳定子策略(The Stability Disc Strategy)落子时考虑落子的位置将会造成多少稳定子来决定该下在哪里,稳定子即无法再被对手所翻动的棋子。在上述的策略中,每一种策略都有其应用的情况,也有其不足之处,所以在一盘棋局中不能只采用一种策略,最好的方式应该是在面对不同的棋局情况时采用对应的策略。图 1-1 位置权重策略示意图1.3 机器博弈与人工智能的发展概况1.3.1 机器博弈的基本思想机器博弈的核心思想并不复杂,实际上就是对博弈树节点的估值过程和对博弈树搜索过程的结合。在博弈的任何一个中间阶段,站在博弈双方其中一方的立场上,可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局,它的儿子节点是假设再行棋一步以后的各种棋局,孙子节点是从儿子节点的棋局再行棋一步的各种棋局,以此类推,构造整棵博弈树,直到可以分出胜负的棋局。整棵的博弈树非常庞大,且不同的棋类有所不同,分支因子大的如围棋的博弈树显然要比分支因子小的如国际象棋的博弈树要大得多。博弈程序的任务就是对博弈树进行搜索找出当前最优的一步行棋。对博弈树进行极大极小搜索,可以达到这一目的。极大极小搜索,是因为博弈双方所要达到的目的相反,一方要寻找的利益恰是一方失去的利益,所以博弈的一方总是希望下一走是儿子节点中取值最大者,而另一方恰恰相反。这便形成了极大极小过程。当然,程序不能也没有必要做到搜索整棵博弈树的所有节点,对于一些已经确定为不佳的走步可以将以它为根节点的子树剪掉。而且,搜索也不必真地进行到分出胜负的棋局,只需要在一定深度范围内对局面进行评价即可。只有搜索空间缩小到一定程度,搜索才可以真正的进行。当搜索进行到一定深度,用局面评价机制来评价棋局,按照极大极小的原则选出最优,向上回溯,给出这一局面的父亲节点的价值评价,然后再继续向上回溯,一直到根节点,最优走步就是这样搜索出来的。在这个过程中,最为重要的是搜索算法,高效的搜索算法可以保证用尽量少的时间和空间损耗来达到寻找高价值的走步。但是真的想要博弈程序棋力提高,还必须有太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸4一个好的局面评价机制,即估值算法作后盾。就是说,用这个估值算法评价的局面价值必须是客观的、正确的,可以确凿的评价局面的优劣以及优劣的程度。1.3.2 机器博弈系统根据机器博弈的基本思想,可以确定一个机器博弈系统的一般构成[6]。首先是知识表示的问题,选用一种合适的方法记录棋局。这时需要考虑在这种知识表示的数据结构之上将要进行的各种操作,知识表示应该使最经常进行的操作花费的时间和空间代价最小。其次,根据不同的棋类的不同规则集,要有一个相应的走法产生机制。它的作用是用来产生整棵博弈树,即处于博弈树的任何一个节点位置上,应该能够运用该机制产生这个节点的所有儿子节点,也就是接下来的所有合法走步。除了以上两个模块以外,就是博弈核心的搜索技术和与之配合的估值技术了。这四个部分相互配合运转起来,就可以实现机器博弈。1.3.3 博弈搜索博弈搜索的基本思想已经提出半个多世纪,目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。也就是说,没有随机因素的博弈在两个人之间进行,在任何一个时刻,一方失去的利益即为另一方得到的利益,不会出现“双赢”的局面,而且在任何时刻,博弈的双方都明确的知道每一个棋子是否存在和存在于哪里。二人、零和、完备信息的博弈搜索理论已经很系统。极大极小算法是所有搜索算法的基础。在这个基础上,目前在这一领域的算法主要有两类,一类是作为主流的深度优先的 alpha-beta 搜索及其系列增强算法,另一类是最佳优先的系列算法。博弈搜索从搜索方向上可以分为宽度优先搜索(Breadth-first search)和深度优先搜索(Depth-first search)。前者能够保证在搜索树中找到一条通向目标节点的最短途径。但是巨大的时间和空间开销使得它在计算机博弈中很少采用。深度优先搜索的最大特点就是可以节省大量的节点存储空间。因为它通常是采用递归过程来遍历搜索树,即后序遍历,得到一个节点值,就对其子节点做递归,然后根据他们的俄返回值来决定自身的返回值,搜索过的底层节点也随即撤销,因此它所占用的动态空间十分有限。1.3.4 Min-Max 搜索在机器与人对弈的过程中,机器事先并不知道人的水平如何,因而机器只能假设人走的每一步都会为自己带来最小的收益,而机器走的每一步都要为自己争取最大的利益,这就是极大极小原理。如果我们把机器和人连接走的每一步画成树状结构(即博弈树) ,对于每一个节点,其子节点是下一步所有可能走的位置(有可能是对方走,也有可能是自己走) ,对于叶子节点我们运用一次估值函数得到叶子的权值,之后便一直向上反推,直到得到根节点的权值。我们把每一次机器要走的节点叫做 Max 节点,因为这个节点的值是其子节点所有值中的最大值,而把每一个人要走的节点叫做 Min 节点,因为这个节点的值是其子节点所有值中的最小值。这样得到的根节点的值,就是机器走这一步期望的最大收益。太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸51.3.5 α-β 剪枝搜索α-β 搜索实际上就是运用 α-β 剪枝优化后的 Min-Max 搜索,其基本的极大极小思想是不变的。首先引入两个变量 α、β,表示当前节点在前面的搜索过程中,依据子节点的返回值来估计出的当前节点最后的结果的下限和上限。下面给出 α 剪枝和β 剪枝的定义:1.如果当前节点是 Min 节点,当前节点的父节点是 Max 节点,那么当当前节点的一个子节点的值小于当前节点的 α 值时,那么当前节点的其余子节点就不用搜索了,这个过程称为 α 剪枝过程。2.如果当前节点是 Max 节点,当前节点的父节点是 Min 节点,那么当当前节点的一个子节点的值大于当前节点的 β 值时,那么当前节点的其余子节点就不用搜索了,这个过程称为 β 剪枝过程。图 1-2 Alpha 剪枝示意图图 1-3 Beta 剪枝示意图1.3.6 alpha-beta 的增强算法介绍1.渴望搜索(Aspiration Search)在 alpha-beta 剪枝过程中,初始的的搜索窗口往往是从-∞(即初始的 alpha 值)到+∞(初始的 beta 值) ,在搜索进行中再不断缩小窗口,加大剪枝效果。渴望搜索就是渴望从一开始就使用小的窗口,从而在搜索初起,就可以进行大量的剪枝。这个初始窗口的选定很重要,如果选择准确,即所要寻找的走步就在这个窗口内,搜索便可以继续进行。如果第一步搜索的返回值证明最佳走步大于 beta 值,就太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸6需要重新确定窗口。以原来的 beta 值为 alpha 值,以+∞为新的 beta 值重新搜索。相反如果第一步的返回值证明最佳走步小于 alpha 值,重新确定的窗口就是以-∞为 alpha值,原来的 alpha 值为 beta 值了。可见第一次搜索猜测的窗口非常重要,如果猜测准确,搜索时间可以大大缩短,如果不准确,这一优势就不明显了。由于渴望搜索是一种基本的搜索方法,它在和后面叙述的遍历深化结合使用的时候,就可以借助前一次深度为 depth 的搜索的结果来猜测当前深度为 depth+1 搜索的窗口了。2.极小窗口搜索(Minimal Window Search)极小窗口搜索,也被称为是主变量导向搜索(Principal Variation Search) ,常常简称为 PVS 算法或者 NegaScout 算法。这个算法应用非常广泛。它的出发点是和渴望搜索大致相同的,即用极小的窗口来限制剪枝范围。它的过程是这样的:在根节点处,假定第一个儿子节点为主变量,也就是假定它为最佳走步,对它进行完整窗口(a,b)的搜索并得到一个返回值 v,对后面的儿子节点依次用极小窗口(也被称为是零窗口) (v,v+1 )来进行搜索,如果搜索返回值大于零窗口,则证明这一分支亦为主变量,对它进行窗口为(v+1,b)的搜索,可是如果返回值小于零窗口,这一分支就可以忽略,因为它的最佳走步还不如已有的走步。极小窗口搜索采用了极小的窗口,剪枝效率最高,并且只对主变量进行大窗口的搜索,所以大部分搜索动作是有效的,搜索产生的博弈树也很小。3.置换表(Transposition Table)在搜索进行中,查询所有的走步,经常会在相同的或者不同的路径上遇到相同的棋局,这样的子树就没有必要重复搜索,把子树根节点的估值、子树的最好走步和取得这个值的深度信息保存在一个称为置换表的数据结构中,下次遇到时直接运用即可。但是,对不同的情况要区别对待。对于固定深度的搜索,如果前一次保存的子树深度小于新节点要搜索的深度,还是要进行重新的搜索以保证所取得数据的准确程度。反之,如果置换表中保存的子树信息表明,子树的深度大于或者等于当前的新节点要求的搜索深度,它的信息就可以直接运用了。置换表增强如果和有效的 alpha-beta 搜索结合使用,结果就会使实际搜索的博弈树小于最小树。博弈树搜索的问题实际上是一个有向图的搜索。那些在置换表中被命中的节点,就是有向图中若干路径的交叉点。只有避免这些交点被重复搜索,搜索过程中生成的搜索树才有可能小于最小树。这也是后来证明深度优先的算法并不比最佳优先的算法差的原因之一。这个算法存在的问题是,置换表的构造,必须使对置换表的查找和插入操作不成为整个搜索的负担,才能提高效率。一般使用散列表来实现。4.遍历深化(Iterative Deepening)遍历深化是因对博弈树进行多次遍历,又不断加深其深度而得名,有人还把它称为蛮力搜索。算法利用了 alpha-beta 算法对子节点排序敏感的特点。它希望通过浅层的遍历给出节点的大致排序,把这个排序作为深层遍历的启发式信息。另外,算法用时间控制遍历次数,时间一到,搜索立即停止,这也符合人类棋手的下棋特点。在关键的开局和残局,由于分支较少,也可以进行较深层次的搜索。
    展开阅读全文
    1
      金牌文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    0条评论

    还可以输入200字符

    暂无评论,赶快抢占沙发吧。

    关于本文
    本文标题:基于Qt的黑白棋游戏.rar
    链接地址:http://www.gold-doc.com/p-139111.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们
    copyright@ 2014-2018 金牌文库网站版权所有
    经营许可证编号:浙ICP备15046084号-3
    收起
    展开