【正文】 AlphaBeta searching。ois Dominic (六/OL)：局面評估函數(shù)[EB].~auntyellow/puter/，202235。ois Dominic (三/OL)：著法的產(chǎn)生[EB].~auntyellow/puter/，202235。 參 考 文 獻(xiàn)[1] 游戲編程（人機(jī)博弈）[M]. 重慶：重慶大學(xué)出版社，2022.[2] C++.NET 小游戲開發(fā)時尚編程百例[M] .西安：機(jī)械工業(yè)出版社，2022.[3] C++ 高級編程技術(shù)——開發(fā)實例剖析[M].西安：電子工業(yè)出版社，1999.[4] C++.NET 基礎(chǔ)教程與上機(jī)指導(dǎo)[M].北京：清華大學(xué)出版社，2022.[5] C++ 編程深入引導(dǎo) [M].長春：中國水利水電出版社，2022.[6] Frederic [EB/OL].~auntyellow/puter/，202237。這在一定程度上影響了程序中下棋引擎的工作效率。在此我要向我的導(dǎo)師致以最衷心的感謝和深深的敬意。在此更要感謝我的導(dǎo)師和專業(yè)老師，是你們的細(xì)心指導(dǎo)和關(guān)懷，使我能夠順利的完成畢業(yè)論文?；叵脒@段日子的經(jīng)歷和感受，我感慨萬千，在這次畢業(yè)設(shè)計的過程中，我擁有了無數(shù)難忘的回憶和收獲。例如，您是紅方，第一步走的是兵七進(jìn)一或兵三進(jìn)一，電腦則會炮 2 進(jìn) 4 或炮 8 進(jìn)4（圖 7）： 圖 7 程序運行界面以上是系統(tǒng)實現(xiàn)的所有界面及功能測試。兵（卒）：兵（卒）在未過河前，只能向前一步步走，過河以后，除不能后退外，允許左右移動，但也只能一次一步。炮：炮在不吃子的時候，走動與車完全相同。它的走法是每次循對角線走兩格，俗稱“象走田” 。帥與將不能在同一直線上直接對面，否則走方判負(fù)。雙方各走一著，稱為一個回合。這種連接方式實現(xiàn)起來非常簡單。為某一特定局面進(jìn)行評分。AlphaBeta 搜索之補(bǔ)充，以提高搜索效率。就當(dāng)前局面生成某一方所有合法著法。 系統(tǒng)實現(xiàn)現(xiàn)在已具備了實現(xiàn)一款中國象棋對弈程序引擎部分的所有要素，將上述模塊分別寫 頭文件。緊接著調(diào)用引擎的搜索函數(shù)計算出計算機(jī)對用戶著法的應(yīng)著，然后執(zhí)行該應(yīng)著?？梢酝ㄟ^這一信息來得知用戶的走法。需要注意的是由于位圖文件不能像 GIF 文件那樣有透明的背景并且棋子是圓形的而位圖文件只能是矩形的，所以如果直接貼圖的話會在棋盤上留下一塊白色的邊框——棋子的背景。繪圖部分void CCChessUIDlg::OnPaint() {……}OnPaint()函數(shù)負(fù)責(zé)的是程序界面的繪圖。可以把有關(guān)中國象棋的棋局初始化情況也放在了這里面。 //偶數(shù)層返回極大值return 0。//紅方不在if(!RedLive)if(i)return 19990+nDepth。j++) { if(position[i][j]==B_KING)BlackLive=TRUE。 } //檢查黑方九宮是否有將 for(i=0。i++) for(j=3。主要代碼如下：int CSearchEngine::IsGameOver(BYTE position[][9], int nDepth){ int i,j。在控件屬性里選擇 Vertical Scroll，使得列表框可垂直滾動以顯示最新的著法名稱。首先，在 ChessDlg 下定義以下函數(shù)： thisGetMoveStr(nFromX,nFromY,nToX,nToY,nSourceID)。 return (CProgressCtrl::SetPos(nPos))。 (TRANSPARENT)。 (TRANSPARENT)。dc,rectClient,(int)maxWidth)。 } CRect rectClient。rect,amp。 GetClientRect(rect)。如：炮八進(jìn)四、馬二進(jìn)三此類。而在還原中所做的剛好和悔棋相反：下棋回合數(shù)加一；將當(dāng)前局面信息保存至隊列，以供悔棋所用；從隊列中取出最近一次悔棋前的棋局信息，恢復(fù)到當(dāng)前局面，然后將其從隊列中剔除；從走法隊列中取出最近一次存入的著法名稱（兩項，因為每回合會產(chǎn)生兩步著法） ，將其重新顯示到列表框中。還原功能是與悔棋功能相對應(yīng)的，只有當(dāng)產(chǎn)生了悔棋功能之后，還原功能才會被激活。根據(jù)所要保存的數(shù)據(jù)定義了如下基本結(jié)構(gòu)類型：typedef struct{ CHESSMOVE cmChessMove。在程序中保存了如下信息：棋局表示中所定義的棋盤數(shù)組；各棋子的貼圖位置；這里需要特別說明的是通常象棋程序處于程序效率的考慮并不保存所有棋子的信息，而只是保存之前一步的走棋信息。而且，在程序中并沒有直接地重新考慮雙方兌子之后的控制區(qū)域及機(jī)動性變化情況（之所以說沒有“直接地重新考慮” ，是因為搜索繼續(xù)展開結(jié)點后仍會考慮這些因素，只是目前不知這樣效果是否受影響——考察這兩種方法在效果上的差異需要一定數(shù)量的試驗數(shù)據(jù)的支持） 。多攻擊/單保護(hù)的情況，并且攻擊者最小子力小于被攻擊者子力與保護(hù)者子力之 和，則攻擊方可能以一子換兩子。之后，再根據(jù)關(guān)系表來具體考察棋子的相互關(guān)系，進(jìn)行關(guān)系打分。 //存放每一位置被保護(hù)的信息BYTE m_FlexibilityPos[10][9]。 對棋子間相互關(guān)系的打分，要用到以下幾個數(shù)據(jù)：int m_BaseValue[15]。如：一個馬可能在對方的炮的攻擊之下同時它又攻擊著對方的車。 棋子的機(jī)動性棋子的機(jī)動性指棋子的靈活度（可移動性） 。所以在評估局面時，首先要考慮雙方的子力總和的對比。就不同的棋類可能要考慮的因素略有差異。 局面評估前文已經(jīng)講過了棋局表示、著法生成、搜索算法（包括搜索輔助“歷史啟發(fā)” ） ， 在象棋程序中如果說搜索算法是心臟，那么局面評估就是大腦。在搜索的過程中，每當(dāng)發(fā)現(xiàn)一個好的走法，就給該走法累加一個增量以記錄其“歷史得分” ，一個多次被搜索并認(rèn)為是好的走法的“歷史得分”就會較高。因而，要想保證 AlphaBeta 搜索算法的效率就需要調(diào)整樹的結(jié)構(gòu)，即調(diào)整待搜索的結(jié)點的順序，使得“裁剪”可以盡可能早地發(fā)生。 //撤銷著法if (val = beta) //裁剪return beta。 //則由局面評估函數(shù)返回估值GenerateLegalMoves()。因為那樣的話，下一步你的對手就會帶給你一個分值不高于 2 的局面。AC DB8 2 10 8 ?2 … …… 采用 “裁剪”方法。2 最終也就成了從結(jié)點 B 傳遞回的值，即倘若你（現(xiàn)在位于結(jié)點 A）選擇了產(chǎn)生結(jié)點 B 的走法，使得局面發(fā)展到了結(jié)點 B。結(jié)點 B 所屬的這一層是輪到你的對手——“最小者”來走棋了，目的是使得棋局的分值盡可能的小。假定棋盤上的局面發(fā)展到了結(jié)點 A（圖 2），現(xiàn)在輪到你走棋了，你是 “最大的一方”——即你希望棋局的分值盡可能的高。所以當(dāng)你看到某個局面有可能產(chǎn)生很糟糕的局面時（確切地說這里的“很糟糕”是與之前分析的情況相比較而言的），你應(yīng)當(dāng)立刻停止對其剩余子結(jié)點的分析——不要對它再抱任何幻 想了，如果你選擇了它，那么你必將得到那個很糟糕的局面，甚至可能更糟。其中 b 是分枝因子，即針對各種局面的合法著法的數(shù)目的平均值，n 是搜索的深度。同樣道理，由于乙方希望棋盤上的分值盡可能小，那么在奇數(shù)層上會選擇分值最小的結(jié)點。假定甲乙兩方下棋，甲勝的局面是一個極大值（一個很大的正數(shù)），那么乙勝的局面就是一個極小值（極大值的負(fù)值），和棋的局面則是零值（或是接近零的值）。該樹包含三種類型的結(jié)點：……表示紅方走棋表示黑方走棋………… 奇數(shù)層的中間結(jié)點（以及根結(jié)點） ，表示輪到紅方走棋；偶數(shù)層的中間結(jié)點，表示輪到黑方走棋；葉子結(jié)點，表示棋局結(jié)束。本節(jié)先介紹 AlphaBeta 搜索算法：在中國象棋里，雙方棋手獲得相同的棋盤信息。搜索算法的好壞直接影響著程序執(zhí)行的效率（從某種角度上，它影響著計算機(jī)的下棋水平。對于每一層的著法數(shù)，也就是當(dāng)前下棋方針對當(dāng)前局面的所有可選的合法著法，據(jù)有關(guān)數(shù)據(jù)統(tǒng)計在象棋實戰(zhàn)中一般最多情況下也就五六十種。因此可以將著法隊列定義為二維數(shù)組 m_MoveList[8][70]，其中第一個數(shù)組下標(biāo)為層數(shù)，第二個數(shù)組下標(biāo)為每一層的全部著法數(shù)。當(dāng)然所有棋子都不能走到棋盤的外面，同時某些特定的棋子還有自己的行棋界限，如將、士不能出九宮，象不能過河。 著法生成在著法生成器中，采用的基本思想就是遍歷整個棋盤（一個接一個地查看棋盤上的每個位置點），當(dāng)發(fā)現(xiàn)有當(dāng)前下棋方的棋子時先判斷它是何種類型的棋子，然后根據(jù)其棋子類型而相應(yīng)地找出其所有合法著法并存入著法隊列。 //走到什么位置 int Score。著法結(jié)構(gòu)定義如下，其中還包含了對著法的歷史得分的記錄項，以供后面要講到的“歷史啟發(fā)”所用。amp。按此方法棋盤的初始情形如下所示： BYTE CChessBoard[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,