中国象棋需求与设计方案（WORD版完整可编辑，需更多资料请联系）一、系统概述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种走法,作者统计了不同搜索策略走第一步棋时搜索到的叶结点数目,这里的叶结点数是指真正会去做局面评估的叶结点.被剪枝的叶结点不在其中.将上表中走法排序后再reverse一次后的PVS搜索策略各搜索深度实际搜索注: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数组元素下标。