还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
单机象棋游戏的设计与实现
1、实验目的中国象棋是一项智力游戏,以往都是人和人下棋,现在有了计算机我们可以和计算机竞技,人可以与计算机进行对弈控制计算机的是人类,而人工智能是综合性很强的一门边缘学科,它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作因此,对游戏__过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向
2、实验步骤
1、中国象棋游戏设计研究方法本系统主要用VisualC++进行__,里面的MFC类库,使游戏__更加方便,并利用人工智能相关搜索算法实现人工智能的着法生成,从而完善整个游戏的功能该象棋人机博弈系统实现的功能主要包括
1、选手选择(人或电脑);
2、人机对弈(人与电脑竞技);
3、电脑棋力难度选择(电脑下棋能力难度选择,共有4级按电脑配置选择难度);
4、悔棋、还原;
5、着法名称显示(象棋走棋规范名称)
2、棋盘和棋子的表示对于中国象棋棋盘局面的表示可采用传统而简单的“棋盘数组”即用一个9*10的数组来存储棋盘上的信息,数组的每个元素存储棋盘上是否有棋子这种表示方法简单易行按此方法棋盘的初始情形如下所示BYTECChes__oard
[9]
[10]={R00P00p00rH0C0000c0hE00P00p00eA00000000aK00P00p00kA00000000aE00P00p00eH0C0000c0hR00P00p00r};给所有棋子定义一个值#defineR_BEGINR_KING#defineR_ENDR_PAWN#defineB_BEGINB_KING#defineB_ENDB_PAWN#defineNOCHESS0//没有棋子黑方#defineB_KING1//黑帅#defineB_CAR2//__#defineB_HORSE3//__#defineB_CANON4//黑炮#defineB_BISHOP5//黑士#defineB_ELEPHANT6//黑象#defineB_PAWN7//黑卒红方#defineR_KING8//红将#defineR_CAR9//红车#defineR_HORSE10//红马#defineR_CANON11//红炮#defineR_BISHOP12//红士#defineR_ELEPHANT13//红相#defineR_PAWN14//红兵判断颜色#defineI__lackxx=B_BEGINx=B_END//判断某个棋子是不是黑色#defineIsRedxx=R_BEGINx=R_END//判断某个棋子是不是红色对于着法的表示,直接借用棋盘数组的下标来记录着法的起点和目标点至于是什么棋子在走,以及是否吃子、吃的是什么子,在着法结构中并不记录这些信息由外部读取棋盘上起点、终点的数据获得着法结构定义如下,其中还包含了对着法的历史得分的记录项,以供后面要讲到的“历史启发”所用typedefstruct{shortnChessID;//表明是什么棋子CHES__ANPOSFrom;//起始位置CHES__ANPOSTo;//走到什么位置intScore;//走法的分数}CHES__OVE;
三、程序代码及实现
1、博弈程序的实现搜索算法的好坏直接影响着程序执行的效率(从某种角度上,它影响着计算机的下棋水平因为,计算机必须在有限的时间内完成思考,搜索速度快意味着在相同的时间内程序可以“看”得更远,“想”的更多)关于棋类对弈程序中的搜索算法,已有成熟的Alpha-Beta搜索算法以及其它一些辅助增强算法(还有众多基于Alpha-Beta算法的派生、变种算法)我们在程序中直接借鉴了Alpha-Beta搜索算法并辅以历史启发本节先介绍Alpha-Beta搜索算法在中国象棋里,双方棋手获得相同的棋盘信息他们轮流走棋,目的就是吃掉对方的将或帅,或者避免自己的将或帅被吃图1博弈树又此,可以用一棵“博弈树”(图1)来表示下棋的过程——树中每一个结点代表棋盘上的一个局面,对每一个局面(结点)根据不同的走法又产生不同的局面(生出新的结点),如此不断进行下去直到再无可选择的走法,即到达叶子结点(棋局结束)中国象棋的博弈树的模型大概如下图所示,可以把其中连接结点的线段看作是着法,不同的着法自然产生不同的局面图2树的裁剪首先,考察结点A的子结点B结点B所属的这一层是轮到你的对手——“最小者”来走棋了,目的是使得棋局的分值尽可能的小依次考察结点B的各个子结点,查看它们的分值(因为事先约定好了搜索两层,现在已达到搜索深度的要求了,所以就停下来调用局面评估函数来给它打分)结点B的第一个子结点(从左到右算起)返回-8,第二个子结点返回了-2,第三个子结点返回了2由于结点B这层是你的对手来做选择,假设他一定会做出明智的选择(你不能寄希望于你的对手会走出一步“昏招”),那么他会选择返回值为-2的那个结点-2最终也就成了从结点B传递回的值,即倘若你(现在位于结点A)选择了产生结点B的走法,使得局面发展到了结点B那么下一步,你的对手的选择就会使得棋局发展成为分值为-2的那个结点所表示的局面再来分析结点A的第二个子结点C,结点C与结点B同属一层,它依然是轮到你的对手作选择依次查看结点C的各个子结点的分值,其第一个子结点返回了2……“最小-最大”的思想再加上“对树的裁剪”,这就是Alpha-Beta搜索算法的核心最基本的Alpha-Beta算法的代码如下intAlphaBetaintdepthintalphaintbeta{ifdepth==0//如果是叶子节点(到达搜索深度要求)returnEvaluate;//则由局面评估函数返回估值GenerateLegalMoves;//产生所有合法着法whileMovesLeft//遍历所有着法{__keNextMove;//执行着法intval=-AlphaBetadepth-1-beta-alpha;//递归调用Un__keMove;//撤销着法ifval=beta//裁剪returnbeta;ifvalalpha//保留最大值alpha=val;}returnalpha;}
2、棋子的相互关系对棋子间相互关系的打分,要用到以下几个数据intm_BaseValue
[15];//存放棋子基本价值intm_FlexValue
[15];//存放棋子灵活性分值shortm_AttackPos
[10]
[9];//存放每一位置被威胁的信息BYTEm_GuardPos
[10]
[9];//存放每一位置被保护的信息BYTEm_FlexibilityPos
[10]
[9];//存放每一位置上棋子的灵活性分值intm_chessValue
[10]
[9];//存放每一位置上棋子的总价值其中计算机会进行所有棋子值的判断,AttackPos和GuardPos分别记录该棋子受到的威胁和被保护的值当遍历一遍棋盘之后,子力打分、控制区域打分和机动性打分都可以完成,而关系表也可以填完之后,再根据关系表来具体考察棋子的相互关系,进行关系打分分析关系时,首先,对王的攻击保护应分离出来单独考虑,因为对王的保护没有任何意义,一旦王被吃掉整个游戏就结束了其次,对一个普通子,当它既受到攻击又受到保护的时候要注意如下几个问题这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保存所有棋子的信息,而只是保存之前一步的走棋信息此后当悔棋的时候,需要撤销着法;还原的时候,需要执行着法然而,在编写自己的程序时一来考虑到程序的可读性和不易出错性,二来考虑到对当今的计算机的配置来说这点开销基本上不会对程序的效率产生什么影响因此保存了全部棋子的信息根据所要保存的数据定义了如下基本结构类型typedefstruct{CHES__OVEcmChes__ove;shortnChessID;//被吃掉的棋子}UNDOMOVE;在对弈过程中,每一回合都将棋局信息(这里指前面所说的需要保存的信息)保存至走法队列,以供悔棋所用还原功能是与悔棋功能相对应的,只有当产生了悔棋功能之后,还原功能才会被激活一个回合的结束意味着前一次操作没有悔棋功能的产生,因此还原队列也应被清空
3、着法名称显示功能的实现每当下棋者(用户或是计算机)走一步棋,在棋盘旁边的一个列表框控件(ListBox)中按照中国象棋关于着法描述的规范要求显示出该着法的名称如炮八进
四、马二进三此类为了获得该着法名称,我们编写了一个函数,其功能就是将被__的棋子类型以及走法的起点坐标、终点坐标这些信息转换成中国象棋所规范的着法名称实现此功能代码如下voidCGra___ntProgressCtrl::OnPaint{CPaintDCdcthis;//devi__contextforpainting//TODO:Addyourmessagehandlercodehereifm_nCurrentPosition=m_nLower||m_nCurrentPosition=m_nUpper{CRectrect;GetClientRectrect;CBrushbrush;brush.CreateSolidBrush::GetSysColorCOLOR_3DFA__;dc.FillRectrectbrush;VERIFYbrush.DeleteO__ect;return;}CRectrectClient;GetClientRectrectClient;float__xWidthfloatm_nCurrentPosition/floatm_nUpper*floatrectClient.right;//绘制DrawGra___ntdcrectClientint__xWidth;//显示进程条进度文字ifm_bShowPer__nt{CStringper__nt;per__nt.For__t%d%%int100*floatm_nCurrentPosition/m_nUpper;dc.SetTextColorm_clrText;dc.SetBkModeTRANSPARENT;dc.DrawTextper__ntrectClientDT_V__NTER|DT___NTER|DT_SINGLELINE;}//显示其他文字ifm_bIsShowText{dc.SetTextColorm_clrText;dc.SetBkModeTRANSPARENT;dc.DrawTextm_strShowrectClientDT_V__NTER|DT___NTER|DT_SINGLELINE;}//DonotcallCProgressCtrl::OnPaintforpaintingmessages}intCGra___ntProgressCtrl::SetPosintnPos{//SetthePositionoftheProgressm_nCurrentPosition=nPos;returnCProgressCtrl::SetPosnPos;}intCGra___ntProgressCtrl::StepIt{m_nCurrentPosition+=m_nStep;returnCProgressCtrl::StepIt;}以下介绍如何对列表框控件(ListBox)进行操作,以显示或删除着法名称首先,在ChessDlg下定义以下函数this-GetMoveStrnFromXnFromYnToXnToYnSour__ID;//用来获得刚下的一步棋的走法;voidCChessDlg::AddChessRecordintnFromXintnFromYintnToXintnToYintnUserChessColorintnSour__ID//将走法添加进下棋记录;然后,显示在Listbox中当列表框中的项的数目超过列表框的显示范围时,列表框会自动添加垂直滚动条(前提是其VerticalScrollbar属性要为True——该属性默认即为True)但是显示的内容依然是最早加进来的项在控件属性里选择VerticalScroll,使得列表框可垂直滚动以显示最新的着法名称想要从列表框中删除项时,可以使用m_lstChessRecord.DeleteStringm_lstChessRecord.GetCount-1;减一之后正好是最后一项的行号
4、胜败判定胜负判定只要一方将另一方的将或帅吃掉就是胜者主要代码如下intCSearchEngine::IsGameOverBYTEposition[]
[9]intnDepth{intij;BOOLRedLive=FALSEBlackLive=FALSE;//检查红方九宫是否有帅fori=7;i10;i++forj=3;j6;j++{ifposition[i][j]==B_KINGBlackLive=TRUE;ifposition[i][j]==R_KINGRedLive=TRUE;}//检查黑方九宫是否有将fori=0;i3;i++forj=3;j6;j++{ifposition[i][j]==B_KINGBlackLive=TRUE;ifposition[i][j]==R_KINGRedLive=TRUE;}i=m_n__xDepth-nDepth+1%2;//取当前奇偶标志,奇数层为电脑方,偶数层为用户方//红方不在if!RedLiveifireturn19990+nDepth;//奇数层返回极大值elsereturn-19990-nDepth;//偶数层返回极小值//黑方不在if!BlackLiveifireturn-19990-nDepth;//奇数层返回极小值elsereturn19990+nDepth;//偶数层返回极大值return0;//将帅都在,返回0}
四、界面设计和系统实现
1、界面设计代码主要分布于以下三大部分
1、初始化部分BOOLCCChessUIDlg::OnInitDialog{}OnInitDialog负责的是对话框的初始化可以把有关中国象棋的棋局初始化情况也放在了这里面初始化的内容包括对引擎部分所用到的变量的初始化包括对棋盘上的棋子位置进行初始化(棋盘数组的初始化),对搜索深度、当前走棋方标志、棋局是否结束标志等的初始化;对棋盘、棋子的贴图位置(即棋盘、棋子在程序中实际显示位置)的初始化;对程序辅助部分所用到的一些变量的初始化包括对悔棋、还原队列的清空,棋盘、棋子样式的默认形式,下棋模式的默认选择,以及着法名称列表的初始化等
2、绘图部分voidCCChessUIDlg::OnPaint{……}OnPaint函数负责的是程序界面的绘图因此,在这里将要完成棋盘、棋子的显示走棋起始位置和目标位置的提示框的显示由于棋盘、棋子等都是以位图的形式给出的所以在OnPaint函数里做的工作主要都是在贴位图需要注意的是由于位图文件不能像GIF文件那样有透明的背景并且棋子是圆形的而位图文件只能是矩形的,所以如果直接贴图的话会在棋盘上留下一块白色的边框——棋子的背景因此,要想让棋子文件的背景“隐藏”需要通过一些“与”和“异或”操作来屏蔽掉棋子的背景
3、走棋部分(用户动作响应部分)为WM_LBUTTONDOWN消息添加消息响应__,可得到如下函数voidCCChessUIDlg::OnLButtonDownUINTnFlagsCPointpoint{……}当用户在窗口客户区按下鼠标左键时,程序就会调用OnLButtonDownUINTnFlagsCPointpoint函数来进行响应其中第二个参数CPointpoint是在本程序中所要用到的,它给出了当鼠标左键被按下时,鼠标指针的位置坐标可以通过这一信息来得知用户的走法
2、系统实现现在已具备了实现一款中国象棋对弈程序引擎部分的所有要素,将上述模块分别写作.h头文件如下ChessDlg.h——象棋相关定义包括棋盘局面和着法的表示BaseClasses.h——着法生成器就当前局面生成某一方所有合法着法MoveList.h——搜索部分使用搜索求出最佳着法Thinkdef.h——历史启发Alpha-Beta搜索之补充,以提高搜索效率Thinker.h——着法排序对着法按其历史得分进行降序排序,以提高搜索效率ThinkOptionDlg.h——局面评估为某一特定局面进行评分当实现了引擎部分的各要素时,可先建立一个Win32控制台项目,之后只要再添加一个.cpp文件负责接受用户的输入、调用搜索函数、显示搜索结果,便可简单的测试引擎了(采用输入着法的起点坐标和终点坐标的方式来传送用户走棋的信息同样,程序显示计算机走棋的起点坐标和终点坐标来做出回应)此后,等到界面部分初步完成,引擎的上述各模块无需作任何改动,仍以.h头文件的形式加入界面工程,只要由界面中的某个.cpp文件调用搜索函数即可这种连接方式实现起来非常简单首先,执行该软件,系统并不需要很高的配置,CPU在
1.5G以上,内存在512M以上就可以很流畅地执行下面简单介绍一下象棋相关规则对局时,由执红棋的一方先走,双方轮流各走一着,直至分出胜、负、和,对局即终了轮到走棋的一方,将某个棋子从一个交叉点走到另一个交叉点,或者吃掉对方的棋子而占领其交叉点,都算走一着双方各走一着,称为一个回合如果有一方的主帅被对方吃了,就算那一方输各种棋子的走法帅(将)帅和将是棋中的首脑,是双方竭力争夺的目标它只能在“九宫”之内活动,可上可下,可左可右,每次走动只能按竖线或横线走动一格帅与将不能在同一直线上直接对面,否则走方判负仕(士)仕(士)是帅(将)的贴身保镖,它也只能在九宫内走动它的行棋路径只能是九宫内的斜线相(象)相(象)的主要作用是防守,保护自己的帅(将)它的走法是每次循对角线走两格,俗称“象走田”相(象)的活动范围限于“河界”以内的本方阵地,不能过河,且如果它走的“田”字__有一个棋子,就不能走,俗称“塞象眼”车车在象棋中威力最大,无论横线、竖线均可行走,只要无子阻拦,步数不受限制因此,一车可以控制十七个点,故有“一车十子寒”之称炮炮在不吃子的时候,走动与车完全相同马马走动的方法是一直一斜,即先横着或直着走一格,然后再斜着走一个对角线,俗称“马走日”马一次可走的选择点可以达到四周的八个点,故有“八面威风”之说如果在要去的方向有别的棋子挡住,马就无法走过去,俗称“蹩马腿”兵(卒)兵(卒)在未过河前,只能向前一步步走,过河以后,除不能后退外,允许左右__,但也只能一次一步在懂的以上规则之后并可进行游戏,执行该软件后,并可进入游戏界面棋盘界面(图3)所示图3棋盘界面从界面上方的菜单栏中可以进行相关设置参数设置界面(图4)如下图4参数设置界面等你将参数设置完毕之后,既可进入游戏走法记录界面(图5)如下图5走法记录界面其他辅助功能界面(图6)如下图6其他辅助功能界面你可以通过上面四个辅助功能对棋局进行研究,从而提高你的下棋水平例如,您是红方,第一步走的是兵七进一或兵三进一,电脑则会炮2进4或炮8进4(图7)图7程序运行界面
五、总结从最初的茫然,到慢慢的进入状态,再到对思路逐渐的清晰,整个写作过程难以用语言来表达脚踏实地,认真严谨,实事求是的学习态度,不怕困难、坚持不懈、吃苦耐劳的精神是我在这次设计中最大的收益我想这是一次意志的磨练,是对我实际能力的一次提升,也会对我未来的学习和工作有很大的帮助在老师的严谨治学态度、渊博的知识、无私的奉献精神使我深受启迪从尊敬的导师身上,我不仅学到了扎实、宽广的专业知识,也学到了做人的道理在此我要向我的导师致以最衷心的感谢和深深的敬意……表示红方走棋表示黑方走棋…………ACDB-8-210-82………。