單機(jī)象棋游戲的設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康闹袊?guó)象棋是一項(xiàng)智力游戲，以往都是人和人下棋，現(xiàn)在有了計(jì)算機(jī)我們可以和計(jì)算機(jī)競(jìng)技，人可以與計(jì)算機(jī)進(jìn)行對(duì)弈?？刂朴?jì)算機(jī)的是人類(lèi)，而人工智能是綜合性很強(qiáng)的一門(mén)邊緣學(xué)科，它的中心任務(wù)是研究如何使計(jì)算機(jī)去做那些過(guò)去只能靠人的智力才能做的工作。因此，對(duì)游戲開(kāi)發(fā)過(guò)程中的人工智能技術(shù)的研究自然也就成了業(yè)界的一個(gè)熱門(mén)研究方向。實(shí)驗(yàn)步驟1、中國(guó)象棋游戲設(shè)計(jì)研究方法本系統(tǒng)主要用VisualC++進(jìn)行開(kāi)發(fā)，里面的MFC類(lèi)庫(kù)，使游戲開(kāi)發(fā)更加方便，并利用人工智能相關(guān)搜索算法實(shí)現(xiàn)人工智能的著法生成，從而完善整個(gè)游戲的功能。該象棋人機(jī)博弈系統(tǒng)實(shí)現(xiàn)的功能主要包括：1、選手選擇（人或電腦）；2、人機(jī)對(duì)弈（人與電腦競(jìng)技）；3、電腦棋力難度選擇（電腦下棋能力難度選擇，共有4級(jí)：按電腦配置選擇難度）；4、悔棋、還原；5、著法名稱(chēng)顯示（象棋走棋規(guī)范名稱(chēng)）。2、棋盤(pán)和棋子的表示對(duì)于中國(guó)象棋棋盤(pán)局面的表示可采用傳統(tǒng)而簡(jiǎn)單的“棋盤(pán)數(shù)組”。即用一個(gè)9*10的數(shù)組來(lái)存儲(chǔ)棋盤(pán)上的信息，數(shù)組的每個(gè)元素存儲(chǔ)棋盤(pán)上是否有棋子。這種表示方法簡(jiǎn)單易行。按此方法棋盤(pán)的初始情形如下所示：BYTECChessBoard[9][10]={R,0,0,P,0,0,p,0,0,r,H,0,C,0,0,0,0,c,0,h,E,0,0,P,0,0,p,0,0,e,A,0,0,0,0,0,0,0,0,a,K,0,0,P,0,0,p,0,0,k,A,0,0,0,0,0,0,0,0,a,E,0,0,P,0,0,p,0,0,e,H,0,C,0,0,0,0,c,0,h,R,0,0,P,0,0,p,0,0,r};給所有棋子定義一個(gè)值：#defineR_BEGINR_KING#defineR_ENDR_PAWN#defineB_BEGINB_KING#defineB_ENDB_PAWN#defineNOCHESS0//沒(méi)有棋子黑方：#defineB_KING 1//黑帥#defineB_CAR 2//黑車(chē)#defineB_HORSE 3//黑馬#defineB_CANON 4//黑炮#defineB_BISHOP5//黑士#defineB_ELEPHANT6//黑象#defineB_PAWN7//黑卒紅方：#defineR_KING 8//紅將#defineR_CAR9//紅車(chē)#defineR_HORSE10//紅馬#defineR_CANON11//紅炮#defineR_BISHOP12//紅士#defineR_ELEPHANT13//紅相#defineR_PAWN14//紅兵判斷顏色：#defineIsBlack(x)(x>=B_BEGIN&&x<=B_END)//判斷某個(gè)棋子是不是黑色#defineIsRed(x)(x>=R_BEGIN&&x<=R_END)//判斷某個(gè)棋子是不是紅色對(duì)于著法的表示，直接借用棋盤(pán)數(shù)組的下標(biāo)來(lái)記錄著法的起點(diǎn)和目標(biāo)點(diǎn)。至于是什么棋子在走，以及是否吃子、吃的是什么子，在著法結(jié)構(gòu)中并不記錄。這些信息由外部讀取棋盤(pán)上起點(diǎn)、終點(diǎn)的數(shù)據(jù)獲得。著法結(jié)構(gòu)定義如下，其中還包含了對(duì)著法的歷史得分的記錄項(xiàng)，以供后面要講到的“歷史啟發(fā)”所用。typedefstruct{ shortnChessID;//表明是什么棋子 CHESSMANPOSFrom;//起始位置 CHESSMANPOSTo;//走到什么位置 intScore;//走法的分?jǐn)?shù)}CHESSMOVE;三、程序代碼及實(shí)現(xiàn)1、博弈程序的實(shí)現(xiàn)搜索算法的好壞直接影響著程序執(zhí)行的效率（從某種角度上，它影響著計(jì)算機(jī)的下棋水平。因?yàn)椋?jì)算機(jī)必須在有限的時(shí)間內(nèi)完成思考，搜索速度快意味著在相同的時(shí)間內(nèi)程序可以“看”得更遠(yuǎn)，“想”的更多）。關(guān)于棋類(lèi)對(duì)弈程序中的搜索算法，已有成熟的Alpha-Beta搜索算法以及其它一些輔助增強(qiáng)算法（還有眾多基于Alpha-Beta算法的派生、變種算法）。我們?cè)诔绦蛑兄苯咏梃b了Alpha-Beta搜索算法并輔以歷史啟發(fā)。本節(jié)先介紹Alpha-Beta搜索算法：在中國(guó)象棋里，雙方棋手獲得相同的棋盤(pán)信息。他們輪流走棋，目的就是吃掉對(duì)方的將或帥，或者避免自己的將或帥被吃?！硎炯t方走棋表示黑方走棋…………圖1博弈樹(shù)又此，可以用一棵“博弈樹(shù)”（圖1）來(lái)表示下棋的過(guò)程——樹(shù)中每一個(gè)結(jié)點(diǎn)代表棋盤(pán)上的一個(gè)局面，對(duì)每一個(gè)局面（結(jié)點(diǎn)）根據(jù)不同的走法又產(chǎn)生不同的局面（生出新的結(jié)點(diǎn)），如此不斷進(jìn)行下去直到再無(wú)可選擇的走法，即到達(dá)葉子結(jié)點(diǎn)（棋局結(jié)束）。中國(guó)象棋的博弈樹(shù)的模型大概如下圖所示，可以把其中連接結(jié)點(diǎn)的線段看作是著法，不同的著法自然產(chǎn)生不同的局面。。AACDB-8-210-8?2………圖2樹(shù)的裁剪首先，考察結(jié)點(diǎn)A的子結(jié)點(diǎn)B。結(jié)點(diǎn)B所屬的這一層是輪到你的對(duì)手——“最小者”來(lái)走棋了，目的是使得棋局的分值盡可能的小。依次考察結(jié)點(diǎn)B的各個(gè)子結(jié)點(diǎn)，查看它們的分值（因?yàn)槭孪燃s定好了搜索兩層，現(xiàn)在已達(dá)到搜索深度的要求了，所以就停下來(lái)調(diào)用局面評(píng)估函數(shù)來(lái)給它打分）。結(jié)點(diǎn)B的第一個(gè)子結(jié)點(diǎn)（從左到右算起）返回-8，第二個(gè)子結(jié)點(diǎn)返回了-2，第三個(gè)子結(jié)點(diǎn)返回了2。由于結(jié)點(diǎn)B這層是你的對(duì)手來(lái)做選擇，假設(shè)他一定會(huì)做出明智的選擇（你不能寄希望于你的對(duì)手會(huì)走出一步“昏招”），那么他會(huì)選擇返回值為-2的那個(gè)結(jié)點(diǎn)。-2最終也就成了從結(jié)點(diǎn)B傳遞回的值，即倘若你（現(xiàn)在位于結(jié)點(diǎn)A）選擇了產(chǎn)生結(jié)點(diǎn)B的走法，使得局面發(fā)展到了結(jié)點(diǎn)B。那么下一步，你的對(duì)手的選擇就會(huì)使得棋局發(fā)展成為分值為-2的那個(gè)結(jié)點(diǎn)所表示的局面。再來(lái)分析結(jié)點(diǎn)A的第二個(gè)子結(jié)點(diǎn)C，結(jié)點(diǎn)C與結(jié)點(diǎn)B同屬一層，它依然是輪到你的對(duì)手作選擇。依次查看結(jié)點(diǎn)C的各個(gè)子結(jié)點(diǎn)的分值，其第一個(gè)子結(jié)點(diǎn)返回了2……。“最小-最大”的思想再加上“對(duì)樹(shù)的裁剪”，這就是Alpha-Beta搜索算法的核心。最基本的Alpha-Beta算法的代碼如下：intAlphaBeta(intdepth,intalpha,intbeta){ if(depth==0) //如果是葉子節(jié)點(diǎn)（到達(dá)搜索深度要求） returnEvaluate(); //則由局面評(píng)估函數(shù)返回估值 GenerateLegalMoves(); //產(chǎn)生所有合法著法 while(MovesLeft()) //遍歷所有著法 { MakeNextMove(); //執(zhí)行著法 intval=-AlphaBeta(depth-1,-beta,-alpha);//遞歸調(diào)用 UnmakeMove(); //撤銷(xiāo)著法 if(val>=beta) //裁剪 returnbeta; if(val>alpha) //保留最大值 alpha=val; } returnalpha;}：2、棋子的相互關(guān)系對(duì)棋子間相互關(guān)系的打分，要用到以下幾個(gè)數(shù)據(jù)：intm_BaseValue[15]; //存放棋子基本價(jià)值intm_FlexValue[15]; //存放棋子靈活性分值shortm_AttackPos[10][9]; //存放每一位置被威脅的信息BYTEm_GuardPos[10][9];//存放每一位置被保護(hù)的信息BYTEm_FlexibilityPos[10][9];//存放每一位置上棋子的靈活性分值intm_chessValue[10][9]; //存放每一位置上棋子的總價(jià)值其中計(jì)算機(jī)會(huì)進(jìn)行所有棋子值的判斷，AttackPos和GuardPos分別記錄該棋子受到的威脅和被保護(hù)的值。當(dāng)遍歷一遍棋盤(pán)之后，子力打分、控制區(qū)域打分和機(jī)動(dòng)性打分都可以完成，而關(guān)系表也可以填完。之后，再根據(jù)關(guān)系表來(lái)具體考察棋子的相互關(guān)系，進(jìn)行關(guān)系打分。分析關(guān)系時(shí)，首先，對(duì)王的攻擊保護(hù)應(yīng)分離出來(lái)單獨(dú)考慮，因?yàn)閷?duì)王的保護(hù)沒(méi)有任何意義，一旦王被吃掉整個(gè)游戲就結(jié)束了。其次，對(duì)一個(gè)普通子，當(dāng)它既受到攻擊又受到保護(hù)的時(shí)候要注意如下幾個(gè)問(wèn)題：這里需要特別說(shuō)明的是通常象棋程序處于程序效率的考慮并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后當(dāng)悔棋的時(shí)候，需要撤銷(xiāo)著法；還原的時(shí)候，需要執(zhí)行著法。然而，在編寫(xiě)自己的程序時(shí)一來(lái)考慮到程序的可讀性和不易出錯(cuò)性，二來(lái)考慮到對(duì)當(dāng)今的計(jì)算機(jī)的配置來(lái)說(shuō)這點(diǎn)開(kāi)銷(xiāo)基本上不會(huì)對(duì)程序的效率產(chǎn)生什么影響。因此保存了全部棋子的信息。根據(jù)所要保存的數(shù)據(jù)定義了如下基本結(jié)構(gòu)類(lèi)型：typedefstruct{ CHESSMOVEcmChessMove; shortnChessID;//被吃掉的棋子}UNDOMOVE;在對(duì)弈過(guò)程中，每一回合都將棋局信息（這里指前面所說(shuō)的需要保存的信息）保存至走法隊(duì)列，以供悔棋所用。還原功能是與悔棋功能相對(duì)應(yīng)的，只有當(dāng)產(chǎn)生了悔棋功能之后，還原功能才會(huì)被激活。一個(gè)回合的結(jié)束意味著前一次操作沒(méi)有悔棋功能的產(chǎn)生，因此還原隊(duì)列也應(yīng)被清空。3、著法名稱(chēng)顯示功能的實(shí)現(xiàn)每當(dāng)下棋者（用戶或是計(jì)算機(jī)）走一步棋，在棋盤(pán)旁邊的一個(gè)列表框控件（ListBox）中按照中國(guó)象棋關(guān)于著法描述的規(guī)范要求顯示出該著法的名稱(chēng)。如：炮八進(jìn)四、馬二進(jìn)三此類(lèi)。為了獲得該著法名稱(chēng)，我們編寫(xiě)了一個(gè)函數(shù)，其功能就是將被移動(dòng)的棋子類(lèi)型以及走法的起點(diǎn)坐標(biāo)、終點(diǎn)坐標(biāo)這些信息轉(zhuǎn)換成中國(guó)象棋所規(guī)范的著法名稱(chēng)。實(shí)現(xiàn)此功能代碼如下：voidCGradientProgressCtrl::OnPaint(){ CPaintDCdc(this);//devicecontextforpainting //TODO:Addyourmessagehandlercodehere if(m_nCurrentPosition<=m_nLower||m_nCurrentPosition>=m_nUpper) { CRectrect; GetClientRect(rect); CBrushbrush; brush.CreateSolidBrush(::GetSysColor(COLOR_3DFACE)); dc.FillRect(&rect,&brush); VERIFY(brush.DeleteObject()); return; } CRectrectClient; GetClientRect(rectClient); floatmaxWidth((float)m_nCurrentPosition/(float)m_nUpper*(float)rectClient.right); //繪制 DrawGradient(&dc,rectClient,(int)maxWidth); //顯示進(jìn)程條進(jìn)度文字 if(m_bShowPercent) { CStringpercent; percent.Format("%d%%",(int)(100*(float)m_nCurrentPosition/m_nUpper)); dc.SetTextColor(m_clrText); dc.SetBkMode(TRANSPARENT); dc.DrawText(percent,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE); } //顯示其他文字 if(m_bIsShowText) { dc.SetTextColor(m_clrText); dc.SetBkMode(TRANSPARENT);dc.DrawText(m_strShow,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE); } //DonotcallCProgressCtrl::OnPaint()forpaintingmessages}intCGradientProgressCtrl::SetPos(intnPos){ //SetthePositionoftheProgress m_nCurrentPosition=nPos; return(CProgressCtrl::SetPos(nPos));}intCGradientProgressCtrl::StepIt(){ m_nCurrentPosition+=m_nStep; returnCProgressCtrl::StepIt();}以下介紹如何對(duì)列表框控件（ListBox）進(jìn)行操作，以顯示或刪除著法名稱(chēng)。首先，在ChessDlg下定義以下函數(shù)：this->GetMoveStr(nFromX,nFromY,nToX,nToY,nSourceID);//用來(lái)獲得剛下的一步棋的走法；voidCChessDlg::AddChessRecord(intnFromX,intnFromY,intnToX,intnToY,intnUserChessColor,intnSourceID)//將走法添加進(jìn)下棋記錄；然后，顯示在Listbox中。當(dāng)列表框中的項(xiàng)的數(shù)目超過(guò)列表框的顯示范圍時(shí)，列表框會(huì)自動(dòng)添加垂直滾動(dòng)條（前提是其VerticalScrollbar屬性要為T(mén)rue——該屬性默認(rèn)即為T(mén)rue）。但是顯示的內(nèi)容依然是最早加進(jìn)來(lái)的項(xiàng)。在控件屬性里選擇VerticalScroll，使得列表框可垂直滾動(dòng)以顯示最新的著法名稱(chēng)。想要從列表框中刪除項(xiàng)時(shí)，可以使用m_lstChessRecord.DeleteString(m_lstChessRecord.GetCount()-1);減一之后正好是最后一項(xiàng)的行號(hào)。4、勝敗判定勝負(fù)判定只要一方將另一方的將或帥吃掉就是勝者。主要代碼如下：intCSearchEngine::IsGameOver(BYTEposition[][9],intnDepth){ inti,j; BOOLRedLive=FALSE,BlackLive=FALSE; //檢查紅方九宮是否有帥 for(i=7;i<10;i++) for(j=3;j<6;j++) { if(position[i][j]==B_KING) BlackLive=TRUE; if(position[i][j]==R_KING) RedLive=TRUE; } //檢查黑方九宮是否有將 for(i=0;i<3;i++) for(j=3;j<6;j++) { if(position[i][j]==B_KING) BlackLive=TRUE; if(position[i][j]==R_KING) RedLive=TRUE; }i=(m_nMaxDepth-nDepth+1)%2;//取當(dāng)前奇偶標(biāo)志，奇數(shù)層為電腦方，偶數(shù)層為用戶方。 //紅方不在 if(!RedLive) if(i) return19990+nDepth;//奇數(shù)層返回極大值 else return-19990-nDepth;//偶數(shù)層返回極小值 //黑方不在 if(!BlackLive) if(i) return-19990-nDepth;//奇數(shù)層返回極小值 else return19990+nDepth;//偶數(shù)層返回極大值 return0;//將帥都在，返回0}四、界面設(shè)計(jì)和系統(tǒng)實(shí)現(xiàn)1、界面設(shè)計(jì)關(guān)于棋盤(pán)和棋子，建了一個(gè)基于對(duì)話框的MFC應(yīng)用程序。主要工作都在對(duì)話框類(lèi)的兩個(gè)文件CChessDlg.h和CChessDlg.cpp下展開(kāi)。代碼主要分布于以下三大部分：1、初始化部分 BOOLCCChessUIDlg::OnInitDialog(){}OnInitDialog()負(fù)責(zé)的是對(duì)話框的初始化?？梢园延嘘P(guān)中國(guó)象棋的棋局初始化情況也放在了這里面。初始化的內(nèi)容包括：對(duì)引擎部分所用到的變量的初始化。包括對(duì)棋盤(pán)上的棋子位置進(jìn)行初始化（棋盤(pán)數(shù)組的初始化），對(duì)搜索深度、當(dāng)前走棋方標(biāo)志、棋局是否結(jié)束標(biāo)志等的初始化；對(duì)棋盤(pán)、棋子的貼圖位置（即棋盤(pán)、棋子在程序中實(shí)際顯示位置）的初始化；對(duì)程序輔助部分所用到的一些變量的初始化。包括對(duì)悔棋、還原隊(duì)列的清空，棋盤(pán)、棋子樣式的默認(rèn)形式，下棋模式的默認(rèn)選擇，以及著法名稱(chēng)列表的初始化等。2、繪圖部分voidCCChessUIDlg::OnPaint(){……}OnPaint()函數(shù)負(fù)責(zé)的是程序界面的繪圖。因此，在這里將要完成棋盤(pán)、棋子的顯示走棋起始位置和目標(biāo)位置的提示框的顯示。由于棋盤(pán)、棋子等都是以位圖的形式給出的。所以在OnPaint()函數(shù)里做的工作主要都是在貼位圖。需要注意的是由于位圖文件不能像GIF文件那樣有透明的背景并且棋子是圓形的而位圖文件只能是矩形的，所以如果直接貼圖的話會(huì)在棋盤(pán)上留下一塊白色的邊框——棋子的背景。因此，要想讓棋子文件的背景“隱藏”需要通過(guò)一些“與”和“異或”操作來(lái)屏蔽掉棋子的背景。3、走棋部分（用戶動(dòng)作響應(yīng)部分）為WM_LBUTTONDOWN消息添加消息響應(yīng)事件，可得到如下函數(shù)： voidCCChessUIDlg::OnLButtonDown(UINTnFlags,CPointpoint){……}當(dāng)用戶在窗口客戶區(qū)按下鼠標(biāo)左鍵時(shí)，程序就會(huì)調(diào)用OnLButtonDown(UINTnFlags,CPointpoint)函數(shù)來(lái)進(jìn)行響應(yīng)。其中第二個(gè)參數(shù)CPointpoint是在本程序中所要用到的，它給出了當(dāng)鼠標(biāo)左鍵被按下時(shí)，鼠標(biāo)指針的位置坐標(biāo)?？梢酝ㄟ^(guò)這一信息來(lái)得知用戶的走法。2、系統(tǒng)實(shí)現(xiàn)現(xiàn)在已具備了實(shí)現(xiàn)一款中國(guó)象棋對(duì)弈程序引擎部分的所有要素，將上述模塊分別寫(xiě)作.h頭文件。如下：ChessDlg.h——象棋相關(guān)定義。包括棋盤(pán)局面和著法的表示。BaseClasses.h——著法生成器。就當(dāng)前局面生成某一方所有合法著法。MoveList.h——搜索部分。使用搜索求出最佳著法。Thinkdef.h——?dú)v史啟發(fā)。Alpha-Beta搜索之補(bǔ)充，以提高搜索效率。Thinker.h——著法排序。對(duì)著法按其歷史得分進(jìn)行降序排序，以提高搜索效率。ThinkOptionDlg.h——局面評(píng)估。為某一特定局面進(jìn)行評(píng)分。當(dāng)實(shí)現(xiàn)了引擎部分的各要素時(shí)，可先建立一個(gè)Win32控制臺(tái)項(xiàng)目，之后只要再添加一個(gè).cpp文件負(fù)責(zé)接受用戶的輸入、調(diào)用搜索函數(shù)、顯示搜索結(jié)果，便可簡(jiǎn)單的測(cè)試引擎了（采用輸入著法的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)的方式來(lái)傳送用戶走棋的信息。同樣，程序顯示計(jì)算機(jī)走棋的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)來(lái)做出回應(yīng)）。此后，等到界面部分初步完成，引擎的上述各模塊無(wú)需作任何改動(dòng)，仍以.h頭文件的形式加入界面工程，只要由界面中的某個(gè).cpp文件調(diào)用搜索函數(shù)即可。這種連接方式實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單。首先，執(zhí)行該軟件，系統(tǒng)并不需要很高的配置，CPU在1.5G以上，內(nèi)存在512M以上就可以很流暢地執(zhí)行。下面簡(jiǎn)單介紹一下象棋相關(guān)規(guī)則：對(duì)局時(shí)，由執(zhí)紅棋的一方先走，雙方輪流各走一著，直至分出勝、負(fù)、和，對(duì)局即終了。輪到走棋的一方，將某個(gè)棋子從一個(gè)交叉點(diǎn)走到另一個(gè)交叉點(diǎn)，或者吃掉對(duì)方的棋子而占領(lǐng)其交叉點(diǎn)，都算走一著。雙方各走一著，稱(chēng)為一個(gè)回合。如果有一方的主帥被對(duì)方吃了，就算那一方輸。各種棋子的走法：