Alpha-beta剪枝

**Alpha-beta 剪枝**是一種搜尋演算法，用以減少極小化極大演算法（Minimax 演算法）搜尋樹的節點數。這是一種對抗性搜尋演算法，主要應用於機器遊玩的二人遊戲（如井字棋、象棋、圍棋）。當演算法評估出某策略的後續走法比之前策略的還差時，就會停止計算該策略的後續發展。該演算法和極小化極大演算法所得結論相同，但剪去了不影響最終決定的分枝。

## 歷史

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_d)—— 即和簡單極小化極大搜尋一樣。若招法排序最佳（即始終優先搜尋最佳招法），則需要評估的最大葉節點數目按層數奇偶性，分別約為 _O_(_b_\*1\*_b_\*1\*...\*_b_) 和 _O_(_b_\*1\*_b_\*1\*...\*1)（或 _O_(_b_d/2) = _O_(√_b_d)）。其中層數為偶數時，搜尋因子相當於減少了其平方根，等於能以同深度搜尋兩次。_b_\*1\*_b_\*1\*... 意義為，對第一名玩家必須搜尋全部招法找到最佳招式，但對於它們，只用將第二名玩家的最佳招法截斷 ——alpha-beta 確保無需考慮第二名玩家的其他招法。但因節點生成順序隨機，實際需要評估的節點平均約為 _O_(_b_3_d_/4)。

一般在 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** 每个子節點
             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 限制函式返回在 α 與 β 包括範圍中的值。

## 參考文獻

* George T. Heineman, Gary Pollice, and Stanley Selkow. Chapter 7: Path Finding in AI. Algorithms in a Nutshell. Oreilly Media. 2008: 217–223. ISBN 978-0-596-51624-6.
* Judea Pearl, _Heuristics_, Addison-Wesley, 1984
* John P. Fishburn. Appendix A: Some Optimizations of α-β Search. Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis). UMI Research Press. 1984: 107-111. ISBN 0-8357-1527-2.

## 外部連結

* http://www.emunix.emich.edu/~evett/AI/AlphaBeta\_movie/sld001.htm（頁面存檔備份，存於網際網路檔案館）
* http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L1\_5B\_McCullough\_Melnyk/（頁面存檔備份，存於網際網路檔案館）
* http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L2\_5B\_Lima\_Neitz/search.html（頁面存檔備份，存於網際網路檔案館）
* https://web.archive.org/web/20021223103359/http://www.maths.nott.ac.uk/personal/anw/G13GAM/alphabet.html
* https://web.archive.org/web/20041123061044/http://chess.verhelst.org/search.html
* http://www.frayn.net/beowulf/index.html（頁面存檔備份，存於網際網路檔案館）
* http://hal.inria.fr/docs/00/12/15/16/PDF/RR-6062.pdf（頁面存檔備份，存於網際網路檔案館）
* Minimax (with or without alpha–beta pruning) algorithm visualization - game tree solving (Java Applet), for balance or off-balance trees（頁面存檔備份，存於網際網路檔案館）
* Demonstration/animation of minimax game search algorithm with alpha–beta pruning (using html5, canvas, javascript, css)（頁面存檔備份，存於網際網路檔案館）
* Java implementation used in a Checkers Game（頁面存檔備份，存於網際網路檔案館）