minimax · α/β cutoff · move ordering

从 Minimax 到 alpha-beta 剪枝

本页把 alpha-beta 拆成四步，每一步都能单步观察博弈树展开、α/β 如何传递、哪片子树被剪：先看 Minimax 把整棵树走完，再看 α / β 窗口与剪枝如何省掉无望子树，然后验证 move ordering 对剪枝效果的决定性影响，最后看它在大模型时代的定位。

1 · 先看 Minimax：把整棵博弈树走完

motivation · 博弈树 + Minimax

双人零和博弈（我赢多少 = 你输多少）可以摊成一棵博弈树：每个节点是一个局面，孩子是「走一步之后」的局面。轮到我方走的是 MAX 层 ▲——在孩子里挑最大；轮到对手走的是 MIN 层 ▽——挑最小（它要害我）。一层 MAX 一层 MIN 交替到底，叶子是 evaluate() 给出的局面分（越大对我方越好）。Minimax = 递归到叶子，再从下往上回溯：每个节点假设双方都走最优，算出「这个局面到底值多少」。

读这棵树：▲ = MAX（我方，取 max）,▽ = MIN（对手，取 min）,□ = 叶子局面分。节点里的数字是它当前已知的回溯值（还没算出时显示 ?）。单步看递归先深入到最左叶子，再逐层把值向上汇报。金色的那条线 = principal variation：双方都最优时，棋实际会怎么走。

问题在于：这棵小树深度才 3、每层 2 个孩子，就有 ${2^3 = 8}$ 个叶子要全部计算。真实棋局分支数 b 几十、深度 d 十几，b^d 规模极大——minimax 全部计算根本算不完。但其中大量叶子的计算并不必要：理性的对手早已把某些局面排除。α / β 窗口与剪枝一节正是省掉这部分。

2 · 核心：α / β 窗口与「无需考察」的剪枝

core · α/β 窗口 + cutoff

alpha-beta 在 minimax 上只加一样东西：一个沿途下传的窗口 $[\alpha , \beta ]$ 。α = 走到这里为止，我方 (MAX) 已经能保证拿到的最高分（下界，只增不减）;β = 对手 (MIN) 已经能保证把我方压到的最低分（上界，只减不增）。规则只有一条——任何节点一旦 α ≥ β，它剩下的孩子直接全剪 (cutoff)。

为什么能这么剪？站在一个 MIN 节点：它的值只会越来越小。如果它已经跌到 $\le \alpha$ ，而 α 是我方在别处已经能保证的分——那我方不会选择走进这个 MIN 节点（这里只会更差），所以它剩下的孩子无需再算（这叫 α-cutoff）。MAX 节点对称：值只增，一旦 $\ge \beta$ ，对手不会让棋走过来，剩余孩子剪掉 (β-cutoff)。关键：被剪的子树只是未被计算，根值不受影响。

**同一棵树，minimax 评估 8 个叶子，alpha-beta 只评估 5 个，根值都是 5。**本例两处剪枝很典型：其一，右上那个 MAX 节点看到 6 就 $\alpha =6 \ge \beta =5$ → β-cutoff，旁边的 9 未被计算；其二，右下整棵 {0, −1} 子树在 $\alpha =5 \ge \beta =2$ 时被 α-cutoff 整片剪掉。省下的都是「对手理性时根本到不了」的局面。

那个 9 为何无关紧要？那是个 MIN 节点（对手选），它已经能取到 5；它的另一个孩子无论多大（哪怕 100）,MIN 也只会取更小的，改变不了「这个 MIN ≤ 5」。而我方在左边已经确定了 5，所以右边这枝再好也无法胜过——计算它没有意义。剪掉的从来不是「可能更优」的枝，只是「已证明无望」的枝。

3 · 顺序决定一切：move ordering 的威力

ordering · b^d → b^(d/2)

剪枝的前提是「已经有一个好的 α 或 β」可用来挡住后面的枝。因此谁先被搜，至关重要——先搜到好招，就能尽早抬高 α / 压低 β，后面大片子树一撞就被剪；先搜到差招，窗口迟迟收不紧，几乎一个也剪不掉、退化回朴素 minimax。同一棵树、同一组 8 个叶子值，仅仅调换排列，评估的叶子数就在 5（最好）~ 8（最差） 之间变化。下面动手验证。

