MCTS 与 AlphaGo：搜索即策略

本文基于模型知识整理（生成时未联网核对），关键结论建议对照 Silver et al. 2016/2017/2018（AlphaGo/Zero/MuZero）复核。

一句话定义

蒙特卡洛树搜索（MCTS）在每个决策点用"选择→扩展→评估→回传"四步迭代构建当前状态的不对称搜索树，UCB 公式平衡"利用高价值分支"与"探索冷门分支"；AlphaGo/AlphaZero 把神经网络（策略先验+价值评估）注入 MCTS，搜索结果反过来当训练目标——"网络指导搜索，搜索教育网络"的自我强化循环击败了人类围棋。

为什么重要

AlphaGo（2016）是 RL 的公共事件：它演示了"模型+搜索+学习"三件套的组合威力，并证明搜索本身就是策略改进算子——同一网络在搜索加持下棋力倍增。MuZero 进一步证明连规则（模型）都可以学出来，把这条路线推广到 Atari 等未知规则环境。

前置知识

kp-005（值迭代/GPI）、kp-006（UCB）、kp-020（模型与规划）。

核心概念

• MCTS 四步循环（重复 N 次）：

1. 选择：从根沿树下行，每节点按 $UCT = \frac{Q(s,a)}{N(s,a)} + c\sqrt{\frac{\ln N(s)}{N(s,a)}}$ 挑子分支（利用+探索，kp-006 的 UCB 移植到树上）； 2. 扩展：到达叶节点，加入新节点； 3. 评估：旧版随机 rollout 到终局，神经网络版直接用价值网络 $v(s)$ 打分； 4. 回传：把评估值沿路径累加更新各节点的 W/N。

• PUCT（AlphaGo 版 UCT）：$UCT = Q(s,a) + c_{puct} P(s,a)\frac{\sqrt{N(s)}}{1+N(s,a)}$——先验概率 P 由策略网络给出，搜索朝"网络觉得有戏"的方向倾斜。
• 自我强化闭环：MCTS 输出的访问频率分布是比原始网络更强的策略（搜索即策略改进）→ 用它作目标训练策略网络 → 更强的先验 → 更高效的搜索。
• AlphaZero vs AlphaGo：去掉人类棋谱（纯自我对弈）、去掉 rollout（价值网络直接评估）、单一网络多任务（策略+价值双头）。
• MuZero：连环境模型也学（隐空间动力学），搜索在想象的隐空间中进行——模型基 RL 与搜索的合体（kp-020/022）。

原理与机制

为什么 MCTS 是"聚焦式 DP"：值迭代（kp-005）均匀遍历全状态空间；MCTS 把计算预算集中在"当前局面可达的子树"——用 UCB 的对数探索保证根节点的价值估计收敛到真值，且越接近根越准（恰好是最需要的部分）。它是"只要当前决策最优"这一需求的完美匹配。

为什么搜索能改进网络：MCTS 相当于"以网络为先验的深度计算增强"——有限网络先验+海量模拟推演出比原网络更准的行动分布（访问率收敛于根节点的改进策略）。这个"policy improvement by search"是 AlphaZero 棋力闭环的发动机；训练目标因此是搜索后的分布而非对局实际落子。

自我对弈的收敛担忧：自我博弈是移动目标的非平稳学习，理论上可能陷入循环（石头剪刀布式）；AlphaZero 的实践答案：确定性收敛不是必要条件，用训练-评估对弈的内部联赛（purification of skill）把"最新最强"作为标准即可。

图示

每个决策点:
 选择: a* = argmax [ Q/N + c·P·√N_parent/(1+N) ]  沿树下探
 扩展: 叶节点入树
 评估: v_θ(s_leaf)   (AlphaZero: 无rollout)
 回传: 路径上 N+=1, W+=v
决策: 根节点按访问频率(softmax温度)落子
训练: π_target = 搜索访问率;  z = 对局结果 → 双头监督

直观类比

AlphaZero 是"一个自己会复盘的棋手"：每步棋先用棋感（策略网络）圈定几个候选，再在脑内把每个候选往后推演几十上百局（MCTS，价值网络替它估"推演到的局面谁优"），推演结论又回头修正棋感。棋感与推演互相喂养，越练越强——且完全不需要人类棋谱。

实例或案例

• AlphaGo 2016 击败李世石（4:1）；AlphaGo Zero（2017）从零训练 40 天超越所有前代，证明人类知识非必需。
• MuZero（2019）：未知规则的 Atari/围棋/国际象棋统一处理——隐空间模型 + 搜索。
• 工程外溢：MCTS 思想进入组合优化（芯片布局、定理证明）与 LLM 推理（树搜索解码/MCTS+LLM 组合）。

常见误区

• 误区一："AlphaZero 靠算力暴力"。算力之外，结构性创新（无 rollout、搜索目标训练、双头单网）才是样本效率的来源；同等算力的朴素 MCTS 远不可及。
• 误区二："MCTS 保证最优"。它收敛于真值的速度取决于先验与评估质量；先验歪会系统性浪费搜索预算——"网络指导搜索"也是风险（搜索只能放大网络判断）。
• 误区三："自我对弈会退化"。非平稳但实践中技能单调上升（有评估对弈兜底）；真正的失败模式是奖励 hacking 型策略循环（kp-027），需要规则约束。

与其他知识点的关系

• kp-005/006：值迭代与 UCB 是 MCTS 的两个直系祖先。
• kp-020：MuZero 是模型基与搜索的合流。
• kp-032：AlphaZero 案例的完整工程拆解。
• kp-013：搜索后的访问分布作为策略目标，本质是策略蒸馏。

自测题

1. 写出 MCTS 的四步循环与 UCT 公式。

答：选择（UCT 最大化：利用 Q/N + 探索 c√(lnN_parent/N)）→ 扩展（叶入树）→ 评估（v 网络/rollout）→ 回传（W/N 更新）。

1. AlphaZero 相比 AlphaGo 砍掉了什么？换来什么？

答：砍掉人类棋谱与 rollout，价值网络直接评估；换来纯自我对弈的通用性（不依赖人类知识）与更快更强的训练闭环。

1. "搜索即策略改进"如何体现在训练目标上？

答：策略网络的学习目标是 MCTS 的访问频率分布（比原网络更强的改进策略），而非对局实际动作——搜索结果蒸馏回网络。

延伸阅读

• Silver 等, "Mastering the game of Go with deep neural networks and tree search"（Nature 2016）。
• Silver 等, "Mastering the game of Go without human knowledge"（Nature 2017，AlphaGo Zero）。
• Schrittwieser 等, "Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model"（MuZero, 2019）。
• Browne 等, "A Survey of Monte Carlo Tree Search Methods"（2012，MCTS 综述）。