《》專題 Alpha-Beta搜索 Bruce Moreland / 文最小-最大的問題Alpha-Beta 同“最小-最大”非常相似，事實(shí)上只多了一條額外的語(yǔ)句。最小最大運(yùn)行時(shí)要檢查整個(gè)博弈樹，然后盡可能選擇最好的線路。這是非常好理解的，但效率非常低。每次搜索更深一層時(shí)，樹的大小就呈指數(shù)式增長(zhǎng)。通常一個(gè)國(guó)際象棋局面都有35個(gè)左右的合理著法，所以用最小-最大搜索來搜索一層深度，就有35個(gè)局面要檢查，如果用這個(gè)函數(shù)來搜索兩層，就有35²個(gè)局面要搜索。這就已經(jīng)上千了，看上去還不怎樣，但是數(shù)字增長(zhǎng)得非常迅速，例如六層的搜索就接近是二十億，而十層的搜索就超過兩千萬(wàn)億了。

　　要想通過檢查搜索樹的前面幾層，并且在葉子結(jié)點(diǎn)上用啟發(fā)式的評(píng)價(jià)，那么做盡可能深的搜索是很重要的。最小-最大搜索無法做到很深的搜索，因?yàn)橛行У姆种σ蜃訉?shí)在太大了。

• 【要說明Alpha-Beta搜索的結(jié)點(diǎn)數(shù)是死辦法(即不用Alpha-Beta搜索的辦法)的平方根的兩倍那么多，可以分別計(jì)算搜索樹中兩種類型的結(jié)點(diǎn)——Alpha結(jié)點(diǎn)和Beta結(jié)點(diǎn)。
• 　　Alpha-Beta搜索是完全搜索，如果某個(gè)結(jié)點(diǎn)是完全搜索的，那么這個(gè)結(jié)點(diǎn)稱為Alpha結(jié)點(diǎn)，顯然根結(jié)點(diǎn)是Alpha結(jié)點(diǎn)。那么Alpha結(jié)點(diǎn)的分枝又是什么呢？至少有一個(gè)Alpha結(jié)點(diǎn)，這是肯定的，最好的情況下，剩余的結(jié)點(diǎn)都可以產(chǎn)生截?cái)?#xff0c;這些結(jié)點(diǎn)稱為Beta結(jié)點(diǎn)。Beta結(jié)點(diǎn)有個(gè)特點(diǎn)，只要它的分枝中有一個(gè)Alpha結(jié)點(diǎn)產(chǎn)生作用，那么剩下的結(jié)點(diǎn)就沒有搜索的必要了，我們還是取最好的情況，分枝中只有一個(gè)Alpha結(jié)點(diǎn)。
• 　　那么如何計(jì)算Alpha結(jié)點(diǎn)的個(gè)數(shù)呢？一個(gè)Alpha結(jié)點(diǎn)下面有b - 1個(gè)Beta結(jié)點(diǎn)，每個(gè)Beta結(jié)點(diǎn)下面又有1個(gè)Alpha結(jié)點(diǎn)，這樣深度每增加了兩層結(jié)點(diǎn)數(shù)才擴(kuò)大b倍，因此總的Alpha結(jié)點(diǎn)數(shù)就是b^n/2。同樣道理，Beta結(jié)點(diǎn)也這么計(jì)算，得到的結(jié)果也是b^n/2，因此總結(jié)點(diǎn)數(shù)就是2b^n/2。】　
• 口袋的例子
• 　
• 　　幸運(yùn)的是我們有辦法來減小分枝因子，這個(gè)辦法非常可靠，實(shí)際上這樣做絕對(duì)沒有壞處，純粹是個(gè)有益的辦法。這個(gè)方法是建立在一個(gè)思想上的，如果你已經(jīng)有一個(gè)不太壞的選擇了，那么當(dāng)你要作別的選擇并知道它不會(huì)更好時(shí)，你沒有必要確切地知道它有多壞。有了最好的選擇，任何不比它更好的選擇就是足夠壞的，因此你可以撇開它而不需要完全了解它。只要你能證明它不比最好的選擇更好，你就可以完全拋棄它。
• 　　你可能仍舊不明白，那么我就舉個(gè)例子。比如你的死敵面前有很多口袋，他和你打賭賭輸了，因此他必須從中給你一樣?xùn)|西，而挑選規(guī)則卻非常奇怪：
• 　　每個(gè)口袋里有幾件物品，你能取其中的一件，你來挑這件物品所在的口袋，而他來挑這個(gè)口袋里的物品。你要趕緊挑出口袋并離開，因?yàn)槟悴辉敢庖恢弊鲈谀抢锓诖屇愕乃罃扯⒅恪?/li>
• 　　假設(shè)你一次只能找一只口袋，在找口袋時(shí)一次只能從里面摸出一樣?xùn)|西。
• 　　很顯然，當(dāng)你挑出口袋時(shí)，你的死敵會(huì)把口袋里最糟糕的物品給你，因此你的目標(biāo)是挑出“諸多最糟的物品當(dāng)中是最好的”那個(gè)口袋。
• 　　你很容易把最小-最大原理運(yùn)用到這個(gè)問題上。你是最大一方棋手，你將挑出最好的口袋。而你的死敵是最小一方棋手，他將挑出最好的口袋里盡可能差的物品。運(yùn)用最小-最大原理，你需要做的就是挑一個(gè)有“最好的最差的”物品的口袋。
• 　　假設(shè)你可以估計(jì)口袋里每個(gè)物品的準(zhǔn)確價(jià)值的話，最小-最大原理可以讓你作出正確的選擇。我們討論的話題中，準(zhǔn)確評(píng)價(jià)并不重要，因?yàn)樗钚?span style="font-family:Times New Roman">-最大或Alpha-Beta的工作原理沒有關(guān)系。現(xiàn)在我們假設(shè)你可以正確地評(píng)價(jià)物品。
• 　　最小-最大原理剛才討論過，它的問題是效率太低。你必須看每個(gè)口袋里的每件物品，這就需要花很多時(shí)間。
• 　　那么怎樣才能做得比最小-最大更高效呢？
• 　　我們從第一個(gè)口袋開始，看每一件物品，并對(duì)口袋作出評(píng)價(jià)。比方說口袋里有一只花生黃油三明治和一輛新汽車的鑰匙。你知道三明治更糟，因此如果你挑了這只口袋就會(huì)得到三明治。事實(shí)上只要我們假設(shè)對(duì)手也會(huì)跟我們一樣正確評(píng)價(jià)物品，那么口袋里的汽車鑰匙就是無關(guān)緊要的了。
• 　　現(xiàn)在你開始翻第二個(gè)口袋，這次你采取的方案就和最小-最大方案不同了。你每次看一件物品，并跟你能得到的最好的那件物品(三明治)去比較。只要物品比三明治更好，那么你就按照最小-最大方案來辦——去找最糟的，或許最糟的要比三明治更好，那么你就可以挑這個(gè)口袋，它比裝有三明治的那個(gè)口袋好。
• 　　比方這個(gè)口袋里的第一件物品是一張20美元的鈔票，它比三明治好。如果包里其他東西都沒比這個(gè)更糟了，那么如果你選了這個(gè)口袋，它就是對(duì)手必須給你的物品，這個(gè)口袋就成了你的選擇。
• 　　這個(gè)口袋里的下一件物品是六合裝的流行唱片。你認(rèn)為它比三明治好，但比20美元差，那么這個(gè)口袋仍舊可以選擇。再下一件物品是一條爛魚，這回比三明治差了。于是你就說“不謝了”，把口袋放回去，不再考慮它了。
• 　　無論口袋里還有什么東西，或許還有另一輛汽車的鑰匙，也沒有用了，因?yàn)槟銜?huì)得到那條爛魚。或許還有比爛魚更糟的東西(那么你看著辦吧)。無論如何爛魚已經(jīng)夠糟的了，而你知道挑那個(gè)有三明治的口袋肯定會(huì)更好。
• 　
• 算法
• 　
• 　　Alpha-Beta就是這么工作的，并且只能用遞歸來實(shí)現(xiàn)。稍后我們?cè)賮碚勛钚∫环降牟呗?#xff0c;我希望這樣可以更明白些。
• 　　這個(gè)思想是在搜索中傳遞兩個(gè)值，第一個(gè)值是Alpha，即搜索到的最好值，任何比它更小的值就沒用了，因?yàn)椴呗跃褪侵?span style="font-family:Times New Roman">Alpha的值，任何小于或等于Alpha的值都不會(huì)有所提高。
• 　　第二個(gè)值是Beta，即對(duì)于對(duì)手來說最壞的值。這是對(duì)手所能承受的最壞的結(jié)果，因?yàn)槲覀冎涝趯?duì)手看來，他總是會(huì)找到一個(gè)對(duì)策不比Beta更壞的。如果搜索過程中返回Beta或比Beta更好的值，那就夠好的了，走棋的一方就沒有機(jī)會(huì)使用這種策略了。
• 　　在搜索著法時(shí)，每個(gè)搜索過的著法都返回跟Alpha和Beta有關(guān)的值，它們之間的關(guān)系非常重要，或許意味著搜索可以停止并返回。
• 　　如果某個(gè)著法的結(jié)果小于或等于Alpha，那么它就是很差的著法，因此可以拋棄。因?yàn)槲仪懊嬲f過，在這個(gè)策略中，局面對(duì)走棋的一方來說是以Alpha為評(píng)價(jià)的。
• 　　如果某個(gè)著法的結(jié)果大于或等于Beta，那么整個(gè)結(jié)點(diǎn)就作廢了，因?yàn)閷?duì)手不希望走到這個(gè)局面，而它有別的著法可以避免到達(dá)這個(gè)局面。因此如果我們找到的評(píng)價(jià)大于或等于Beta，就證明了這個(gè)結(jié)點(diǎn)是不會(huì)發(fā)生的，因此剩下的合理著法沒有必要再搜索。
• 　　如果某個(gè)著法的結(jié)果大于Alpha但小于Beta，那么這個(gè)著法就是走棋一方可以考慮走的，除非以后有所變化。因此Alpha會(huì)不斷增加以反映新的情況。有時(shí)候可能一個(gè)合理著法也不超過Alpha，這在實(shí)戰(zhàn)中是經(jīng)常發(fā)生的，此時(shí)這種局面是不予考慮的，因此為了避免這樣的局面，我們必須在博弈樹的上一個(gè)層局面選擇另外一個(gè)著法。
• 　　在第二個(gè)口袋里找到爛魚就相當(dāng)于超過了Beta，如果口袋里沒有爛魚，那么考慮六盒裝流行唱片的口袋會(huì)比三明治的口袋好，這就相當(dāng)于超過了Alpha(在上一層)。算法如下，醒目的部分是在最小-最大算法上改過的：
• 　
• int AlphaBeta(int depth, int alpha, int beta) {
• 　if (depth == 0) {
• 　　return Evaluate();
• 　}
• 　GenerateLegalMoves();
• 　while (MovesLeft()) {
• 　　MakeNextMove();
• 　　val = -AlphaBeta(depth - 1, -beta, -alpha);
• 　　UnmakeMove();
• 　　if (val >= beta) {
• 　　　return beta;
• 　　}
• 　　if (val > alpha) {
• 　　　alpha = val;
• 　　}
• 　}
• 　return alpha;
• }
• 　
• 　　把醒目的部分去掉，剩下的就是最小-最大函數(shù)。可以看出現(xiàn)在的算法沒有太多的改變。
• 　　這個(gè)函數(shù)需要傳遞的參數(shù)有：需要搜索的深度，負(fù)無窮大即Alpha，以及正無窮大即Beta：
• 　
• val = AlphaBeta(5, -INFINITY, INFINITY);
• 　
• 　　這樣就完成了5層的搜索。我在寫最小-最大函數(shù)時(shí)，用了一個(gè)訣竅來避免用了“Min”還用“Max”函數(shù)。在那個(gè)算法中，我從遞歸中返回時(shí)簡(jiǎn)單地對(duì)返回值取了負(fù)數(shù)。這樣就使函數(shù)值在每一次遞歸中改變?cè)u(píng)價(jià)的角度，以反映雙方棋手的交替著子，并且它們的目標(biāo)是對(duì)立的。
• 　　在Alpha-Beta函數(shù)中我們做了同樣的處理。唯一使算法感到復(fù)雜的是，Alpha和Beta是不斷互換的。當(dāng)函數(shù)遞歸時(shí)，Alpha和Beta不但取負(fù)數(shù)而且位置交換了，這就使得情況比口袋的例子復(fù)雜，但是可以證明它只是比最小-最大算法更好而已。
• 　　最終出現(xiàn)的情況是，在搜索樹的很多地方，Beta是很容易超過的，因此很多工作都免去了。
• 　
• 可能的弱點(diǎn)
• 　
• 　　這個(gè)算法嚴(yán)重依賴于著法的尋找順序。如果你總是先去搜索最壞的著法，那么Beta截?cái)嗑筒粫?huì)發(fā)生，因此該算法就如同最小-最大一樣，效率非常低。該算法最終會(huì)找遍整個(gè)博弈樹，就像最小-最大算法一樣。
• 　　如果程序總是能挑最好的著法來首先搜索，那么數(shù)學(xué)上有效分枝因子就接近于實(shí)際分枝因子的平方根。這是Alpha-Beta算法可能達(dá)到的最好的情況。
• 　　由于國(guó)際象棋的分枝因子在35左右，這就意味著Alpha-Beta算法能使國(guó)際象棋搜索樹的分枝因子變成6。
• 　　這是很大的改進(jìn)，在搜索結(jié)點(diǎn)數(shù)一樣的情況下，可以使你的搜索深度達(dá)到原來的兩倍。這就是為什么使用Alpha-Beta搜索時(shí)，著法順序至關(guān)重要的原因。
• 　
• 　　原文：http://www.seanet.com/~brucemo/topics/alphabeta.htm
• 　　譯者：象棋百科全書網(wǎng) (webmaster@xqbase.com)
• 　　類型：全譯

總結(jié)

以上是生活随笔為你收集整理的对弈程序基本技术----Alpha-Beta搜索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。