从蒙特卡洛评估到 UCT：计算机如何学会下围棋

课程定位：本文将马少平《跟我学 AI·计算机是如何学会下棋的（四）》上下两部分的 AI 字幕与 PPT 合并整理，并对 ASR 错误、公式记号和算法细节进行专业校正。它不是逐字稿，而是一篇可独立阅读的教学型技术博客。

阅读目标

读完本文，应当能够解释以下问题：

1. 为什么传统的 Alpha-Beta 搜索在围棋上长期表现不佳；
2. 如何用随机对局估计一个棋局的胜率；
3. 为什么纯蒙特卡洛评估还不够，必须组织成搜索树；
4. MCTS 的选择、扩展、模拟、回传分别做什么；
5. UCB1 如何平衡探索与利用，UCT 又如何把它放进搜索树；
6. 二人零和博弈中，胜负结果应该怎样回传；
7. MCTS 与强化学习、AlphaGo、AlphaZero 之间到底是什么关系。

0. 字幕纠错与技术校准

AI 字幕中出现了大量同音替换。本文统一采用下列术语：

ASR 原文或近似识别	正确术语	说明
阿菲贝德减脂、阿菲菲剪枝	Alpha-Beta 剪枝	极小极大搜索的剪枝算法
维基、v7、问题	围棋	由语境确定
搜索数、蒙特卡洛数	搜索树、蒙特卡洛树	tree 被识别成“数”
蒙德卡洛、蒙斯塔罗	蒙特卡洛	Monte Carlo
普风投针、普通投针	蒲丰投针	Buffon’s needle
可若子点	可落子点	合法动作
副节点、附近节点	父节点	parent node
此节点、直接点	子节点	child node
多比老虎机	多臂老虎机	multi-armed bandit
信心上舰、信息上限	置信上界 / 信心上限	Upper Confidence Bound
信息上限数	置信上界树 / 信心上限树	UCT
UCD、UCDE、UGT	UCT	Upper Confidence bounds applied to Trees
上传、飞船	回传	backpropagation / backup
收益、回报	回报 / 累积奖励	return / reward
相机功能	评价函数	evaluation function

三处需要补充限定的课程表述

第一，“状态多不是本质原因”不能按字面绝对化。 围棋的高分支因子、搜索深度和状态规模确实是 Alpha-Beta 难以奏效的核心计算原因；与此同时，围棋局面难以构造稳定、精确的人工评价函数，使得有限深度搜索缺少可靠的叶节点估值。严格说，这是“搜索规模巨大”和“局面评价困难”共同造成的，而不是二选一。

第二，MCTS 不是每一步都随机。 经典 MCTS 中，树内的 selection 通常由 UCT 等树策略控制；随机性主要出现在尚未展开区域的 rollout / default policy。现代系统甚至会用策略网络替代近乎纯随机的 rollout。

第三，搜索结束后的最终动作不一定取经验胜率最高。 课程 PPT 为便于入门，采用“选择胜率最大子节点”的说法。实际工程中常选访问次数最多的根子节点，即 robust child，因为它通常比直接比较高方差的经验均值更稳定。

---

1. 从 Alpha-Beta 的边界说起

Alpha-Beta 剪枝建立在极小极大搜索上：我方选择使收益最大的动作，对手选择使我方收益最小的动作。若能搜索到终局，结论原则上是精确的；现实中搜索深度有限，因此必须在叶节点调用评价函数：

V̂(s)≈V*(s) \hat V(s) \approx V^*(s)

其中 V*(s)V^*(s) 是状态 ss 的真实博弈价值，V̂(s)\hat V(s) 是人工规则或模型给出的近似值。

Alpha-Beta 能否有效，取决于三个条件：

• 分支数不能过大：否则深度每增加一层，节点数指数增长；
• 走法排序较好：越早搜索到强走法，剪枝越充分；
• 叶节点评价足够可靠：否则搜索得再深，也可能在错误的评价基础上作决定。

