基于QT的中国象棋设计与实现答辩ppt.ppt
基于QT中国象棋游戏的设计与实现,1.引言,1.1象棋游戏设计目的与意义 棋牌游戏属于休闲类游戏，相对于角色扮演类游戏和即时战略类游戏等其他游戏，具有上手快、游戏时间短的特点，更利于用户进行放松休闲。作为中华民族悠久文化的代表之一，中国象棋不仅源远流长，而且基础广泛，作为一项智力运动，中国象棋开始走向世界。,1.2象棋的研究方法： 本设计在linux平台操作与开发。 对于象棋来说，核心设计主要包括人工智能算法、整个游戏界面及程序辅助部分的实现。主要用QT开发，使游戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生产，从而完成整个游戏的功能。,本设计目 标 实现中国象棋人机对弈程序。 该程序功能包括：人机对弈； 人人对弈（不过在同一个平台上）； 搜索算法的设定； 悔棋、还原； 整个程序实现为两大部分： 一、人工智能算法设计 该部分实现了如何让计算机下中国象棋，其中涉及人机对弈的基本理论及思想，是该本设计的核心部分。 二、界面及程序辅助设计 在下棋引擎尚不能满足人机交互的基本要求，因此还需要一个界面来作为引擎的载体，同时提供一些诸如悔棋，还原之类的辅助功能。 下面分别介绍各个部分实现。由于界面及程序辅助部分涉及内容宽泛而有繁琐，因而本文只介绍其中重点部分。,2 概述 2.1 QT简介 Qt是一个跨平台的C+图形用户界面库，由挪威TrollTech公司出品，目前包括Qt、基于FrameBuffer的Qtopia Core、快速开发工具Qt Designer和国际化工具Qt Linguist等部分。Qt支持所有的UNIX系统，当然也包括Linux系统，还支持WinNT/Win2k、Windows 95/98平台。 基本上Qt同X-Window上的Motif、Openwin、GTK等图形界面库和Windows平台上的MFC、OWL、VCL、ATL是同类型的。不过Qt还具有下列一些优点。 （1）优良的跨平台特性。 Qt支持下列操作系统：Microsoft Windows 95/98、Microsoft Windows NT、Linux、Solaris、SunOS、HP-UX、Digital UNIX (OSF/1、Tru64)、Irix、FreeBSD、BSD/OS、SCO、AIX、OS390和QNX等。,（2）面向对象。 Qt的良好封装机制使得Qt的模块化程度非常高，可重用性较好，对于用户开发来说是非常方便的。Qt提供了一种称为signals/slots 的安全类型来替代callback，这使得各个元件之间的协同工作变得十分简单。 （3）丰富的API。 Qt包括多达250个以上的C+类，还提供基于模板的collections、serialization、file、I/O device、directory management和date/time类。甚至还包括正则表达式的处理功能 （4）支持2D/3D图形渲染，支持OpenGL。 （5）大量的开发文档。 （6）XML支持。,2.2 Linux操作系统简介 Linux是一种自由和开放源码的类Unix操作系统。 Linux操作系统是Nuix操作系统的一种克隆系统。它诞生于1991 年的10 月5 日以后借助于Internet 网络，并经过全世界各地计算机爱好者的共同努力下，现已成为今天世界上使用最多的一种UNIX 类操作系统，并且使用人数还在迅猛增长。 Linux 操作系统的诞生、发展和成长过程始终依赖着以下五个重要支柱：UNIX 操作系统、MI操作系统、GNU 计划、POSIX 标准和Internet 网络。 目前，Linux的发行版有很多，如Ubuntu，RedHat，Debian，Fedora等等。,3 人工智能算法设计 程序的基本框架: 从程序的结构上讲,大体上分为四大块： 棋局表示; 着法生成； 搜索算法； 局面评估； 程序的大概的思想是： 首先使用一个数据数据结构来描述棋局信息，对某一特定的棋局信息由着法生产器生产当前下棋方所有合法的着法并依次存入着法队列。然后通过搜索算法来逐一读取着法并调用局面估值函数对该着法所生产的后继局面进行评估打分，从中选出一个最有可能导致棋方取胜的着法。在搜索的过程中还可以采用一些辅助手段来提高搜索的效率。其过程如下所示（图1）：,3.1 棋局表示 对于棋盘局面的表示可采用传统而简单的“棋盘数组”。即用一个10*9的数组来存储棋盘上的信息，数组每个元素储存棋盘上是否有棋子。这种表示方法简单易行。按此方法棋盘的初始情形如下所示： const BYTE initBoard109 = B_CAR,B_HORSE,B_ELEPHANT,B_BISHOP,B_KING,B_BISHOP,B_ELEPHANT,B_HORSE,B_CAR, NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS, NOCHESS,B_CANON,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,B_CANON,NOCHESS, B_PAWN,NOCHESS,B_PAWN,NOCHESS,B_PAWN,NOCHESS,B_PAWN,NOCHESS,B_PAWN, NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS, /楚河 汉界/ NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS, R_PAWN,NOCHESS,R_PAWN,NOCHESS,R_PAWN,NOCHESS,R_PAWN,NOCHESS,R_PAWN, NOCHESS,R_CANON,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,R_CANON,NOCHESS, NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS,NOCHESS, R_CAR,R_HORSE,R_ELEPHANT,R_BISHOP,R_KING,R_BISHOP,R_ELEPHANT,R_HORSE,R_CAR ;,对于着法的表示，直接借用棋盘数组的下标来记录着法的起点和目标点。至于是什么棋子在走，以及是否吃子、吃的是什么子，在着法结构中并不记录。这些信息由外部读取棋盘上的起点、终点的数据获得。着法结构定义如下，其中包括了对着法的历史得分的记录项，以供后面要讲到的“历史启发”所用。 typedef struct short nChessID; /表明是什么棋子 CHESSMANPOS From;/起始位置 CHESSMANPOS To; /走到什么位置 int Score; /走法的分数 CHESSMOVE;,3.2 着法生成 程序需要让计算机在轮到它走子的时候能够执行一步它认为对它最有利的着法，那前提就是它要有诸多可供选择的着法，提供所有候选着法的“清单”就是着法生产器所要完成的。之后用搜索函数来搜索“清单”，并用局面评估函数来逐一打分，最后就可以选择出“最佳着法”并执行了。 在着法生产器中，采用的基本思想就是遍历整个棋局（一个接一个地查看棋盘上的每一个位置点），当发现有当前下棋方的棋子是先判断他是何种类型的棋子，然后根据其棋子类型而相应地找出去所有合法着法并存入着法队列。,3.3 搜索算法 搜素算法对于整个下棋引擎来说都至关重要。它如同程序的心脏，驱动这着整个程序关于棋类对弈程序中的搜索算法，已有成熟的Alpha-Beta 搜索算法以及其它一些辅助增强算法（还有众多基于Alpha-Beta 算法的派生、变种算法）在程序中直接借鉴了Alpha-Beta 搜索算法并辅以了历史启发。本节先介绍Alpha-Beta 搜索算法：在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是将死对方，或者避免被将死。,可以用一棵“博弈树”（图2）来表示下棋的过程树的每一个节点代表棋盘上的一个局面，对每一个局面（结点）根据不同的偶发又产生不同的局面（生产新的结点），如此不断直到再无可选择的走法，即叶子结点（棋局结束）。中国象棋的博弈树的模型大概如下图所示，可以把棋子连接点的线段看作是着法，不同的着法自然产生不同的局面。 该树包含三种类型的结点： 奇数层的中间结点（以及根结点），表示轮到红方走棋； 偶数层的中间结点，表示轮到黑方走棋； 叶子结点，表示棋局结束。,下面介绍下树的裁剪：图中方框 表示该结点要取子结点中的最大值； 圆圈表示该结点要取子结点中的最小值。 图3 树的裁剪,下棋双假定棋盘上的局面发展到了结点A(图3)，现在轮到你走棋了，你是“最大的一方”即你希望局面的分值尽可能的高。用搜索两层看一看“树的裁剪”对提高搜索效率的帮助。 考察结点A的子结点B。结点B所属的这一层是轮到你的对手“最小者”来走棋了，目的是使得棋局的分值尽可能的小。一次考察结点B的各个子结点，查看它们的分值（因为事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。来选择自己的最想要的一个值，这就是“最大-最小”的思想！,“最小-最大”的思想再加上“对树的裁剪”，这就是Alpha-Beta搜索算法的核心。最基本的Alpha-Beta算法的代码如下： int AlphaBeta(int depth, int alpha, int beta) if (depth = 0) /如果是叶子节点（到达搜索深度要求） return Evaluate(); /则由局面评估函数返回估值 GenerateLegalMoves(); /产生所有合法着法 while (MovesLeft() /遍历所有着法 MakeNextMove(); /执行着法 int val = -AlphaBeta(depth - 1, -beta, -alpha); /递归调用 UnmakeMove(); /撤销着法 if (val = beta) /裁剪 return beta; if (val alpha) /保留最大值 alpha = val; return alpha; ,3.5 局面评估 前面已经讲过了棋局的表示、着法生成、搜索算法（包括搜索辅助），在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。 首先，先介绍一下局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素有差异。在中国象棋中所要考虑的最基本的结构因素包括如下四点：,一、子力总和 子力是指某一个子本身所具有的价值。通俗地讲就是一个棋子它值个什么例如，车值500的话，那可能马值300，卒值80等等。所以在评估局面时，首先考虑双方的子力总和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。 二、棋子位置 棋子位置，或者控制区域，是指某一方的棋子在棋盘上所占（控制）的位置。例如，沉底炮，过河卒、以及车占士角等都是叫好的棋子位置状态，而窝心马、将离开底线等则属于较差的棋子位置状态。 三、棋子的机动性 棋子的机动性指棋子的灵活度。例如，起始位置的车动性较差，所以讲究早出车。同样四面被憋马腿的死马机动性也较差。 四、棋子的相互关系 这一点的分析较为复杂，因为一个棋子与其它子之间往往存在多重关系。如：一个马可能在对方的炮的攻击之下同时它又攻击对方的车。,3.6程序组装 至此，已具备了实现一款中国象棋对弈程序引擎部分的所有要素，将上述模块分别写作.h头文件。如下： Define.h /象棋的相关定义。 MoveGenerator.h /着法生产器。 SerarchEngine.h /搜索部分。 HistoryHeuristic.h /历史启发。 Eveluation.h /局面评估。 当实现了引擎部分的各要素时，可先建了一个QT控制台项目，之后只要再添加一个.cpp文件负责接受用户的输入、调用搜索函数、显示搜索结果，便可简单的测试引擎了（采用输入着法的起点坐标和终点坐标的方式来传送用户走棋的信息。同样，程序显示计算机走棋的起点坐标和终点坐标来做出回应）。,4 界面及程序辅助设计 4.1 界面基本框架 关于界面，建立一个基于对话框的QT应用程序，主要工作都在对话框的两个文件chessgame.h和chessgame.cpp下展开。 代码主要分布于以下三大部分： 初始化部分 Void CChessGame:initChessBoard() CChessGame() 负责的是对话框的初始化。可以把有关中国象棋初始化情况也放在这里面。初始化的内容包括： 对引擎部分所用到的变量的初始化。包括对棋盘上的棋子位置进行初始化，对搜索深度、当前走棋方标志、棋局是否结束标志等的初始化； 对棋盘、棋子的贴图位置（即棋盘、棋子在程序中实际显示位置）的初始化； 对程序辅助部分所用到的一些变量的初始化。包括对悔棋、还原队列的清空，棋盘、棋子样式的默认形式，下棋模式的默认选择，以及着法名称列表的初始化等。,4.3悔棋和还原 悔棋中主要完成了以下任务： 1.下棋回合数减一； 2.将当前局面信息保存至走法队列，以供还原所用； 3从走法队列中取出上一回合的棋局信息，恢复到当前局面，然后将其从队列中删除它。 4.将列，以供还原所用。然后从列表框中删除它。显示着法名称的列表框中的本回合的着法名称保存到一个着法名称队 而在还原中所做的刚好和悔棋相反： 1.下棋回合数加一； 2.将当前局面信息保存至队列，以供悔棋所用； 3. 从队列红取出最近一次存入的着法名称（两项，因为每回合产生两步着法），将其重新显示到列表框中。然后将其从中剔除。,5 系统实现 棋盘界面：,从界面上方的菜单栏中可以进行相关设置 参数设置界面如下：,打开QT软件如下图：,打开chess.pro项目文件,运行该程序，总体效果如下图：,28,结论 本论文对计算机博弈技术进行了研究，在深入研究了机器下中国象棋方法理论基础上，实现了人机对弈中国象棋程序，以及人人对弈（在同一个台机子上），然而，由于时间关系，程序也存在着几点不足： 第一，没对计算机下棋引擎部分作跟深入的挖掘和研究。对于诸如位棋盘（bitboard）、迭代加深、机器学习等当今棋类对弈程序中所采用的先进技术和思想，在程序中并未涉及。这在一定程度上影响了程序中下棋引擎的工作效率。 第二，由于对于人工算法的不熟悉，在Alpha-Beta搜索算法上花大量的时间来了解，导致论文进度的缓慢。尽管，这些问题都得以解决。但却影响了程序开发的过程。 第三，程序中仍在局面检测和贴图刷新上存在随机性的出错可能（出错几率很小）。,谢谢各位老师！,
