毕业设计（论文）-中国象棋游戏的设计与实现.doc

中国象棋游戏的设计与实现中国象棋游戏的设计与实现 摘摘 要要 本文首先研究了中国象棋在计算机中的表示问题 接着讨论如何产生着法 一系列相关内容 其次研究了博弈树的极小极大搜索技术及在此基础上发展起 来的 Alpha Beta 剪枝算法 使用 MFC 文档视图体系结构和 Visual C 开发工具 实现了一个具有一定棋力的中国象棋人机对弈程序 象棋程序的实现可以被分为人工智能和界面程序辅助两大部分 人工智能 部分主要体现计算机的下棋思路 既计算机如何进行思考并以最佳走法完成下 一步 先由相应的搜索算法进行搜索 并对各种可能的走法进行估值 从中选 择胜利面最大的一步 而界面及程序辅助部分主要便于用户通过以前的下棋步 骤 更好地调整下棋思路 着法显示使用户能够清楚地知道下棋过程 更准确 地把握整个局面 目目 录录 1引言 1 1 1象棋设计背景和研究意义 1 1 2象棋设计研究方法 1 2人工智能算法设计 2 2 1棋局表示 3 2 2着法生成 4 2 3搜索算法 5 2 4历史启发及着法排序 9 2 5局面评估 9 2 6程序组装 11 3界面及程序辅助设计 12 3 1界面基本框架 12 3 2多线程 13 3 3着法名称显示 14 3 4悔棋和还原 15 4系统实现 16 结 论 19 参考文献 20 致 谢 21 声 明 22 1引言引言 1 1 象棋设计背景和研究意义象棋设计背景和研究意义 电脑游戏行业经过二十年的发展 已经成为与影视 音乐等并驾齐驱的全 球最重要的娱乐产业之一 其年销售额超过好莱坞的全年收入 游戏 作为一 种娱乐活动 早期的人类社会由于生产力及科技的制约 只能进行一些户外的 游戏 随着生产力的发展和科技进步 一种新的游戏方式 电子游戏也随之 诞生 当计算机发明以后 电子游戏又多了一个新的载体 电子游戏在整个计算 机产业的带动下不断地创新 发展着 自从计算机发明 向各个领域发展 到 成为我们现在每天工作和生活必不可少的一部分的这个过程中 电子游戏也逐 步渗入我们每个人的娱乐活动中 而计算机已经普及的今天 对于可以用计算 机进行程序编辑的人来说 开发属于自己的游戏 已经不再是梦想 事实上 个人计算机软件市场的大约 80 销售份额是来自游戏软件 棋牌游戏属于休闲 类游戏 相对于角色扮演类游戏和即时战略类游戏等其它游戏 具有上手快 游戏时间短的特点 更利于用户进行放松休闲 为人们所喜爱 特别是棋类游 戏 方便 快捷 操作简单 在休闲娱乐中占主要位置 作为中华民族悠久文 化的代表之一 中国象棋不仅源远流长 而且基础广泛 作为一项智力运动 中国象棋开始走向世界 随着计算机处理速度的飞速提高 人们很早就提出了疑问 计算机是否会 超越人类 世界国际象棋大师已被计算机打败 计算机已经超过了人类 而人 工智能是综合性很强的一门边缘学科 它的中心任务是研究如何使计算机去做 那些过去只能靠人的智力才能做的工作 因此 对游戏开发过程中的人工智能 技术的研究自然也就成了业界的一个热门研究方向 1 2 象棋设计研究方法象棋设计研究方法 对于象棋来说 核心设计主要包括人工智能算法的以及整个游戏中界面及 程序辅助部分的实现 主要用 Visual C 进行开发 里面的 MFC 类库 使游 戏开发更加方便 并利用人工智能相关搜索算法实现人工智能的着法生成 从 而完善整个游戏的功能 本文的目标是实现一款有着一定下棋水平且交互友好的中国象棋人机对弈 程序 该程序功能包括 人机对弈 搜索深度设定 电脑棋力选择 悔棋 还原 着法名称显示 整个程序的实现可分为两大部分 一 人工智能算法设计 计算机下棋引擎 该部分实现了如何让计算机下中国象棋 其中涉及人机对弈的基本理论及 思想 是该程序的核心部分 同时也是本项目研究的重点所在 二 界面及程序辅助设计 光有下棋引擎尚不能满足人机交互的基本要求 因此还需要一个框架 界 面 来作为引擎的载体 同时提供一些诸如悔棋 还原之类的附属功能 程序 辅助 下面分别介绍各部分实现 由于界面及程序辅助部分涉及内容宽泛而又繁 琐 因而本文只介绍其中重点部分 2人工智能算法设计人工智能算法设计 程序的基本框架 从程序的结构上讲 大体上可以将引擎部分划分为四大块 棋局表示 着法生成 搜索算法 局面评估 程序的大概的思想是 首先使用一个数据结构来描述棋局信息 对某一特定的棋局信息由着法生 成器生成当前下棋方所有合法的着法并依次存入着法队列 然后通过搜索算法 来逐一读取着法并调用局面评估函数对该着法所产生的后继局面进行评估打分 从中选出一个最有可能导致走棋方取胜的着法 在搜索的过程中还可以采用一 些辅助手段来提高搜索的效率 其过程如下所示 图 1 当前棋局 着法生成器 m1m2m3 mn 搜索算法 搜索辅助 局面评估 着法队列 图 1 程序结构图 下面将分别介绍程序各个部分 2 1 棋局表示棋局表示 计算机下棋的前提是要让计算机读懂象棋 所谓读懂 即计算机应该能够 清楚地了解到棋盘上的局面 棋盘上棋子的分布情况 以及下棋方所走的每一 种着法 因而首先需要设计一套数据结构来表示棋盘上的局面以及着法 对于棋盘局面的表示可采用传统而简单的 棋盘数组 即用一个 9 10 的 数组来存储棋盘上的信息 数组的每个元素存储棋盘上是否有棋子 这种表示 方法简单易行 缺点是效率不是很高 按此方法棋盘的初始情形如下所示 BYTE CChessBoard 9 10 R 0 0 P 0 0 p 0 0 r H 0 C 0 0 0 0 c 0 h E 0 0 P 0 0 p 0 0 e A 0 0 0 0 0 0 0 0 a K 0 0 P 0 0 p 0 0 k A 0 0 0 0 0 0 0 0 a E 0 0 P 0 0 p 0 0 e H 0 C 0 0 0 0 c 0 h R 0 0 P 0 0 p 0 0 r 给所有棋子定义一个值 define R BEGIN R KING define R END R PAWN define B BEGIN B KING define B END B PAWN define NOCHESS 0 没有棋子 黑方 define B KING 1 黑帅 define B CAR 2 黑车 define B HORSE 3 黑马 define B CANON 4 黑炮 define B BISHOP 5 黑士 define B ELEPHANT 6 黑象 define B PAWN 7 黑卒 红方 define R KING 8 红将 define R CAR 9 红车 define R HORSE 10 红马 define R CANON 11 红炮 define R BISHOP 12 红士 define R ELEPHANT 13 红相 define R PAWN 14 红兵 判断颜色 define IsBlack x x B BEGIN if val alpha 保留最大值 alpha val return alpha 2 4 历史启发及着法排序历史启发及着法排序 既然 Alpha Beta 搜索算法是在 最小 最大 的基础上引入 树的裁剪 的思想以期提高效率 那么它的效率将在很大程度上取决于树的结构 如果 搜索了没多久就发现可以进行 裁剪 了 那么需要分析的工作量将大大减少 效率自然也就大大提高 而如果直至分析了所有的可能性之后才能做出 裁剪 操作 那此时 裁剪 也已经失去了它原有的价值 因为你已经分析了所有情 况 这时的 Alpha Beta 搜索已和 最小 最大 搜索别无二致了 因而 要想 保证 Alpha Beta 搜索算法的效率就需要调整树的结构 即调整待搜索的结点的 顺序 使得 裁剪 可以尽可能早地发生 可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序 因为 通 常当一个局面经过搜索被认为较好时 其子结点中往往有一些与它相似的局面 如个别无关紧要的棋子位置有所不同 也是较好的 由 J Schaeffer 所提出 的 历史启发 History Heuristic 就是建立在这样一种观点之上的 在搜 索的过程中 每当发现一个好的走法 就给该走法累加一个增量以记录其 历 史得分 一个多次被搜索并认为是好的走法的 历史得分 就会较高 对于即 将搜索的结点 按照 历史得分 的高低对它们进行排序 保证较好的走法 历史得分 高的走法 排在前面 这样 Alpha Beta 搜索就可以尽可能早地 进行 裁剪 从而保证了搜索的效率 对于着法的排序可以使用各种排序算法 在程序中采用了归并排序 归并 排序的空间复杂度为 O n 时间复杂度为 O nlog2n 具有较高的效率 2 5 局面评估局面评估 前文已经讲过了棋局表示 着法生成 搜索算法 包括搜索辅助 在象 棋程序中如果说搜索算法是心脏 那么局面评估就是大脑 搜索算法负责驱动 整个程序 而局面评估则负责对搜索的内容进行判断和评价 因而搜索与局面 评估是整个下棋引擎的核心 首先 先介绍一下在局面评估中需要考虑的因素 就不同的棋类可能要考 虑的因素略有差异 在中国象棋中所要考虑的最基本的几个因素包括如下四点 1 子力总和 子力是指某一棋子本身所具有的价值 通俗地讲就是一个棋子它值个什么 价 例如 车值 500 的话 那可能马值 300 卒值 80 等等 所以在评估局面时 首先要考虑双方的子力总和的对比 比如红方拥有士象全加车马炮 而黑方只 有残士象加双马 则红方明显占优 2 棋子位置 棋子位置 或称控制区域 是指某一方的棋子在棋盘上所占据 控制 的 位置 例如 沉底炮 过河卒 以及车占士角等都是较好的棋子位置状态 而 窝心马 将离开底线等则属较差的棋子位置状态 3 棋子的机动性 棋子的机动性指棋子的灵活度 可移动性 例如 起始位置的车机动性较 差 所以下棋讲究早出车 同样四面被憋马腿的死马机动性也较差 对于一步 也不能走的棋子 可以认为其机动性为零 4 棋子的相互关系 这一点的分析较为复杂 因为一个棋子与其它子之间往往存在多重关系 如 一个马可能在对方的炮的攻击之下同时它又攻击着对方的车 在程序中 估值函数最后返回的是每一方的总分的差值 而各方的总分就 是上面所提到的四个因素的打分的总和 对于子力打分和控制区域打分 只要遍历棋盘 当遇到棋子时简单地去查 事先定义好的 子力价值表 和 控制区域价值表 取出相对应的值进行累加 即可 这些值的具体设定参考了前人的程序并作了适当的调整 今后仍应根据电 脑下棋所反映出的实际问题对这些值作适当修改 对于机动性打分 需要求出各个子总共有多少种走法 然后根据各个子所 不同的机动性价值每多一种走法就加一次相应的分数 对棋子间相互关系的打分 要用到以下几个数据 int m BaseValue 15 存放棋子基本价值 int m FlexValue 15 存放棋子灵活性分值 short m AttackPos 10 9 存放每一位置被威胁的信息 BYTE m GuardPos 10 9 存放每一位置被保护的信息 BYTE m FlexibilityPos 10 9 存放每一位置上棋子的灵活性分值 int m chessValue 10 9 存放每一位置上棋子的总价值 其中计算机会进行所有棋子值的判断 AttackPos 和 GuardPos 分别记录该 棋子受到的威胁和被保护的值 当遍历一遍棋盘之后 子力打分 控制区域打分和机动性打分都可以完成 而关系表也可以填完 之后 再根据关系表来具体考察棋子的相互关系 进行 关系打分 分析关系时 首先 对王的攻击保护应分离出来单独考虑 因为对王的保 护没有任何意义 一旦王被吃掉整个游戏就结束了 其次 对一个普通子 当它既受到攻击又受到保护的时候要注意如下几个 问题 1 攻击者子力小于被攻击者子力 攻击方将愿意换子 比如 一个车正遭 受一个炮的攻击 那么任何对车的保护都将失去意义 对方肯定乐意用一个 炮来换一个车 2 多攻击 单保护的情况 并且攻击者最小子力小于被攻击者子力与保护 者子力之和 则攻击方可能以一子换两子 3 三攻击 两保护的情况 并且攻击者子力较小的二者之和小于被攻击者 子力与保护者子力之和 则攻击方可能以两子换三子 4 攻击方与保护方数量相同 并且攻击者子力小于被攻击者子力与保护者 子力之和再减去保护者中最大子力 则攻击方可能以 n 子换 n 子 当然 上述四条只是覆盖了最常见的几种情况 覆盖并不全面 而且 在 程序中并没有直接地重新考虑双方兑子之后的控制区域及机动性变化情况 之 所以说没有 直接地重新考虑 是因为搜索继续展开结点后仍会考虑这些因素 只是目前不知这样效果是否受影响 考察这两种方法在效果上的差异需要一 定数量的试验数据的支持 所以 如果今后要对引擎进行改进 提高程序的下 棋水平的话 还应当在此进行研究 2 6 程序组装程序组装 至此 已具备了实现一款中国象棋对弈程序引擎部分的所有要素 将上述 模块分别写作 h 头文件 如下 Define h 象棋相关定义 包括棋盘局面和着法的表示 CMoveGenerator h 着法生成器 就当前局面生成某一方所有合法着法 CSearchEngine h 搜索部分 使用搜索求出最佳着法 HistoryHeuristic h 历史启发 Alpha Beta 搜索之补充 以提高搜索效率 着法排序 对着法按其历史得分进行降序排序 以提高搜索效率 CEveluate h 局面评估 为某一特定局面进行评分 当实现了引擎部分的各要素时 可先建了一个 Win32 控制台项目 之后只 要再添加一个 cpp 文件负责接受用户的输入 调用搜索函数 显示搜索结果 便可简单的测试引擎了 采用输入着法的起点坐标和终点坐标的方式来传送用 户走棋的信息 同样 程序显示计算机走棋的起点坐标和终点坐标来做出回应 此后 等到界面部分初步完成 引擎的上述各模块无需作任何改动 仍以 h 头文件的形式加入界面工程 只要由界面中的某个 cpp 文件调用搜索函数即 可 这种连接方式实现起来非常简单 3界面及程序辅助设计界面及程序辅助设计 3 1 界面基本框架界面基本框架 关于界面 建了一个基于对话框的 MFC 应用程序 主要工作都在对话框类 的两个文件 CChessDlg h 和 CChessDlg cpp 下展开 代码主要分布于以下三大部分 一 初始化部分 BOOL CCChessUIDlg OnInitDialog OnInitDialog 负责的是对话框的初始化 可以把有关中国象棋的棋局初 始化情况也放在了这里面 初始化的内容包括 对引擎部分所用到的变量的初始化 包括对棋盘上的棋子位置进行初始化 棋盘数组的初始化 对搜索深度 当前走棋方标志 棋局是否结束标志等的 初始化 对棋盘 棋子的贴图位置 即棋盘 棋子在程序中实际显示位置 的初始 化 对程序辅助部分所用到的一些变量的初始化 包括对悔棋 还原队列的清 空 棋盘 棋子样式的默认形式 下棋模式的默认选择 以及着法名称列表的 初始化等 二 绘图部分 void CCChessUIDlg OnPaint OnPaint 函数负责的是程序界面的绘图 因此 在这里将要完成棋盘 棋 子的显示走棋起始位置和目标位置的提示框的显示 由于棋盘 棋子等都是以位图的形式给出的 所以在 OnPaint 函数里做 的工作主要都是在贴位图 需要注意的是由于位图文件不能像 GIF 文件那样有透明的背景并且棋子是 圆形的而位图文件只能是矩形的 所以如果直接贴图的话会在棋盘上留下一块 白色的边框 棋子的背景 因此 要想让棋子文件的背景 隐藏 需要通过 一些 与 和 异或 操作来屏蔽掉棋子的背景 三 走棋部分 用户动作响应部分 为 WM LBUTTONDOWN 消息添加消息响应事件 可得到如下函数 void CCChessUIDlg OnLButtonDown UINT nFlags CPoint point 当用户在窗口客户区按下鼠标左键时 程序就会调用 OnLButtonDown UINT nFlags CPoint point 函数来进行响应 其中第二个参数 CPoint point 是在 本程序中所要用到的 它给出了当鼠标左键被按下时 鼠标指针的位置坐标 可以通过这一信息来得知用户的走法 在 OnLButtonDown 函数里处理如下两种操作 1 如果用户点击鼠标的位置落在己方的棋子上 表示用户选中了该棋子 下一步将移动该子进行走棋 也可能用户下一步将会选择己方另外的棋子 总 之这一操作会记录下用户所选的将要走的棋子 2 如果之前用户已经选过了棋子 那么这一次的点击 如果不是另选本方 的其它棋子的话 表达了用户的一次走棋过程 在收到用户传达的走棋信息后 可先判断该着法是否合法 是否符合中国象棋的游戏规则 如果合法 则执行 之 紧接着调用引擎的搜索函数计算出计算机对用户着法的应着 然后执行该 应着 如此 在 OnLButtonDown 函数里 实现了人与机器的对弈 当然每走一步 棋 也还需要绘图函数来显示棋盘局面的更新 以上三部分并非界面程序的全部 而仅仅是与程序密切相关的部分 此外 还有其它部分对程序同样必不可少 但这些部分主要由 MFC 自动生成 无需人 为改动 故在此不多做介绍 3 2 多线程多线程 如采用单线程方式 按照如下顺序编写代码 用户走棋 计算机思考并走棋 按这种方式编写的程序似乎毫无问题 程序运行一切正常 然而 在给程序加入这些功能 后面将会在讲到其实现 后 程序出现了 异常 有时对用户方的功能完全正确 而对电脑方的有些功能却不起作用 是 由于程序在进行搜索时会占用大量的 CPU 时间 因而阻塞了位于同一线程内的 其他指令 使之无法正常工作 解决方案就是另外开一个线程 让各程序分开 于多个线程 启动一个新的线程的方法非常简单 只需调用函数 AfxBeginThread 即可 函数原型 CWinThread AfxBeginThread AFX THREADPROC ThinkProc LPVOID pParam int nPriority THREAD PRIORITY NORMAL UINT nStackSize 0 DWORD dwCreateFlags 0 LPSECURITY ATTRIBUTES lpSecurityAttrs NULL 该函数启动一个新的线程并返回一个指向该新线程对象的指针 然后新的 线程与启动该新线程的线程同时运行 该函数的第一个参数 AFX THREADPROC ThinkProc 指定了线程函数 线程函数的内容即为新线程所要执行的内容 线 程函数执行完毕 新线程结束 自动销毁 线程函数必须被定义为全局函数 其返回值类型必须是 UINT 必须有一个 LPVOID 类型的参数 可以把调用引擎部分的搜索函数的代码以及完成走棋动作 的代码放入所定义的思考线程内 如下 DWORD WINAPI ThinkProc LPVOID pParam CChessDlg pDlg CChessDlg pParam pDlg Think 计算机思考并走棋 return 0 然后 只要将原先调搜索函数并完成走棋的代码代之以调用 AfxBeginThread 来启动新线程即可 实现了程序的多线程 不能正常工作的问 题也就随之解决了 3 3 着法名称显示着法名称显示 每当下棋方 用户或是计算机 走一步棋 在棋盘旁边的一个列表框控件 List Box 中按照中国象棋关于着法描述的规范要求显示出该着法的名称 如 红炮二平五 黑马 8 进 7 此类 为了获得该着法名称 写了一个六百余行 的函数 其功能就是将被移动的棋子类型以及走法的起点坐标 终点坐标这些 信息转换成中国象棋所规范的着法名称 由于该函数主要涉及的是中国象棋关 于着法表示的规范要求 故在此不对其具体实现做额外的解释 主要讨论的是 如何对列表框控件 List Box 进行操作 以显示或删除着法名称 首先 在 ChessDlg 下定义以下函数 this GetMoveStr nFromX nFromY nToX nToY nSourceID 用来获得刚下的一步棋的走法 void CChessDlg AddChessRecord int nFromX int nFromY int nToX int nToY int nUserChessColor int nSourceID 将走法添加进下棋记录 然后 显示在 Listbox 中 当列表框中的项的数目超过列表框的显示范围时 列表框会自动添加垂直 滚动条 前提是其 VerticalScrollbar 属性要为 True 该属性默认即为 True 但是显示的内容依然是最早加进来的项 在控件属性里选择 Vertical Scroll 使得列表框可垂直滚动以显示最新的着法名称 想要从列表框中删除项时 可以使用 m lstChessRecord DeleteString m lstChessRecord GetCount 1 减一之后正好是最后一项的行号 3 4 悔棋和还原悔棋和还原 悔棋和还原是棋类软件中较为基本的功能 要实现悔棋和还原功能 首先 要明确哪些信息应当被保存以供悔棋和还原所使用 在程序中保存了如下信息 棋局表示中所定义的棋盘数组 各棋子的贴图位置 这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保存所有棋 子的信息 而只是保存之前一步的走棋信息 此后当悔棋的时候 需要撤销着 法 还原的时候 需要执行着法 然而 在编写自己的程序时一来考虑到程序 的可读性和不易出错性 二来考虑到对当今的计算机的配置来说这点开销基本 上不会对程序的效率产生什么影响 因此保存了全部棋子的信息 根据所要保存的数据定义了如下基本结构类型 typedef struct CHESSMOVE cmChessMove short nChessID 被吃掉的棋子 UNDOMOVE 在对弈过程中 每一回合都将棋局信息 这里指前面所说的需要保存的信 息 保存至走法队列 以供悔棋所用 还原功能是与悔棋功能相对应的 只有 当产生了悔棋功能之后 还原功能才会被激活 一个回合的结束意味着前一次 操作没有悔棋功能的产生 因此还原队列也应被清空 在悔棋中主要完成了以下任务 1 下棋回合数减一 2 将当前局面信息保存至走法队列 以供还原所用 3 从走法队列中取出上一回合的棋局信息 恢复到当前局面 然后将其从 队列中剔除掉 4 将显示着法名称的列表框中的本回合的着法名称保存到一个着法名称队 列 以供还原所用 然后从列表框中删除它 而在还原中所做的刚好和悔棋相反 1 下棋回合数加一 2