0. 从 Minimax 到 MCTS - 经典博弈树搜索基础

📝 博弈树搜索黑称

game tree (博弈树): 把所有可能走法画成的有根树, 每个 node 是 state, 每条 edge 是 action
zero-sum game: 一方 gain = 另一方 loss, 两边目标完全对立
Minimax: 假设对手最优时自己能保证拿到的最佳 outcome
Alpha-Beta Pruning: Minimax 的剪枝加速版
MCTS (Monte Carlo Tree Search): 用随机采样 + 统计估计替代完整树搜索
UCT (Upper Confidence bounds for Trees): MCTS 的 Selection 阶段公式
rollout / playout / simulation: 从 leaf 出发 random play 到终局, 拿 1 个 noisy sample
Markov property: 给定当前 state, 未来跟历史无关 — MCTS / minimax 都依赖这个

为什么要写这一篇

读 LATS (Language Agent Tree Search) 之前必须先理解 MCTS, 而 MCTS 的设计逻辑只有放在 minimax / alpha-beta 的演化脉络里看才看得透; 这篇是为读 ReAct + Reflexion - Reasoning Acting and Verbal Reinforcement Learning 后续补 LATS 段做的前置阅读;

整条理解线索:

Minimax (1928, von Neumann)
   ↓ "chess / Go 上指数爆炸不可行"
Depth-Limited Minimax + Heuristic Eval
   ↓ "Go 上 heuristic 设计不出来"
Alpha-Beta Pruning (1958)
   ↓ "Go 上分支因子 250, alpha-beta 救不了"
MCTS (Coulom 2006) + UCT (Kocsis-Szepesvári 2006)
   ↓ "用采样 + LLN 替代完整搜索"
AlphaGo / AlphaZero (Silver 2016, 2017)
   ↓ "把 NN 嵌进 MCTS, 后来完全去掉 random rollout"
LATS (Zhou 2024)
   ↓ "搬到 LLM 推理, 用 LLM verbal feedback 替 NN value"

前置基础: 博弈树和零和博弈

任何 turn-based 棋类游戏都可以画成博弈树:

node = 一个 game state (棋盘 + 当前轮到谁 + 任何 history flag)
edge = 一个 action
root = 起始 state (例如 chess 开局)
leaf = terminal state (赢 / 输 / 平)

零和博弈 = A 的 utility + B 的 utility = 0; A 赢 = B 输; 这让评分变简单 — eval(s_final) 只从 A 视角算, B 自动相反;

典型例子: Tic-Tac-Toe / Chess / Go / Othello 都是 deterministic, perfect-information, zero-sum, 2-player; minimax 适用的就是这一类;

Minimax: 假设对手最优时的保底策略

递归形式化

A 是 max 玩家 (想让自己 utility 最大), B 是 min 玩家 (想让 A 的 utility 最小):

\begin{aligned} v_A(s_i) &= \max_{a_i} v_B(\text{move}(s_i, a_i)) \quad \text{with} \quad v_A(\hat{s}) = \text{eval}(\hat{s}) \\ v_B(s_i) &= \min_{a_i} v_A(\text{move}(s_i, a_i)) \quad \text{with} \quad v_B(\hat{s}) = -\text{eval}(\hat{s}) \end{aligned}

注意 move 返回的 state 接 $v_B$ 而不是 $v_A$ — 这是回合切换的体现; A 走完之后下一回合是 B, next state 的 value 由 B 视角衡量, 递归继续;

直觉: 在 B 最强 counter 下 A 能拿到的下界

minimax 的本质不是 “让 B 难走” 或 “限制 B 的选项”, 而是:

从 A 的 actions 里, 找一个 — 即使 B 在下一回合用最强 counter — A 仍然能拿到最好结果的 action;

也叫 悲观主义 + 保底策略, 中文经典翻译是 极小化极大;

用一个小例子跑一遍

A 在某 state 有 3 个候选 $m_1, m_2, m_3$ , 每个 move 后 B 有 2 个回应, 终局 eval:

              A 的回合 (max)
  ┌───────────────┼────────────────┐
 m_1             m_2              m_3
  |               |                |
