1.3 Minimax、Alpha-Beta 与不确定性：对手也在选择

棋盘上的路径规划多了一项麻烦：对手也有自己的计划。你选择一步后，还要考虑对手可能的回应。博弈搜索因此需要表示其他决策者的目标和信息，才能判断当前行动的后果。

Minimax 适用于确定、轮流行动、完全信息、零和博弈。超出这些假设时，需要 chance node、belief state、博弈求解或采样方法，不能机械套递归。

本课目标

• 用 terminal utility 定义 minimax 值；
• 解释 alpha-beta 的界、正确性与 move ordering；
• 处理深度截止、评价函数和 transposition；
• 区分对抗节点、随机节点与隐藏信息。

1. Minimax 的递归含义

对 MAX 玩家：

$$V(s)=\underset{a\in A(s)}{max}V(Result(s,a)).$$

对 MIN 玩家：

$$V(s)=\underset{a\in A(s)}{min}V(Result(s,a)).$$

终局返回从固定视角定义的 utility，例如胜 +1、和 0、负 -1。MIN 不是“随机走差的一步”，而是知道局面并最小化 MAX 的结果。

下面的 Python 3 代码均为接口片段（partial），依赖调用者实现 game 的合法动作、转移、终局判断和评分方法。假设双方交替行动，每个非终局状态至少有一个合法动作，评分始终使用 MAX 视角。

def minimax_value(state, player, game):
    if game.is_terminal(state):
        return game.utility(state)  # 始终从 MAX 视角

    children = [
        minimax_value(game.result(state, action), game.next_player(player), game)
        for action in game.actions(state)
    ]
    return max(children) if player == game.max_player else min(children)

在有限树中，它给出双方最优行动下的值。现实对手不最优时，minimax 可能过度保守，但“对手模型”要用验证而非希望替代。

2. Alpha-Beta 剪掉不可能改变决定的分支

• $\alpha$：MAX 在当前路径已保证的下界；
• $\beta$：MIN 在当前路径已保证的上界。

当 $\alpha \ge \beta$，当前节点剩余子树不可能改变祖先选择，可以停止展开。剪枝不改变根节点的 minimax 值。例如根节点 MAX 已有得分 4 的选择，另一个 MIN 子节点刚看到一个得分 2 的后继，它的最终值就至多为 2，余下分支可以跳过。这个界的含义见 Berkeley CS 188 的 Alpha-Beta 说明。

def alpha_beta(state, depth, alpha, beta, player, game):
    if game.is_terminal(state):
        return game.utility(state)
    if depth == 0:
        return game.evaluate(state)

    if player == game.max_player:
        value = float("-inf")
        for action in game.ordered_actions(state):
            child = game.result(state, action)
            value = max(value, alpha_beta(
                child, depth - 1, alpha, beta,
                game.next_player(player), game,
            ))
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value

    value = float("inf")
    for action in game.ordered_actions(state):
        child = game.result(state, action)
        value = min(value, alpha_beta(
            child, depth - 1, alpha, beta,
            game.next_player(player), game,
        ))
        beta = min(beta, value)
        if alpha >= beta:
            break
    return value

最坏的行动顺序仍接近 $O(b^d)$；理想顺序才可接近 $O(b^{d/2})$。剪枝不是“只加两行、代价为零”：排序、缓存和实现复杂度都有成本。

3. 根节点还要返回动作

值本身不能落子：

def choose_action(state, depth, game):
    if game.is_terminal(state):
        return None, game.utility(state)
    if depth < 1:
        raise ValueError("choose_action requires depth >= 1")
    best_action = None
    best_value = float("-inf")
    alpha, beta = float("-inf"), float("inf")

    for action in game.ordered_actions(state):
        value = alpha_beta(
            game.result(state, action), depth - 1,
            alpha, beta, game.min_player, game,
        )
        if value > best_value:
            best_value, best_action = value, action
        alpha = max(alpha, best_value)

    return best_action, best_value

该根节点函数假设轮到 MAX；终局返回 None 动作，非终局要求深度至少为 1。否则递归从负深度开始，永远碰不到 depth == 0 的截止条件。平局策略也应明确：稳定选择、随机打破，或在同效用动作中偏好更快获胜、更晚失败。

4. 深度截止与评价函数

大棋盘无法搜到终局，只能在深度 $d$ 截止，用 evaluate(state) 估计值。评价函数应：

• 与终局效用方向一致；
• 在对称局面上保持对称；
• 计算足够便宜；
• 对关键战术具有区分力；
• 在独立局面和对弈中验证。

固定深度会产生 horizon effect：灾难刚好落在视野之外。可用 quiescence search 在不稳定局面继续搜索，或 iterative deepening 在时间预算内逐层加深。

5. Move ordering 决定剪枝效率

优先搜索可能最佳的动作，能更早收紧 alpha/beta：

• 上一轮 iterative deepening 的 principal variation；
• captures/checks 等领域规则；
• killer/history heuristic；
• 轻量评价函数或学习模型。

排序错误不改变完整 alpha-beta 的值，只会减少剪枝；但时间截止时，排序也会影响最终可用答案。

6. Transposition table

不同动作顺序可能到达同一局面。用局面 key 缓存搜索结果可以避免重算，但缓存项需要：

state key（含轮到谁、规则状态）
searched depth
value
bound type：EXACT / LOWER / UPPER
best move

剪枝返回的值有时只是界，不能一律当 exact。Zobrist hash 等紧凑 key 还需处理碰撞风险。

7. 有随机事件：Expectiminimax

掷骰子、随机掉落等不是对手选择，应加入 chance node：

$$V(s)=\sum _{o}P(o\mid s,a)V(Result(s,a,o)).$$

错误地让 MIN 选择最坏骰子结果，会过度悲观；只取期望则依赖概率模型正确。风险敏感任务还可能关心尾部损失，而不只是期望。

8. 隐藏信息不是普通 chance node

扑克等不完全信息博弈中，玩家不知道真实状态。需要对 information set/belief 建模，并考虑策略随机化和对手从行动推断信息。把未知手牌当作每一步重新随机抽取，会违反信息一致性。

Monte Carlo Tree Search（MCTS）用 selection、expansion、simulation、backup 聚焦有希望分支，适合巨大空间或有生成模型的场景，但表现依赖探索规则、模拟策略和预算。它不是自动替代 minimax。

9. 测试一个博弈搜索器

立即获胜时必须选择胜招
必须阻止对手下一步获胜
对称局面给出相等值
alpha-beta 与完整 minimax 在小树上同值
不同 move ordering 不改变完整搜索值
transposition 开关不改变结果
时间截止始终返回已完成深度的合法动作

常见误区

• Minimax 适合所有竞争场景：它假设零和、轮流、确定、完全信息。
• Alpha-beta 总是 $O(b^{d/2})$：这是理想行动排序量级。
• 评价函数分数就是胜率：除非经过相应定义和校准。
• 缓存值都可直接复用：剪枝值可能只是上下界。

练习

1. 为井字棋实现终局 utility 与状态 key，验证旋转对称。
2. 比较三种 move ordering 的扩展节点数。
3. 为带骰子的小游戏加入 chance node，对比最坏情况策略。
4. 给 alpha-beta 加 transposition table，正确存储 bound type。

小结

对抗搜索把环境转移变成其他决策者的选择。Minimax 的保证来自清晰博弈假设，alpha-beta 通过上下界减少无效展开；深度、评价、缓存和不确定性决定它能否进入真实系统。

下一章处理知识表示与推理：当智能体不只需要搜索局面，还要表达事实、约束和不确定关系，表示方式会决定可推导什么。