11 · 剪枝

⏱ 34 分钟 ｜ ⭐⭐ 结果和不剪枝一模一样，但同样的时间能多看一倍深度

🎯 一句话

搜索时随身带一个区间 $[\alpha, \beta]$，值落到区间外的分支整条丢掉 —— 根的值和选出的走法和 Minimax 完全一致，而在理想的走法顺序下复杂度从 $O(b^m)$ 降到 $O(b^{m/2})$。

这就是《博弈论与集体决策》第 13 章说的那个「剪枝」—— 它把搜索算法整块指到了本板块，这一章是它 🔗 表里点名的落点。

♟ 一、动机：证明一步棋坏，只要一个理由

讲义在讲算法之前先问了两个问题：

Q1：为什么「皇后到 G5」对黑方是步坏棋？ Q2：你为了回答 Q1，考虑了白方的几种应招？

答案是：一种就够。只要看到一个足够可怕的回应，这步棋就废了 —— 白方另外三十几种走法长什么样，你不需要知道。

⭐⭐ 讲义把它写成一句对仗： 要证明一步棋坏，只需要考虑一个（好的）应招；要证明一步棋好，得看遍所有应招。 α-β 剪枝的全部内容就是这一句，剩下的都是记账。

🔤 二、α 和 β 各是什么

每个节点都带着一个窗口 $[\alpha, \beta]$ 往下走。只有值落进这个窗口，才可能改变根的决定。

⚠️ 最常见的误解：$\alpha$ 和 $\beta$ 不是当前节点的值，而是从祖先一路传下来的约束 —— 讲义把重点全押在一个短语上：它们都是 off the current path（不在当前这条路上）找到的最好值。

⭐ 如果当前节点的值超过了 $\beta$，说明它「好得不真实」—— 对方根本不会让我走到这儿，于是剩下的孩子直接剪掉。

✂ 三、什么时候能剪，为什么剪掉是安全的

规则：MIN 节点上 $\beta \le \alpha$ 就剪；MAX 节点上 $\alpha \ge \beta$ 就剪。剪掉的是这个节点剩下还没看的孩子。

为什么安全（以 MIN 节点为例，三句话）：

1. 这个 MIN 节点上已经看到某个孩子的值 $v$，而且 $v \le \alpha$
2. MIN 层只会取更小的，所以此节点最终值一定 $\le v \le \alpha$
3. 而 $\alpha$ 是 MAX 在别的分支上已经拿到手的保底 —— 这一支给不出更好的，MAX 绝不会选它，剩下的孩子改不了根的决定

⭐ 讲义原话：α-β pruning is guaranteed to give the same result as minimax.

⚠️ 这句话要精确理解：根的值和选出的走法一字不差，但被剪过的内部节点，值不再精确，它变成了一个界 （比如只知道「$\le 2$」，不知道到底是 2 还是 $-7$）。 ⭐ 这不是缺陷，第 12 章会看到 TreeStrap 这类算法专门拿这些界当训练目标。

讲义给的伪代码：

function alphabeta(node, depth, α, β)
    if node is terminal or depth = 0 { return heuristic value of node }
    if we are to play at node                    // MAX
        foreach child of node
            α = max(α, alphabeta(child, depth−1, α, β))
            if α ≥ β { return α }                // β 截断
        return α
    else                                          // MIN
        foreach child of node
            β = min(β, alphabeta(child, depth−1, α, β))
            if β ≤ α { return β }                // α 截断
        return β

🧮 四、在讲义那棵树上完整手算

还是第 10 章那棵树：根是 MAX，三个 MIN 孩子 $B$、$C$、$D$，叶子 $[3,12,8]$、$[2,4,6]$、$[14,5,2]$，从左往右深度优先。

一步一步（$\alpha$ 是根一路传下来的下界）：

账：9 个叶子看了 7 个。⚠️ 第 4 步值得盯一眼：$D$ 也触发了截断条件，但触发得太晚（最后一个孩子），收益是零。 ⭐ 剪枝省多少，完全取决于「该剪的分支排在第几个」 —— 这就是下一节。

🔨 把开关拨一下，数给你看

# 同一棵树，prune 开关一拨，数一数少看了几个叶子
TREE = [[3, 12, 8], [2, 4, 6], [14, 5, 2]]

def search(node, is_max, alpha, beta, seen, prune):
    if isinstance(node, int):
        seen.append(node)                       # 叶子：记一笔「看过了」
        return node
    if is_max:
        v = float("-inf")
        for c in node:
            v = max(v, search(c, False, alpha, beta, seen, prune))
            alpha = max(alpha, v)               # ⭐ α = 我方在别处已经保底的值
            if prune and alpha >= beta:         # ⭐ β 截断：对方不会放我走到这儿
                break
        return v
    v = float("inf")
    for c in node:
        v = min(v, search(c, True, alpha, beta, seen, prune))
        beta = min(beta, v)                     # ⭐ β = 对方在别处已经把我压到的值
        if prune and beta <= alpha:             # ⭐ α 截断：这一支不可能被我方选中
            break
    return v

INF = float("inf")
for prune in (False, True):
    seen = []
    v = search(TREE, True, -INF, INF, seen, prune)
    print("%s 根值=%d  看了 %d 个叶子：%s" %
          ("α-β  " if prune else "不剪枝", v, len(seen), seen))

实跑输出：

不剪枝 根值=3  看了 9 个叶子：[3, 12, 8, 2, 4, 6, 14, 5, 2]
α-β   根值=3  看了 7 个叶子：[3, 12, 8, 2, 14, 5, 2]