1.1 象棋的评价函数为什么相对容易构造

国际象棋和中国象棋中的棋子具有较明确的材料价值。评价函数通常可以从以下部分组合：

Eval(s)=Material+Mobility+KingSafety+PawnStructure+⋯ \text{Eval}(s)=\text{Material}+\text{Mobility}+\text{KingSafety}+\text{PawnStructure}+\cdots

“车、马、炮、兵分别值多少分”虽然是近似，但局部棋子的价值具有一定可分解性。搜索进入残局后，棋子数量减少，某些局面甚至可以由残局数据库精确求解。

1.2 围棋为何难以手工评价

围棋的单颗棋子几乎没有固定价值。它的作用取决于：

• 是否连接成块；
• 棋块的气、眼形和死活；
• 对全局实地、厚势和先手的影响；
• 数十手之后是否形成攻击、转换或弃子收益。

因此，围棋评价呈现强烈的非局部性、整体性和长程依赖。早期程序很难把职业棋手的直觉压缩成稳定的手工公式。

课程中关于“左脑逻辑、右脑形象”的说法属于早期通俗化解释，不宜作为现代神经科学的严格结论。更可靠的算法表述是：围棋需要复杂的空间模式识别和长程价值判断，而早期基于符号规则的程序在这些方面能力有限。

---

2. 蒙特卡洛方法：把求解变成统计估计

蒙特卡洛方法不是某一个具体算法，而是一类共同思想：

当目标难以直接解析求解时，构造可采样的随机过程，通过重复实验的统计量估计目标值。

设随机变量 XX 的期望为 μ\mu，独立采样得到 X1,…,XNX_1,\dots,X_N，则样本均值为：

μ̂N=1N∑i=1NXi \hat\mu_N=\frac{1}{N}\sum_{i=1}^N X_i

在适当条件下，随着 NN 增大，μ̂N\hat\mu_N 会趋近于 μ\mu。其标准误差通常按 O(1/N)O(1/\sqrt N) 缩小。这意味着：若想把随机误差缩小一半，采样量通常要增加到约四倍。

2.1 蒲丰投针：用随机实验估计 π\pi

设平行线间距为 dd，针长为 ll，且 l≤dl\le d。令：

• x∈[0,d/2]x\in[0,d/2]：针中心到最近平行线的距离；
• α∈[0,π]\alpha\in[0,\pi]：针与平行线的夹角。

针与直线相交的条件是：

x≤l2sinα x\le \frac{l}{2}\sin\alpha

在 (α,x)(\alpha,x) 参数空间中，相交事件对应曲线下方区域。概率为：

P(相交)=∫0πl2sinαdαπ⋅d/2=2lπd P(\text{相交}) =\frac{\int_0^\pi \frac{l}{2}\sin\alpha\,d\alpha}{\pi\cdot d/2} =\frac{2l}{\pi d}

若共投针 nn 次，其中 mm 次相交，则：

mn≈2lπd⇒π≈2lndm \frac{m}{n}\approx \frac{2l}{\pi d} \quad\Longrightarrow\quad \pi\approx \frac{2ln}{dm}

这个例子最重要的不是用它高精度计算 π\pi，而是理解转换方式：把一个待求常数写成随机事件概率，再用频率估计概率。

---

3. 棋局的纯蒙特卡洛评估

设当前棋局为状态 ss。最直接的蒙特卡洛评估方法是：

1. 从 ss 出发；
2. 双方按照某个 rollout policy 交替落子；
3. 直到终局；
4. 将胜、负、和映射成回报，例如 +1,−1,0+1,-1,0；
5. 重复 NN 次，计算平均回报。

V̂(s)=1N∑i=1NGi \hat V(s)=\frac{1}{N}\sum_{i=1}^N G_i

若只记录我方胜负，且胜为 1、负为 0，则 V̂(s)\hat V(s) 就是经验胜率。

