2026-01-22

Monte Carlo Tree Search

Try Interactive Demo / 试一试交互式演示

AlphaGo的决策大脑：蒙特卡洛树搜索详解

2016年，AlphaGo击败了世界围棋冠军李世石，震惊了整个世界。在这个历史性胜利的背后，有一个关键算法——蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）。

围棋的搜索空间有 $10^{170}$ 种可能，比宇宙中的原子数量还多。传统的穷举搜索完全无法胜任。MCTS提供了一种智能的解决方案：通过随机模拟和统计分析，在巨大的搜索空间中找到最优决策。

核心思想

MCTS的核心思想可以用一句话概括：

“通过反复模拟游戏，统计哪些走法更可能获胜”

想象你在下棋，不确定下一步该怎么走。你可以：

尝试每种走法
从那里开始，随机下完整局游戏
记录哪些走法最终赢了
选择胜率最高的走法

这就是MCTS的基本思路！

四个阶段

MCTS的每次迭代包含四个阶段：

1. 选择（Selection）

从根节点开始，使用某种策略选择子节点，直到到达一个未完全展开的节点。

最常用的选择策略是UCB1（Upper Confidence Bound）：

UCB1 = \frac{W_i}{N_i} + c\sqrt{\frac{\ln N}{N_i}}

其中：

$W_i$ ：节点i的累计胜利次数
$N_i$ ：节点i的访问次数
$N$ ：父节点的访问次数
$c$ ：探索参数（通常取 $\sqrt{2}$ ）

第一项代表利用（选择已知好的），第二项代表探索（尝试未充分测试的）。

2. 扩展（Expansion）

在选定的节点上，添加一个或多个子节点，代表可能的下一步行动。

3. 模拟（Simulation）

从新节点开始，进行随机游戏直到终局。这个过程也叫”rollout”或”playout”。

简单的MCTS使用完全随机的模拟，而更高级的版本会使用启发式策略来指导模拟。

4. 反向传播（Backpropagation）

将模拟结果（胜/负）沿着路径向上传递，更新所有经过节点的统计信息。

根节点
  ├─ 子节点A（胜率: 60%, 访问: 100次）
  │    ├─ 孙节点A1（胜率: 70%, 访问: 40次）
  │    └─ 孙节点A2（胜率: 50%, 访问: 60次）
  └─ 子节点B（胜率: 40%, 访问: 80次）

为什么MCTS有效？

1. 渐进最优

随着模拟次数增加，MCTS会收敛到最优策略。

2. 无需评估函数

不像传统搜索需要手工设计评估函数，MCTS只需要游戏规则和终局判断。

3. 平衡探索与利用

UCB公式自动平衡尝试新走法和深化已知好走法。

4. 任意时间停止

可以在任何时候停止搜索并返回当前最佳走法。

MCTS + 神经网络 = AlphaGo

AlphaGo的创新在于将MCTS与深度神经网络结合：

策略网络：预测每个走法的概率，指导树搜索的方向
价值网络：评估棋盘状态的胜率，替代或辅助随机模拟

UCB_{AlphaGo} = Q(s,a) + c \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}

这种结合大大提高了搜索效率和决策质量。

应用场景

1. 棋类游戏

围棋（AlphaGo）
国际象棋
将棋

2. 视频游戏

实时策略游戏
回合制游戏

3. 规划问题

机器人路径规划
自动驾驶决策
资源调度

4. 其他领域

程序合成
定理证明
分子设计

MCTS的变体

1. RAVE（Rapid Action Value Estimation）

利用同一动作在不同状态的统计信息，加速学习。

2. Progressive Widening

限制每个节点的子节点数量，适用于连续动作空间。

3. Parallel MCTS

并行化搜索，充分利用多核CPU。

优缺点

优点：

不需要领域知识（可以直接用规则）
能处理高分支因子的游戏
天然支持任意时间决策
易于并行化

缺点：

对于深度很大的游戏可能收敛慢
随机模拟可能不够准确
需要大量迭代才能获得好的估计

MCTS代表了一种优雅的思想：在不确定的世界中，通过大量随机尝试和统计分析，我们可以做出明智的决策。这种思想不仅适用于游戏，也启发着更广泛的AI决策问题。

