一、核心概念与定义（填空/选择题高频）

1. 多臂赌博机问题（MAB）

• 定义：K 台老虎机，每台奖励分布未知，需在探索与利用之间平衡以最大化总奖励。

• 关键矛盾：探索（exploration） vs 利用（exploitation）

• 常用策略：

  • 贪心算法（Greedy）：选择当前估计奖励最大的老虎机

  • 上限置信区间算法（UCB1）：选择置信上限最大的老虎机

  • Boltzmann 策略：按概率选择，概率与估计奖励相关

2. 蒙特卡洛方法

• 基本思想：通过随机采样（概率实验）估计未知量

• 典型例子：蒲丰投针问题（估算π）

• 应用场景：难以解析求解或计算复杂的随机问题

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

• 构成四步骤：

  • 选择（Selection）：从根节点开始递归选择子节点，常用 UCB1

  • 扩展（Expansion）：当节点未被完全扩展时，随机扩展一个子节点

  • 模拟（Simulation）：从扩展节点出发，使用简单策略（如随机）进行游戏至终止

  • 反向传播（Backpropagation）：将模拟结果（奖励）回溯更新路径上所有节点的统计数据（总奖励/访问次数）

---

二、算法原理与流程（计算与简答重点）

2. MCTS 特点 （蒙特卡洛树搜索）

• 无需静态评估函数：通过模拟对局结果评估节点优劣

• 适应大规模状态空间：适用于围棋等复杂博弈

• 渐进收敛性：随着模拟次数增加，策略趋近最优

• 支持实时决策：可随时中断并输出当前最佳动作

3. 与 Minimax 对比（常考辨析）

维度	MCTS	Minimax
搜索方式	随机采样 + 树构建	穷举 + 剪枝
评估依据	模拟结果	静态评估函数
适用场景	大规模、随机性强、完全/部分信息	小规模、确定性、完全信息
内存使用	仅保存部分树	可能需保存整树
收敛性	渐进收敛	有限深度内最优

---

三、典型例题与考点（对应回忆卷题型）

1. 填空题考点

• MCTS 四阶段：选择、扩展、模拟、反向传播

• MAB 问题的核心矛盾：探索 vs 利用

• UCB1 中c常取22​

• 蒙特卡洛方法的基本思想：通过频率估计概率

2. 简答题示例

1. 简述 MCTS 的基本流程及其与 Minimax 的主要区别。

2. 解释“探索-利用困境”在 MAB 和 MCTS 中如何体现？

3. 为什么 AlphaGo 选择 MCTS 而不是 Minimax？

4. 反向传播时，MAX层和MIN层的奖励更新有何不同？为什么？

3. 计算题示例（类似选择题4）

题目可能给出一个 MCTS 树的部分结构，节点标注“总奖励/访问次数”，要求：

• 计算某节点的UCB1值

• 判断接下来应选择哪个子节点

• 模拟一次对局后更新节点统计信息

---

四、与试卷中其他章节的关联

• 与对抗搜索关联：MCTS 也用于博弈，但适用于状态空间更大的情况

• 与强化学习关联：MCTS 可视为一种基于模拟的强化学习方法

• 与启发式搜索关联：MCTS 也是一种启发式随机搜索

• 与AlphaGo联系：MCTS + 深度强化学习的成功案例

---

五、复习建议

1. 掌握流程：能默写 MCTS 四步骤，理解每一步的作用。

2. 理解 UCB1：会计算 UCB1 值，理解其如何平衡探索与利用。

3. 对比学习：与 Minimax、Alpha-Beta 剪枝对比，明确适用场景。

4. 联系实际：理解 AlphaGo、围棋 AI 中 MCTS 的作用。

5. 注意细节：反向传播时 MAX 与 MIN 层更新方式的差异。

---

蒙特卡洛树搜索 · 模拟练习题

一、填空题（每空1分）

1. 多臂赌博机问题的核心矛盾是________与________之间的权衡。

2. 在UCB1算法中，选择动作的依据是________最大的动作。

3. 蒙特卡洛方法的基本思想是通过________来估计一个未知量。

4. MCTS的四个步骤依次是：选择、、模拟、。

5. 在MCTS中，节点通常记录两个统计量：________和访问次数。

