【正文】 efine 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 IsBlack(x) (x=B_BEGIN amp。amp。 x=B_END)//判斷某個(gè)棋子是不是黑色 define IsRed(x) (x=R_BEGIN amp。amp。 x=R_END)//判斷某個(gè)棋子是不是紅色對(duì)于著法的表示，直接借用棋盤數(shù)組的下標(biāo)來(lái)記錄著法的起點(diǎn)和目標(biāo)點(diǎn)。至于是什么棋子在走，以及是否吃子、吃的是什么子，在著法結(jié)構(gòu)中并不記錄。這些信息由外部讀取棋盤上起點(diǎn)、終點(diǎn)的數(shù)據(jù)獲得。著法結(jié)構(gòu)定義如下，其中還包含了對(duì)著法的歷史得分的記錄項(xiàng)，以供后面要講到的“歷史啟發(fā)”所用。 typedef struct { short nChessID。 //表明是什么棋子 CHESSMANPOS From。//起始位置 CHESSMANPOS To。 //走到什么位置 int Score。 //走法的分?jǐn)?shù) }CHESSMOVE。 有了對(duì)棋盤局面和著法的表示之后，程序才能夠完成以下操作： 生成所有合法著法； 執(zhí)行著法、撤銷著法； 針對(duì)某一局面進(jìn)行評(píng)估。 因而，棋局表示好比是整個(gè)程序（計(jì)算機(jī)下棋引擎部分）的地基，之后所有的操作都將建立在其基礎(chǔ)上。 著法生成在著法生成器中，采用的基本思想就是遍歷整個(gè)棋盤（一個(gè)接一個(gè)地查看棋盤上的每個(gè)位置點(diǎn)），當(dāng)發(fā)現(xiàn)有當(dāng)前下棋方的棋子時(shí)先判斷它是何種類型的棋子，然后根據(jù)其棋子類型而相應(yīng)地找出其所有合法著法并存入著法隊(duì)列。這里談到的“合法著法”包括以下幾點(diǎn)：各棋子按其行子規(guī)則行子。諸如馬跳“日”字、象走“田”字、士在九宮內(nèi)斜行等等（這里需要特別注意的是卒（兵）的行子規(guī)則會(huì)隨其所在位置的不同而發(fā)生變化——過(guò)河后可以左右平移）。行子不能越出棋盤的界限。當(dāng)然所有棋子都不能走到棋盤的外面，同時(shí)某些特定的棋子還有自己的行棋界限，如將、士不能出九宮，象不能過(guò)河。行子的半路上不能有其它子阻攔（除了炮需要隔一個(gè)子才能打子之外）以及行子的目的點(diǎn)不能有本方的棋子（當(dāng)然不能自己吃自己了）。將帥不能碰面（本程序中只在生成計(jì)算機(jī)的著法時(shí)認(rèn)為將帥碰面是非法的，而對(duì)用戶所走的導(dǎo)致將帥碰面的著法并不認(rèn)為其非法，而只是產(chǎn)生敗局罷了）。產(chǎn)生了著法后要將其存入著法隊(duì)列以供搜索之用，由于搜索會(huì)搜索多層（即考慮雙方你來(lái)我往好幾步，這樣才有利于對(duì)局面進(jìn)行評(píng)估以盡可能避免“目光短淺”），所以在把著法存入著法隊(duì)列的時(shí)候還要同時(shí)存儲(chǔ)該著法所屬的搜索層數(shù)。因此可以將著法隊(duì)列定義為二維數(shù)組 m_MoveList[8][70]，其中第一個(gè)數(shù)組下標(biāo)為層數(shù)，第二個(gè)數(shù)組下標(biāo)為每一層的全部著法數(shù)。關(guān)于搜索層數(shù)，設(shè)定為 4，實(shí)際使用的是 1 到 3（在界面中將其限定為 1—3）。搜索層數(shù)的增加會(huì)顯著提高電腦的下棋水平（當(dāng)然計(jì)算機(jī)的棋力在很大程度上也依賴于局面評(píng)估）。在配置為 ，512M 內(nèi)存的計(jì)算機(jī)上最多只能搜索 3 層，再多將導(dǎo)致搜索時(shí)間達(dá)到令人無(wú)法容忍的地步（這里還需要特別說(shuō)明的是，搜索的速度也和著法生成的效率以及局面評(píng)估的復(fù)雜度有關(guān)，因?yàn)槊糠治鲆粋€(gè)結(jié)點(diǎn)都要執(zhí)行這兩種操作）。對(duì)于每一層的著法數(shù)，也就是當(dāng)前下棋方針對(duì)當(dāng)前局面的所有可選的合法著法，據(jù)有關(guān)數(shù)據(jù)統(tǒng)計(jì)在象棋實(shí)戰(zhàn)中一般最多情況下也就五六十種。定義第二個(gè)數(shù)組下標(biāo)為 70， 應(yīng)當(dāng)可以保證十分的安全。3 走棋和博弈程序的實(shí)現(xiàn) 博弈程序的實(shí)現(xiàn) 搜索算法搜索算法對(duì)于整個(gè)下棋引擎來(lái)說(shuō)都是至關(guān)重要的。它如同程序的心臟，驅(qū)動(dòng)著整個(gè)程序。搜索算法的好壞直接影響著程序執(zhí)行的效率（從某種角度上，它影響著計(jì)算機(jī)的下棋水平。因?yàn)?，?jì)算機(jī)必須在有限的時(shí)間內(nèi)完成思考，搜索速度快意味著在相同的時(shí)間內(nèi)程序可以“看”得更遠(yuǎn)， “想”的更多） 。關(guān)于棋類對(duì)弈程序中的搜索算法，已有成熟的 AlphaBeta 搜索算法以及其它一些輔助增強(qiáng)算法（還有眾多基于 AlphaBeta 算法的派生、變種算法） 。我們?cè)诔绦蛑兄苯咏梃b了 AlphaBeta 搜索算法并輔以歷史啟發(fā)。本節(jié)先介紹 AlphaBeta 搜索算法：在中國(guó)象棋里，雙方棋手獲得相同的棋盤信息。他們輪流走棋，目的就是吃掉對(duì)方的將或帥，或者避免自己的將或帥被吃。圖 1 博弈樹又此，可以用一棵“博弈樹” （圖 1）來(lái)表示下棋的過(guò)程——樹中每一個(gè)結(jié)點(diǎn)代表棋盤上的一個(gè)局面，對(duì)每一個(gè)局面（結(jié)點(diǎn)）根據(jù)不同的走法又產(chǎn)生不同的局面（生出新的結(jié)點(diǎn)） ，如此不斷進(jìn)行下去直到再無(wú)可選擇的走法，即到達(dá)葉子結(jié)點(diǎn)（棋局結(jié)束） 。中國(guó)象棋的博弈樹的模型大概如下圖所示，可以把其中連接結(jié)點(diǎn)的線段看作是著法，不同的著法自然產(chǎn)生不同的局面。該樹包含三種類型的結(jié)點(diǎn)：……表示紅方走棋表示黑方走棋………… 奇數(shù)層的中間結(jié)點(diǎn)（以及根結(jié)點(diǎn)） ，表示輪到紅方走棋；偶數(shù)層的中間結(jié)點(diǎn)，表示輪到黑方走棋；葉子結(jié)點(diǎn)，表示棋局結(jié)束?，F(xiàn)在讓計(jì)算機(jī)來(lái)下中國(guó)象棋，它應(yīng)當(dāng)選擇一步對(duì)它最有利的著法（最終導(dǎo)致它取勝的著法） 。獲得最佳著法的方法就是“試走”每一種可能的著法，比較它們所產(chǎn)生的不同后果，然后從中選出能夠產(chǎn)生對(duì)自己最有利的局面的著法。結(jié)合上面所講的博弈樹，若給每個(gè)結(jié)點(diǎn)都打一個(gè)分值來(lái)評(píng)價(jià)其對(duì)應(yīng)的局面（這一任務(wù)由后面所講的局面評(píng)估來(lái)完成），那么可以通過(guò)比較該分值的大小來(lái)判斷局面的優(yōu)劣。假定甲乙兩方下棋，甲勝的局面是一個(gè)極大值（一個(gè)很大的正數(shù)），那么乙勝的局面就是一個(gè)極小值（極大值的負(fù)值），和棋的局面則是零值（或是接近零的值）。如此，當(dāng)輪到甲走棋時(shí)他會(huì)盡可能地讓局面上的分值大，相反輪到乙走棋時(shí)他會(huì)選盡可能地讓局面上的分值小。反映到博弈樹上，即如果假設(shè)奇數(shù)層表示輪到甲方走棋，偶數(shù)層表示輪到乙方走棋。那么由于甲方希望棋盤上的分值盡可能大，則在偶數(shù)層上會(huì)挑選分值最大的結(jié)點(diǎn)——偶數(shù)層的結(jié)點(diǎn)是甲走完一步棋之后的棋盤局面，反映了甲方對(duì)棋局形勢(shì)的要求。同樣道理，由于乙方希望棋盤上的分值盡可能小，那么在奇數(shù)層上會(huì)選擇分值最小的結(jié)點(diǎn)。這是“最小最大”（Minimax）的基本思想。這樣搜索函數(shù)在估值函數(shù)的協(xié)助下可以通過(guò)在奇數(shù)層選擇分值最大（最?。┑慕Y(jié)點(diǎn)，在偶數(shù)層選擇分值最?。ㄗ畲螅┑慕Y(jié)點(diǎn)的方式來(lái)搜索以當(dāng)前局面為根結(jié)點(diǎn)、限定搜索層數(shù)以內(nèi)的整棵樹來(lái)獲得一個(gè)最佳的著法。然而不幸的是，博弈樹相當(dāng)龐大（它會(huì)成指數(shù)增長(zhǎng)），因而搜索（限定層數(shù)以內(nèi)的）整棵樹是一件相當(dāng)費(fèi)時(shí)的工作——其時(shí)間復(fù)雜度為 O(bn)。其中 b 是分枝因子，即針對(duì)各種局面的合法著法的數(shù)目的平均值，n 是搜索的深度。對(duì)于中國(guó)象棋而言，在中盤時(shí)平均著法數(shù)目大約是 40 種左右，那么搜索 4 層需要檢查 250 萬(wàn)條路線，搜索 5 層需要檢查 1 億條路線，搜索 6 層需要檢查 40 億條路線！AlphaBeta 搜索能在不影響搜索精度的前提下大幅減少工作量。因?yàn)椋绻紤]到下棋是一個(gè)你來(lái)我往的交替進(jìn)行并且相互“較勁”的過(guò)程。由于每一方都會(huì)盡可能將局面導(dǎo)向?qū)ψ约河欣鴮?duì)對(duì)方不利的方向（假定下棋雙方對(duì)棋局有著同樣的認(rèn)知，即你認(rèn)為對(duì)你很糟糕的局面，在你的對(duì)手看來(lái)則是對(duì)他很有利的局面），那么某些局面由于能夠產(chǎn)生出很糟糕的局面因而根本沒(méi)有再繼續(xù)考慮的價(jià)值。所以當(dāng)你看到某個(gè)局面有可能產(chǎn)生很糟糕的局面時(shí)（確切地說(shuō)這里的“很糟糕”是與之前分析的情況相比較而言的），你應(yīng)當(dāng)立刻停止對(duì)其剩余子結(jié)點(diǎn)的分析——不要對(duì)它再抱任何幻 想了，如果你選擇了它，那么你必將得到那個(gè)很糟糕的局面，甚至可能更糟。這樣一來(lái)便可以在很大程度上減少搜索的工作量，提高搜索效率，這稱為“樹的裁剪”。下面用圖來(lái)進(jìn)一步說(shuō)明“樹的裁剪”。為了簡(jiǎn)便起見，將博弈樹進(jìn)行了簡(jiǎn)化——每個(gè)結(jié)點(diǎn)只有三個(gè)分支，實(shí)際情況中，剛才講過(guò)在盤中應(yīng)有大約 40 個(gè)分支。假定棋盤上的局面發(fā)展到了結(jié)點(diǎn) A（圖 2），現(xiàn)在輪到你走棋了，你是 “最大的一方”——即你希望棋局的分值盡可能的高。用搜索兩層來(lái)看一看“樹的裁剪”對(duì)提高搜索效率的幫助。圖中 表示該結(jié)點(diǎn)要取子結(jié)點(diǎn)中的最大值； 表示該結(jié)點(diǎn)要取子結(jié)點(diǎn)中的最小值。圖 2 樹的裁剪首先，考察結(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……。AC DB8 2 10