B (min)         B (min)          B (min)
 / \             / \              / \
+5  -3          +2  +1           +4  -1

B 永远选对 A 最坏的:

$m_1$ → B 选 -3 → A 拿 -3
$m_2$ → B 选 +1 → A 拿 +1
$m_3$ → B 选 -1 → A 拿 -1

A 应该选: $\arg\max(-3, +1, -1) = m_2$ , $v_A(s_{cur}) = +1$ ;

注意 $m_1$ 有最高潜在 outcome (+5), 但 A 不会选 — 因为 B 不傻, 会把 A 推到 -3; A 选的是"在 B 最优反击下我自己最好"的那条;

Minimax 的根本缺陷: 指数爆炸

理论 minimax 要递归到终局, 中间 node 的 value 不能直接打分, 必须从终局往上 backup;

但完整 game tree 太大:

游戏	状态总数	全树 minimax
Tic-Tac-Toe	~ $10^5$	✅ 完全可行
Connect-4	~ $10^{14}$	⚠️ 勉强
Chess	~ $10^{120}$	❌ 不可能
Go	~ $10^{360}$	❌ 完全不可能

Chess / Go 上必须砍掉一部分搜索;

Depth-Limited Minimax + Heuristic Eval

工程上最直接的 fix:

1
2
3

1. 不递归到终局, 只递归到固定 depth D
2. 在 depth=D 的 "horizon" 上用 heuristic eval() 估值
3. 然后照常 backup 上来

例如 Stockfish 用 depth ~20-30 的 minimax + 一套精心调过的 chess eval (棋子价值 + 位置评分 + 王安全度 + …);

但 heuristic eval 难做

瓶颈从"搜索成本"转到 “怎么设计 horizon 上的 eval()”:

chess: 千行 hand-crafted eval, 几十年才调出来, 不是任意一个人能轻松写的
Go: heuristic eval 几乎不可能 — 局面太复杂, 没办法用简单 rule 估值; 这是 Go 让传统 minimax 失败 的本质原因

这是 MCTS 出现的真正动机: 与其设计 eval, 不如让 random play 自己说话;

Alpha-Beta Pruning

minimax 的剪枝优化, 一个简单 insight:

如果我已经知道 $m_2$ 至少能给我 +1, 那探索 $m_1$ 时一旦发现 B 有一个 response 能让我拿到 < +1, 就不用再看 m_1 的其他 B response — 反正我不会选 m_1 了;

最优排序下复杂度从 $O(b^d) \to O(b^{d/2})$ , 等同 depth 翻倍; 救活了 chess engines, 但 Go 上分支因子 250, 翻倍仍不实用; 真正改变 Go 的是 MCTS;

Monte Carlo Tree Search (MCTS)

核心 idea

MCTS 用采样 + 统计估计代替完整树搜索:

“我不展开全树, 我用 random rollout 估每个 candidate 大概多好, 反复采样让大数定律把噪声磨平; 同时用 UCT 在已展开的树里做 smart descent, 越好的 path 越被反复 refine;”

跟 minimax 的核心 trade-off:

	Minimax (全树)	MCTS
树展开	完整	采样, 渐进增长
估值方式	终局 eval 回 backup	random rollout 拿 noisy sample, 多次 LLN 平均
是否需要 heuristic eval	depth-limited 时需要	❌ 不需要 (rollout 到终局拿真分)
Chess / Go	Chess OK, Go 不行	Go 主战场, AlphaGo 用它
并行性	一般	天然适合并行 (多 rollout 独立)

4 Phase Loop

MCTS 不是一次性算法, 是个循环, 每次迭代做 4 件事, 跑 N 次:

                      MCTS 一次迭代
                            │
   ┌──────────────┬─────────┴─────────┬──────────────────┐
   │              │                   │                  │
1. Selection  2. Expansion       3. Simulation   4. Backpropagation
   (UCT 向下)   (加 1 个新 child)    (random rollout)  (沿反向更新)

Phase 1: Selection — 从 root 出发, 在已有 tree 里用 UCT 公式贪心向下走, 一直走到 in-tree boundary (即"已展开但还有 un-tried child" 的 node);

