软件系统设计报告

1、软件系统设计报告齐天大圣之中国象棋专 业：计算机科学与技术 班级：计04-6班小组成员：周川祥指导教师：张博、徐慧职称：2007年6月 徐州 TOC o 1-5 h z 一、概述-1 - HYPERLINK l bookmark29 o Current Document 1引言-1 - HYPERLINK l bookmark32 o Current Document 2项目开发计划-1 - HYPERLINK l bookmark35 o Current Document 2.1开发周期-1 - HYPERLINK l bookmark41 o Current Document 2.2详细计

2、划-1 - HYPERLINK l bookmark44 o Current Document 二、概要设计-2 - HYPERLINK l bookmark47 o Current Document 1网络对战平台-2 - HYPERLINK l bookmark56 o Current Document 2人机对弈-2 - HYPERLINK l bookmark66 o Current Document 3游戏流程-2 - HYPERLINK l bookmark69 o Current Document 三、详细设计-4 - HYPERLINK l bookmark72 o Curre

3、nt Document 1、基本数据结构定义-4 - HYPERLINK l bookmark76 o Current Document 1.1棋子与棋子坐标-4 - HYPERLINK l bookmark79 o Current Document 2.2棋子移动于悔棋-4 - HYPERLINK l bookmark103 o Current Document 2、基本走法判断和走法产生-5 - HYPERLINK l bookmark107 o Current Document 2.1走法判断-5 - HYPERLINK l bookmark110 o Current Document

4、2.2走法产生与搜索-5 - HYPERLINK l bookmark113 o Current Document 3、网络版-5 - HYPERLINK l bookmark117 o Current Document 3.1网络消息定义-5 - HYPERLINK l bookmark126 o Current Document 3.2网络套接字设计-6 - HYPERLINK l bookmark138 o Current Document 3.3网络消息处理-6 - HYPERLINK l bookmark141 o Current Document 4、单机版-6 -4.1估值函数-

5、6 -4.1.1棋子的基本值与附加值-6 - HYPERLINK l bookmark152 o Current Document 4.1.2棋子的灵活性与棋盘控制74.1.3棋子关系的评估7 HYPERLINK l bookmark155 o Current Document 4.1.4返回给搜索接口84.2搜索函数8博弈树8 HYPERLINK l bookmark165 o Current Document alpha-beta 搜索8 HYPERLINK l bookmark174 o Current Document 5、其他功能10 HYPERLINK l bookmark178

6、o Current Document 5.1悔棋与还原10 HYPERLINK l bookmark181 o Current Document 5.2保存残局10 HYPERLINK l bookmark184 o Current Document 5.3动态显示CPU和内存使用情况10 HYPERLINK l bookmark187 o Current Document 6、界面10 HYPERLINK l bookmark191 o Current Document 6.1绘制棋子106.2皮肤11四、项目测试11 HYPERLINK l bookmark197 o Current Do

7、cument 1、网络版11 HYPERLINK l bookmark201 o Current Document 2、单机版11 HYPERLINK l bookmark205 o Current Document 五、用户使用说明11 HYPERLINK l bookmark212 o Current Document 六、问题分析11 HYPERLINK l bookmark216 o Current Document 1、程序执行效率11 HYPERLINK l bookmark228 o Current Document 2、内存管理的时间开销12 HYPERLINK l bookm

8、ark231 o Current Document 3、程序智商12齐天大圣之中国象棋软件系统设计1引言前几学期，我们学习了计算机专业的几门核心课程，如数据结构、操作系统 等。但是所学的仅仅停留在理论层次，没有系统的将理论于实践结合起来，缺乏 动手能力。针对以上问题，本项目主要是运用数据结构与算法、计算机网络及TCP/IP 与编程等基础知识，结合人工智能、博弈论相关理论，用Visual C+ 6.0开发平 台来开发“齐天大圣之中国象棋”，本项目融合人机对弈和网络版于一体，用户 可以随心所欲的在单机版与网络版中切换，还可以登录游戏大厅（简易版），选 择好友对战。2项目开发计划21开发周期8周（2

9、007年5月2007年7月）2.2详细计划1113周复习有关数据结构与算法和网络编程基本方法，学习博弈论相关理论1415周编制象棋中各个棋子的走法和攻防判断，初步开发出网络版雏形，给出评估函数。16周完善网络版，运用前期学习的博弈树和人工智能方法，给出简易搜索函数17周优化搜索函数，进一步做好细节部分，进行项目测试18周整体把握，进一步完善二、概要设计1网络对战平台网络版主要功能如下：1、聊天功能2、判断走棋是否正确，程序自动恢复用户走错的棋位。3、如果一方走棋超时，给出提示后程序自动走一步。4、任意一方可以提出悔棋请求，待对方同意后即可悔棋5、任意一方可以提出还原悔棋请求，待对方同意后即可还

10、原6、根据用户需要更改皮肤（包括整体颜色和背景图片）2人机对弈人机对弈主要功能如下：1、对当前的棋局进行估值，判断双方的势力优劣2、根据当前棋局估值结果，寻找一步最优的走法3、调用搜索线程，根据当前的搜索结果走一步棋4、具有悔棋和还原功能5、动态显示当前搜索使用CPU和内存情况，评价搜索的效率6、根据用户要求改变下棋的难度7、根据用户需要更改皮肤（包括整体颜色和背景图片）3游戏流程以下是本游戏的流程图:中国象棋游戏总流程图三、详细设计1、基本数据结构定义1.1棋子与棋子坐标typedef enum /棋子定义NoChessMan=0,/ 没有棋子/帅 车马炮 仕象兵BlackKing,Blac

11、kRook,BlackHouse,BlackGunner,BlackAssist,BlackBishop, BlackSoldier,/将 车 马 炮士 象 卒RedKing,RedRook,RedHouse,RedGunner,RedAssist,RedBishop,RedSoldier,ChessMan;_ 棋子坐标，由于考虑到搜索时内存可能会占用很多，为了尽量节省内存， 采用 了 byte 类型，byte 类型的定义为：typedef BYTE unsigned charstruct ChessPosBYTE x;BYTE y;2.2棋子移动于悔棋棋子的移动struct ChessMov

12、eint ChessID;ChessPos pFrom;ChessPos pTo;正在移动的棋子struct MovingChessBYTE nChessID;POINT ptMovePoint;悔棋时需要的数据结构struct UnDoMoveChessMove cmChessMove;short nChessID;/被吃掉的棋子;/棋子类型定义typedef enumBLACKCHESS,REDCHESS;2、基本走法判断和走法产生2.1走法判断主要工作在CMoveGenerator类的成员函数IsValided（涵数中实现，分别对 每个棋子进行判断。此处省略。2.2走法产生与搜索在进行走

13、法产生的时候，往往伴随着搜索进行。对于一个局面的所有直接后 继，有两种选择：一次产生一种走法然后搜索之；或者一次产生其所有走法然后 搜索之。由于存在着剪枝算法，对一个局面的某一走法搜索之后往往可能不再需 要搜索其他后继，也就是说：可能不用产生全部走法就能够完成搜索。一次产生 一种走法看起来似乎更有效率。但是，由于剪枝算法的剪枝效率很大程度上依赖 于节点的排列顺序，往往一次产生所有节点，然后以某种方法调整其排列顺序会 使搜索效率大大提高。所以，在实际使用中，先一次产生一个局面的全部走法， 然后调整其搜索顺序。实际上，为了减少运算量，事先建立的小型数据库，将所有的走法都保存在 数据库中，然后检索数

14、据库，这样会效率高一些。3、网络版3.1网络消息定义定义在CMyMessage类中。在CMyMessage中，成员函数virtual void Serialize（CArchive& ar）;来将网络消息先序列化后再进行传输，接受方受到消息在调用Serialize（）函数，就可以恢复出消息，这样方便。但这样只能用于有限的数据类型。3.2网络套接字设计本程序将套接字以类的形式进行了封装，由于基于c/s模式需要侦听和接受 套接字，所以本程序主要将不同的套接口须完成的任务封装成了两个 类:CClientSock ,CServerSock，他们都派生于MFC封装的CSocket类，然后重载 相应得虚函

15、数，用来完成各自得功能。在CClient类中，定义类以下几个数据成 员CArchive* m_aSessionIn;CArchive* m_aSessionOut;CSocketFile* m_sfSocketFile;用于发送/接受消息时进行串行化。详细请参考源代码。3.3网络消息处理网络消息处理主要放在CClient类的OnReceive()函数中，当然也可以放 在CChineseChessDlg中。根据网络消息的定义iFlag标志为分为不同的消息进行 处理。/0表示走棋，1表示下载服务器信息,2表示同步请求，具体处理见Client.cpp 文件中的OnReceve()函数4、单机版4.1