The Decision-Making Brain of AlphaGo: Understanding Monte Carlo Tree Search

In 2016, AlphaGo defeated world Go champion Lee Sedol, shocking the entire world. Behind this historic victory was a key algorithm—Monte Carlo Tree Search (MCTS).

The search space of Go has $10^{170}$ possibilities, more than the number of atoms in the universe. Traditional exhaustive search is completely inadequate. MCTS provides an intelligent solution: through random simulation and statistical analysis, finding optimal decisions in a huge search space.

Core Idea

The core idea of MCTS can be summarized in one sentence:

“Through repeated game simulations, statistically determine which moves are more likely to win”

Imagine you’re playing chess, unsure of your next move. You could:

Try each possible move
From there, play the game randomly to the end
Record which moves eventually won
Choose the move with the highest win rate

This is the basic idea of MCTS!

Four Phases

Each MCTS iteration contains four phases:

1. Selection

Starting from the root node, use some policy to select child nodes until reaching a node that is not fully expanded.

The most common selection policy is UCB1 (Upper Confidence Bound):

UCB1 = \frac{W_i}{N_i} + c\sqrt{\frac{\ln N}{N_i}}

Where:

$W_i$ : Cumulative wins at node i
$N_i$ : Visit count of node i
$N$ : Visit count of parent node
$c$ : Exploration parameter (usually $\sqrt{2}$ )

The first term represents exploitation (choosing known good options), the second represents exploration (trying insufficiently tested options).

2. Expansion

At the selected node, add one or more child nodes representing possible next actions.

3. Simulation

From the new node, play a random game until the end. This process is also called “rollout” or “playout.”

Simple MCTS uses completely random simulation, while more advanced versions use heuristic policies to guide simulation.

4. Backpropagation

Propagate the simulation result (win/loss) up the path, updating statistics of all nodes along the way.

Root Node
  ├─ Child A (Win rate: 60%, Visits: 100)
  │    ├─ Grandchild A1 (Win rate: 70%, Visits: 40)
  │    └─ Grandchild A2 (Win rate: 50%, Visits: 60)
  └─ Child B (Win rate: 40%, Visits: 80)

Why Does MCTS Work?

1. Asymptotically Optimal

As the number of simulations increases, MCTS converges to the optimal policy.

2. No Evaluation Function Needed

Unlike traditional search requiring hand-designed evaluation functions, MCTS only needs game rules and terminal state judgment.

3. Balances Exploration and Exploitation

The UCB formula automatically balances trying new moves and deepening known good moves.

4. Anytime Stoppable

Can stop searching at any time and return the current best move.

MCTS + Neural Networks = AlphaGo

AlphaGo’s innovation combined MCTS with deep neural networks:

Policy Network: Predicts probability of each move, guiding tree search direction
Value Network: Evaluates board state win rate, replacing or supplementing random simulation

UCB_{AlphaGo} = Q(s,a) + c \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}

This combination greatly improved search efficiency and decision quality.

Applications

1. Board Games

Go (AlphaGo)
Chess
Shogi

2. Video Games

Real-time strategy games
Turn-based games

3. Planning Problems

Robot path planning
Autonomous driving decisions
Resource scheduling

4. Other Domains

Program synthesis
Theorem proving
Molecular design

MCTS Variants

1. RAVE (Rapid Action Value Estimation)

Uses statistics of the same action in different states to accelerate learning.

2. Progressive Widening

Limits the number of children per node, suitable for continuous action spaces.

3. Parallel MCTS

Parallelizes search to fully utilize multi-core CPUs.

Advantages and Disadvantages

Advantages:

No domain knowledge needed (can use rules directly)
Can handle games with high branching factor
Naturally supports anytime decisions
Easy to parallelize

Disadvantages:

May converge slowly for very deep games
Random simulation may not be accurate enough
Requires many iterations for good estimates

MCTS represents an elegant idea: in an uncertain world, through many random trials and statistical analysis, we can make wise decisions. This thinking applies not only to games but also inspires broader AI decision-making problems.