Phase 2: Expansion — 在 boundary 上加 1 个 un-tried child 进 tree, 初始化 N=0, Q=0; 这个新 node 从此 visited;

Phase 3: Simulation (Rollout / Playout) — 从新加的 node $L_{new}$ 出发, uniform random play 一直到 terminal, 拿到 result $R \in \{-1, 0, +1\}$ ; rollout 经过的临时 state 不进 tree, 用完就丢, 只保留终局 R;

Phase 4: Backpropagation — 从 $L_{new}$ 沿 Selection path 的反向一路向上到 root, 每经过一个 in-tree node $v$ : $N(v) \mathrel{+}= 1$ , $Q(v)$ 用 $R$ 更新 running average;

跑 N 次后, root 下每个 action 都积累了 visit count + Q value, 选 visit count 最高的 action 作为最终决策;

Tree growth model

MCTS 的 tree 是 incremental 长出来的, 每次迭代加 1 个 node:

迭代 1: ROOT (1 node) → Expansion 加 1 个 child → tree 2 nodes
迭代 2: Selection 下钻到那个 child → Expansion 加 child 的 child → tree 3 nodes
迭代 N: tree 大约 N+1 个 node
        N(ROOT) ≈ N (每次 backprop 都经过)
        越深的 node visit count 越少

一个具体迭代的 walkthrough

假设 tree 当前长这样, 跑迭代 K:

Before iteration K:
              ROOT (N=20, Q=0.30)
              /         \
            A (N=15)   B (N=5)
            /  \         |
          X(N=8) Y(N=7) Z(N=5)

迭代 K:

1. Selection: ROOT → A → X (UCT 引导)
2. Expansion: X 有 un-tried child Q, 加进 tree (N(Q)=0)
3. Simulation: 从 Q 出发 random rollout → terminal → R = +1
4. Backprop:
   - Q:    N=0→1, Q value 用 +1 更新
   - X:    N=8→9, Q value 用 +1 更新
   - A:    N=15→16, Q value 用 +1 更新
   - ROOT: N=20→21, Q value 用 +1 更新

迭代 K 之后:

      ROOT (N=21)
      /         \
    A (N=16)   B (N=5)
    /  \         |
  X(N=9) Y(N=7) Z(N=5)
  /
Q (N=1, Q=+1) ← 新加进来的 node

为什么 random rollout 能给好信号 — LLN 视角

单次 random rollout 的 $R$ 很 noisy (赢 / 输 / 平差距 2), 但大数定律 (LLN) 保证 N 次 $R$ 的均值会收敛到真实期望:

\bar{R}_N = \frac{1}{N} \sum_{i=1}^{N} R_i \xrightarrow{N \to \infty} \mathbb{E}[R \mid \text{leaf state}, \pi_{\text{random}}]

而且偏差按 $\frac{1}{\sqrt{N}}$ 衰减 (CLT); N=1000 时噪声只剩 ~0.03, 足够把"强 node vs 弱 node" 的方向性信号挖出来;

注意: MCTS 估的不是两人都最优时的 minimax value, 而是两人都 random 时的 expected outcome; 这两者不一样, 但相关性强 — 真正强的 state, 即使两边都瞎下, 强的一方平均仍更可能赢; noisy 但 directionally correct;

UCT 公式 (Selection 阶段的 smart descent)

UCT = Upper Confidence bounds applied to Trees, 由 Kocsis & Szepesvári (2006) 引入; 它决定 Selection 阶段从当前 node 走哪个 child:

\text{UCT}(s, a) = \underbrace{Q(s, a)}_{\text{exploit}} + c \cdot \underbrace{\sqrt{\frac{\ln N(s)}{N(s, a)}}}_{\text{explore}}

Exploit term $Q(s, a)$ : 这个 child 历史平均胜率, 越高越想选 (利用已知好的)
Explore term $c \sqrt{\ln N(s) / N(s, a)}$ : 这个 child 越少被访问 (即 $N(s, a)$ 越小), 这一项越大, 越想去试试 (探索冷门的)
$c$ : 调节 exploit / explore 平衡的超参数, 经典经验值 $c = \sqrt{2}$

