【正文】 ois Dominic (四/OL)：基本搜索方法[EB].~auntyellow/puter/，202235。老 師的嚴(yán)謹(jǐn)治學(xué)態(tài)度、淵博的知識、無私的奉獻(xiàn)精神使我深受啟迪。馬一次可走的選擇點(diǎn)可以達(dá)到四周的八個點(diǎn)，故有“八面威風(fēng)”之說。下面簡單介紹一下象棋相關(guān)規(guī)則：對局時，由執(zhí)紅棋的一方先走，雙方輪流各走一著，直至分出勝、負(fù)、和，對局即終了。包括棋盤局面和著法的表示。由于棋盤、棋子等都是以位圖的形式給出的。 }i=(m_nMaxDepthnDepth+1)%2。減一之后正好是最后一項(xiàng)的行號。rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE)。 (::GetSysColor(COLOR_3DFACE))。//被吃掉的棋子}UNDOMOVE。其次，對一個普通子，當(dāng)它既受到攻擊又受到保護(hù)的時候要注意如下幾個問題：攻擊者子力小于被攻擊者子力，攻擊方將愿意換子。同樣四面被憋馬腿的死馬機(jī)動性也較差（對于一步也不能走的棋子，可以認(rèn)為其機(jī)動性為零） 。對于著法的排序可以使用各種排序算法，在程序中采用了歸并排序?！白钚∽畲蟆钡乃枷朐偌由稀皩涞牟眉簟?，這就是 AlphaBeta 搜索算法的核心。圖中 表示該結(jié)點(diǎn)要取子結(jié)點(diǎn)中的最大值； 表示該結(jié)點(diǎn)要取子結(jié)點(diǎn)中的最小值。反映到博弈樹上，即如果假設(shè)奇數(shù)層表示輪到甲方走棋，偶數(shù)層表示輪到乙方走棋。3 走棋和博弈程序的實(shí)現(xiàn) 博弈程序的實(shí)現(xiàn) 搜索算法搜索算法對于整個下棋引擎來說都是至關(guān)重要的。 有了對棋盤局面和著法的表示之后，程序才能夠完成以下操作： 生成所有合法著法； 執(zhí)行著法、撤銷著法； 針對某一局面進(jìn)行評估。即用一個 9*10 的數(shù)組來存儲棋盤上的信息，數(shù)組的每個元素存儲棋盤上是否有棋子。此博弈程序?qū)崿F(xiàn)了人機(jī)博弈，悔棋，電腦難度設(shè)置，著法名稱生成等功能?？刂朴?jì)算機(jī)的是人類，而人工智能是綜合性很強(qiáng)的一門邊緣學(xué)科，它的中心任務(wù)是研究如何使計(jì)算機(jī)去做那些過去只能靠人的智力才能做的工作。 x=B_END)//判斷某個棋子是不是黑色 define IsRed(x) (x=R_BEGIN amp。行子不能越出棋盤的界限。我們在程序中直接借鑒了 AlphaBeta 搜索算法并輔以歷史啟發(fā)。然而不幸的是，博弈樹相當(dāng)龐大（它會成指數(shù)增長），因而搜索（限定層數(shù)以內(nèi)的）整棵樹是一件相當(dāng)費(fèi)時的工作——其時間復(fù)雜度為 O(bn)。由于結(jié)點(diǎn) B 這層是你的對手來做選擇，假設(shè)他一定會做出明智的選擇（你不能寄希望于你的對手會走出一步“昏招”），那么他會選擇返回值為2 的那個結(jié)點(diǎn)。 //遞歸調(diào)用 UnmakeMove()。首先，先介紹一下在局面評估中需要考慮的因素。對于機(jī)動性打分，需要求出各個子總共有多少種走法，然后根據(jù)各個子所不同的機(jī)動性價(jià)值每多一種走法就加一次相應(yīng)的分?jǐn)?shù)。當(dāng)然，上述四條只是覆蓋了最常見的幾種情況，覆蓋并不全面。然后從列表框中刪除它。 return。 } // Do not call CProgressCtrl::OnPaint() for painting messages } int CGradientProgressCtrl::SetPos(int nPos) { //Set the Position of the Progress m_nCurrentPosition=nPos。i10。//奇數(shù)層返回極小值elsereturn 19990+nDepth。其中第二個參數(shù) CPoint point 是在本程序中所要用到的，它給出了當(dāng)鼠標(biāo)左鍵被按下時，鼠標(biāo)指針的位置坐標(biāo)。 ——?dú)v史啟發(fā)。它只能在“九宮”之內(nèi)活動，可上可下，可左可右，每次走動只能按豎線或橫線走動一格。走法記錄界面（圖 5）如下：圖 5 走法記錄界面其他輔助功能界面（圖 6）如下：圖 6 其他輔助功能界面你可以通過上面四個輔助功能對棋局進(jìn)行研究，從而提高你的下棋水平。對于諸如位棋盤（BitBoard） 、迭代加深（Iterative Deepening） 、機(jī)器學(xué)習(xí)（ Machine Learning）等當(dāng)今棋類對弈程序中所采用的先進(jìn)技術(shù)和思想，在程序中并未涉及。game tree。[7] Fran231。腳踏實(shí)地，認(rèn)真嚴(yán)謹(jǐn)，實(shí)事求是的學(xué)習(xí)態(tài)度，不怕困難、堅(jiān)持不懈、吃苦耐勞的精神是我在這次設(shè)計(jì)中最大的收益。相（象）的活動范圍限于“河界”以內(nèi)的本方陣地，不能過河，且如果它走的“田”字中央有一個棋子，就不能走，俗稱“塞象眼” 。當(dāng)實(shí)現(xiàn)了引擎部分的各要素時，可先建立一個 Win32 控制臺項(xiàng)目，之后只要再添加 文件負(fù)責(zé)接受用戶的輸入、調(diào)用搜索函數(shù)、顯示搜索結(jié)果，便可簡單的測試引擎了（采用輸入著法的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)的方式來傳送用戶走棋的信息。如此，在 OnLButtonDown 函數(shù)里，實(shí)現(xiàn)了人與機(jī)器的對弈（當(dāng)然每走一步棋，也還需要繪圖函數(shù)來顯示棋盤局面的更新） 。初始化的內(nèi)容包括：對引擎部分所用到的變量的初始化。i3。 //用來獲得剛下的一步棋的走法； void CChessDlg::AddChessRecord(int nFromX,int nFromY,int nToX,int nToY,int nUserChessColor,int nSourceID) //將走法添加進(jìn)下棋記錄； 然后，顯示在 Listbox 中。 //顯示進(jìn)程條進(jìn)度文字 if(m_bShowPercent) { CString percent。為了獲得該著法名稱，我們編寫了一個函數(shù)，其功能就是將被移動的棋子類型以及走法的起點(diǎn)坐標(biāo)、終點(diǎn)坐標(biāo)這些信息轉(zhuǎn)換成中國象棋所規(guī)范的著法名稱。此后當(dāng)悔棋的時候，需要撤銷著法；還原的時候，需要執(zhí)行著法。//存放每一位置上棋子的靈活性分值int m_chessValue[10][9]。比如紅方擁有士象全加車馬炮，而黑方只有殘士象加雙馬，則紅方明顯占優(yōu)。可以根據(jù)部分已經(jīng)搜索過的結(jié)果來調(diào)整將要搜索的結(jié)點(diǎn)的順序。不必再繼續(xù)考察結(jié)點(diǎn) C 的剩余子結(jié)點(diǎn)了，因?yàn)榻Y(jié)點(diǎn) C 已經(jīng)夠糟糕的了，不管結(jié)點(diǎn) C 的剩余子結(jié)點(diǎn)有怎樣的分值，它最多只能傳回8（有可能其剩余子結(jié)點(diǎn)中還有分值更小的結(jié)點(diǎn)，因而結(jié)點(diǎn) C 還有可能傳回更小的值）。這樣一來便可以在很大程度上減少搜索的工作量，提高搜索效率，這稱為“樹的裁剪”?，F(xiàn)在讓計(jì)算機(jī)來下中國象棋，它應(yīng)當(dāng)選擇一步對它最有利的著法（最終導(dǎo)致它取勝的著法） 。關(guān)于搜索層數(shù)，設(shè)定為 4，實(shí)際使用的是 1 到 3（在界面中將其限定為 1—3）。 typedef struct { short nChessID。放眼未來，象棋軟件已經(jīng)走完了一波持續(xù)上漲的行情，有可能出現(xiàn)逐步降溫的滑坡趨勢。 畢 業(yè) 設(shè) 計(jì)中國象棋游戲的設(shè)計(jì)與實(shí)現(xiàn) 摘 要中國象棋發(fā)展至今已有數(shù)千年的歷史了，它是中華民族智慧的結(jié)晶?？偠灾?，各類象棋軟件既有自身的優(yōu)點(diǎn)，也存在共通性的缺陷，如：中局審勢不夠智能化，走不出棄子取勢的人性化佳構(gòu)，殘局時智力明顯低于人腦，難以走出殘局例勝的必然著法等。著法結(jié)構(gòu)定義如下，其中還包含了對著法的歷史得分的記錄項(xiàng)，以供后面要講到的“歷史啟發(fā)”所用。因此可以將著法隊(duì)列定義為二維數(shù)組 m_MoveList[8][70]，其中第一個數(shù)組下標(biāo)為層數(shù)，第二個數(shù)組下標(biāo)為每一層的全部著法數(shù)。該樹包含三種類型的結(jié)點(diǎn)：……表示紅方走棋表示黑方走棋………… 奇數(shù)層的中間結(jié)點(diǎn)（以及根結(jié)點(diǎn)） ，表示輪到紅方走棋；偶數(shù)層的中間結(jié)點(diǎn)，表示輪到黑方走棋；葉子結(jié)點(diǎn)，表示棋局結(jié)束。所以當(dāng)你看到某個局面有可能產(chǎn)生很糟糕的局面時（確切地說這里的“很糟糕”是與之前分析的情況相比較而言的），你應(yīng)當(dāng)立刻停止對其剩余子結(jié)點(diǎn)的分析——不要對它再抱任何幻 想了，如果你選擇了它，那么你必將得到那個很糟糕的局面，甚至可能更糟。AC DB8 2 10 8 ?2 … …… 采用 “裁剪”方法。因而，要想保證 AlphaBeta 搜索算法的效率就需要調(diào)整樹的結(jié)構(gòu)，即調(diào)整待搜索的結(jié)點(diǎn)的順序，使得“裁剪”可以盡可能早地發(fā)生。所以在評估局面時，首先要考慮雙方的子力總和的對比。 //存放每一位置被保護(hù)的信息BYTE m_FlexibilityPos[10][9]。在程序中保存了如下信息：棋局表示中所定義的棋盤數(shù)組；各棋子的貼圖位置；這里需要特別說明的是通常象棋程序處于程序效率的考慮并不保存所有棋子的信息，而只是保存之前一步的走棋信息。如：炮八進(jìn)四、馬二進(jìn)三此類。dc,rectClient,(int)maxWidth)。首先，在 ChessDlg 下定義以下函數(shù)： thisGetMoveStr(nFromX,nFromY,nToX,nToY,nSourceID)。 } //檢查黑方九宮是否有將 for(i=0?？梢园延嘘P(guān)中國象棋的棋局初始化情況也放在了這里面。緊接著調(diào)用引擎的搜索函數(shù)計(jì)算出計(jì)算機(jī)對用戶著法的應(yīng)著，然后執(zhí)行該應(yīng)著。為某一特定局面進(jìn)行評分。它的走法是每次循對角線走兩格，俗稱“象走田” 。回想這段日子的經(jīng)歷和感受，我感慨萬千，在