基本介紹
- 中文名：AlphaBeta剪枝算法
- 外文名：AlphaBeta pruning algorithm
- 實現：遞歸
- 最佳化：對Minimax方法最佳化
前提假設,內容,代碼,缺點,
前提假設
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，這在實戰中是經常發生的，此時這種局面是不予考慮的，因此為了避免這樣的局面，我們必須在博弈樹的上一個層局面選擇另外一個著法。
代碼
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;} 