3.1 这种估计解决了什么

它绕开了“如何手工写出围棋评价函数”的难题。程序不必准确解释某块棋为什么厚、某一步为什么有先手，只需要能够：

• 生成合法走法；
• 执行完整对局；
• 判断终局结果。

3.2 纯随机 rollout 的主要缺陷

纯随机棋局包含大量明显不合理的着法，因此存在高方差和系统偏差：

• 好局面可能被随机坏棋毁掉；
• 某些需要精确次序的战术在线性随机模拟中难以出现；
• 不同首着的模拟预算若平均分配，会浪费大量计算。

因此，我们需要同时解决两个问题：

1. 如何把已经得到的模拟结果沿搜索路径复用；
2. 下一次模拟的预算应该分配给哪个分支。

这正是蒙特卡洛树搜索要解决的核心。

---

4. 蒙特卡洛树搜索（MCTS）

MCTS 将状态转移组织成一棵按需增长的树。它不预先展开全部状态，而是不断重复一次“采样—更新”循环，使计算集中到更有希望的区域。

每轮迭代包含四个阶段：

1. Selection（选择）
2. Expansion（扩展）
3. Simulation / Rollout（模拟）
4. Backpropagation / Backup（回传）

4.1 选择：沿树策略向下走

从根节点开始，只要当前节点已经完全展开且不是终局，就根据树策略选择一个子节点继续向下。

目标不是简单选择当前平均胜率最高的节点，而是在两种需求之间平衡：

• 利用（exploitation）：优先搜索目前看起来更好的分支；
• 探索（exploration）：给访问较少、估计仍不确定的分支机会。

4.2 扩展：只增加一个或少量新节点

到达尚未完全展开的节点后，从未尝试动作中选择一个，创建对应子节点。

经典实现通常每轮只扩展一个新节点。这样搜索树的增长与模拟次数近似同步，属于“逐步加深、选择性变宽”。

4.3 模拟：从新节点走到终局

从扩展出的节点开始，使用 default policy 完成对局。最简单的 default policy 是均匀随机合法落子；更强的围棋程序会加入：

• 禁止明显自杀或填真眼；
• 局部吃子、逃跑和模式规则；
• 轻量策略网络；
• 价值网络直接截断 rollout。

4.4 回传：更新整条祖先路径

模拟得到终局回报后，沿路径更新每个节点或边的：

• 访问次数 NN；
• 累积价值 WW；
• 平均价值 Q=W/NQ=W/N。

一次终局模拟由整条路径共享，这就是 PPT 所说“父节点可以利用子节点的模拟结果”。

4.5 Anytime 特性

MCTS 是典型的 anytime algorithm：只要完成过若干轮迭代，随时停止都能返回当前最优估计；预算越多，通常越稳定。这使它天然适合“每步棋最多思考 1 秒或 10 秒”的实时决策。

---

5. 多臂老虎机：探索与利用的最小模型

多臂老虎机有 KK 个拉杆。拉动第 jj 个拉杆会从未知分布中获得随机回报。目标不是只识别最优拉杆，而是在有限次数内最大化累计回报。

它揭示了一个普遍矛盾：

• 反复选择当前均值最高的拉杆，可能过早锁定一个次优选项；
• 均匀探索所有拉杆，又会在明显差的选项上浪费预算。

在 MCTS 的某个父节点上，每个子节点就对应一只“拉杆”；选择该子节点继续模拟，相当于再次拉动该拉杆。

---

6. UCB1：用“均值 + 不确定性”选择拉杆

对第 jj 个拉杆，UCB1 的常见写法为：

UCB1j=X‾j+2lnnnj \operatorname{UCB1}_j =\bar X_j+\sqrt{\frac{2\ln n}{n_j}}

其中：

• X‾j\bar X_j：拉杆 jj 的平均回报；
• nn：所有拉杆的总访问次数；
• njn_j：拉杆 jj 的访问次数。