16、估值函数4.1.1棋子的基本值与附加值棋子的价值评估，简单的说就是评估双方都有哪些棋子在棋盘上。程序中让 一个车价值为500，一个马价值为300，一个兵价值为100等等。将的价值为无 限大(通常用一个远大于其他棋子的数)。一方的棋子总值就是棋盘上存活的该 方棋子乘以棋子价值的和。用一个式子表达：SideValue=Sum ( PieceNumber X PieceValue)其中PieceNumber是某种棋子的数量，PieceValue是该种棋子的价值，Sum是 对各种棋子的总价值求和。如果红色的棋子价值总和大于黑色的棋子价值总和， 通常这意味着红方的局势优于黑方。而红黑双方的SideVal

17、ue之差越大，红方的 优势也就越大。但对于卒/兵，还存在过河卒的附加值，程序中的基本值为：卒的附加值矩阵为：constint卒的附加值矩阵为：constintBlackSoldier_AddValue109=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,100,100,100,100,100,100,100,100,100,100,120,140,140,140,140,140,120,100,120,120,140,150,150,150,140,120,12

18、0,120,120,140,150,150,150,140,120,120,0,0,0,0,0,0,0,0,0,;RedSoldier_AddValue109= 0,0,0,0,0,0,0,0,0,120,120,140,150,150,150,140,120,120,120,120,140,150,150,150,140,120,120,100,120,140,140,140,140,140,120,100,100,100,100,100,100,100,100,100,100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

19、,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4.1.2棋子的灵活性与棋盘控制棋子的灵活性是指棋子的活动范围，通常是越大越好。一匹不能动的马很难 在棋局中发挥重要作用；同样，一个蹲在角落里的车也是价值不高的。评估棋子的灵活性较为简单，将一个棋子的所有合法走法罗列出来，乘上该 种棋子每一可走步的价值就行了。Mobility=Sum (MoveNumber X MoveValue)其中，MoveNumber是某种棋子的合法走法数量，MoveValue是该种棋子每 一走法的价值，Sum是对所有棋子的灵活性价值求和。Mobility就是所有棋子的 灵活性分数。与灵活性评估类似，还可

20、以评估博弈双方对棋盘上位置的控制能力。在象棋 中，如果一位置落在某方棋子的合法走步上，就可以认为被该方控制。如果某一 位置同时落在双方的合法走步上，我们可以根据双方控制该位置的棋子数量及棋 子价值来决定孰优孰劣。能控制更多位置的一方应在这项评分上占优。4.1.3棋子关系的评估棋子间的关系也是估值的重要内容之一，我们可以将某个棋子被对方棋子威 胁看成是一个不利的因素。例如红车的位置在黑马的合法走步当中，此时我们可 以把红车的价值减去一个值(例如200)来刻画这种情形。而如果红马在黑车的 合法走步之中，而红马同时也在红卒的合法走步之中，我们可以认为红马置于红 卒的保护之下，没有受到威胁，价值不变。

21、棋子关系的评估应考虑到该谁走棋的问题。如果某个红马落在黑炮的合法走 步之内，但此时轮到红方走棋，应认为红马受到的威胁较轻。而如果此时轮到黑 方走棋，就应认为红马受到的威胁很大，应减去一个相对较大的值了。如果将被 对方威胁，且轮到对方走棋，那么无论有何种棋子可以走到将位都没有意义，将 等于失去了。此时应结束估值返回失败的估值（通常是极大或极小值）。4.1.4返回给搜索接口一个估值函数可以从若干角度评价某一局面上博弈双方的优劣程度。把这些 不同方面的评价得分加在一起，就构成了一方的价值总和。如果我们把红方的价 值总和叫做RedValue，黑方价值总和叫做BlackValue，那么一个局面的估值Va

22、lue 就是红方和黑方的价值差。表达如下式：Value=RedValue-BlackValue这个Value也就是最终返回给搜索引擎的估值。4.2搜索函数4.2.1博弈树甲乙两人对弈，假定现在该甲走棋，甲可以有40种走法（不论好坏）；而对 甲的任一走法，乙也可以有与之相对的若干种走法。然后又轮到甲走棋，对乙的走法甲又有若干种方法应对如此往复。显然， 我们可以依此构建一棵博弈树，将所有的走法罗列出来。在这棵树的根部是棋局 的初始局面。根的若干子节点则是由甲的每一种可能走法所生成的局面，而这些 节点的子节点则是由与之相对的乙的每一种可能走法所生成的局面在这棵 树的末梢，是结束的棋局，甲胜或者乙胜或

23、者是双方都无法取胜的平局。在通常的棋局当中，一个局面的评估往往并不像输、赢、平3种状态这么简 单，在分不出输赢的局面中棋局也有优劣之分。根据估值函数的分析，可规定甲 胜为+8 ；乙胜为-8 ；和局为0；其他的情形依据双方剩余棋子的数量及位置 评定-8+8之间的具体分数。这样我们可以建立一棵固定深度的搜索树，其 叶子节点不必是终了状态，而只是固定深度的最深一层的节点，其值由上述函数 评出；对于中间节点，如同前面提到的那样，甲方取子节点的最大值，乙方取子 节点的最小值。4.2.2 alpha-beta 搜索Alpha-beta搜索是有基本的极大极小值搜索经过alpha和beta剪枝优化后 而得。详

24、细的alpha-beta搜索分析在这里不再敖述，以下为alpha-beta搜索的伪 代码：/nDeep为搜索深度，nAlpha,nBeta为当前的alpha和beta值。intAlphaBeta （nDeep，nAlpha， nBeta）if (gameover)return Eveluation ； 胜负已分，返回估值if (nDeep = 0)returnEveluation ； 叶子节点返回估值if (IsMinNode) 此句用于判断当前节点是何种节点/是取极小值的节点for (eachpossiblemove m) 对每一可能的走法 mmakemovem； 生成新节点score =

25、alphabeta (nDeep-1, nAlpha, nBeta) 递归搜索子节点 unmakemovem ； 撤销搜索过的节点if (score = nBeta)returnnAlpha； /alpha剪枝，抛弃后继节点returnnBeta； 返回最小值else取极大值的节点for (each possible move m) 对每一可能的走法 mmake move m； 生成新节点score = alphabeta (nDeep-1, nAlpha, nBeta) 递归unmake move m ； 撤销搜索过的节点if(score nAlpha) /取极大值nAlpha = scor

26、e；if (nAlpha = nBeta)return nBeta； /beta剪枝，抛弃后继节点return nAlpha ； 返回极大值5、其他功能5.1悔棋与还原悔棋的思想很简单，只是调用STL的stack容器，保存每一步走法，当需要悔棋时，从相应 得栈中弹出来即可，注意需要导入#includeUsing namespace std;5.2保存残局运用CFileDialog类对象打开文件选择对话框，定义FILE* fp;fp=fopen(pCMFile,nw);/打 开for(i=0;i10;i+)for(j=0;j=BlackKing&x=RedKing&x=RedSoldier)判断

27、是不是同一方的棋子#define IsSameSide(x,y) (IsBlack(x)&IsBlack(y)|(IsRed(x)&IsRed(y)这样C+就当作内联来处理。有些函数在程序中反复被调用了无数次，如果把它写成内联函数，这样会大 大提高执行效率的，但是，C +的编译器对于任何内有循环语句的内联函数都 认为是过于复杂， 而不当作内联处理了。例如判断游戏 是否中止的函数 IsGameOver(),这段代码检查了将帅是否都还存在，并返回了结果。我们可以把该 函数内部的循环展开，将若干语句逐一写上去，将帅的位置并不太多，这样也比 使用循环快一点。然后，编译的时候内联代码就产生了。C+中虚函

28、数存在后期绑定问题，由于走法产生、估值、搜索相互对象中 存在反复调用，严重影响了执行速度，较快速的方法也是将估值、走法产生和搜 索引擎合成一个类，让它们之间在互相调用时不再使用对象指针操作虚函数，这 样就可以去除在核心代码中由于后期绑定所造成的性能损失。但是这样，这个类 就太庞大了，影响了程序的可读性，也违反了面向对象的基本思想。2、内存管理的时间开销申请内存的操作同算术运算、赋值、函数调用等操作相比，是相当缓慢的。 所以当程序执行市，在搜索的过程中避免动态的申请内存。也要避免创建对象， 因为任何对象的创建同样会引发内存的动态分配在产生走法时，程序首先将走法队列置于一段预先申请的内存当中，以避免 频繁的申请动态内存而引起大量的时间耗费。当搜索引擎对象被创建出来时，所 有的