Alpha–beta剪枝是一种树搜索算法，旨在减少极小化极大算法在其搜索树中评估的节点数量。它是一种对抗性搜索算法，常用于机器玩双人组合游戏，如井字棋、国际象棋和四子棋。该算法在发现至少一种可能性证明某一步棋比先前检查过的棋步更差时，便停止评估该棋步，因此无需进一步评估此类棋步。当应用于标准极小化极大树时，它返回与极小化极大算法相同的棋步，但会剪除那些不可能影响最终决策的分支。
该算法是人工智能中分支定界方法的经典例子，支撑了许多游戏程序，包括早期国际象棋计算机和现代引擎。其效率提升允许在相同计算预算内进行更深入的搜索，使其成为对抗性搜索中的基础技术。
历史
约翰·麦卡锡在1956年的达特茅斯研讨会上遇到了正在编写国际象棋程序的IBM的亚历克斯·伯恩斯坦。麦卡锡发明了alpha–beta搜索并推荐给伯恩斯坦，但伯恩斯坦“不以为然”。艾伦·纽厄尔和赫伯特·A·西蒙在1958年使用了麦卡锡所称的“近似方法”，他们写道alpha–beta“似乎已被多次重新发明”。亚瑟·塞缪尔有一个用于跳棋模拟的早期版本。理查兹、蒂莫西·哈特、迈克尔·莱文和/或丹尼尔·爱德华兹也在美国独立发明了alpha–beta。麦卡锡在达特茅斯研讨会期间提出了类似想法，并建议给他的一群学生，包括1961年在麻省理工学院的艾伦·科托克。亚历山大·布鲁德诺独立构思了alpha–beta算法，并于1963年发表了其结果。唐纳德·克努斯和罗纳德·W·摩尔在1975年完善了该算法。朱迪亚·珀尔在两篇论文中证明了其在随机分配叶值树上的期望运行时间方面的最优性。迈克尔·萨克斯和阿维·维格德森在1986年证明了随机版本alpha–beta的最优性。
核心思想
游戏树可以表示许多双人零和游戏，如国际象棋、跳棋和黑白棋。树中的每个节点代表游戏中的一种可能局面。分支的每个终端节点（结果）被分配一个数值分数，该分数决定了对下一步移动玩家而言该结果的价值。
该算法维护两个值，alpha和beta，分别代表最大化玩家确保的最小分数和最小化玩家确保的最大分数。最初，alpha为负无穷大，beta为正无穷大，意味着双方玩家都从最差可能分数开始。每当最小化玩家（“beta”玩家）确保的最大分数变得小于最大化玩家（“alpha”玩家）确保的最小分数（即beta < alpha）时，最大化玩家无需考虑此节点的进一步后代，因为在实际游戏中永远不会到达这些节点。
用一个现实例子来说明，假设某人正在下国际象棋，轮到他走棋。棋步“A”将改善玩家的位置。玩家继续寻找棋步以确保没有错过更好的选择。棋步“B”也是一个好棋步，但玩家随后意识到这将允许对手在两步内强制将死。因此，走棋步B的其他结果不再需要考虑，因为对手可以强制获胜。对手在棋步B后能强制达到的最大分数是负无穷大：对玩家来说是一种失败。这小于先前找到的最小位置；棋步A不会导致两步内强制失败。
对朴素极小化极大的改进
alpha–beta剪枝的好处在于可以消除搜索树的分支。这样，搜索时间可以限制在“更有前景”的子树中，并在相同时间内进行更深入的搜索。与其前身一样，它属于分支定界类算法。如果节点以最优或接近最优的顺序评估（每一步移动方的最佳选择排在首位），优化将有效深度减少到简单极小化极大的一半多一点。
对于（平均或恒定）分支因子b和搜索深度d层，评估的叶节点位置最大数量（当移动排序最差时）为O(b^d)，，与简单极小化极大搜索相同。如果搜索的移动排序是最优的（意味着最佳棋步总是首先搜索），则评估的叶节点位置数量对于奇数深度约为O(b 1 b 1 ... b)，对于偶数深度约为O(b 1 b 1 ... 1)，或O(b^(d/2)) = O(sqrt(b^d))。在后一种情况下，其中搜索的层数为偶数，有效分支因子减少到其平方根，或者等效地，搜索可以在相同计算量下深入两倍。b1b1...的解释是，必须研究第一个玩家的所有棋步以找到最佳棋步，但对于每个棋步，只需要第二个玩家的最佳棋步来反驳除第一个（和最佳）第一个玩家棋步之外的所有棋步，，alpha–beta确保无需考虑第二个玩家的其他棋步。
当节点以随机顺序考虑时（即算法随机化），渐近地，在具有二元叶值的均匀树中，预期评估节点数为Theta(((b-1+sqrt(b^2+14b+1))/4)^d)。对于相同的树，当叶值彼此独立分配且零和一均等可能时，预期评估节点数为Theta((b/2)^d)。
实现考虑
在实践中，alpha–beta剪枝通常与迭代加深一起实现，其中搜索深度逐步增加。移动排序对于实现接近最优性能至关重要；常见启发式包括首先检查吃子、使用杀手棋步和采用置换表。该算法可以通过诸如静止搜索等技术扩展以避免地平线效应，并构成更高级算法（如主变例搜索和negascout）的基础。Alpha–beta剪枝广泛用于国际象棋程序，包括在国际象棋计算机系统等平台上运行的程序，并已集成到各种游戏AI框架中。
遗产与影响
Alpha–beta剪枝对人工智能和博弈论产生了持久影响。它是早期国际象棋程序的关键组成部分，在现代游戏引擎中仍然相关，尤其是对于具有大分支因子的游戏。该算法的效率改进已被广泛研究，其原理影响了搜索和优化的其他领域。尽管机器学习和深度学习等新技术已改变了游戏AI，但alpha–beta剪枝仍然是对抗性搜索中的基本工具，其历史发展突显了AI研究的协作和迭代性质。