6.1 第一项：利用

X‾j \bar X_j

平均回报越高，说明历史结果越好，下一次被选择的倾向越强。

6.2 第二项：探索奖励

2lnnnj \sqrt{\frac{2\ln n}{n_j}}

• 当 njn_j 很小时，探索奖励较大；
• 随着 njn_j 增加，该项逐渐衰减；
• lnn\ln n 缓慢增长，使已被忽略的拉杆仍会周期性获得机会。

因此，UCB1 实际比较的是某个拉杆真实均值的“乐观上界”：在不确定时先假设它可能较好，再通过采样消除不确定性。

6.3 初始化与未访问节点

公式在 nj=0n_j=0 时无定义。常见处理方式有两种：

1. 先把每个拉杆至少访问一次；
2. 直接把未访问拉杆的 UCB 设为 +∞+\infty。

6.4 常数为什么有不同写法

工程中常见：

X‾j+clnnnj \bar X_j+c\sqrt{\frac{\ln n}{n_j}}

有的公式把 2 写在根号内，有的吸收到 cc 中。它们并不矛盾，只是参数化习惯不同。比较实验时必须同时说明奖励范围与 cc 的定义。

---

7. UCT：把 UCB1 放进搜索树

UCT 全称为 Upper Confidence bounds applied to Trees。在父节点 ss 选择动作 aa 时，可写为：

UCT(s,a)=Q(s,a)+clnN(s)N(s,a) \operatorname{UCT}(s,a) =Q(s,a)+c\sqrt{\frac{\ln N(s)}{N(s,a)}}

其中：

• Q(s,a)=W(s,a)/N(s,a)Q(s,a)=W(s,a)/N(s,a)：动作的经验平均价值；
• N(s)N(s)：父节点访问次数；
• N(s,a)N(s,a)：该动作或子节点访问次数；
• cc：探索系数。

7.1 cc 的含义

• cc 较小：偏向利用，搜索集中，可能过早陷入当前最优分支；
• cc 较大：偏向探索，树更宽，但对已有强分支投入不足；
• c=0c=0：退化为贪心地选择经验均值最大的子节点。

PPT 的算例令 c=0c=0，只是为了手工演示方便，不代表实际 UCT 应这样设置。

7.2 UCT 不是严格等同于独立老虎机

标准 UCB1 假设每个拉杆的回报分布相对稳定且彼此独立。树搜索中，子节点价值会随着更深层策略改善而变化，兄弟分支也共享结构信息，因此这些假设并不完全成立。UCT 是把 bandit 的乐观选择原则递归应用于树，理论和工程都比静态老虎机更复杂。

---

8. 完整 UCT 流程

课程 PPT 的伪代码可整理为：

function UCT_SEARCH(root_state, budget):
    root ← Node(root_state)

    while budget not exhausted:
        leaf ← TREE_POLICY(root)          # selection + expansion
        reward ← DEFAULT_POLICY(leaf)     # simulation
        BACKUP(leaf, reward)              # backpropagation

    return FINAL_ACTION(root)

TREE_POLICY 的典型逻辑：

function TREE_POLICY(node):
    while node is not terminal:
        if node has unexpanded action:
            return EXPAND(node)
        else:
            node ← argmax_child UCT(node, child)
    return node

8.1 搜索阶段和最终决策阶段要分开

树内选择需要探索奖励：

Q+clnN/n Q+c\sqrt{\ln N/n}

但搜索结束时不再需要探索。常见最终策略是：

a*=argmaxaN(s0,a) a^*=\arg\max_a N(s_0,a)

也就是选访问次数最多的根动作。另一种方法是选 QQ 最大者，但在有限预算下可能更容易被偶然高值误导。

---

9. 回传中的视角：最容易写错的实现细节

二人零和交替博弈中，同一个终局结果对双方符号相反。若黑胜：

