📑 本页目录（点开跳转）
10 · 博弈树与 Minimax
⏱ 33 分钟 ｜ ⭐⭐ 1928 年的定理说「那个值存在」，这一章讲怎么真的把它算出来
🎯 一句话
当环境里多了一个目标和你完全相反的人，「解」就不再是一条路径而是一个策略； Minimax 从叶子往根倒推，MAX 层取大、MIN 层取小，一路推到根就得到了这个策略。
📜 这一章是另一套教程指过来的落点
《博弈论与集体决策》第 13 章讲完零和博弈之后，明确把读者指到了这里：
「（它们还带先后顺序，属于扩展式博弈，零和结论在那里换成极小化极大搜索 + 剪枝 —— 下一章讲博弈树和逆向归纳，而搜索算法本身在《不靠数据的 AI》10–12 章。）」
⭐ 它把话分成了两半：定理那一半留在自己那边（零和博弈的值、极小化极大定理）， 算法这一半交给本板块。它的连接表里还专门有两行，分别指向本章和第 11 章。
⚠️ 那边的第 14 章确实不教 α-β——它讲逆向归纳和子博弈完美均衡，只在一句话里提过 「工程上只能剪枝 + 估值函数」。展开在这里：本章讲极小化极大搜索本身，第 11 章讲 α-β 剪枝。
🤺 一、断层：环境里多了一个跟你作对的人
前九章的世界是被动的：你选动作，状态按规则变，障碍不会追着你跑。所以解是一条路径。
博弈不一样：树上有一半的边不是你选的，而且选它的那个人希望你输。
⭐ 讲义原话："Unpredictable" opponent ⇒ solution is a strategy —— 你没法只规划一条路线，因为对手随时可能走出你没打算过的那一步。 你要准备的是对他每一种回应都有答案的一整套方案。
第二个变化是时间：象棋一步棋只有几分钟，所以必然要近似（讲义："tradeoff between speed and accuracy"）。 这条会在第 12 章展开。
🎲 二、博弈的分类
讲义的分法很干净，而且直接决定了用哪个算法：
| 类型 | 例子 | 用什么 |
|---|---|---|
| 离散 · 完全可观测 · 确定 | 国际象棋、跳棋、围棋、黑白棋 | ⭐ Minimax + α-β（本章和下一章） |
| 离散 · 完全可观测 · 随机 | 西洋双陆棋、大富翁 | 期望极小极大（第 12 章） |
| 离散 · 部分可观测 | 桥牌、扑克、拼字 | 抽样 + Minimax、反事实遗憾最小化 |
| 连续、具身 | Robocup 足球、台球 | 回到第 9 章的运动规划 + 策略层 |
本章只做第一行：二人、轮流、确定、完全可观测、零和。这是最干净的一格，也正是第 13 章证明「完全可解」的那一格。
🌳 三、博弈树
- 节点 = 一个局面（棋盘状态 + 轮到谁走）
- 边 = 一步合法走子
- 层交替：轮到我方的层叫 MAX 层，轮到对方的层叫 MIN 层
- 终局节点带一个效用：讲义的井字棋用 $+1$（我赢）、$0$（和）、$-1$（我输）
⭐ 为什么每个终局只写一个数就够？因为零和：对方的收益恒等于 $-$ 我的收益，写一个另一个就定了。 这不是简化，是第 13 章那条 $u_1 + u_2 = 0$ 的直接后果。
🧮 四、Minimax：从叶子往根倒推
$$V(n) = \begin{cases} U(n) & n \text{ 是终局}\\ \max_{c \in \text{子}(n)} V(c) & n \text{ 在 MAX 层}\\ \min_{c \in \text{子}(n)} V(c) & n \text{ 在 MIN 层} \end{cases}$$
⭐ 读法：「假设对手每一步都打得最狠，我最多能拿到多少」。 MAX 层挑最大是因为那一步归我选；MIN 层挑最小是因为那一步归他选，而他会挑对我最差的。
手算讲义那棵树
根是 MAX 层，三个孩子 $A_1, A_2, A_3$ 都是 MIN 层，九个叶子的效用是 $[3, 12, 8]$、$[2, 4, 6]$、$[14, 5, 2]$。
一步一步：
| 步 | 在算什么 | 结果 |
|---|---|---|
| 1 | $A_1$ 是 MIN 层，取 $\min(3, 12, 8)$ | $A_1 = 3$ |
| 2 | $A_2$ 取 $\min(2, 4, 6)$ | $A_2 = 2$ |
| 3 | $A_3$ 取 $\min(14, 5, 2)$ | $A_3 = 2$ |
| 4 | 根是 MAX 层，取 $\max(3, 2, 2)$ | ⭐ 根 = 3，走 $A_1$ |
⚠️ 注意第 3 步：$A_3$ 底下有个 14，是全树最大的数，可它对结果毫无影响 —— 因为那一步归对手选，他当然选 2 不选 14。「树里有个大数」和「你能拿到这个大数」是两回事， 这是初学者最常犯的错。
🔨 十几行跑一遍
# 讲义那棵树：根是 MAX 层，三个 MIN 孩子，共 9 个叶子
TREE = [[3, 12, 8], [2, 4, 6], [14, 5, 2]]
leaves = [] # 记录「看过哪些叶子」
def minimax(node, is_max):
if isinstance(node, int): # 叶子：直接返回效用
leaves.append(node)
return node
if is_max:
v = float("-inf")
for c in node:
v = max(v, minimax(c, False)) # ⭐ MAX 层取孩子的最大值
return v
v = float("inf")
for c in node:
v = min(v, minimax(c, True)) # ⭐ MIN 层取孩子的最小值
return v
print("三个 MIN 节点的值 =", [minimax(sub, False) for sub in TREE])
leaves.clear()
print("根（MAX）的值 =", minimax(TREE, True))
print("看过的叶子 %d 个：%s" % (len(leaves), leaves))
实跑输出：
三个 MIN 节点的值 = [3, 2, 2]
根（MAX）的值 = 3
看过的叶子 9 个：[3, 12, 8, 2, 4, 6, 14, 5, 2]
⭐ 记住最后那行「9 个」—— 下一章会在同一棵树上把它变成 7 个。
📏 五、性质：三个好消息，一个坏消息
| 问题 | 答案 |
|---|---|
| 完备？ | 树有限才完备。象棋专门有防无限的规则（五十步、三次重复） |
| 最优？ | ⭐ 对最优对手最优 |
| 时间 | $O(b^m)$，$b$ 是分支因子，$m$ 是整局的步数 |
| 空间 | $O(bm)$ —— ⚠️ 是 $b$ 乘以 $m$，不是 $b$ 的 $m$ 次方，因为它是深度优先，同时只在栈上留一条路径 |
⚠️ 「对最优对手最优」这句话有个反面：如果对手会犯错，Minimax 不会去占这个便宜。 它假设最坏，所以从不冒险。讲义在井字棋那页专门问了这件事： 「如果相信对手可能失误，能不能选一个比中心格更好的开局？」—— 中心格是对最优对手的最优解，但面对新手，一个能设陷阱的角落可能赢面更大。
坏消息：这东西根本跑不动
国际象棋 $b \approx 35$，一局 $m \approx 100$ 步。$35^{100} \approx 10^{154}$。
作为对照，可观测宇宙的原子数大约是 $10^{80}$。差了 74 个数量级。
⭐ 所以真实棋类程序必须做两件事，一件都不能少：
➖ 六、Negamax：把两个分支合成一个
上面的写法里 MAX 和 MIN 是两段几乎一样的代码 —— 这是 bug 的温床。
⭐ 讲义给的化简：不要固定从白方视角评估，改成从「轮到走棋的那一方」视角评估。 这样每一层都是 MAX 层，只要在递归返回时取个负号：
function negamax(node, depth)
if node is terminal or depth = 0
return heuristic value of node // 从当前该走棋一方的视角
α = −∞
foreach child of node
α = max(α, −negamax(child, depth−1))
return α
代码少一半，出错的地方也少一半。⚠️ 代价：评估函数必须严格反对称（$V(s)$ 对一方是 $+x$，对另一方就必须是 $-x$），否则符号会错得很隐蔽。
🔗 七、和博弈论的两个接口
这两条是理解 Minimax 到底是什么的关键，别跳过。
⭐⭐ 接口一：定理 vs 算法
| 极大极小定理（von Neumann, 1928） | Minimax 搜索 | |
|---|---|---|
| 它说什么 | 存在唯一的值 $v$，玩家 1 能保证至少拿 $v$、玩家 2 能保证最多输 $v$ | 给一棵具体的树，把 $v$ 算出来并给出取到它的那一步 |
| 类型 | 存在性结论 | 构造性算法 |
| 靠什么 | 分离超平面 / 线性规划对偶 | 深度优先递归 |
| 代价 | 不管你怎么找 | $O(b^m)$，象棋是 $10^{154}$ |
⭐⭐ 一句话：1928 年那条定理告诉你「那个数存在且唯一」，Minimax 告诉你「怎么把它算出来」。 一个是「有」，一个是「怎么找到」。知道东西存在和能在两分钟内找到它，中间隔着这两章。
⭐ 接口二：逆向归纳就是 Minimax
《博弈论与集体决策》第 14 章的逆向归纳和这一章的 Minimax， 是同一个思想的两种语言：都从叶子开始，把「这个子博弈值多少」一层层往根填。
| 博弈论那边 | 本章这边 |
|---|---|
| 扩展式博弈的博弈树 | 博弈树 |
| 玩家 1 / 玩家 2 的决策节点 | MAX 层 / MIN 层 |
| 收益向量 $(u_1, u_2)$ | ⭐ 零和时只写 $u_1$ 一个数 |
| 逆向归纳 | Minimax 递归 |
| 子博弈完美均衡 | 从根出发的最优走法序列 |
⚠️ 差别只有两处，都是工程上的：① 博弈论那边树是画得出来的，这边树有 $10^{154}$ 个节点， 所以必须截断 + 估值；② 博弈论关心「均衡是什么」，这边关心「两分钟内算得完吗」—— 于是有了下一章。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 11-剪枝.html | 本章算出根值 3 看了 9 个叶子；α-β 会证明其中 2 个根本不用看，而且结果一模一样 |
| ../博弈论与集体决策/13-零和与极大极小.html | ⭐⭐ 那一章证明零和博弈的值 $v$ 存在且唯一，本章是把 $v$ 算出来的算法。⭐ 那一章明写着「搜索算法本身在《不靠数据的 AI》10–12 章」，🔗 表里两行分别指向本章和 11 章 |
| ../博弈论与集体决策/14-扩展式博弈.html | 逆向归纳和 Minimax 是同一个思想的两种语言，术语对照表见上一节 |
| 12-评估函数与棋类AI.html | $35^{100}$ 搜不完，所以要在半路停下来估值 —— 那一章讲怎么估，以及估错会怎样 |
✅ 检查点
- 为什么博弈里的「解」是一个策略而不是一条路径？
- 讲义把博弈分成哪几类？本章处理的是哪一类？
- 博弈树的终局节点为什么只写一个数就够了？
- 手算：MIN 层三个节点的孩子分别是 $[3,12,8]$、$[2,4,6]$、$[14,5,2]$，根是 MAX 层。三个 MIN 值和根值各是多少？树里最大的 14 为什么没用？
- Minimax 的时间和空间复杂度各是多少？空间那个式子为什么不是指数？
- 「对最优对手最优」的反面是什么？
- 极大极小定理和 Minimax 搜索的分工是什么？
- 逆向归纳和 Minimax 的关系是什么？两者的差别在哪里？
👀 答案
- 因为树上有一半的边不是你选的，而且选它的人希望你输（讲义："unpredictable opponent ⇒ solution is a strategy"）。你没法只规划一条路线，必须对他的每一种回应都准备好答案。
- 离散 · 完全可观测 · 确定（象棋、围棋）；离散 · 完全可观测 · 随机（西洋双陆棋）；离散 · 部分可观测（桥牌、扑克）；连续具身（Robocup、台球）。⭐ 本章只做第一类（二人、轮流、确定、完全可观测、零和）。
- 因为零和：$u_2 = -u_1$，写一个另一个就定了。这是第 13 章那条 $u_1+u_2=0$ 的直接后果。
- $A_1 = \min(3,12,8) = 3$，$A_2 = \min(2,4,6) = 2$，$A_3 = \min(14,5,2) = 2$；根 $= \max(3,2,2) = \mathbf{3}$，走 $A_1$。⚠️ 14 没用，因为那一步归对手选，他会选 2。「树里有个大数」和「你拿得到这个大数」是两回事。
- 时间 $O(b^m)$，空间 $O(bm)$。空间不是指数，是因为它深度优先：同一时刻栈上只有从根到当前节点的一条路径（$m$ 层），每层最多记 $b$ 个兄弟。
- 它假设对手最优，所以从不去占对手犯错的便宜。讲义在井字棋那页问过：面对可能失误的对手，能不能选比中心格更好的开局？中心格对最优对手最优，但面对新手，一个能设陷阱的角落赢面可能更大。
- ⭐⭐ 定理（1928）是存在性结论：那个值 $v$ 存在且唯一。Minimax 是构造性算法：给一棵具体的树，把 $v$ 算出来并给出对应的走法。一个说「有」，一个说「怎么找到」。
- ⭐ 同一个思想的两种语言 —— 都从叶子开始把「这个子博弈值多少」一层层往根填。MAX/MIN 层对应两个玩家的决策节点，Minimax 递归对应逆向归纳，根出发的走法序列对应子博弈完美均衡。差别是工程上的：博弈树在这边有 $10^{154}$ 个节点，必须截断估值；而且这边关心的是「两分钟内算得完吗」。
🛑 可以停在这里
⚡ 走神救援
这一章是《博弈论与集体决策》13 章指过来的落点 —— 那边把定理（零和博弈的值存在且唯一）留在自己那儿，把算法交给本板块；它 14 章讲逆向归纳、只提过一句「工程上只能剪枝 + 估值函数」，展开在本章和 11 章。断层：前九章的环境是被动的，解是一条路径；博弈里一半的边不是你选的，选它的人还希望你输，所以解是策略。讲义把博弈分四类，本章只做二人 · 轮流 · 确定 · 完全可观测 · 零和这一格 —— 正是 13 章证明「完全可解」的那一格。博弈树：节点是局面，边是走子，MAX 层归我、MIN 层归对方，终局带效用 $+1/0/-1$；⭐ 只写一个数是因为零和（$u_2=-u_1$）。Minimax：MAX 层取最大、MIN 层取最小，从叶子一路推到根。讲义那棵树 $[3,12,8]/[2,4,6]/[14,5,2]$ → MIN 层得 3、2、2 → 根 $\max(3,2,2)=\mathbf 3$，走最左支。⚠️ 全树最大的 14 毫无用处，因为那一步归对手选，他挑 2 —— 「树里有个大数」和「你拿得到」是两回事。代码实跑：根 = 3，看了 9 个叶子（下一章会变成 7 个）。性质：树有限才完备；对最优对手最优 —— 但反面是它从不去占对手犯错的便宜（讲义的井字棋问题：面对新手，能设陷阱的角落可能比中心格赢面大）；时间 $O(b^m)$，空间 $O(bm)$ ——⚠️ 是 $b$ 乘 $m$，因为深度优先时栈上只有一条路径。坏消息：象棋 $b\approx35$、$m\approx100$，$35^{100}\approx10^{154}$，而可观测宇宙的原子数才 $10^{80}$。所以真程序必须两件事都做：半路停下来估值（12 章）+ α-β 剪枝（11 章）。Negamax 把 MAX/MIN 两段几乎相同的代码合成一段：改成从「轮到走棋那方」的视角评估，每层都取 max、返回时加负号，代价是评估函数必须严格反对称。⭐⭐ 最后两个接口：极大极小定理（1928）是存在性结论（$v$ 存在且唯一），Minimax 是构造性算法（把 $v$ 算出来）—— 一个说「有」，一个说「怎么找到」；逆向归纳和 Minimax 是同一个思想的两种语言，差别只在这边的树有 $10^{154}$ 个节点、必须截断估值。
下一节 👉 11-剪枝.html