中国象棋游戏开发设计报告.doc

中国象棋游戏开发设计报告班级： 小组编号： 小组成员： 指导老师： 一、开发的目的和意义面向对象程序设计作为一门软件设计的课程，具有极强的实践性，要求学生具备灵活应用理论知识的能力及面向对象程序设计技能的基础。通过游戏开发，学生能了解c+面向对象的设计方法与技巧，有效地、深刻地理解课程内容，体会理论、方法和设计原则，培养分析实际问题和解决问题的能力，具备使用面向对象程序设计开发工具设计实际系统的能力。还能够了解并通过使用mfc，掌握一种可视化编程的方法，并通过游戏的开发加深对可视化编程的理解。同时，可以提高运用c+编程语言解决实际问题的能力。棋牌游戏属于休闲类游戏，具有上手快、游戏时间短的特点，更利于用户进行放松休闲，为人们所喜爱，特别是棋类游戏，方便、快捷、操作简单，在休闲娱乐中占主要位置。中国象棋作为中国自古以来的经典棋牌游戏之一，一直都是人之间的较量，将中国象棋制作成游戏，可以实现人与计算机之间的对弈。而且人工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。开发出了计算机象棋游戏，以后不仅仅可以进行休闲游戏，还能锻炼自己的智力和象棋技术，更加方便了人们的日常生活。二、功能描述和分析（用户需求分析）2.1开发背景 我们周围有许多同学喜欢下象棋,尤其是男同学，希望能有人可以和自己下象棋，但这种意愿常因为受到条件的限制而难以如愿，比如说需要身边刚好有现成的棋盘棋子，比如说需要是同样懂得中国象棋的对手，但是大家都知道我们这所大学男性同学占少数,即便是条件都满足了，还要考虑这位对手是否有何自己下棋的心情。 这时，如果有一台计算机，一个能够支持人机对弈的程序，上面的问题迎刃而解。而我们小组的这个想起游戏设计，正是希望能够做出一款拥有良好性能，良好的智能，能够满足大多数爱好象棋的同学的需求中国象棋人机对弈程序。2.2用户需求分析 一款能够与用户对弈，满足用户需求的中国象棋程序，需要有棋盘棋子的局面、鼠标响应控制棋子移动、棋子的走法规则、人机对弈的搜索算法、避免异常引入的多线程、胜负判断，具体分析如下：2.2.1棋盘棋子的局面 作为中国象棋的这项游戏，其必不可少的是就是棋子和棋盘，没有这两个部分，想起功能无法实现，不仅仅如此，如果，仅仅有棋子和棋盘，而没有将两者结合起来，那么，也将无法实现中国象棋的游戏功能，所以，棋子和棋盘的设计在这个游戏设计中至关重要。2.2.2鼠标响应在对弈中，棋子是必须可以移动的，不然游戏无法进行。因此，鼠标左键点击是必不可少的一部分。2.2.3棋子的功能分析：中国象棋中各色的象棋棋子的功能使象棋具有了真正的趣味性，中国象棋的棋子的类型大致分为：帅（将）、士、象、马、车、炮、兵（卒）等几个类型。帅（将）：红方中的帅和黑方中的将的功能相同，都是只能在九宫格中进行横向和竖向的移动，每次移动一格，并且不能移动超出九宫格，帅和将不能见面。士：士在整片棋盘中，和帅的移动范围类似，也是只能在九宫格中移动，不过士的移动方向是对角线，并且每次只能在一个格子中移动。象：象的走法遵循“象走田”的原则，不能绊象腿。马：马的走法遵循“马走日”的原则，不能绊马腿。车：在整块棋盘中，车可以横向或纵向3移动任意格。炮：每次移动和车的类似，但是在吃对方棋子的时候必须中间有且只能有一个棋子的间隔。兵（卒）：红方的兵和黑方的卒的功能相同，特点是只能向对方前进，而不能后退，过河之前不能横向移动，过河之后可以横向移动，不管是前进还是横向移动，每次都只能移动一格。2.2.4良好的人机对弈要实现人机的对弈，搜索算法是很重要的一部分。关于棋类对弈程序中的搜索算法，已有成熟的alpha-beta搜索算法。我们在程序中直接借鉴了alpha-beta搜索算法并辅以历史启发。alpha-beta搜索算法：在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是吃掉对方的将或帅，或者避免自己的将或帅被吃。搜索算法的搜索过程很漫长，因此对搜索算法进行简化是有必要的。2.2.5多线程的必要性由于程序在进行搜索时会占用大量的cpu时间，因而阻塞了位于同一线程内的其他指令，使之无法正常工作，因而引入了多线程的思想另外开一个线程，让各程序分开于多个线程。就可以解决程序异常的问题了，因此，多线程思想的引入是有必要的。2.2.6判断胜负游戏需要判断最后由谁胜出三、采用的开发工具和技术，开发环境，适用环境开发工具：visual c+ mfc工程；开发环境：win7；适用环境：windows系统；四、小组成员分工初始化、局面设计部分（贺景）；判断胜负、棋子走法部分（邹京甫）；鼠标响应、绘图部分（吴鑫）；搜索引擎部分等由组员共同完成。五、具体开发方法和过程5.1初始化部分oninitdialog()负责的是对话框的初始化。可以把有关中国象棋的棋局初始化情况也放在了这里面。初始化的内容包括：对引擎部分所用到的变量的初始化。包括对棋盘上的棋子位置进行初始化（棋盘数组的初始化），对搜索深度、当前走棋方标志、棋局是否结束标志等的初始化；对棋盘、棋子的贴图位置（即棋盘、棋子在程序中实际显示位置）的初始化；对程序辅助部分所用到的一些变量的初始化。棋盘、棋子样式的默认形式，以及着法名称列表的初始化等。1.对棋盘的初始化memcpy(m_bychessboard,initchessboard,90);2.对棋盘、棋子的贴图位置（即棋盘、棋子在程序中实际显示位置）的初始化；memdc.selectobject(&poldbmp);/恢复内存dc的原位图3.对程序辅助部分所用到的一些变量的初始化棋盘、棋子样式的默认形式，下棋模式的默认选择，以及着法名称列表的初始化等。初始化部分的代码如下：bool cchessdlg:oninitdialog()cdialog:oninitdialog();/ add about. menu item to system menu./ idm_aboutbox must be in the system command range.assert(idm_aboutbox & 0xfff0) = idm_aboutbox);assert(idm_aboutbox appendmenu(mf_separator);psysmenu-appendmenu(mf_string, idm_aboutbox, straboutmenu);seticon(m_hicon, true);/ set big iconseticon(m_hicon, false);/ set small icon/彩色进度条设置m_progressthink.setstartcolor(rgb(0xff,0xff,0x00);/黄色m_progressthink.setendcolor(rgb(0x00,0x93,0x00); /绿色m_progressthink.setbkcolor(rgb(0xe6,0xe6,0xfa); /淡紫色m_progressthink.settextcolor(rgb(0,0,255);m_progressthink.showpercent(1);m_tooltip.create(this);m_tooltip.activate(1);m_chessman.create(idb_chessman,36,14,rgb(0,255,0);/创建含有棋子图形的imglist，用于绘制棋子/下面这段代码取棋盘图形的宽，高bitmap bitmap;m_boardbmp.loadbitmap(idb_chessboard);m_boardbmp.getbitmap(&bitmap); /取bitmap 对象m_nboardwidth=bitmap.bmwidth; /棋盘宽度m_nboardheight=bitmap.bmheight;/棋盘高度m_boardbmp.deleteobject();memcpy(m_bychessboard,initchessboard,90);/初始化棋盘memcpy(m_byshowchessboard,initchessboard,90);memcpy(m_bybackupchessboard,initchessboard,90);m_pse-setsearchdepth(3); /设定搜索层数为3m_pse-setmovegenerator(m_pmg);/给搜索引擎设定走法产生器m_pse-seteveluator(m_pevel); /给搜索引擎设定估值核心m_pse-setuserchesscolor(m_nuserchesscolor); /设定用户为黑方或红方m_pse-setthinkprogress(&m_progressthink); /设定进度条m_movechess.nchessid=nochess;/将移动的棋子清空return true; / return true unless you set the focus to a control5.2局面设计游戏设计中，我们的象棋棋盘采用的是直接加载位图生成棋盘，图片的大小是宽度377*高度417，棋盘上每个格子的大小：39*39，图片格式为：bmp。棋子部分是通过加载位图实现的，图片的大小是：宽度32*高度32，图片的格式也是bmp。我们用一个10*9的数组来存储棋盘上的信息，数组的每个元素存储棋盘上是否有棋子。棋盘的初始情形如下所示（图1是整个棋盘与棋子的局面图）：const byte initchessboard109=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;图1 局面设计图棋子的定义：#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 b_begin b_king#define b_end b_pawn#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 r_begin r_king#define r_end r_pawn#define isblack(x) (x=b_begin & x=r_begin & x=r_end)/判断某个棋子是不是红色。/判断两个棋子是不是同色#define issameside(x,y) (isblack(x) & isblack(y) | (isred(x) & isred(y)/棋子位置typedef structbyte x;byte y;chessmanpos;5.3绘图部分对于绘图部分，主要实现的是程序界面的绘图因此我们在这里将要完成棋盘、棋子的显示走棋起始位置和目标位置的提示框的显示。而要实现这些我们必须通过void cchessdlg:onpaint() 这个函数实现void cchessdlg:onpaint() cpaintdc dc(this);cdc memdc;int i,j;point pt;cbitmap* poldbmp;memdc.createcompatibledc(&dc);m_boardbmp.loadbitmap(idb_chessboard);poldbmp=memdc.selectobject(&m_boardbmp);/绘制棋盘上的棋子for(i=0;i10;i+)for(j=0;j9;j+)if(m_byshowchessboardij=nochess)continue;pt.x=j*grilleheight+14;pt.y=i*grillewidth+15;m_chessman.draw(&memdc,m_byshowchessboardij-1,pt,ild_transparent);/绘制用户正在拖动的棋子if(m_movechess.nchessid!=nochess)m_chessman.draw(&memdc,m_movechess.nchessid-1,m_movechess.ptmovepoint,ild_transparent);dc.bitblt(0,0,m_nboardwidth,m_nboardheight,&memdc,0,0,srccopy); /将绘制的内容刷新到屏幕memdc.selectobject(&poldbmp);/恢复内存dc的原位图memdc.deletedc(); /释放内存 m_boardbmp.deleteobject(); /删除棋盘位图对象5.4鼠标响应部分鼠标响应部分包括lbuttondown和lbuttonup两个功能，lbuttondown实现的主要功能是拖动棋子在棋盘上的移动，他的重要性是，如果没有这个功能，将无法走棋，其函数实现通过：void cchessdlg:onlbuttondown(uint nflags, cpoint point) lbuttonup这个函数主要实现的功能是：拖动棋子完毕后放置到拖动后的位置，在进行放置的过程中，需要使用一个drop的释放函数。函数实现通过：void cchessdlg:onlbuttonup(uint nflags, cpoint point) 5.5棋子走法typedef structshort nchessid; /表明是什么棋子chessmanpos from;/起始位置chessmanpos to; /走到什么位置int score; /走法的分数chessmove;在着法生成器中，采用的基本思想就是遍历整个棋盘（一个接一个地查看棋盘上的每个位置点），当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型而相应地找出其所有合法着法并存入着法队列。这里谈到的“合法着法”包括以下几点：1、各棋子按其行子规则行子。诸如马跳“日”字、象走“田”字、士在九宫内斜行等等（这里需要特别注意的是卒（兵）的行子规则会随其所在位置的不同而发生变化过河后可以左右平移）。2、行子不能越出棋盘的界限。当然所有棋子都不能走到棋盘的外面，同时某些特定的棋子还有自己的行棋界限，如将、士不能出九宫，象不能过河。3、行子的半路上不能有其它子阻拦（除了炮需要隔一个子才能打子之外）以及行子的目的点不能有本方的棋子。4、将帅不能碰面（本程序中只在生成计算机的着法时认为将帅碰面是非法的，而对用户所走的导致将帅碰面的着法并不认为其非法，而只是产生败局罢了）。产生了着法后要将其存入着法队列以供搜索之用，由于搜索会搜索多层，所以在把着法存入着法队列的时候还要同时存储该着法所属的搜索层数。因此可以将着法队列定义为二维数组，其中第一个数组下标为层数，第二个数组下标为每一层的全部着法数。着法生成中的各个棋子走法以及其他规则代码见movegenerator.cpp。棋子的移动由以下的函数分别执行：帅（将）：void cmovegenerator:gen_kingmove()士：红士void cmovegenerator:gen_rbishopmove()黑士void cmovegenerator:gen_bbishopmove()象：void cmovegenerator:gen_elephantmove()马：void cmovegenerator:gen_horsemove()车：void cmovegenerator:gen_carmove()炮：void cmovegenerator:gen_canonmove()兵（卒）：红兵void cmovegenerator:gen_rpawnmove() 黑卒 void cmovegenerator:gen_bpawnmove()5.6搜索算法我们用一棵象棋树来表示下棋的过程：树中每一个结点代表棋盘上的一个局面，对每一个局面根据不同的走法又产生不同的局面。该象棋树包含三种类型的结点：奇数层的中间结点以及根结点，表示轮到红方走棋；偶数层的中间结点，表示轮到黑方走棋；叶子结点，表示棋局结束。结合上面所讲的树，若给每个结点都打一个分值来评价其对应的局面，我们通过估值引擎seteveluator()来实现，过比较该分值的大小来判断局面的优劣。void seteveluator(ceveluation* peval)m_peval=peval;假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。如此，当轮到甲走棋时他会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到博弈树上，即如果假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。那么由于甲方希望棋盘上的分值尽可能大，则在偶数层上会挑选分值最大的结点偶数层的结点是甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。同样道理，由于乙方希望棋盘上的分值尽可能小，那么在奇数层上会选择分值最小的结点。这是“最小-最大”（minimax）的基本思想。这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的着法。下面是“最大-最小”的主要代码int cnegamaxengine:negamax(int ndepth)int current=-20000;int score;int count,i;byte type;i=isgameover(curposition,ndepth);/检查棋局是否结束if(i!=0)return i;/棋局结束，返回极大/极小值if(ndeptheveluate(curposition,(m_nmaxdepth-ndepth)%2,m_nuserchesscolor);/列举当前棋局下一步所有可能的走法count=m_pmg-createpossiblemove(curposition,ndepth,(m_nmaxdepth-ndepth)%2,m_nuserchesscolor);if(ndepth=m_nmaxdepth)/在根节点设定进度条m_pthinkprogress-setrange(0,count);m_pthinkprogress-setstep(1);for(i=0;istepit();/走进度条type=makemove(&m_pmg-m_movelistndepthi); /根据走法产生新局面 score=-negamax(ndepth-1); /递归调用负极大值搜索下一层节点unmakemove(&m_pmg-m_movelistndepthi,type); /恢复当前局面if(scorecurrent) /如果score大于已知的最大值current=score; /修改当前最大值为scoreif(ndepth=m_nmaxdepth)m_cmbestmove=m_pmg-m_movelistndepthi;/靠近根部时保存最佳走法return current;/返回极大值“最小-最大”思想再加上“树的裁剪”就是alpha-beta搜索算法的核心。最基本的alpha-beta算法的代码如下：int calphabetaengine:alphabeta(int ndepth,int alpha,int beta)int score;int count,i;byte type;i=isgameover(curposition,ndepth);/检查是否游戏结束if(i!=0)return i;/结束，返回估值/叶子节点取估值if(ndeptheveluate(curposition,(m_nmaxdepth-ndepth)%2,m_nuserchesscolor);/此函数找出当前局面所有可能的走法，然后放进m_pmg -m_movelist当中count=m_pmg-createpossiblemove(curposition,ndepth,(m_nmaxdepth-ndepth)%2,m_nuserchesscolor);if(ndepth=m_nmaxdepth)/在根节点设定进度条m_pthinkprogress-setrange(0,count);m_pthinkprogress-setstep(1);/对所有可能的走法for(i=0;istepit();/走进度条type=makemove(&m_pmg-m_movelistndepthi); /将当前局面应用此走法，变为子节点的局面score=-alphabeta(ndepth-1,-beta,-alpha); /递归搜索子节点unmakemove(&m_pmg-m_movelistndepthi,type);/将此节点的局面恢复为当前节点if(scorealpha)alpha=score;/保留极大值/靠近根节点时保留最佳走法if(ndepth=m_nmaxdepth)m_cmbestmove=m_pmg-m_movelistndepthi;if(alpha=beta)break;/剪枝，放弃搜索剩下的节点return alpha;/返回极大值alpha-beta搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率，它的效率将在很大程度上取决于树的结构如果搜索了没多久就发现可以进行“裁剪”了，那么需要分析的工作量将大大减少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此时“裁剪”也已经失去了它原有的价值（因为你已经分析了所有情况，这时的alpha-beta搜索已和“最小-最大”搜索别无二致了）。因而，要想保证alpha-beta搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。由j.schaeffer所提出的“历史启发”（history heuristic）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样alpha-beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。对于着法的排序可以使用各种排序算法，在程序中采用了归并排序。归并排序的空间复杂度为o(n)，时间复杂度为o(nlog2n)，具有较高的效率。历史启发部分的主要代码如下：void chistoryheuristic:resethistorytable()memset(m_historytable,10,8100*4);int chistoryheuristic:gethistoryscore(chessmove *move)int nfrom,nto;nfrom=move-from.y*9+move-from.x;/原始位置nto=move-to.y*9+move-to.x; /目标位置return m_historytablenfromnto;/返回历史得分5.7多线程由于程序出现了异常：有时对用户方的功能完全正确，而对电脑方的有些功能却不起作用，这是由于程序在进行搜索时会占用大量的cpu时间，因而阻塞了位于同一线程内的其他指令，使之无法正常工作，因而我们引入了多线程的思想另外开一个线程，让各程序分开于多个线程。函数原型：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来启动新线程即可，实现了程序的多线程，不能正常工作的问题也就随之解决了。5.8判断胜负红方的帅被吃，或者黑方的将被吃，游戏结束，判断被吃的一方输。具体代码如下：int cchessdlg:isgameover(byte position9)int i,j;bool redlive=false,blacklive=false;/检查红方九宫是否有帅for(i=7;i10;i+)for(j=3;j6;j+)if(positionij=b_king)blacklive=true;if(positionij=r_king)redlive=true;/检查黑方九宫是否有将for(i=0;i3;i+)for(j=3;j6;j+)if(positionij=b_king)blacklive=true;if(positionij=r_king)redlive=true;if(m_nuserchesscolor=redchess)if(!redlive)return 1;if(!