⭐ 根值都是 3。 这不是运气 —— 是第三节那三句话证明过的。

📉 五、节点序：这不是常数优化，是指数砍掉一半

国际象棋 $b \approx 35$，$\sqrt{35} \approx 5.9$ —— ⭐ 完美排序等于把分支因子从 35 压到 6。 搜到 8 层要看的叶子数：不剪枝 $35^8 \approx 2.25\times10^{12}$，随机序 $\approx 35^6 \approx 1.84\times10^{9}$， 完美序 $35^4 \approx 1.50\times10^{6}$ —— 少了 6 个数量级。

⭐⭐ 但真正该记住的是换算成深度的那句话（讲义原文）：

α-β 可以搜到普通 Minimax 两倍的深度。 讲义补了一句：搜索深度从 6 提到 12，能把一个很弱的棋手变成一个相当强的棋手。

这笔账自己算一遍：同样的节点预算 $N$，不剪枝搜 $\log_b N$ 层，完美序搜 $\log_{\sqrt b} N = 2\log_b N$ 层 —— 正好两倍。

🔧 六、怎么把好走法排到前面

排序不需要准，只需要比随机好。工程上这几条加起来就够用：

⚠️ 迭代加深看着很浪费 —— 深度 1 到 $d-1$ 全白搜了一遍。其实不然：节点数按 $b$ 指数增长， 前面所有层加起来也只比最后一层多约 $\dfrac{1}{b-1}$，$b = 35$ 时就是 3%。 用 3% 换一个好排序，而排序的收益是指数级的 —— 所以现代引擎全都这么干。

🔗 这一章连到哪里

✅ 检查点

1. 讲义用「皇后到 G5」问的那两个问题，想说明什么？把结论写成一句对仗的话。
2. $\alpha$ 和 $\beta$ 各代表什么？为什么说它们「和当前节点没有直接关系」？
3. MIN 节点上什么时候剪？用三句话说清为什么剪掉是安全的。
4. α-β 和 Minimax 的结果「完全一样」这句话，精确说应该怎么讲？
5. 手算：树是 $[3,12,8]$、$[2,4,6]$、$[14,5,2]$，从左往右深度优先。哪几个叶子被剪掉了？根值是多少？一共看了几个叶子？
6. 第 4 步里 $D$ 也触发了截断条件，为什么一点收益都没有？这说明了什么？
7. 完美排序下复杂度是多少？换算成「深度」是什么结论？$b = 35$ 时 $\sqrt b$ 大约是几？
8. 迭代加深要把浅层重搜一遍，为什么这不算浪费？

🛑 可以停在这里

⚡ 走神救援

α-β 剪枝的全部思想是讲义那句对仗：要证明一步棋坏只需要一个（好的）应招，要证明一步棋好得看遍所有应招。做法是搜索时随身带一个窗口 $[\alpha,\beta]$：$\alpha$ 是在当前路径之外 MAX 方已确保拿到的最好值（根值下界，只增），$\beta$ 是 MIN 方已确保把 MAX 压到的值（上界，只减）。⚠️ 它们不是当前节点的值，是从祖先传下来、记录「树的别处发生过什么」的约束。规则：MIN 节点 $\beta \le \alpha$ 就剪，MAX 节点 $\alpha \ge \beta$ 就剪。安全性三句：已看到某孩子值 $v \le \alpha$ → MIN 只会更小、此节点最终 $\le \alpha$ → 而 $\alpha$ 是 MAX 在别处已到手的保底，这一支绝不会被选。⭐ 讲义那句「保证给出和 minimax 一样的结果」要精确读：根值和走法一字不差，但被剪的内部节点值退化成一个界（如「$\le 2$」）—— 这不是缺陷，第 12 章的 TreeStrap 专门拿这些界当训练目标。手算（$[3,12,8]/[2,4,6]/[14,5,2]$，从左往右）：$B$ 三个叶子全看得 3，根 $\alpha$ 抬到 3；$C$ 只看第一个叶子 2 就有 $\beta=2\le\alpha=3$，✂ 叶 4 和叶 6 直接不看，返回「$\le 2$」；$D$ 三个叶子全看得 2（最后一个也触发截断，但太晚，收益为零）；根 $=\max(3,\le2,2)=3$。9 个叶子看了 7 个，代码把 prune 开关一拨就能验。⭐ $D$ 那一下说明：剪枝省多少全看该剪的分支排在第几个。所以节点序是胜负手：最坏序 $O(b^m)$ 一个都剪不掉，随机序约 $O(b^{3m/4})$，⭐⭐ 完美序 $O(b^{m/2})=O((\sqrt b)^m)$。$b=35$ 时 $\sqrt{35}\approx5.9$，分支因子从 35 压到 6；搜 8 层的叶子数从 $2.25\times10^{12}$ 降到 $1.50\times10^{6}$，少 6 个数量级。换算成深度就是讲义那句：同样时间能搜两倍深（$\log_{\sqrt b}N = 2\log_b N$），而深度从 6 提到 12 能把一个很弱的棋手变成相当强的棋手。排序手段：吃子优先、⭐ 迭代加深（用上一层的最佳走法给下一层排序）、杀手走法、最佳应招、置换表。⚠️ 迭代加深看着浪费，其实前面所有层加起来只比最后一层多约 $1/(b-1)$，$b=35$ 时是 3% —— 3% 换一个指数级收益的排序。

下一节 👉 12-评估函数与棋类AI.html