当前位置:首页>> >>


vc中国象棋算法设计与实现.rar

收藏

资源目录
    文档预览:
    编号:20180913212648242    类型:共享资源    大小:23.11MB    格式:RAR    上传时间:2018-09-13
    尺寸:148x200像素    分辨率:72dpi   颜色:RGB    工具:   
    45
    金币
    关 键 词:
    vc 中国象棋 算法 设计 实现
    资源描述:
    中国象棋需求与设计报告吕文龙,10300720147高楠,10300720246一、系统概述1.1 软件用途提供了一个 PC 端的中国象棋游戏。同时发布了 GUI 版与 CLI 版。其中 CLI版为象棋 AI 部分开发过程中用作测试。但已经具有完整的人机对弈功能与相对友好的界面。考虑到有些用户可能相对 GUI 更偏向命令行操作方式,因此与 GUI版本一起发布。CLI 版本只有人机对弈功能,默认黑方(AI)先走。AI 原理与 GUI 版相同, 以下文档只对 GUI 版作出说明。如无特殊说明, 提到”软件 ”时,所指均为 GUI 版本。软件具有两种模式,双人对弈与人机对弈。 若选择双人对弈, 因为此版本暂未开发联机对弈功能, 只能双人共用一台PC,红方先走,黑方后走,有一方被将死,即无棋可走时, 电脑会自动判定胜负。若选择人机对弈,默认用户执红子,AI 执黑子。软件可自动判定胜负。软件在 ubuntu 13。04、windows7、windowsXP 平台下测试性能良好。此版本未实现的功能:长将判负。即假定红方只剩 5 个兵与一个将,且全部过河。黑方只剩一个将与一个车。则黑方基本不可能将死红方。但红方必定可在有限步之后将死黑方。则黑方为自保,最优策略是每一步都用车将红方的军 ,但无法将其将死。此时游戏会陷入循环。在正式象棋比赛中,任何情况下, 长将判负。考虑到主要是面向人机对弈, 和棋功能无意义, 亦未开发。此 AI 与软件作者对弈 ,目前 AI 保持不败战绩。与其他测试者对弈,也是胜多败少。与作者 ipad 上的象棋 app 对弈,互有胜负, 但软件 AI 胜少败多游戏截图:进场画面:游戏界面:1.2 游戏特色最大可达可接受时间内 7 层搜索深度,AI 具有较高棋力。游戏固定权值与棋盘位置分值相结合的评估函数。基于 alpha-beta 搜索 ,走法排序后 PVS 搜索策略。1.3 系统开发过程软件作者为吕文龙与高楠。 吕文龙负责开发系统的 AI 部分,即局面表示,走法生成,局面评估 ,Alpha-Beta 搜索,搜索策略优化。高楠负责系统 GUI 的设计与实现。部分 GUI 设计吕文龙亦有参与。 开发过程:先实现了一个无 GUI 的搜索策略为 alpha-beta 剪枝的命令行版本。再实现了一个基本的 GUI 版本。接下来 GUI 部分开始开发 regret/restart/搜索进度条 等工作。 AI 部分则着重于搜索策略的优化。六月份开始进行优化, 一共经历过两次优化, 一次走法栈生成时的自动排序使得 Alpha-Beta 的可接受搜索深度(在 10s 左右完成搜索)由 depth=5 提升到 depth=6。搜索时引入 PVS 算法,使得可接受的搜索深度增加为 7。文档的 GUI 部分为高楠负责写作,AI 部分由吕文龙负责写作1.4 AI 代码阅读提示AI 部分代码在 kernel 文件夹中,建议用户先阅读 global.h,了解声明了哪些全局变量。则其余代码的算法都不复杂,应当较容易阅读。1.5 提交文件的结构二、系统需求说明2.1 系统总体功能可以实现双人对弈与人机博弈.AI 会检查走子的有效性.AI 会自动判定胜负具有悔棋功能. 但软件作者一致认为君子有所为有所不为,落子无悔才是值得提倡的.因此对用户悔棋功能设置了一些障碍 .用户需连续点击弹出的对话框10 次之后 ,同时接受 AI 的冷嘲热讽. 才允许悔棋. 若用户终于决定放弃悔棋.关闭对话框即可.若选择人机对弈,用户被 AI 吃子后会提示被吃了哪个子.可以 restart,即棋局进行到中局或是一局终了, 用户想要重新玩一局, 可点击 restart.若用户被将军,则必须应将,若不应将, 则会弹出对话框提醒用户.人机对战模式中,AI 会在被将死之前就认输,即当 AI 检测到它几步之后必然会被将死, 就会提前认输.可接受的时间内搜索深度可达 7 层 alpha-beta 搜索 .但是一开始就采用 7 步搜索无必要.因而设定前 5 回合(十步)进行 5 层搜索 ,5 回合之后到 25 回合(50 步)采用 6 步搜索.若之后用户仍未被将死.将采用 7 步搜索.人机对弈模式中,界面右下方会以进度条显示 AI 已搜索结点的比例。2.2 环境需求AI 部分与 GUI 部分由两人分工完成 .(一) 开发环境AI 部分:TOSHIBA C600D-01L 笔记本电脑.AMD Athlon(tm)II P320 Dual-Core Processor,Ubuntu13.04 操作系统,使用 vim 编写, 测试程序使用 g++4.7.4 编译.AI 部分测试功能正确后, 交由高楠进行 GUI 的实现.GUI 开发环境:Acer Aspire 4736ZG 笔记本电脑.Pentium (R) Dual-Core CPU T4500, Windows7 企业版 32 位操作系统,使用 Qt Creator 4.8 编写(二)运行环境在 ubuntu13.04 及 windows7、winXP 操作系统下可流畅运行.作者测试游戏所用 CPU 较为低端,游戏运行仍较为流畅.用户所用 CPU 性能不错的话,可以考虑一开始就将搜索深度设为 6 或者 7.2.3 系统功能需求可选的对战模式____双人对弈或人机对弈启动游戏后, 点击相应 button,即可选择相应对战模式。双人对弈:若选择双人对弈功能,则可双方交替走子. 系统会自动检测走子的有效性,不合规则的走子无法走出.若一方胜利,则系统会弹出对话框告知 “black_lose”或是”red lose”.人机对弈:选择人机对弈模式之后,默认用户执红子先走. 同样会检测走子有效性,同时还会检测红黑双方是否被将军,若被将军,则必须应将, 不应将的走法时无效的.即红黑双方的将在游戏过程中并不会真正的被吃掉,只要一方的将被将死 ,则系统会判定胜负.AI 会在被将死之前几步就检测出自己会被将死而无可补救,此时 AI 会认输.退出功能:点击 exit 按钮, 可以退出程序.restart 功能:点击 restart 按钮, 可重新开始棋局.悔棋功能:点击 regret 按钮 ,弹出对话框劝用户不要悔棋 ,用户执意悔棋, 则撤销之前两步的走法(红方与黑方的).注意:悔棋是撤销两步走法,因此若是在双人对弈模式,A、B 两人对弈,A 走出之后要悔棋,必需在 B 走完之后才能成功。将军提醒:用户被将军而不应将时,系统会作出提醒.进度条:选择人机对战模式时,机器思考时,界面下方会有进度体啊显示机器搜索的程度.三、系统设计3.1 系统设计决策AI系统设计时,将 AI 与 GUI 分开设计.AI 根据当前局面进行搜索/决策,产生最优走法, 将走法传递给 GUI,GUI 刷新界面.GUI 部分在用户界面设计部分会有详细说明,此处介绍 AI 的设计.用户可以通过运行 CLI 版本的游戏了解 AI 的整体架构.AI 设计策略:一切以程序的运行速度为优先考量 .为了说明采用这种编码方式的理由,可以先看一下 AI 设计完成之后,作者做的一组统计:开局第一步,共有 44 种走法 ,作者统计了不同搜索策略走第一步棋时搜索到的叶结点数目, 这里的叶结点数是指真正会去做局面评估的叶结点 .被剪枝的叶结点不在其中.未经走法排序的 Alpha-Beta 搜索各搜索深度实际搜索叶节点数搜索深度 1 2 3 4 5 6 7结点数 44 1131 27771 308046 6844627 速度无法 速度无法接受 接受经过走法排序后的 Alpha-Beta 搜索各搜索深度实际搜索叶节点数搜索深度 1 2 3 4 5 6 7结点数 44 84 1660 13653 136914 970891 速度无法接受经过走法排序后采用 PVS 算法的搜索策略各搜索深度实际搜索叶节点数搜索深度 1 2 3 4 5 6 7结点数 44 84 1660 12090 114080 889412 6482373将上表中走法排序后再 reverse 一次后的 PVS 搜索策略各搜索深度实际搜索叶节点数搜索深度 1 2 3 4 5 6 7结点数 48 2063 72295 1519640 14700791 速度无法接受 速度无法接受注:PVS 算法为先用小窗口的 alpha-beta 试探,若试探失败,则重新进行搜索.所以排序排的不好,可能访问结点数大于实际结点数,如第三张表中搜索深度为 1时,实际有 44 中走法, 却访问了 48 个结点.上表中各种搜索策略文档后面会详述,但是用户可以很直观的感受到 :(1)不同搜索策略搜索效率差别很大,甚至可以是数量级上的差异 .(2)搜索量随搜索深度指数上升.因而 AI 部分属于高计算量的程序 ,微小的速度差异会在大量的计算过程中被放大.AI 的实质是数学上的决策过程.因而在 AI 部分编码过程中, 没有采用面向对象的设计风格。因为 AI 思考的过程本质上是计算过程而非事件直接消息传递的模型。同时,具体实现上 ,大量的采用辅助数组等冗余数据结构,以空间换时间。函数的参数通过全局变量传递/引用传递而非值传递传递.分支结构尽量采用switch-case 结构而非 if-else 结构.GUIGUI 部分的设计包括一个进场画面,选择对战模式,以及实际游戏的棋盘。进场画面选择了一个战争的场面,因为象棋是模拟战争的游戏。棋盘没有采用一般的象棋的木质拟物设计,而是自己手绘设计了棋盘。棋子也经过重新设计。红方采用瘦金体,而黑方则采用颜体楷书。进场画面为游戏《三国策》壁纸,棋盘采用 ipad 上的 app “Paper”绘制。3.2 系统总体设计3.2.1 设计思想AI 与 GUI 部分分别完成 ,通过接口实现通信.AI 部分AI 部分采用 bottom-up 的方法设计,包括局面表示/走法生成/局面评估/ 将军检测/搜索算法.AI 部分代码在 kernel 文件夹中.kernel 文件夹中代码的组织与 AI的结构同构.表征局面的数据结构以及其他一些全局变量在 global.h 中声明, 在define_global.cpp 中定义.move 文件夹中为走法生成的函数 .check 文件夹中为将军检测函数.eval 文件夹中为局面评估函数.search 文件夹中为搜索函数.每个文件夹中都有 test.cpp 及 makefile,为相应函数的测试代码. 用户可到相应文件夹中运行 make,然后执行可执行文件查看测试结果(makefile 在 linux 环境下写成)AI 部分概述:以长度为 256 的一维数组表示棋盘,其中 90 个数字表征棋盘,其余部分为冗余数据,置零.棋盘的表示还有相关冗余数据结构. 棋子以数字编码.走法生成函数生成走法,搜索算法调用评估函数,给出局面估值及最佳走法.搜索基于 alpha-beta 剪枝算法. 剪枝效率与遍历走法栈的顺序关系很大,因此生成走法时按照一定规则对走法栈排序. 还采用了 PVS 算法对 alpha-beta 算法进行优化.GUI 部分/*****************/3.2.2 系统体系结构分为 AI 部分, AI 部分没有使用面向对象的方法,只以文字说明。GUI 部分有类图等描述(一)局面表示.建议用户阅读 global.h 头文件. 其他文件中的代码大抵知道函数功能即可.表征局面/ 走法等的数据结构均在 global.h 中声明,在 define_global.cpp 中定义.其中 short side 表示当前走棋一方,side=0,表示红方,side=1,表示黑方.局面的表征主要通过两个数组,棋盘数组 board 和棋子数组 piece,这两个数组是等价的,在 AI 思考过程中保持同步。之所以设置两个数组,是因为不同情况下使用不同数组更加方便或者运算速度更高。采用 short board[256] 表征棋盘 ,非棋盘位置 0.棋盘上无棋子的位置也为 0.采用 256 长度的数组, 可以方便的像使用二位数组那样使用一维数组, 如想要表征第三行第四列, 只需使用 board[0x34]即可.对每一个棋子,有一个(对兵来说,有两个, 红黑有别)合法位置数组,也是长 256 的一维数组.若棋盘上的一个位置是该棋子的合法位置,则为 1,否则则为 0.棋子在 board 数组中位置为 board 数组元素下标。棋盘为 9*10,因此是嵌在 board 数组中。如图所示:对于棋子,用不同数字表示不同棋子,一个编码数字与一枚棋子一一对应,编码如下:红方 帅 仕 相 马 车 炮 兵表示数 16 17,18 19,20 21,22 23,24 25,26 27,28,29,30,31黑方 将 士 象 马 车 炮 卒表示数 32 33,34 35,36 37,38 39,40 41,42 43,44,45,46,47如此,譬如红方将一开始是在上图中 c7 位置处,则有 board[0xc7]=16。这样编码的好处:令 side_tag=(side==0 ? 16 :32)则红方编码 & 16 ==16, 红方编码 & 32==0,
    展开阅读全文
    1
      金牌文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    0条评论

    还可以输入200字符

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

    关于本文
    本文标题:vc中国象棋算法设计与实现.rar
    链接地址:http://www.gold-doc.com/p-139102.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们
    copyright@ 2014-2018 金牌文库网站版权所有
    经营许可证编号:浙ICP备15046084号-3
    收起
    展开