• 从黑方视角是 +1+1；
• 从白方视角是 −1-1。

常见的三种一致实现如下。

9.1 固定根玩家视角

所有节点都记录“根玩家”的价值。回传时符号不变，但在对手节点做选择时必须取最小值，或对 QQ 取负。

9.2 当前行动者视角

每个节点记录当前行动者的价值。沿路径每上一层，价值取反：

v←−v v\leftarrow -v

这与 Negamax 的思想一致。

9.3 上一步行动者视角

每个子节点记录“走出该节点的玩家”的收益。由于某个父节点的所有子节点都由同一当前玩家走出，父节点可以直接选择子节点中均值最大的一个。本文后面的 Python 示例采用这种方式。

PPT 中“每个节点都从本节点立场记录胜利次数”的表述可以成立，但“本节点立场”必须在代码中精确定义。若定义混乱，MCTS 会出现对手也在替我方最大化收益的严重错误。

---

10. 读取 PPT 中的 UCT 算例

PPT 用“获胜次数 / 模拟次数”表示节点统计，并令 c=0c=0，因此选择阶段只比较经验胜率。

假设一条选中路径上的节点胜率依次最大，扩展新节点后模拟一次。若新节点视角获胜，则回传时：

• 新节点访问次数加 1，胜利次数加 1；
• 上一层属于对手视角，访问次数加 1，胜利次数不加；
• 再上一层回到我方视角，访问次数和胜利次数都加 1；
• 如此交替直到根节点。

这解释了 PPT 中统计量从：

6/10 → 7/11
3/5  → 3/6
2/3  → 3/4
1/1  → 1/2
new   → 1/1

的变化。重点不是死记数字，而是确保访问次数每层都加一，胜负统计按视角一致更新。

---

11. 为什么 MCTS 比“每个首着独立随机模拟”更有效

设根节点有 BB 个合法动作，纯蒙特卡洛方法可能给每个动作平均分配预算；MCTS 则具备以下优势：

11.1 自适应预算分配

明显差的动作在初步验证后会得到较少预算；强动作与不确定动作得到更多预算。

11.2 层级复用

一次深层模拟不只评估叶节点，也更新整条祖先路径。随着树增长，局部变例被反复利用。

11.3 不需要固定搜索深度

Alpha-Beta 通常按深度迭代；MCTS 按模拟预算运行。不同分支可以自然形成不同深度：战术关键分支更深，价值明确的分支更浅。

11.4 随时可中断

搜索时间耗尽时，已有访问统计可以直接产生动作。

2006 年前后，Coulom 的工作将蒙特卡洛评价与选择性树搜索结合，Kocsis 与 Szepesvári 提出 UCT；Gelly、Wang 等把 UCT 用于 Monte-Carlo Go。早期程序的棋力受棋盘大小、硬件、规则和评级系统影响，不能把“业余四五段”当作统一、精确的跨平台指标，但 MCTS 确实使计算机围棋在较短时期内取得显著跃升。

---

12. MCTS 与强化学习是什么关系

12.1 MCTS 本身首先是一种规划 / 搜索算法

如果环境模型或游戏规则已知，MCTS 可以只在决策时做模拟，不更新任何长期参数。这种情况下，它属于 online planning，不一定构成强化学习。

12.2 它使用了强化学习的核心对象

MCTS 与强化学习共享：

• 状态 ss；
• 动作 aa；
• 环境转移 P(s′∣s,a)P(s’\mid s,a)；
• 奖励 rr；
• 回报 GG；
• 策略 π(a∣s)\pi(a\mid s)；
• 状态价值和动作价值。

纯 rollout 的平均终局收益，本质上是在估计某个策略下的：

Vπ(s)=𝔼π[G∣S0=s] V^\pi(s)=\mathbb E_\pi[G\mid S_0=s]

12.3 MCTS 与学习结合后形成闭环

