基本介紹
- 中文名：Alpha-beta剪枝
- 外文名：Alpha-beta pruning
- 類型：一種搜尋算法
歷史,對原版極小化極大算法的改進,偽代碼,
歷史
Allen Newell和Herbert A. Simon在1958年，使用了John McCarthy所謂的“近似”alpha-beta算法，此算法當時“應已重新改造過多次”。Arthur Samuel有一個早期版本，同時Richards、Hart、Levine和/或Edwards在美國分別獨立發現了alpha-beta。McCarthy在1956年達特默思會議上提出了相似理念，並在1961年建議給他的一群學生，其中包括MIT的Alan Kotok。Alexander Brudno獨立發現了alpha-beta算法，並在1963年發布成果。Donald Knuth和Ronald W. Moore在1975年最佳化了算法，Judea Pearl在1982年證明了其最優性。
對原版極小化極大算法的改進
Alpha-beta的優點是減少搜尋樹的分枝，將搜尋時間用在“更有希望”的子樹上，繼而提升搜尋深度。該算法和極小化極大算法一樣，都是分支限界類算法。若節點搜尋順序達到最佳最佳化或近似最佳最佳化（將最佳選擇排在各節點首位），則同樣時間內搜尋深度可達極小化極大算法的兩倍多。
在（平均或恆定）分枝因子為b，搜尋深度為d層的情況下，要評估的最大（即招法排序最差時）葉節點數目為O(b*b*...*b) =O(b)——即和簡單極小化極大搜尋一樣。若招法排序最優（即始終優先搜尋最佳招法），則需要評估的最大葉節點數目按層數奇偶性，分別約為O(b*1*b*1*...*b)和O(b*1*b*1*...*1)（或O(b) =O(√b)）。其中層數為偶數時，搜尋因子相當於減少了其平方根，等於能以同深度搜尋兩次。b*1*b*1*...意義為，對第一名玩家必須搜尋全部招法找到最佳招式，但對於它們，只用將第二名玩家的最佳招法截斷——alpha-beta確保無需考慮第二名玩家的其他招法。但因節點生成順序隨機，實際需要評估的節點平均約為O(b)。
一般在alpha-beta中，子樹會由先手方優勢或後手方優勢暫時占據主導。若招式排序錯誤，這一優勢會多次切換，每次讓效率下降。隨著層數深入，局面數量會呈指數性增長，因此排序早期招式價值很大。儘管改善任意深度的排序，都以能指數性減少總搜尋局面，但排序臨近根節點深度的全部局面相對經濟。在實踐中，招法排序常由早期、小型搜尋決定，如通過疊代加深。
算法使用兩個值alpha和beta，分別代表大分玩家放心的最高分，以及小分玩家放心的最低分。alpha和beta的初始值分別為正負無窮大，即雙玩家都以可能的最低分開始遊戲。在選擇某節點的特定分枝後，可能發生小分玩家放心的最小分小於大分玩家放心的最大分（beta <= alpha）。這種情況下，父節點不應選擇這個節點，否則父節點分數會降低，因此該分枝的其他節點沒有必要繼續探索。
偽代碼
下面為一有限可靠性版本的Alpha-beta剪枝的偽代碼：
function alphabeta(node, depth, α, β, maximizingPlayer) // node = 節點，depth = 深度，maximizingPlayer = 大分玩家 if depth = 0 or node是終端節點 return 節點的啟發值 if maximizingPlayer v := -∞ for 每個子節點 v := max(v, alphabeta(child, depth - 1, α, β, FALSE)) // child = 子節點 α := max(α, v) if β ≤ α break // β裁剪 return v else v := ∞ for each 每個子節點 v := min(v, alphabeta(child, depth - 1, α, β, TRUE)) β := min(β, v) if β ≤ α break // α裁剪 return v (* 初始調用 *) alphabeta(origin, depth, -∞, +∞, TRUE) // origin = 初始節點
在這個有限可靠性的alpha-beta中，當v超出調用參數α和β構成的集合時（v < α或v > β），alphabeta函式返回值v。而與此相對，強化的有限可靠性alpha-beta限制函式返回在α與β包括範圍中的值。
