AlphaBeta剪枝算法

AlphaBeta剪枝算法

AlphaBeta剪枝算法是一個搜尋算法旨在減少在其搜尋樹中,被極大極小算法評估的節點數。 這是一個常用人機遊戲對抗的搜尋算法。它的基本思想是根據上一層已經得到的當前最優結果,決定目前的搜尋是否要繼續下去。

前提假設

AlphaBeta剪枝算法是對Minimax方法的最佳化,它們產生的結果是完全相同的,只不過運行效率不一樣。

這種方法的前提假設與Minimax也是一樣的:

1)雙方都按自己認為的最佳著法行棋。

2)對給定的盤面用一個分值來評估,這個評估值永遠是從一方(搜尋程式)來評價的,紅方有利時給一個正數,黑方有利時給一個負數。(如果紅方有利時返回正數,當輪到黑方走棋時,評估值又轉換到黑方的觀點,如果認為黑方有利,也返回正數,這種評估方法都不適合於常規的算法描述)。

3)從我們的搜尋程式(通常把它稱為Max)看來,分值大的數表示對己方有利,而對於對方Min來說,它會選擇分值小的著法。

內容

Alpha-Beta只能用遞歸來實現。這個思想是在搜尋中傳遞兩個值,第一個值是Alpha,即搜尋到的最好值,任何比它更小的值就沒用了,因為策略就是知道Alpha的值,任何小於或等於Alpha的值都不會有所提高。

第二個值是Beta,即對於對手來說最壞的值。這是對手所能承受的最壞的結果,因為我們知道在對手看來,他總是會找到一個對策不比Beta更壞的。如果搜尋過程中返回Beta或比Beta更好的值,那就夠好的了,走棋的一方就沒有機會使用這種策略了。

在搜尋著法時,每個搜尋過的著法都返回跟Alpha和Beta有關的值,它們之間的關係非常重要,或許意味著搜尋可以停止並返回。

如果某個著法的結果小於或等於Alpha,那么它就是很差的著法,因此可以拋棄。因為我前面說過,在這個策略中,局面對走棋的一方來說是以Alpha為評價的。

如果某個著法的結果大於或等於Beta,那么整個節點就作廢了,因為對手不希望走到這個局面,而它有別的著法可以避免到達這個局面。因此如果我們找到的評價大於或等於Beta,就證明了這個結點是不會發生的,因此剩下的合理著法沒有必要再搜尋。

如果某個著法的結果大於Alpha但小於Beta,那么這個著法就是走棋一方可以考慮走的,除非以後有所變化。因此Alpha會不斷增加以反映新的情況。有時候可能一個合理著法也不超過Alpha,這在實戰中是經常發生的,此時這種局面是不予考慮的,因此為了避免這樣的局面,我們必須在博弈樹的上一個層局面選擇另外一個著法。

代碼

缺點

這個算法嚴重依賴於著法的尋找順序。如果你總是先去搜尋最壞的著法,那么Beta截斷就不會發生,因此該算法就如同最小-最大一樣,效率非常低。該算法最終會找遍整個搜尋樹,就像最小-最大算法一樣。

如果程式總是能挑最好的著法來首先搜尋,那么數學上有效分枝 因子就接近於實際分枝因子的平方根。這是Alpha-Beta算法可能達到的最好的情況。

AlphaBeta剪枝算法 AlphaBeta剪枝算法

這是很大的改進,在搜尋結點數一樣的情況下,可以使你的搜尋深度達到原來的兩倍。這就是為什麼使用Alpha-Beta搜尋時,著法順序至關重要的原因。

熱門詞條

聯絡我們