从 Minimax 到 alpha-beta 剪枝

双人零和博弈的推演可以摊成一棵博弈树：节点是局面，孩子是走一步之后的局面，我方走的层取最大值，对手走的层取最小值。Minimax 展开整棵树，alpha-beta 在同一棵树上得到同一个根值，却只考察其中一部分。本页用一棵深度 3、每层 2 个孩子的固定小树量出这个差额，并检验它对搜索次序的依赖。

1 · 博弈树与 Minimax 回溯

轮到我方走的是 MAX 层，在孩子里取最大；轮到对手走的是 MIN 层，取最小。两层交替到底，叶子的取值由 evaluate() 给出，越大对我方越有利。Minimax 递归到叶子再自下而上回溯，每个节点的值表示「双方都走最优时这个局面值多少」。各节点取值时选中的孩子首尾相连，即 principal variation，也就是双方都最优时棋局的实际走法。

这棵树深度 3、每层 2 个孩子，已有 $2^3 = 8$ 个叶子。实战棋类的分支数 $b$ 为几十、深度 $d$ 十几，$b^d$ 规模无法枚举。但其中大量叶子对根值没有贡献：理性的对手不会让棋局走进那些分支。§2 给出识别它们的判据。

2 · α/β 窗口与 cutoff

alpha-beta 在 Minimax 之上只加一个沿途下传的区间。

判据的成立性可以就地论证。MIN 节点的值随孩子的考察只降不升，一旦降到 $\le \alpha$，而我方在别处已能保证 $\alpha$，我方不会选择走进这个节点，它剩下的孩子对根值没有影响，这种情形称为 α-cutoff。MAX 节点对称：值只升不降，一旦 $\ge \beta$，对手不会让棋局走过来，剩余孩子同样剪掉，称为 β-cutoff。被剪的子树只是未被计算，根值与 Minimax 完全一致。

图 2-1 的树上 Minimax 评估 8 个叶子，alpha-beta 评估 5 个，根值同为 5。两处剪枝分别是：右上的 MAX 节点看到 6 后 $\alpha = 6 \ge \beta = 5$，触发 β-cutoff，旁边的 9 未被计算；右下整棵 $\lbrace 0, -1 \rbrace$ 子树在 $\alpha = 5 \ge \beta = 2$ 时被 α-cutoff 整片剪掉。

那个 9 之所以无关紧要：它的父节点是 MIN 节点，已经取到 5，另一个孩子无论多大，MIN 都只会取更小的，改变不了「该 MIN 节点 $\le 5$」这个结论；而我方在左边已确定 5。被剪掉的是已证明无望的枝，不是可能更优的枝。

3 · move ordering 对剪枝量的影响

剪枝的前提是手上已有一个够紧的 $\alpha$ 或 $\beta$ 用来挡住后面的枝，所以考察次序直接决定剪掉多少。先搜到好招，窗口尽早收紧，后续大片子树一撞即剪；先搜到差招，窗口迟迟收不紧，退化回朴素 Minimax。安排这一次序的环节称为 move ordering。

穷举结果：评估 5 个叶子的排列 4032 种，6 个 11648 种，7 个 11072 种，8 个 13568 种，均值 6.85 个。达到下界 5 的只占 10%，而 33.6% 的排列评估满 8 个叶子，一片也没剪掉。

下界的表达式是 $b^{\lceil d/2 \rceil} + b^{\lfloor d/2 \rfloor} - 1$，本例为 $4 + 2 - 1 = 5$。$d$ 较大时它约等于 $\sqrt{b^d} = b^{d/2}$，相当于在同等评估预算下把有效搜索深度翻倍，或把分支因子从 $b$ 降到 $\sqrt b$。

实战引擎为排序投入了专门的机制：iterative deepening 先搜浅一层，用上一层的结果给这一层排序；transposition table 缓存已算过的局面，优先试那里记下的走法；killer move 与 history heuristic 优先试在别处频繁触发 cutoff 的走法；静态评估排序把吃子、将军这类大概率的好招排到前面。它们都不改变最终结果，只改变考察次序。

4 · 搜索与评估器的分工

神经网络与树搜索承担的是不同的工作：网络做模式判断，即泛化与难以显式表述的局面评估；搜索做推演，即在给定评估器下精确且可验证地选出最优走法。最强的博弈引擎把两者组合起来，被替换掉的是手写的 evaluate()，alpha-beta 与 MCTS 这层搜索框架保留。

4.1 · 等评估预算下的可达深度

§3 给出的下界意味着：在同样的评估次数预算下，alpha-beta 能搜到约两倍的深度。

4.2 · Stockfish 与 AlphaZero 的对照

表中的搜索速度取自 AlphaZero 论文（arXiv:1712.01815）的对局配置，当时的 Stockfish 用的还是手写评估。AlphaZero 每秒只看 Stockfish 约千分之一的局面，靠先验把搜索集中到少数分支上；两者的评估器不同，搜索层都保留。Rich Sutton 在 The Bitter Lesson（2019）里把这一点归纳为：七十年里能随算力持续变强的方法只有 search 与 learning 两类，二者并列。AlphaZero 去掉全部人类棋谱知识、只留自我对弈学习与树搜索仍然更强，是这个论断的例子。