点洗牌随机重排叶子，或套用 最优 / 最差 预设，观察博弈树重新跑 alpha-beta：左侧计分牌的「评估叶子数」会变，被剪的叶子在树上和下方叶子条里标红 (✂)。下方柱状图是穷举全部 8! = 40320 种排列得到的真实分布。

为什么最好情况是「看 5 个」？理论上，排序完美时 alpha-beta 评估的叶子数约 $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$ 。这正是 alpha-beta 能让引擎「同样时间多算一倍深度」的来源。

因此实战引擎竭力「把好招排在前面」：

iterative deepening——先搜浅一层，用上一层的结果给这一层排序；
置换表 (transposition table)——缓存以前算过的局面，优先试那个走法；
killer move / history heuristic——在别处频繁触发 cutoff 的走法，这里也优先试；
静态评估排序——吃子、将军等大概率是好招的走法先搜。

它们都不改变最终结果，只改变搜索顺序——而顺序正是 alpha-beta 剪枝效果的关键。

4 · 在大模型时代仍是搜索骨架

applications · 在大模型时代的定位

一个常见的疑问：深度学习已经很强，alpha-beta 这类「手工算法」还有意义吗？这个问题混淆了两件事。神经网络擅长「模式判断」（模式识别、泛化、难以显式表述的评估），搜索擅长「推演」（精确、可验证、保证最优）。两者不是替代关系，而是互补：最强的博弈 AI 恰恰是「搜索 + 神经网络」的结合——神经网络替换的只是手写的 evaluate(),搜索框架本身 (alpha-beta / MCTS) 被完整保留了下来。

同一个搜索骨架，只是把「评估器」插槽换了内容：

换的永远是插槽里的评估器，不变的是外面那层搜索。

4.1 · 同样的算力，搜索能换来多深

move ordering 一节说明过：排序理想时 alpha-beta 把评估量从 b^d 压到 ≈ b^(d/2)。反过来看——同样的「评估次数」预算，alpha-beta 能搜到大约两倍深度。拖动深度看差距：

4.2 · Stockfish 与 AlphaZero：两套顶级引擎都依赖搜索

维度	Stockfish (alpha-beta)	AlphaZero (MCTS)
搜索方式	alpha-beta + 大量剪枝增强	蒙特卡洛树搜索 MCTS
评估局面靠	NNUE 小神经网络	policy + value 大网络
每步搜索节点	数千万（剪枝狠、单点快）	数万（单点慢、靠先验聚焦）
领域知识	少量人工（排序启发式等）	几乎为零（自我对弈学出）
去掉搜索会怎样	棋力大幅下降	棋力大幅下降

两套顶级引擎在「评估器」上各不相同（手写规则 / NNUE / 大网络），但都以树搜索 + 剪枝为骨架——去掉搜索两者都无法维持棋力。

The Bitter Lesson (Rich Sutton, 2019):AI 七十年反复证明，能随算力持续变强的方法只有两类——search 和 learning。它俩是并列的两根支柱，不是谁取代谁。AlphaZero 删掉全部人类棋谱知识，只留「自我对弈学习 + 树搜索」反而更强，正是这一课的教科书注脚。

小结：大模型替代的是「靠经验积累的模式判断」，不是「按规则做精确推演」。alpha-beta 这类搜索属于后者——没有被淘汰，而是「神经网络做判断、搜索做验证」这种混合架构里必不可少的一半。理解剪枝，在今天（ToT / Agent 规划 / test-time compute 都是同一套思路的延续）仍然有用。

和别的系列串起来看：这里「沿乐观窗口剪掉无望子树」的思路，和分支限界 branch & bound是同一个家族——分支限界给子树估乐观界 bound 来剪，alpha-beta 用对抗双方的 α/β 来剪；两者都依据「即便再理想也胜不过已知最优」直接切掉指数级的枝叶。而把估值换成 f = g + h，就成了 A* 搜索。