以 AlphaGo Zero 风格系统为例：

1. 神经网络输出策略先验 P(s,a)P(s,a) 和价值 v(s)v(s)；
2. MCTS 使用网络引导搜索；
3. 搜索访问分布形成改进策略 π\pi；
4. 智能体按 π\pi 自我对弈；
5. 用最终胜负 zz 和搜索策略 π\pi 训练网络；
6. 新网络再引导下一轮搜索。

这是典型的 planning improves learning，learning improves planning。

---

13. 从 UCT 到 AlphaGo / AlphaZero：PUCT

现代神经网络 MCTS 常使用 PUCT。一个常见形式是：

at=argmaxa[Q(s,a)+cpuctP(s,a)∑bN(s,b)1+N(s,a)] a_t=\arg\max_a \left[ Q(s,a)+c_{\text{puct}}P(s,a) \frac{\sqrt{\sum_b N(s,b)}}{1+N(s,a)} \right]

与 UCT 相比，PUCT 的探索项加入了策略先验 P(s,a)P(s,a)：

• 网络认为更有希望的动作在早期优先获得搜索预算；
• 随着访问次数增加，真实搜索回报逐渐主导；
• 价值网络可以替代大量低质量随机 rollout。

13.1 AlphaGo 2016

AlphaGo 结合：

• 监督学习策略网络；
• 自我对弈强化学习策略网络；
• 价值网络；
• MCTS。

13.2 AlphaGo Zero / AlphaZero

AlphaGo Zero 不依赖人类棋谱，以自我对弈产生训练数据；AlphaZero 将类似框架推广到围棋、国际象棋和将棋。其关键不是“只靠神经网络”，而是神经网络与树搜索形成策略迭代式闭环。

13.3 MuZero 的进一步扩展

传统棋类 MCTS 假设已知环境规则，能精确执行落子。MuZero 则学习一个只服务于规划的隐空间模型，预测奖励、价值和策略，而不要求重建完整环境状态。这把树搜索扩展到规则或动力学未知的问题。

---

14. 工程实现中的关键选择

14.1 节点统计放在节点还是边上

在无重复动作的简单树中，两者都可行。现代实现常把 N,W,Q,PN,W,Q,P 放在边 (s,a)(s,a) 上，更自然地表示动作价值，也便于一个状态存在多个入边时处理。

14.2 状态去重与换位表

棋局可能通过不同动作顺序到达同一状态，此时真实结构是有向无环图而不是严格的树。可用哈希与 transposition table 共享统计，但并发和回传语义会更复杂。

14.3 Rollout 策略的偏差—方差权衡

• 随机策略计算便宜但方差大；
• 启发式策略更强，但若规则偏差严重，会把估计系统性带偏；
• 价值网络速度快，但会引入函数逼近误差。

14.4 Progressive Widening

当动作空间极大或连续时，不能一次展开所有动作。可令可扩展子节点数随访问次数增长：

|Aexpanded(s)|≤kN(s)α,0<α<1 |A_{\text{expanded}}(s)|\le kN(s)^\alpha, \quad 0<\alpha<1

这称为渐进式扩展。

14.5 并行搜索

常见方式包括根并行、树并行和叶并行。树并行中需要避免多个线程同时涌向同一节点，常采用 virtual loss 临时降低正在被其他线程探索的分支吸引力。

14.6 树复用

真实落子后，可把对应子节点提升为新根，保留其子树统计，避免每一步从零开始。

14.7 数值与边界条件

实现时至少处理：

• 未访问节点除零；
• 父节点访问次数为 0 时的 log0\log 0；
• 和棋回报；
• 非法动作与终局判断；
• 奖励范围与探索常数匹配；
• 时间预算检查不能只放在外层，否则单次 rollout 过长会超时。

---

15. 一个可运行的最小 MCTS：Nim 取石子

