蒙特卡洛树搜索 Monte Carlo Tree Search (MCTS)

1. MCTS 概述

蒙特卡洛树搜索 (Monte Carlo Tree Search, MCTS) 是一种用于决策的启发式搜索算法，广泛应用于围棋（AlphaGo）、象棋等博弈场景。MCTS 的核心思想是通过反复模拟（simulation）来评估每个可能的动作，逐步构建一棵搜索树。

每次模拟的四个步骤

MCTS 的每一次模拟 (simulation) 包含 4 个步骤，循环执行：

步骤	名称	核心任务
1	Selection 选择	决定探索哪个动作
2	Expansion 扩展	模拟对手的响应，生成新状态
3	Evaluation 评估	评估新状态的优劣
4	Backup 回传	将评估结果回传更新 Q 值

重要：Steps 1-3 中的动作都是虚拟的（imaginary），不会实际执行。只有在 MCTS 全部模拟结束后，才做出真正的决策。

MCTS 4 steps overview

2. Step 1: Selection 选择

2.1 问题

观察到状态 $S_t$ ，应该探索哪个动作？

2.2 选择公式

对所有合法动作 $a$ ，计算得分：

$\text{score}(a) = Q(a) + \eta \cdot \frac{\pi(a|S_t; \theta)}{1 + N(a)}$

选择得分最大的动作：

$a^* = \arg\max_a \text{score}(a)$

2.3 公式各项解释

符号	含义
$Q(a)$	MCTS 计算的动作价值（初始为 0）
$\pi(a	S_t; \theta)$
$N(a)$	在状态 $S_t$ 下，动作 $a$ 被选中的次数
$\eta$	探索超参数

2.4 选择公式的两个组成部分

$\text{score}(a) = \underbrace{Q(a)}_{\text{利用 (exploitation)}} + \underbrace{\eta \cdot \frac{\pi(a|S_t; \theta)}{1 + N(a)}}_{\text{探索 (exploration)}}$

利用项 $Q(a)$ ：Q 值越高，说明这个动作历史上表现越好，倾向于再选它
探索项：策略先验概率 $\pi$ 越大且访问次数 $N(a)$ 越少的动作，得分越高，鼓励尝试新动作

这与 UCB (Upper Confidence Bound) 的思想一致：在利用已知好动作和探索未知动作之间取得平衡。

Step 1 Selection

3. Step 2: Expansion 扩展

3.1 问题

选择动作 $a_t$ 后，对手会怎么响应？新状态是什么？

3.2 状态转移

给定玩家选择了动作 $a_t$ ，对手的动作 $a_t'$ 将导致新状态 $S_{t+1}$ ：

$S_t \xrightarrow{a_t} \text{opponent} \xrightarrow{a_t'} S_{t+1}$

3.3 对手动作的模拟

对手的动作从策略网络中随机采样：

$a_t' \sim \pi(\cdot | s_t'; \theta)$

其中 $s_t'$ 是对手观察到的状态。

3.4 用策略网络近似状态转移

在真实环境中，状态转移概率 $p(s_{t+1}|s_t, a_t)$ 通常是未知的。MCTS 用策略函数 $\pi$ 作为状态转移函数 $p$ 的近似：

$p(s_{t+1}|s_t, a_t) \approx \pi(a_t'|s_t'; \theta)$

这意味着：对手的每个可能动作 $a_t'$ 对应一个转移概率（即策略输出的概率），最终到达的新状态由这个概率决定。

Step 2 Expansion

4. Step 3: Evaluation 评估

4.1 问题

新状态 $S_{t+1}$ 有多好？

4.2 Rollout（推演到终局）

从 $S_{t+1}$ 开始，用策略网络模拟游戏直到结束（时间步 $T$ ）：

$\text{For } k = t+1, t+2, \ldots, T:$

玩家动作： $a_k \sim \pi(\cdot | s_k; \theta)$
对手动作： $a_k' \sim \pi(\cdot | s_k'; \theta)$
在终局获得奖励 $r_T$ $r_{T}$ ：
- 胜利： $r_T = +1$
- 失败： $r_T = -1$

4.3 综合评分

最终评分结合了价值网络的即时估计和rollout 的终局奖励：

$V(s_{t+1}) = \frac{1}{2} \, v(s_{t+1}; w) + \frac{1}{2} \, r_T$

其中：

$v(s_{t+1}; w)$ ：价值网络 (value network) 对状态 $s_{t+1}$ 的即时评估
$r_T$ ：rollout 到终局后得到的实际奖励

设计思想：价值网络提供快速的短期评估，rollout 提供准确但昂贵的长期评估，两者的平均是一种平衡。

Step 3 Evaluation

5. Step 4: Backup 回传

5.1 问题

如何利用评估结果 $V(s_{t+1})$ 来更新搜索树？

5.2 更新规则

MCTS 会重复模拟多次。对于动作 $a_t$ 产生的每个子状态，都有多条记录的 $V$ 值。更新动作价值为这些记录的均值：