每到一个 in-tree node, 从所有 child 里选 UCT 最大的那个, 一路下去到 leaf;

直观: $N$ 小的 child 会被 explore term 抬高优先级, 即使 $Q$ 一般也有机会被访问; 一旦反复访问后 $N$ 变大, explore term 衰减到忽略, exploit 占主导, 留下的就是真正强的 child;

UCT 是 MCTS 智能性的源头 — Selection 是 smart 的, Simulation 是 fast 的, 两者协作就是 MCTS 的本质;

MCTS 的几种重要变种

变种	Simulation 阶段做什么	来源
Classical MCTS	uniform random rollout 到 terminal	Coulom 2006
Heavy rollout	hand-crafted heuristic 引导 rollout (不是纯随机)	Go AI 早期 (MoGo, CrazyStone)
AlphaGo	NN policy 引导 rollout + NN value 估值	Silver 2016
AlphaGo Zero / AlphaZero	完全去掉 rollout, 只用 NN value head 估 leaf value	Silver 2017
LATS	完全去掉 rollout, 用 LLM verbal feedback 当 leaf value	Zhou 2024

注意 AlphaGo Zero 起改名 “MCTS” 已经不严格 “Monte Carlo” 了 — 因为没有 random sampling, 只有 NN 估值; 但骨架还是 4 phase, 大家继续叫它 MCTS;

一些 mental model 要 internalize

“Visited” 有两层语义

层	含义	何时发生
Tree-membership	这个 node 在不在 tree 里; binary; 由 Expansion 一次性决定	Expansion 阶段
Visit count $N(v)$	这个 in-tree node 被多少次 iteration 的 backprop path 经过; integer; 每次 backprop 经过就 +1	Backpropagation 阶段

“Unvisited node” 指还没被 Expansion 加进 tree 的候选 child, 不是 " $N = 0$ 的 in-tree node";

State 必须 Markov

Simulation 从 leaf $L$ 出发时只看 $L$ 的 state, 不看 history; 这依赖 Markov property:

P(\text{next state} \mid \text{current state}) = P(\text{next state} \mid \text{current state}, \text{history})

要求 state 是 self-contained 的 — 棋盘位置 + 当前轮到谁 + 任何 history flag (chess castling 权, en passant 等) 都在 state 里; 设计不当的 state 让 simulation 出 bug, 这是 MCTS 实现的常见隐性 trap;

Backprop = Selection path 的反向

1
2
3

Selection (向下): ROOT → A → X → in_tree_leaf
Expansion: in_tree_leaf 加 L_new
Backprop (向上): L_new → in_tree_leaf → X → A → ROOT

backprop 用同一个 rollout 的 $R$ 更新 path 上所有 in-tree 祖先;

零和博弈下 backprop 时要按 node 的回合翻 $R$ 的符号 (negamax style); 单 agent 任务 (LATS / 推理) 不翻;

一次 rollout vs 多次 rollout

维度	一次 rollout 内部	跨多次 iteration
每步是否 random	✅ uniform random	—
每步是否重复	❌ 单次走过就走过, 不重复	—
Leaf $L$ 是否被多次访问	—	✅ Selection 反复走到 $L$ , 每次 rollout 拿不同 $R$
平均产生胜率估计	—	✅ LLN 把 $N$ 次 $R$ 平均出 $L$ 的 Q value

修正常见 misconception

❌ 错觉	✅ 实际
“rollout 经过的所有 state 都加进 tree”	rollout 经过的 state 全部丢弃, 只保留终局 R; tree 只通过 Expansion 长
“MCTS 每步都重复 random play”	一次 rollout 内每步只走 1 次; 重复发生在跨多次 iteration
“MCTS 不考虑对手”	Selection 严格建模对手 (smart); Simulation 阶段对手 random; 是"妥协地建模"而非"不考虑"
“minimax 是看 2 步”	工程上是 depth-limited 2-N 步; 理论上 minimax 看到终局
“Simulation 需要 last action 信息”	不需要; state 是 Markov self-contained, last action 的效果已经在 state 里