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的艾伦·科托克。Alexander Brudno独立发现了alpha-beta算法，并在1963年发布成果。Donald Knuth和Ronald W. Moore在1975年优化了算法，Judea Pearl在1982年证明了其最优性。

## 对原版极小化极大算法的改进

Alpha-beta的优点是减少搜索树的分枝，将搜索时间用在“更有希望”的子树上，继而提升搜索深度。该算法和极小化极大算法一样，都是分支限界类算法。若节点搜索顺序达到最优化或近似最优化（将最佳选择排在各节点首位），则同样时间内搜索深度可达极小化极大算法的两倍多。

在（平均或恒定）分枝因子为b，搜索深度为d层的情况下，要评估的最大（即招法排序最差时）叶节点数目为O(b*b*...*b) = O(bd)——即和简单极小化极大搜索一样。若招法排序最优（即始终优先搜索最佳招法），则需要评估的最大叶节点数目按层数奇偶性，分别约为O(b*1*b*1*...*b)和O(b*1*b*1*...*1)（或O(bd/2) = O(√bd)）。其中层数为偶数时，搜索因子相当于减少了其平方根，等于能以同深度搜索两次。b*1*b*1*...意义为，对第一名玩家必须搜索全部招法找到最佳招式，但对于它们，只用将第二名玩家的最佳招法截断——alpha-beta确保无需考虑第二名玩家的其他招法。但因节点生成顺序随机，实际需要评估的节点平均约为O(b3d/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, -[[Infinity|∞]], +[[Infinity|∞]], TRUE) ''// origin = 初始節點''
```

在这个有限可靠性的alpha-beta中，当v超出调用参数α和β构成的集合时（v β），alphabeta函数返回值v。而与此相对，强化的有限可靠性alpha-beta限制函数返回在α与β包括范围中的值。

## 参考文献

- Judea Pearl, Heuristics, Addison-Wesley, 1984

## 外部链接

- 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