下面示例不依赖第三方库。规则是：一堆石子，每次可取 1～3 个，取走最后一个者获胜。

代码采用“上一步行动者视角”存储节点价值，因此父节点选择子节点时可以统一最大化子节点均值。最终动作使用访问次数最多的 robust child。

from __future__ import annotations

from dataclasses import dataclass, field
from math import log, sqrt
import random

@dataclass(frozen=True)
class NimState:
    stones: int
    player_to_move: int  # 0 or 1

    def legal_actions(self) -> list[int]:
        return list(range(1, min(3, self.stones) + 1))

    def apply(self, action: int) -> "NimState":
        if action not in self.legal_actions():
            raise ValueError(f"illegal action: {action}")
        return NimState(self.stones - action, 1 - self.player_to_move)

    def is_terminal(self) -> bool:
        return self.stones == 0

    def winner(self) -> int:
        if not self.is_terminal():
            raise ValueError("winner() requires a terminal state")
        return 1 - self.player_to_move

@dataclass
class Node:
    state: NimState
    parent: "Node | None" = None
    action_from_parent: int | None = None
    children: dict[int, "Node"] = field(default_factory=dict)
    visits: int = 0
    value_sum: float = 0.0

    def __post_init__(self) -> None:
        self.untried_actions = self.state.legal_actions()
        self.player_just_moved = 1 - self.state.player_to_move

    @property
    def mean_value(self) -> float:
        return self.value_sum / self.visits if self.visits else 0.0

    def select_child(self, exploration: float) -> "Node":
        if not self.children:
            raise ValueError("cannot select from a leaf")
        log_parent = log(max(1, self.visits))

        def uct(child: Node) -> float:
            if child.visits == 0:
                return float("inf")
            exploitation = child.mean_value
            exploration_bonus = exploration * sqrt(log_parent / child.visits)
            return exploitation + exploration_bonus

        return max(self.children.values(), key=uct)

    def expand(self, rng: random.Random) -> "Node":
        action = rng.choice(self.untried_actions)
        self.untried_actions.remove(action)
        child = Node(
            state=self.state.apply(action),
            parent=self,
            action_from_parent=action,
        )
        self.children[action] = child
        return child

def rollout(state: NimState, rng: random.Random) -> int:
    while not state.is_terminal():
        state = state.apply(rng.choice(state.legal_actions()))
    return state.winner()

def backpropagate(node: Node, winner: int) -> None:
    while node is not None:
        node.visits += 1
        node.value_sum += 1.0 if winner == node.player_just_moved else -1.0
        node = node.parent

def mcts_search(
    state: NimState,
    simulations: int = 2_000,
    exploration: float = sqrt(2.0),
    seed: int = 0,
) -> tuple[int, Node]:
    if state.is_terminal():
        raise ValueError("cannot search from a terminal state")

    rng = random.Random(seed)
    root = Node(state)

    for _ in range(simulations):
        node = root

        # 1. Selection
        while not node.state.is_terminal() and not node.untried_actions:
            node = node.select_child(exploration)

        # 2. Expansion
        if not node.state.is_terminal() and node.untried_actions:
            node = node.expand(rng)

        # 3. Simulation
        winner = rollout(node.state, rng)

        # 4. Backpropagation
        backpropagate(node, winner)

    # Robust child: choose the most visited root child.
    best = max(root.children.values(), key=lambda child: child.visits)
    assert best.action_from_parent is not None
    return best.action_from_parent, root

if __name__ == "__main__":
    action, root = mcts_search(NimState(stones=15, player_to_move=0))
    print("recommended action:", action)
    for a, child in sorted(root.children.items()):
        print(a, child.visits, round(child.mean_value, 3))

对于 15 颗石子，理论最优动作是取 3 颗，把 12 颗这个必败态留给对手。增加模拟次数后，MCTS 会逐渐把绝大多数访问预算集中到动作 3。

15.1 把这个示例迁移到棋类，需要替换什么

