Alpha-Beta 剪枝是什么？下棋程序跳过不必看的走法

Alpha-Beta 剪枝（Alpha-beta Pruning）是一种用于下棋等双人对弈游戏的搜索优化算法。它在极小极大搜索的基础上，跳过那些肯定不会影响最终决策的走法分支，从而大幅减少需要考察的局面数量，但得到的结果与完整的搜索完全相同。它是传统棋类程序的核心技术之一。

从极小极大搜索说起

在国际象棋、中国象棋这样的双人对弈游戏中，双方轮流行动，一方的得利就是另一方的损失。计算机下棋的基本思路是：向前推演若干步，把所有可能的走法展开成一棵“博弈树”，树的每个节点是一个局面，每条边是一步走法；在推演到一定深度后，用一个评估函数给局面打分，比如根据双方剩余的棋子和位置估计谁占优。然后从下往上推算：轮到自己走的时候，选择对自己最有利、分数最高的走法，这叫极大层；轮到对手走的时候，假设对手会选择对自己最不利、分数最低的走法，这叫极小层。这就是极小极大算法，它的思想可以追溯到冯·诺依曼的博弈论和香农在 1950 年关于计算机下棋的论文。

问题在于，博弈树的规模增长得极快。国际象棋每一步平均约有 35 种可能的走法，向前看 10 步，局面的数量就是 35 的 10 次方，约为 2.7 乘以 10 的 15 次方，逐一搜索是不可能的。

剪枝的思路

Alpha-Beta 剪枝的关键在于发现：很多分支根本不需要看完就能判断它们不会被选中。举个例子：你在考虑两种走法。第一种走法，经过仔细推演，你知道无论对手怎么应对，你至少能得到 5 分。接着你考虑第二种走法，在推演对手的应对时，发现对手有一种应对能让你只得 2 分。这时你就不需要再继续考察第二种走法下对手的其他应对了：既然对手至少有一种办法能把你压到 2 分以下，而你已经有一种能保证 5 分的走法，你肯定不会选第二种走法。它剩下的那些分支可以直接“剪掉”。

算法用两个值来记录这些信息：α 表示到目前为止，己方在当前路径上至少能保证得到的分数；β 表示对手至多允许己方得到的分数。搜索过程中不断地更新这两个值，一旦发现某个节点的 α 大于等于 β，就说明这个分支不可能影响最终的结果，立即停止对它的搜索。这一思想在 20 世纪 50 年代由多位研究者独立提出，Donald Knuth 和 Ronald Moore 在 1975 年对它进行了严格的分析。

效果有多好

剪枝的效果很大程度上取决于考察走法的顺序：如果能先考察最好的走法，后面的分支就能被尽早地剪掉。在最理想的情况下，Alpha-Beta 剪枝需要考察的节点数量大约只有原来的平方根，这意味着在同样的时间内，搜索的深度可以增加大约一倍。因此，下棋程序会使用各种技巧来改善走法的排序，比如优先考察吃子的走法、利用上一轮浅层搜索的结果，再结合迭代加深、置换表等技术。1997 年，IBM 的“深蓝”击败了国际象棋世界冠军卡斯帕罗夫，它的核心就是在专用的硬件上进行大规模的 Alpha-Beta 搜索。

后来的发展

对于围棋这样每一步可选的走法多达数百种、局面又很难评估的游戏，传统的 Alpha-Beta 搜索效果很差。2016 年击败李世石的 AlphaGo 改用了蒙特卡罗树搜索，并用深度神经网络来评估局面和选择走法。不过，在国际象棋领域，基于 Alpha-Beta 搜索的程序，比如 Stockfish，在引入了高效的神经网络评估函数之后，至今仍然是棋力很高的国际象棋程序。