【文章內(nèi)容簡(jiǎn)介】 ta 算法的派生、變種算法）在程序中直接. . . .學(xué)習(xí)參考借鑒了 AlphaBeta 搜索算法并輔以了歷史啟發(fā)。本節(jié)先介紹 AlphaBeta 搜索算法：在中國(guó)象棋里，雙方棋手獲得相同的棋盤(pán)信息。他們輪流走棋，目的就是將死對(duì)方，或者避免被將死。由此，可以用一棵“博弈樹(shù)” （圖 2）來(lái)表示下棋的過(guò)程——樹(shù)中每一個(gè)結(jié)點(diǎn)代表棋盤(pán)上的一個(gè)局面，對(duì)每一個(gè)局面（結(jié)點(diǎn)）根據(jù)不同的走法又產(chǎn)生不同的局面（生出新的結(jié)點(diǎn)） ，如此不斷直到再無(wú)可選擇的走法，即到達(dá)葉子結(jié)點(diǎn)（棋局結(jié)束） 。中國(guó)象棋的博弈樹(shù)的模型大概如下圖所示，可以把其中連接結(jié)點(diǎn)的線段看作是著法，不同的著法自然產(chǎn)生不同的局面。。表示黑方走棋表示紅方走棋圖 2 博弈樹(shù)該樹(shù)包含三種類型的結(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é)合上面所講的博弈樹(shù)，若給每個(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ù)層表示輪到乙方走棋。那么由于甲方希望棋盤(pán)上的分值盡可能大，則在偶數(shù)層上會(huì)挑選分值最大的結(jié)點(diǎn)——偶數(shù)層的結(jié)點(diǎn)是甲走完一步棋之后的棋盤(pán)局面，反映了甲方對(duì)棋局形勢(shì)的要求。同樣道理，由于乙方希望棋盤(pán)上的分值盡可能小，那么在奇數(shù)層上會(huì)選擇分值最小的結(jié)點(diǎn)。這是“最小最大” （Minimax）的基本思想。這樣搜索函數(shù)在估值函數(shù)的. . . .學(xué)習(xí)參考協(xié)助下可以通過(guò)在奇數(shù)層選擇分值最大（最?。┑慕Y(jié)點(diǎn)，在偶數(shù)層選擇分值最?。ㄗ畲螅┑慕Y(jié)點(diǎn)的方式來(lái)搜索以當(dāng)前局面為根結(jié)點(diǎn)、限定搜索層數(shù)以內(nèi)的整棵樹(shù)來(lái)獲得一個(gè)最佳的著法。然而不幸的是，博弈樹(shù)相當(dāng)龐大（它會(huì)成指數(shù)增長(zhǎng)） ，因而搜索（限定層數(shù)以內(nèi)的）整棵樹(shù)是一件相當(dāng)費(fèi)時(shí)的工作——其時(shí)間復(fù)雜度為 O(bn)。其中 b 是分枝因子，即針對(duì)各種局面的合法著法的數(shù)目的平均值，n 是搜索的深度。對(duì)于中國(guó)象棋而言，在中盤(pán)時(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)便可以在很大程度上減少搜索的工作量，提高搜索效率，這稱為“樹(shù)的裁剪” 。下面用圖來(lái)進(jìn)一步說(shuō)明“樹(shù)的裁剪” 。為了簡(jiǎn)便起見(jiàn)，將博弈樹(shù)進(jìn)行了簡(jiǎn)化——每個(gè)結(jié)點(diǎn)只有三個(gè)分支，實(shí)際情況中，剛才講過(guò)在盤(pán)中應(yīng)有大約 40 個(gè)分支。假定棋盤(pán)上的局面發(fā)展到了結(jié)點(diǎn) A（圖 3） ，現(xiàn)在輪到你走棋了，你是“最大的一方”——即你希望棋局的分值盡可能的高。用搜索兩層來(lái)看一看“樹(shù)的裁剪”對(duì)提高搜索效率的幫助。圖中 表示該結(jié)點(diǎn)要取子結(jié)點(diǎn)中的最大值； 表示該結(jié)點(diǎn)要取子結(jié)點(diǎn)中的最小值。ＡＢ Ｃ Ｄ1 0 5 2 8？ ？ 。 。 。 。 。 。圖 3 樹(shù)的裁剪首先，考察結(jié)點(diǎn) A 的子結(jié)點(diǎn) B。結(jié)點(diǎn) B 所屬的這一層是輪到你的對(duì)手——. . . .學(xué)習(xí)參考“最小者”來(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)（從左到右算起）返回 10，第二個(gè)子結(jié)點(diǎn)返回了5，第三個(gè)子結(jié)點(diǎn)返回了 2。由于結(jié)點(diǎn) B 這層是你的對(duì)手來(lái)做選擇，假設(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)所表示的局面。再來(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)返回了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)分析過(guò)的結(jié)點(diǎn) B 所傳回5 相比較，作為“最大一方”的你顯然更不愿意看到8 的局面。所以，你當(dāng)然不會(huì)選擇相應(yīng)的著法使得局面發(fā)展成為結(jié)點(diǎn) C。因?yàn)槟菢拥脑?，下一步你的?duì)手就會(huì)帶給你一個(gè)分值不高于8的局面。由此，在不影響搜索質(zhì)量的前提下避免了搜索“無(wú)價(jià)值的”結(jié)點(diǎn) C 的剩余子結(jié)點(diǎn)的大量工作，從而節(jié)省了寶貴時(shí)間，為在同樣機(jī)器配置下搜索更多的層數(shù)提供了可能。“最小最大”的思想再加上“對(duì)樹(shù)的裁剪” ，這就是 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()。 //撤銷著法. . . .學(xué)習(xí)參考if (val = beta) //裁剪return beta。if (val alpha) //保留最大值alpha = val。}return alpha。} 歷史啟發(fā)及著法排序既然 AlphaBeta 搜索算法是在“最小最大”的基礎(chǔ)上引入“樹(shù)的裁剪”的思想以期提高效率，那么它的效率將在很大程度上取決于樹(shù)的結(jié)構(gòu)——如果搜索了沒(méi)多久就發(fā)現(xiàn)可以進(jìn)行“裁剪”了，那么需要分析的工作量將大大減少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此時(shí)“裁剪”也已經(jīng)失去了它原有的價(jià)值（因?yàn)槟阋呀?jīng)分析了所有情況，這時(shí)的 AlphaBeta 搜索已和“最小最大”搜索別無(wú)二致了） 。因而，要想保證 AlphaBeta 搜索算法的效率就需要調(diào)整樹(shù)的結(jié)構(gòu)，即調(diào)整待搜索的結(jié)點(diǎn)的順序，使得“裁剪”可以盡可能早地發(fā)生?？梢愿鶕?jù)部分已經(jīng)搜索過(guò)的結(jié)果來(lái)調(diào)整將要搜索的結(jié)點(diǎn)的順序。因?yàn)?，通常?dāng)一個(gè)局面經(jīng)過(guò)搜索被認(rèn)為較好時(shí)，其子結(jié)點(diǎn)中往往有一些與它相似的局面（如個(gè)別無(wú)關(guān)緊要的棋子位置有所不同）也是較好的。由 所提出的“歷史啟發(fā)” （History Heuristic）就是建立在這樣一種觀點(diǎn)之上的。在搜索的過(guò)程中，每當(dāng)發(fā)現(xiàn)一個(gè)好的走法，就給該走法累加一個(gè)增量以記錄其“歷史得分” ，一個(gè)多次被搜索并認(rèn)為是好的走法的“歷史得分”就會(huì)較高。對(duì)于即將搜索的結(jié)點(diǎn)，按照“歷史得分”的高低對(duì)它們進(jìn)行排序，保證較好的走法（“歷史得分”高的走法）排在前面，這樣 AlphaBeta 搜索就可以盡可能早地進(jìn)行“裁剪” ，從而保證了搜索