只需替换状态接口：

legal_actions(state)
apply_action(state, action)
is_terminal(state)
winner_or_reward(state)

但要获得强棋力，还需要更好的：

• 状态表示与快速复制；
• 合法着生成；
• rollout policy 或 value network；
• 走法先验；
• 并行与缓存；
• 时间管理。

---

16. 常见误区

误区一：MCTS 就是随机下很多盘棋

不完整。随机模拟只是其中一步；真正决定效率的是树结构、选择策略和统计回传。

误区二：访问次数最多等于胜率最高

不一定。访问次数反映了 UCT 在探索与利用后的预算分配；均值反映经验回报。搜索阶段和最终决策阶段的指标可以不同。

误区三：探索常数越大越好

不是。过大时搜索接近平均撒网，过小时容易早熟。最优值与奖励尺度、分支数、预算和领域有关。

误区四：模拟次数足够多就一定实用

渐近收敛不等于有限预算下高效。若 rollout 噪声极大、动作空间过宽或关键奖励极稀疏，朴素 MCTS 可能需要不可接受的采样量。

误区五：MCTS 天然适合所有强化学习问题

它更适合可以快速模拟、动作后果可计算、有效规划深度有限的问题。真实世界环境若模拟器昂贵、模型错误或部分可观测，需要模型学习、风险建模和专门的 POMDP 方法。

---

17. 一条完整的知识链

有限深度 Alpha-Beta
        ↓ 依赖叶节点评价
围棋评价函数难以手工构造
        ↓
随机完整对局估计胜率
        ↓ 预算不能平均浪费
蒙特卡洛树搜索 MCTS
        ↓ 需要选择下一条模拟路径
多臂老虎机：探索 vs. 利用
        ↓
UCB1
        ↓ 递归应用到树
UCT
        ↓ 加入策略先验与价值模型
PUCT + 神经网络
        ↓ 自我对弈训练闭环
AlphaGo Zero / AlphaZero

---

18. 结论

MCTS 的突破不在于“随机”本身，而在于把三种机制组合起来：

1. 用终局采样替代难以手工构造的静态评价；
2. 用树结构复用每次模拟产生的信息；
3. 用 UCB/UCT 在探索和利用之间自适应分配预算。

它把传统博弈树的精确规划与统计采样结合起来，并为后续“神经网络 + 搜索 + 自我对弈”的强化学习系统提供了核心规划框架。

---

参考资料

课程材料

1. 马少平：《跟我学 AI——第二篇 计算机是如何学会下棋的（四）》课程 PPT。
2. 视频上半部分 AI 字幕：BV1jS4y1U7pD.zh-CN.srt。
3. 视频下半部分 AI 字幕：BV1WY411n7Zf.zh-CN.srt。

论文与原始资料

1. Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47, 235–256. https://doi.org/10.1023/A:1013689704352
2. Kocsis, L., & Szepesvári, C. (2006). Bandit Based Monte-Carlo Planning. ECML 2006. https://ggp.stanford.edu/readings/uct.pdf
3. Coulom, R. (2006). Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. https://inria.hal.science/inria-00116992
4. Gelly, S., & Wang, Y. (2006). Exploration Exploitation in Go: UCT for Monte-Carlo Go. https://hal.science/hal-00115330
5. Browne, C. B., et al. (2012). A Survey of Monte Carlo Tree Search Methods. IEEE TCIAIG, 4(1), 1–43. https://doi.org/10.1109/TCIAIG.2012.2186810
6. Silver, D., et al. (2016). Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529, 484–489. https://doi.org/10.1038/nature16961
7. Silver, D., et al. (2017). Mastering the Game of Go without Human Knowledge. Nature, 550, 354–359. https://doi.org/10.1038/nature24270
8. Schrittwieser, J., et al. (2020). Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model. Nature, 588, 604–609. https://doi.org/10.1038/s41586-020-03051-4