Software Systems Atlas

中文

English

中文

English

主题

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

模型工坊把地图换成棋盘。你选择一步后，世界不会沿固定边继续，而是由对手挑一个对你最不利的回应。普通最短路只计算环境转移；博弈搜索还要建模其他决策者的目标和信息。

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

本课目标 ​

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

1. Minimax 的递归含义 ​

对 MAX 玩家：

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

对 MIN 玩家：

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

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

python
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 值。

python
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. 根节点还要返回动作 ​

值本身不能落子：

python
def choose_action(state, depth, game):
    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

平局策略应明确：稳定选择、随机打破、偏好更快获胜或更晚失败。它不改变效用值，却影响行为和可复现性。

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 缓存搜索结果可以避免重算，但缓存项需要：

text
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. 测试一个博弈搜索器 ​

text
立即获胜时必须选择胜招
必须阻止对手下一步获胜
对称局面给出相等值
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 通过上下界减少无效展开；深度、评价、缓存和不确定性决定它能否进入真实系统。

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

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang