【文章內(nèi)容簡介】 成計(jì)算機(jī)的著法時(shí)認(rèn)為將帥碰面是非法的，而對(duì)用戶所走的導(dǎo)致將帥碰面的著法并不認(rèn)為其非法，而只是產(chǎn)生敗局罷了） 。產(chǎn)生了著法后要將其存入著法隊(duì)列以供搜索之用，由于搜索會(huì)搜索多層（即考慮雙方你來我往好幾步，這樣才有利于對(duì)局面進(jìn)行評(píng)估以盡可能避免“目光短淺” ） ，所以在把著法存入著法隊(duì)列的時(shí)候還要同時(shí)存儲(chǔ)該著法所屬的搜索層數(shù)。因此可以將著法隊(duì)列定義為二維數(shù)組 m_MoveList[8][80]，其中第一個(gè)數(shù)組下標(biāo)為層數(shù)，第二個(gè)數(shù)組下標(biāo)為每一層的全部著法數(shù)。關(guān)于搜索層數(shù)，設(shè)定為 8，實(shí)際使用的是 1 到 7（在界面中將其限定為 1—7） 。搜索層數(shù)的增加會(huì)顯著提高電腦的下棋水平（當(dāng)然計(jì)算機(jī)的棋力在很大程度上也依賴于局面評(píng)估） 。在配置為 ，512M 內(nèi)存的計(jì)算機(jī)上最多只能搜索4 層，再多將導(dǎo)致搜索時(shí)間達(dá)到令人無法容忍的地步（這里還需要特別說明的是，搜索的速度也和著法生成的效率以及局面評(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)為 80，應(yīng)當(dāng)可以保證十分的安全。著法生成為搜索部分提供了“原料” ，接下來的任務(wù)就交給搜索和局面評(píng)估了。 搜索算法搜索算法對(duì)于整個(gè)下棋引擎來說都是至關(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 算法的派生、變種算法）在程序中直接借鑒了 AlphaBeta 搜索算法并輔以了歷史啟發(fā)。本節(jié)先介紹 AlphaBeta 搜索算法：在中國象棋里，雙方棋手獲得相同的棋盤信息。他們輪流走棋，目的就是將死對(duì)方，或者避免被將死。由此，可以用一棵“博弈樹” （圖 2）來表示下棋的過程——樹中每一個(gè)結(jié)點(diǎn)代表棋盤上的一個(gè)局面，對(duì)每一個(gè)局面（結(jié)點(diǎn)）根據(jù)不同的走法又產(chǎn)生不同的局面（生出新的結(jié)點(diǎn)） ，如此不斷直到再無可選擇的走法，即到達(dá)葉子結(jié)點(diǎn)（棋局結(jié)束） 。中國象棋的博弈樹的模型大概如下圖所示，可以把其中連接結(jié)點(diǎn)的線段看作是著法，不同的著法自然產(chǎn)生不同的局面。。表示黑方走棋表示紅方走棋圖 2 博弈樹該樹包含三種類型的結(jié)點(diǎn)： 奇數(shù)層的中間結(jié)點(diǎn)（以及根結(jié)點(diǎn)） ，表示輪到紅方走棋； 偶數(shù)層的中間結(jié)點(diǎn)，表示輪到黑方走棋； 葉子結(jié)點(diǎn)，表示棋局結(jié)束。現(xiàn)在讓計(jì)算機(jī)來下中國象棋，它應(yīng)當(dāng)選擇一步對(duì)它最有利的著法（最終導(dǎo)致它取勝的著法） 。獲得最佳著法的方法就是“試走”每一種可能的著法，比較它們所產(chǎn)生的不同后果，然后從中選出能夠產(chǎn)生對(duì)自己最有利的局面的著法。結(jié)合上面所講的博弈樹，若給每個(gè)結(jié)點(diǎn)都打一個(gè)分值來評(píng)價(jià)其對(duì)應(yīng)的局面（這一任務(wù)由后面所講的局面評(píng)估來完成） ，那么可以通過比較該分值的大小來判斷局面的優(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ù)層上會(huì)選擇分值最小的結(jié)點(diǎn)。這是“最小最大” （Minimax）的基本思想。這樣搜索函數(shù)在估值函數(shù)的協(xié)助下可以通過在奇數(shù)層選擇分值最大（最?。┑慕Y(jié)點(diǎn)，在偶數(shù)層選擇分值最小（最大）的結(jié)點(diǎn)的方式來搜索以當(dāng)前局面為根結(jié)點(diǎn)、限定搜索層數(shù)以內(nèi)的整棵樹來獲得一個(gè)最佳的著法。然而不幸的是，博弈樹相當(dāng)龐大（它會(huì)成指數(shù)增長） ，因而搜索（限定層數(shù)以內(nèi)的）整棵樹是一件相當(dāng)費(fèi)時(shí)的工作——其時(shí)間復(fù)雜度為 O(bn)。其中 b 是分枝因子，即針對(duì)各種局面的合法著法的數(shù)目的平均值，n 是搜索的深度。對(duì)于中國象棋而言，在中盤時(shí)平均著法數(shù)目大約是 40 種左右，那么搜索 4 層需要檢查 250 萬條路線，搜索 5 層需要檢查 1 億條路線，搜索 6 層需要檢查 40 億條路線！AlphaBeta 搜索能在不影響搜索精度的前提下大幅減少工作量。因?yàn)?，如果考慮到下棋是一個(gè)你來我往的交替進(jìn)行并且相互“較勁”的過程。由于每一方都會(huì)盡可能將局面導(dǎo)向?qū)ψ约河欣鴮?duì)對(duì)方不利的方向（假定下棋雙方對(duì)棋局有著同樣的認(rèn)知，即你認(rèn)為對(duì)你很糟糕的局面，在你的對(duì)手看來則是對(duì)他很有利的局面） ，那么某些局面由于能夠產(chǎn)生出很糟糕的局面因而根本沒有再繼續(xù)考慮的價(jià)值。所以當(dāng)你看到某個(gè)局面有可能產(chǎn)生很糟糕的局面時(shí)（確切地說這里的“很糟糕”是與之前分析的情況相比較而言的） ，你應(yīng)當(dāng)立刻停止對(duì)其剩余子結(jié)點(diǎn)的分析——不要對(duì)它再抱任何幻想了，如果你選擇了它，那么你必將得到那個(gè)很糟糕的局面，甚至可能更糟……這樣一來便可以在很大程度上減少搜索的工作量，提高搜索效率，這稱為“樹的裁剪” 。下面用圖來進(jìn)一步說明“樹的裁剪” 。為了簡便起見，將博弈樹進(jìn)行了簡化——每個(gè)結(jié)點(diǎn)只有三個(gè)分支，實(shí)際情況中，剛才講過在盤中應(yīng)有大約 40 個(gè)分支。假定棋盤上的局面發(fā)展到了結(jié)點(diǎn) A（圖 3） ，現(xiàn)在輪到你走棋了，你是“最大的一方”——即你希望棋局的分值盡可能的高。用搜索兩層來看一看“樹的裁剪”對(duì)提高搜索效率的幫助。圖中 表示該結(jié)點(diǎn)要取子結(jié)點(diǎn)中的最大值； 表示該結(jié)點(diǎn)要取子結(jié)點(diǎn)中的最小值。ＡＢ Ｃ Ｄ1 0 5 2 8？ ？ 。 。 。 。 。 。圖 3 樹的裁剪首先，考察結(jié)點(diǎn) A 的子結(jié)點(diǎn) B。結(jié)點(diǎn) B 所屬的這一層是輪到你的對(duì)手——“最小者”來走棋了，目的是使得棋局的分值盡可能的小。依次考察結(jié)點(diǎn) B 的各個(gè)子結(jié)點(diǎn)，查看它們的分值（因?yàn)槭孪燃s定好了搜索兩層，現(xiàn)在已達(dá)到搜索深度的要求了，所以就停下來調(diào)用局面評(píng)估函數(shù)來給它打分） 。結(jié)點(diǎn) B 的第一個(gè)子結(jié)點(diǎn)（從左到右算起）返回 10，第二個(gè)子結(jié)點(diǎn)返回了5，第三個(gè)子結(jié)點(diǎn)返回了 2。由于結(jié)點(diǎn) B 這層是你的對(duì)手來做選擇，假設(shè)他一定會(huì)做出明智的選擇（你不能寄希望于你的對(duì)手會(huì)走出一步“昏招” ） ，那么他會(huì)選擇返回值為5 的那個(gè)結(jié)點(diǎn)。5 最終也就成了從結(jié)點(diǎn) B 傳遞回的值，即倘若你（現(xiàn)在位于結(jié)點(diǎn)A）選擇了產(chǎn)生結(jié)點(diǎn) B 的走法，使得局面發(fā)展到了結(jié)點(diǎn) B。那么下一步，你的對(duì)手的選擇就會(huì)使得棋局發(fā)展成為分值為5 的那個(gè)結(jié)點(diǎn)所表示的局面。再來分析結(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)返回了8……采用 “裁剪”方法。不必再繼續(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 還有可能傳回更小的值） 。而與前面已經(jīng)分析過的結(jié)點(diǎn) B 所傳回5 相比較，作為“最大一方”的你顯然更不愿意看到8 的局面。所以，你當(dāng)然不會(huì)選擇相應(yīng)的著法使得局面發(fā)展成為結(jié)點(diǎn) C。因?yàn)槟菢拥脑挘乱徊侥愕膶?duì)手就會(huì)帶給你一個(gè)分值不高于8的局面。由此，在不影響搜索質(zhì)量的前提下避免了搜索“無價(jià)值的”結(jié)點(diǎn) C 的剩余子結(jié)點(diǎn)的大量工作，從而節(jié)省了寶貴時(shí)間，為在同樣機(jī)器配置下搜索更多的層數(shù)提供了可能?！白钚∽畲蟆钡乃枷朐偌由稀皩?duì)樹的裁剪” ，這就是 AlphaBeta 搜索算法的核心。最基本的 AlphaBeta 算法的代碼如下：int AlphaBeta(int depth, int alpha, int beta){if (depth == 0) //如果是葉子節(jié)點(diǎn)（到達(dá)搜索深度要求）return Evaluate()。 //則由局面評(píng)估函數(shù)返回估值GenerateLegalMoves()。 //產(chǎn)生所有合法著法while (MovesLeft()) //遍歷所有著法{MakeNextMove()。 //執(zhí)行著法int val = AlphaBeta(depth 1, beta, alpha)。 //遞歸調(diào)用UnmakeMove()。 //撤銷著法if (val = beta) //裁剪return beta。if (val alpha) //保留最大值alpha = val。}return alpha。} 歷史啟發(fā)及著法排序既然 Alpha