$Q(a_t) = \text{mean}(\text{recorded } V\text{'s for } a_t)$

展开写：

$Q(a_t) = \frac{1}{N(a_t)} \sum_{i=1}^{N(a_t)} V^{(i)}(s_{t+1})$

其中 $N(a_t)$ 是动作 $a_t$ 的总选择次数， $V^{(i)}$ 是第 $i$ 次模拟记录的评估值。

5.3 搜索树的更新

      s_t
     / | \
    /  |  \
  a_t^(1)  a_t^(2)  a_t^(3)
   |        |        |
Records:  Records:  Records:
V₁⁽¹⁾    V₁⁽²⁾    V₁⁽³⁾
V₂⁽¹⁾    V₂⁽²⁾    V₂⁽³⁾
V₃⁽¹⁾    V₃⁽²⁾    ...
...      ...

每完成一次模拟，对应动作的记录中就新增一条 $V$ 值，Q 值随之更新。

5.4 Q 值的用途

更新后的 $Q(a)$ 将在下一次模拟的 Step 1 (Selection) 中使用，形成闭环。

Step 4 Backup

6. MCTS 循环

6.1 多次模拟

MCTS 不是只做一次模拟就结束，而是重复执行多次上述 4 个步骤。每一次模拟都从当前状态 $S_t$ 出发，沿搜索树向下探索。

for simulation = 1, 2, ..., M:
    Step 1: Selection    → 根据 score(a) = Q(a) + η·π/(1+N(a)) 选择动作
    Step 2: Expansion    → 用策略网络模拟对手，得到新状态
    Step 3: Evaluation   → Rollout + 价值网络，得到 V(s_{t+1})
    Step 4: Backup       → 用 V 更新 Q(a)，Q 用于下一次 Selection

6.2 随模拟次数增长的搜索树

随着模拟次数增加：

$N(a)$ 增大 → 探索项减小 → 逐渐从探索转向利用
$Q(a)$ 收敛 → 动作价值估计越来越准确
搜索树越来越深、越来越广

6.3 Revisit Selection

在有了多次模拟的 Q 值之后，Step 1 的选择会变得更加准确：

$\text{score}(a) = \underbrace{Q(a)}_{\text{越来越准确}} + \underbrace{\eta \cdot \frac{\pi(a|S_t; \theta)}{1 + N(a)}}_{\text{探索项逐渐减小}}$

Revisit Selection

7. 决策：MCTS 之后的选择

7.1 问题

MCTS 执行了 $M$ 次模拟之后，玩家应该做出什么真正的决策？

7.2 基于访问次数的决策

与模拟中使用 Q 值 + 探索项的选择不同，最终决策直接使用访问次数：

$a_t = \arg\max_a N(a)$

7.3 为什么用访问次数而不是 Q 值？

方式	公式	问题
Q 值	$\arg\max_a Q(a)$	可能受噪声影响，方差大
访问次数	$\arg\max_a N(a)$	更鲁棒，被选最多次的动作综合表现最好

访问次数本身就是 Q 值和探索的综合结果——Q 值高的动作会被反复选择，因此 $N(a)$ 大的动作本质上就是 MCTS 认为最好的动作。

Decision Making after MCTS

8. 概念关系总结

MCTS 完整流程

┌─────────────────────────────────────────────────────────────┐
│                 Monte Carlo Tree Search                     │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│   观察当前状态 S_t                                           │
│         ↓                                                   │
│   ┌─────────────────────────────────────────────┐          │
│   │  重复 M 次模拟                               │          │
│   │                                             │          │
│   │  ┌─ Step 1: Selection ──────────────────┐   │          │
│   │  │ score(a) = Q(a) + η·π(a|S_t;θ)/(1+N) │   │          │
│   │  │ 选择 score 最大的 a（虚拟动作）       │   │          │
│   │  └──────────────┬──────────────────────┘   │          │
│   │                 ↓                           │          │
│   │  ┌─ Step 2: Expansion ─────────────────┐   │          │
│   │  │ 对手: a' ~ π(·|s'; θ)               │   │          │
│   │  │ 得到新状态 S_{t+1}                   │   │          │
│   │  └──────────────┬──────────────────────┘   │          │
│   │                 ↓                           │          │
│   │  ┌─ Step 3: Evaluation ─────────────────┐  │          │
│   │  │ Rollout 到终局 → r_T (+1/-1)         │  │          │
│   │  │ V(s_{t+1}) = ½v(s_{t+1};w) + ½r_T  │  │          │
│   │  └──────────────┬──────────────────────┘   │          │
│   │                 ↓                           │          │
│   │  ┌─ Step 4: Backup ─────────────────────┐  │          │
│   │  │ Q(a_t) = mean(recorded V's)          │  │          │
│   │  │ 更新 N(a_t) ← N(a_t) + 1             │  │          │
│   │  └───────────────────────────────────────┘  │          │
│   └─────────────────────────────────────────────┘          │
│         ↓                                                   │
│   最终决策: a_t = argmax_a N(a)（真正执行）                 │
│                                                             │
└─────────────────────────────────────────────────────────────┘

MCTS 与神经网络的关系

┌──────────────────────────────────────────────┐
│           神经网络 (预训练)                    │
│                                              │
│  策略网络 π(a|s; θ)     价值网络 v(s; w)    │
│       ↓                      ↓               │
│  · Selection 的先验概率    · Evaluation 的    │
│  · Expansion 的状态转移      即时评估         │
│                              ↓               │
│                          · 与 rollout r_T    │
│                            平均 → V(s)      │
└──────────────────────────────────────────────┘

MCTS vs 纯策略网络

数学符号汇总

符号	含义
$S_t$	当前状态
$a_t$	玩家动作（虚拟/真实）
$a_t'$	对手动作（虚拟）
$s_t'$	对手观察到的状态
$S_{t+1}$	扩展后的新状态
$\pi(a\\|s; \theta)$	策略网络（先验概率）
$v(s; w)$	价值网络
$Q(a)$	MCTS 计算的动作价值
$N(a)$	动作 $a$ 的累计访问次数
$\text{score}(a)$	选择得分
$\eta$	探索超参数
$V(s_{t+1})$	综合评估分数
$r_T$	终局奖励（+1/-1）
$M$	MCTS 模拟总次数

核心公式速查

1. Selection（选择公式）