6. UCB1公式中的常数c通常取值为________。

7. 在反向传播步骤中，MAX层节点的总奖励更新规则是________（加/减）模拟得分。

8. MCTS适用于状态空间________（大/小）的博弈问题。

9. 蒙特卡洛树搜索是一种________（确定性/随机性）搜索算法。

10. 在MAB问题中，贪心算法只进行________，而忽略探索。

---

二、选择题（每题2分）

1. 下列哪项不是MCTS的步骤？
   A) 选择
   B) 剪枝
   C) 扩展
   D) 反向传播

2. UCB1公式中，ln⁡N(p)N(v) 项主要鼓励：
   A) 利用
   B) 探索
   C) 收敛
   D) 模拟

3. 在MCTS中，模拟阶段通常使用什么策略？
   A) Minimax策略
   B) 随机策略
   C) UCB1策略
   D) 贪心策略

4. 关于MCTS与Minimax的对比，以下说法正确的是：
   A) MCTS需要静态评估函数
   B) Minimax更适合围棋等大规模博弈
   C) MCTS通过采样减少搜索空间
   D) Minimax一定优于MCTS

5. 在反向传播时，MIN层节点的总奖励更新规则是：
   A) 加上模拟得分
   B) 减去模拟得分
   C) 乘以模拟得分
   D) 除以模拟得分

---

三、计算与简答题（10分）

假设在某MCTS节点处，其三个子节点的统计信息如下：

节点	总奖励（Q）	访问次数（N）
A	20	5
B	15	3
C	5	2

父节点访问次数 N(p)=12，UCB1常数 c=2。

1. 分别计算节点A、B、C的UCB1值。

2. 根据UCB1值，接下来应该选择哪个节点进行扩展？

3. 若从该节点进行模拟，最终得分为+3（对MAX有利），请写出反向传播后A、B、C节点更新后的总奖励值（假设A被选择并模拟）。

---

四、简答题（每题5分）

1. 简述“探索-利用困境”在多臂赌博机问题中的体现，并说明UCB1如何解决该困境。

2. 为什么MCTS在围棋等复杂博弈中比Minimax更适用？

3. 描述MCTS反向传播过程中，MAX层和MIN层更新总奖励的区别及其原因。

---

参考答案

一、填空题

1. 探索，利用

2. 置信上限

3. 随机采样（或频率估计）

4. 扩展，反向传播

5. 总奖励（或累积奖励）

6. 22​

7. 减

8. 大

9. 随机性

10. 利用

二、选择题

1. B

2. B

3. B

4. C

5. A

三、计算与简答题

1. UCB1计算：

   • UCB1(A)=205+2×ln⁡125≈4+1.414×0.699≈4.99UCB1(A)=520​+2​×5ln12​​≈4+1.414×0.699≈4.99

   • UCB1(B)=153+2×ln⁡123≈5+1.414×0.895≈6.27UCB1(B)=315​+2​×3ln12​​≈5+1.414×0.895≈6.27

   • UCB1(C)=52+2×ln⁡122≈2.5+1.414×1.099≈4.05UCB1(C)=25​+2​×2ln12​​≈2.5+1.414×1.099≈4.05

2. 应选择节点B（UCB1值最大）

3. 反向传播后更新：

   • A为MAX层子节点，总奖励更新：20−3=1720−3=17（MAX层减分）

   • B、C未被访问，总奖励不变（仍为15和5）

四、简答题

1. 探索-利用困境：在MAB中，若过早利用当前最优动作，可能错过更优动作；若过度探索，则短期收益低。
   UCB1解决方案：通过置信区间上限平衡，对访问少的动作赋予更高探索潜力，同时考虑平均奖励。

2. MCTS更适用于围棋的原因：

   • 状态空间极大，Minimax无法穷举

   • 无需静态评估函数，通过模拟结果评估局面

   • 支持渐进收敛和实时决策

   • 适用于部分随机环境

3. 反向传播更新区别：

   • MAX层：总奖励减去模拟得分（因为模拟得分对MAX有利时为正，MAX希望最小化对手奖励）

   • MIN层：总奖励加上模拟得分（MIN希望最小化得分，因此加正分表示不利）

   • 原因：统一使用UCB1选择时，需将MIN层目标转化为最大化问题，故取反处理。