1.4 Alpha-Beta 剪枝

上一节末尾我们留了个难题：Minimax 要把整棵树走完，太慢。这一节的 Alpha-Beta 剪枝（α-β pruning）是它最重要的一个加速。它的妙处在于——结果和 Minimax 一模一样，一分不差，只是少看了大量注定无关紧要的分支。这是“不损失任何正确性的提速”，几乎是白捡的。

一、动机：有些分支，瞄一眼就知道不必再看

先建立直觉，用买东西打个比方。你想买“最便宜”的某件商品（你是最小化方），已经在 A 店看到标价 50 元。现在你走进 B 店，第一眼就瞧见它家同款要 80 元——这时你还需要把 B 店里这款的其它颜色、其它批次挨个问一遍价吗？不需要。它家最低也不会低于你看到的，反正不可能比 A 店的 50 便宜，掉头就走。

Minimax 搜索里到处是这种情形。看下面这棵小树，你（Max）想要分数尽量大，已经在左边分支 A 算出能稳拿 5 分。接着你去看分支 B，而 B 的下一层轮到对手（Min，他想压低分数）：

            你（Max）：想要尽量大
           /                  \
      分支A：已算出 = 5      分支B：轮到对手(Min)
                            /        |        \
                          3       (?)       (?)   ← 对手第一手就能把分数压到 3
                                                   对手只会取更小 → B 最多值 3
                                                   比 A 的 5 还差，后两手不必看 → 剪掉

关键在于：对手在 B 里第一手就能把分数砍到 3，而对手只会越压越低，所以分支 B 的最终价值绝不会超过 3。可你手里已经有 A 的 5 了，B 再怎么算也比不过 A——那何必把 B 里剩下的走法再算一遍？直接剪掉。这，就是 α-β 剪枝。

二、α 和 β：两条“已经保底”的线

为了让程序自动识别上面那种“不必再看”的时刻，我们在搜索时一路带着两个数：

α（alpha）：到目前为止，最大化方已经能保证拿到的最好分数（它的“地板”，上例中的 5）。
β（beta）：到目前为止，最小化方已经能保证压到的最低分数（它的“天花板”）。

搜索往下走时，α 只会升、β 只会降，它俩像一把越收越紧的钳子。一旦出现 α ≥ β，就说明“这条分支再算下去，也改变不了上层的选择了”——当前节点剩下的走法可以全部剪掉。记住这个判定，下面的代码核心就是它。

三、最小实现：在 Minimax 上加两个参数

好消息是，α-β 不是另起炉灶，它就是给上一节的 Minimax 多带两个参数 alpha、beta，并在循环里加一句“够了，剪枝”。最大化方负责抬高 α，最小化方负责压低 β，谁让钳子合拢（alpha >= beta）谁就停：

import copy

def alphabeta(game, alpha=-float('inf'), beta=float('inf'), depth=0):
    """带 α-β 剪枝的 Minimax。返回 (分数, 最优走法)，结果与朴素 Minimax 完全一致。"""
    if game.is_terminal():
        return game.winner() * (10 - depth), None

    best_move = None
    if game.current_player == 1:              # 最大化方
        value = -float('inf')
        for move in game.legal_moves():
            child = copy.deepcopy(game); child.make_move(move)
            score, _ = alphabeta(child, alpha, beta, depth + 1)
            if score > value:
                value, best_move = score, move
            alpha = max(alpha, value)         # 抬高我的“地板”
            if alpha >= beta:                # 钳子合拢：对手不会让局面走到这儿
                break                         # → 剪掉剩下的走法
        return value, best_move
    else:                                     # 最小化方
        value = float('inf')
        for move in game.legal_moves():
            child = copy.deepcopy(game); child.make_move(move)
            score, _ = alphabeta(child, alpha, beta, depth + 1)
            if score < value:
                value, best_move = score, move
            beta = min(beta, value)           # 压低我的“天花板”
            if alpha >= beta:                # 钳子合拢
                break
        return value, best_move

对照上一节的 Minimax，你会发现骨架几乎没变——多出来的只有 alpha/beta 的更新和那句 break。最值得记住的一点是：它给出的分数和最佳走法，与朴素 Minimax 分毫不差。剪掉的全是“算了也不影响结论”的分支，所以这是一次无损提速。把 best_move() 改成调用 alphabeta 即可，井字棋上它照样是不可战胜的，只是更快了。

四、到底省了多少？顺手数一数节点

“快了”不能只是嘴上说。最简单的验证办法，是在函数里放一个全局计数器，每进一个节点就加一，分别用 Minimax 和 α-β 跑同一个开局，比一比访问的节点数：

nodes = 0

def alphabeta(game, alpha=-float('inf'), beta=float('inf'), depth=0):
    global nodes
    nodes += 1            # 每访问一个节点就记一笔
    # ……（其余同上）……

你会看到 α-β 访问的节点数大幅下降，而最终选出的着法完全相同。理论上，在“好走法尽量先搜”的理想顺序下，α-β 大约只需访问 Minimax 平方根那么多的节点——这意味着在同样的时间里，它能往下多搜差不多一倍的深度。对井字棋只是“更快”，但对大棋盘，多搜一倍深度往往就是“能看穿杀棋”和“看不穿”的天壤之别。

五、反思：剪得多还是少，全看走子顺序

这里藏着一个特别重要、也特别容易被忽略的点。回看第一节那个例子——我们之所以能剪掉 B 的后两手，是因为恰好先看了值 5 的 A。要是我们倒霉，把最差的分支排在最前面，那 α、β 这把钳子就迟迟合不拢，α-β 会退化得和朴素 Minimax 一样，一个分支都剪不掉。

换句话说：α-β 的威力，几乎完全取决于你“先试哪一步”。越能把好棋排在前面，剪得越狠。这就直接引出了下一个话题——走子排序：我们得想办法在搜索前，先猜个大概“哪些走法可能更好”，把它们提到前面。这条线我们在 1.5 先打个底，到第二章五子棋上会变成决定性的工程手段。

同时，别忘了上一节那个更根本的难题依然没解决：哪怕剪枝再狠，五子棋和国际象棋的树还是大到搜不到底。剪枝让我们“同样时间搜得更深”，但“深”仍然有限，到不了终局。所以我们终究需要那件还没登场的工具——在搜不到底时，给中间局面估个分的“评估函数”。

六、小结与下一节

剪枝的直觉：当一个分支“再算也不可能改变上层选择”时，就不必算完——像进店一眼看到更贵就掉头。
α 与 β：分别是最大化方的地板、最小化方的天花板；当 alpha >= beta 时剪枝。
无损提速：α-β 结果与 Minimax 完全相同，只是少看了无关分支；理想顺序下约省到平方根级的节点。
命门是顺序：剪枝效果高度依赖走子顺序——这是“走子排序”的起点；而“搜不到底”则呼唤“评估函数”。

这两条线——评估函数与走子排序——正是下一节的主题。我们去 1.5 评估函数与走子排序，先在小小的井字棋上把它们预演一遍，为第二章的五子棋热身。