Ch6 博弈搜索与蒙特卡洛树搜索 (Adversarial Search & MCTS)

课件：lec6.pdf (Game Playing, 2026/03/25) + MCTS.pdf (蒙特卡洛树搜索简介)
教材：Artificial Intelligence: A Modern Approach (Russell & Norvig), Ch5 (Adversarial Search and Games)
教师：吉建民，USTC

0. 本章概述

本章承接第 3–5 章的（单智能体）搜索，转向多智能体对抗环境下的搜索——“博弈搜索 (Adversarial Search)”。核心问题：当环境中存在目标与我方相反的对手时，如何选择一个策略 (strategy / contingency plan)，使得无论对手如何应对，我方都能保证一个尽量好的收益。

本章分两大块：

1. 经典博弈搜索（lec6）：博弈类型分类 → Minimax 最优策略 → α-β 剪枝 → 资源受限下的启发式评估 → 期望极小极大（含随机性）→ 不完全信息博弈。
2. 蒙特卡洛树搜索 MCTS（MCTS.pdf）：以随机抽样替代精确遍历，用 UCB1/UCT 平衡探索与利用，四步循环 (Selection / Expansion / Simulation / Backpropagation)；并以 AlphaGo (PUCT) 为代表讲深度 MCTS。

第一部分：博弈与博弈搜索 (lec6)

6.1 为什么研究博弈 (Game Playing)

博弈长期被视为 AI 研究的好问题：

• 非平凡：需要非平凡的智能决策
• 需要"类人"智能：玩家需要推理、规划和策略
• 复杂度高：象棋（Chess）和围棋（Go）的状态空间极其庞大
• 有限时间内决策：必须在时间限制下做出选择
• 环境优良：定义清晰、可重复、完全可观察、环境受限
• 可直接比较：人类与计算机的直接对抗提供了明确的能力衡量标准

博弈 vs. 普通搜索问题

历史脉络

• 1846 — Babbage 提出计算机考虑可能的走法路线
• 1912/1944 — Zermelo / Von Neumann 提出完美博弈算法
• 1945–1950 — Zuse/Wiener/Shannon 提出有限深度 + 近似评估
• 1951 — Turing 编写第一个国际象棋程序
• 1952–57 — Samuel 使用机器学习改进评估精度
• 1956 — McCarthy 提出剪枝以允许更深搜索

一些棋类的复杂度（量级）

• 围棋 (Go)：分支因子 $b>300$（19×19 棋盘），博弈树规模 $>10^{170}$；
• 国际象棋 (Chess)：$b\approx 35$，合理对局深度 $m\approx 100$。

6.2 博弈的分类 (Types of Games)

按两个维度划分（4 类）：

MCTS.pdf 给出更细的术语：

• 双人零和 (Two-Player Zero-Sum)：双方收益之和为零，一方收益 = −（另一方收益）。其纳什均衡"唯一"且"易计算"。
• 完全信息 (Full Information)：所有玩家都能看到全部状态与历史行动，无隐藏信息或不确定性。
• 扩展式博弈 (Extensive Form)：博弈是时序的、分步的，可用博弈树 (Game Tree) 描述：从根节点（初始状态）出发，每一层对应一个玩家的行动，叶子节点（Terminal State）给出收益。
• 例：国际象棋、中国象棋、围棋属于"双人零和完全信息扩展式博弈"；扑克（不完全信息+随机性）、飞行棋（随机性）不属于。

6.3 博弈论基础：正常形式博弈

正常形式博弈 (Normal-Form Game)

⭐ 正常形式（矩阵）博弈定义为元组 $(n,\,A_{1\ldots n},\,R_{1\ldots n})$：

• $n$：智能体数；
• $A_i$：玩家 $i$ 的动作集；联合动作集 $A=A_1\times\cdots\times A_n$；
• $R_i:A\to\mathbb{R}$：玩家 $i$ 的奖励函数。

每个玩家 $i$ 选择策略 $\pi_i:A_i\to[0,1]$（$\pi_i\in PD(A_i)$，即动作上的概率分布），以概率 $\pi_i(a_i)$ 取动作 $a_i$，获得效用 $R_i(a_1,\ldots,a_n)$。给定策略组合 $\langle\pi_1,\ldots,\pi_n\rangle$，玩家 $i$ 的期望效用为：

$$R_i(\pi_1,\ldots,\pi_n)=\sum_{a\in A} R_i(a)\prod_{j=1}^{n}\pi_j(a_j)$$

所有玩家都想最大化自己的期望效用。这是一次性交互 (one-shot)，可表示为 $n$ 维收益矩阵。

经典例子：囚徒困境 (Prisoners’ Dilemma)、石头剪刀布 (Rock-Paper-Scissors)。（收益矩阵见原课件图，需对照原课件查看。）

最优性概念 (Optimality Concepts)

• 最优反应 (Best-Response Function)：给定其他玩家当前策略，使自身效用最大的策略集。

$$\pi_i^{*}\in BR_i(\pi_{-i})\ \ \text{iff}\ \ \forall\pi_i\in PD(A_i),\ R_i(\langle\pi_i^{*},\pi_{-i}\rangle)\ge R_i(\langle\pi_i,\pi_{-i}\rangle)$$

• ⭐ 纳什均衡 (Nash Equilibrium)：所有玩家都在使用最优反应策略。

$$\forall i=1\ldots n,\ \ \pi_i\in BR_i(\pi_{-i})$$

• 定理：所有正常形式博弈至少存在一个 Nash 均衡（可能为混合策略）。

双人零和博弈

• 两对手对抗；对称奖励（始终和为零）。
• 通常只有一个均衡；若存在多个，则它们可互换 (interchangeable)：若 $\langle\pi_1,\pi_2\rangle$ 和 $\langle\mu_1,\mu_2\rangle$ 都是 Nash 均衡，则 $\langle\pi_1,\mu_2\rangle$、$\langle\mu_1,\pi_2\rangle$ 也是，且效用相等。
• Minimax 定理：在策略空间上，

$$\max_{\pi\in PD(A)}\min_{o\in O}\sum_{a\in A}\pi(a)\,R(a,o)$$

可形式化为一个线性规划 (Linear Program) 求解。注意：同时出招使得确定性策略失效，必须用混合策略。

6.4 Minimax 搜索 ⭐⭐⭐

基本设定

针对确定性、完全信息、双人、轮流、零和博弈（如 tic-tac-toe、Chess、Checkers）：

• 博弈是一棵状态空间搜索树 (game tree)，玩家交替落子；
• 每一层（ply，一"层"= 一个玩家的一回合）；
• 一方（MAX）最大化结果，另一方（MIN）最小化结果。

Minimax 原理

• 假设双方都按最优策略行棋；
• 我方走完后，假设对手会选择使结果最小化的着法；
• 我方在选择时，要同时考虑自己的着法和对手的最优应对。

Minimax 值与定义

⭐ Minimax 值 (minimax value)：在对手也使用最优策略的条件下，能导致至少不比其它策略差的结果——即"best achievable payoff against best play"。

$$\text{Minimax}(s)=\begin{cases}\text{Utility}(s) & \text{若 }s\text{ 为终局}\\[2pt]\displaystyle\max_{a}\text{Minimax}(\text{Result}(s,a)) & \text{若 }s\text{ 为 MAX 节点}\\[2pt]\displaystyle\min_{a}\text{Minimax}(\text{Result}(s,a)) & \text{若 }s\text{ 为 MIN 节点}\end{cases}$$

• MAX 优先选有极大值的状态；MIN 优先选有极小值的状态。

Minimax 算法（伪代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function MINIMAX-DECISION(state):
    v = -∞
    best = None
    for each a in ACTIONS(state):
        v2 = MIN-VALUE(RESULT(state, a))
        if v2 > v:
            v, best = v2, a
    return best

function MAX-VALUE(state):              # MAX 节点：返回可达最大值
    if TERMINAL(state): return UTILITY(state)
    v = -∞
    for each a in ACTIONS(state):
        v = max(v, MIN-VALUE(RESULT(state, a)))
    return v

function MIN-VALUE(state):              # MIN 节点：返回可达最小值
    if TERMINAL(state): return UTILITY(state)
    v = +∞
    for each a in ACTIONS(state):
        v = min(v, MAX-VALUE(RESULT(state, a)))
    return v

Minimax 性质 ⭐

对国际象棋 $b\approx35,\ m\approx100$ → 精确求解完全不可行。引出剪枝需求。

6.5 α-β 剪枝 ⭐⭐⭐

动机

“If you have an idea that is surely bad, don’t take the time to see how truly awful it is.” — Pat Winston

面对聪明的对手，博弈树中有些分支根本不会被走到——可剪除。

α 与 β 的定义 ⭐

• α：当前路径上 MAX 目前已确保 (assured of) 的最小分数（即 MAX 的下界）。
• β：当前路径上 MIN 目前已确保 的最大分数（即 MIN 的上界，等价于 MAX 的上界）。
• ⭐ 剪枝条件：每当 β < α，MAX 不必再考虑该节点的其余后代——它们在实际博弈中永不会到达。

课件原文：α 是"到目前为止在路径上的任意选择点发现的 MAX 的最佳（最大值）选择"；若某值 $v$ 比 α 还差，MAX 会回避它，故可停止考察 $v$ 的其余子节点。β 对 MIN 类似定义。

α-β 算法（伪代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function ALPHA-BETA-SEARCH(state):
    v, best = MAX-VALUE(state, -∞, +∞)
    return best

function MAX-VALUE(state, α, β):
    if TERMINAL(state): return UTILITY(state)
    v = -∞
    for each a in ACTIONS(state):
        v = max(v, MIN-VALUE(RESULT(state, a), α, β))
        if v ≥ β: return v        # β 剪枝：MIN 不会让这分支发生
        α = max(α, v)
    return v

function MIN-VALUE(state, α, β):
    if TERMINAL(state): return UTILITY(state)
    v = +∞
    for each a in ACTIONS(state):
        v = min(v, MAX-VALUE(RESULT(state, a), α, β))
        if v ≤ α: return v        # α 剪枝：MAX 不会让这分支发生
        β = min(β, v)
    return v

α-β 性质 ⭐

• 剪枝不影响最终结果：被剪掉的分支注定不影响决策，结果与完整 Minimax 完全一致。
• 效果取决于后继的考察顺序：先考察最好的后继时剪枝最有效。
  • 最坏情况：无任何剪枝，与穷举相同 $O(b^m)$；
  • 最好情况 / 完美排序 (perfect ordering)：⭐ 时间复杂度 $=O(b^{m/2})$ → 可搜索深度翻倍；
  • 实际中性能更接近最好情况。
• 这是"元推理 (metareasoning)“——推理"哪些计算是相关的”——的一个简单例子。
• 即便如此，国际象棋 $35^{50}$ 仍不可能穷举 → 还需启发式评估。

课件中 α-β 剪枝的多张分步示例图（Minimax 值回填、剪枝发生过程）以图示为主，需对照原课件查看。

6.6 资源受限下的近似评估

评估函数 (Evaluation Function)

当无法搜索到终局时，在深度限制 (depth limit) 处用一个启发式评估函数 EVAL(s) 估计当前局面对我方的好坏。

⭐ 线性评估函数 (linear weighted sum of features)：

$$\text{EVAL}(s)=w_1 f_1(s)+w_2 f_2(s)+w_3 f_3(s)+\cdots$$

• $f_i$ 为特征 (features)（由领域专家构造，如国际象棋的子力、王安全、兵形等）；
• $w_i$ 为权重，越重要的特征权重越大（可人工设定或学习得到，参见 Samuel 1952–57）；
• 棋艺质量直接取决于评估函数的质量。

序数效用 (Ordinal Utility) —— 确定性博弈中精确值不重要

⭐ 行为在任何对 EVAL 的单调变换 (monotonic transformation) 下保持不变；只有值的顺序 (order) 重要：

$$\text{payoff 在确定性博弈中起的是序数效用 (ordinal utility) 函数的作用}$$

应对时间限制：迭代加深搜索 (IDS)

• 实际对局有每步时间上限 $T$；α-β 不能中途停下使用结果。
• 做法：迭代加深搜索 (Iterative Deepening Search, IDS)——以递增的深度限制反复运行 α-β；时钟到点时，使用最后一次完整完成的 α-β 搜索的结果（最深的那次）。
• 优点：充分利用时间，且浅层结果可用于指导深层排序（move ordering）。

实战里程碑

6.7 含随机性的博弈：随机博弈 (Stochastic Games)

随机博弈定义

随机博弈 (Stochastic Game) 是正常形式博弈与 MDP 的推广——多状态、多智能体环境。定义为元组 $(n,S,A_{1,\ldots,n},T,R_{1,\ldots,n})$：

• $n$：智能体数；
• $S$：状态集；
• $A_i$：玩家 $i$ 的动作集，$A=A_1\times\cdots\times A_n$ 为联合动作集；
• $T:S\times A\times S\to[0,1]$：转移函数，依赖所有玩家的动作；
• $R:S\times A\times S\to\mathbb{R}$：奖励函数（期望值），同样依赖所有玩家的动作。

每个玩家 $i$ 选择策略 $\pi_i:S\to PD(A_i)$（$\pi_i(a_i\mid s)$），联合策略 $\pi=\langle\pi_i,\pi_{-i}\rangle$。它具有马尔可夫性 (Markovian)，但从单个玩家视角看并非马尔可夫（因他人策略未知）。

最优性概念（带折扣）

考虑折扣累积奖励（同 MDP）：

$$V^{\pi_i}(s)=\mathbb{E}\!\left[\sum_{k=0}^{\infty}\gamma^{k}r^{i}_{t+k+1}\,\middle|\,s_t=s,\pi\right]=\sum_{a}\pi(s,a)\sum_{s'}T(s,a,s')\big[R^{i}(s,a,s')+\gamma V^{\pi_i}(s')\big]$$

$$Q^{\pi_i}(s,a)=\sum_{s'}T(s,a,s')\big[R^{i}(s,a,s')+\gamma V^{\pi_i}(s')\big]$$

• 最优反应 (Best-Response)：以状态价值为参考，
  $\pi_i^{*}\in BR_i(\pi_{-i})$ iff $\forall\pi_i,\forall s\in S:\ V_i^{\langle\pi_i^{*},\pi_{-i}\rangle}(s)\ge V_i^{\langle\pi_i,\pi_{-i}\rangle}(s)$。
• Nash 均衡：所有玩家都使用最优反应策略。

⭐ 最大期望效用原则 (Maximum Expected Utility)

“Why should we average utilities? Why not minimax?”

最大期望效用原则：智能体应在自身知识下选择最大化期望效用的动作。这是决策的一般原则，常被视为理性的定义，将贯穿全课程。

Expectiminimax 算法

对随机博弈（如西洋双陆棋 Backgammon），博弈树中引入第三种节点 CHANCE（机会节点），按各结果的概率取期望：

$$\text{Expectiminimax}(s)=\begin{cases}\text{Utility}(s) & \text{终局}\\[2pt]\max_{a}\text{Expectiminimax}(\text{Result}(s,a)) & \text{MAX}\\[2pt]\min_{a}\text{Expectiminimax}(\text{Result}(s,a)) & \text{MIN}\\[2pt]\displaystyle\sum_{r}P(r)\,\text{Expectiminimax}(\text{Result}(s,r)) & \text{CHANCE}\end{cases}$$

⚠️ 随机博弈中"精确值重要"

与确定性博弈（6.6，序数效用）相反：在含随机性的博弈中，精确的数值确实重要 (Exact values DO matter)——因为 CHANCE 节点要对不同分支做加权平均，数值的相对大小（而非仅顺序）直接影响期望。

6.8 不完全信息博弈 (Games of Imperfect Information)

例：桥牌、德州扑克等纸牌游戏——对手初始手牌未知。通常可为每种发牌计算一个概率。

思路：期望极小极大 (Expectiminimax over deals)

在评价一个有未知牌的给定行动过程时，首先计算出每副可能牌的出牌行动的极小极大值，然后再用每副牌的概率计算得到对所有发牌情况的期望值。

形式化：对所有可能的"发牌 (deal)" $d$（概率 $P(d)$）：

1. 计算每个动作 $a$ 在该 deal 下的极小极大值 $\text{MinimaxValue}(a,d)$；
2. 选择 $\arg\max_a\sum_d P(d)\cdot\text{MinimaxValue}(a,d)$。

直觉上相当于在博弈开始时引入一次大的随机掷骰（发牌）。

课件示例：四张牌的桥牌/红心大战

• MAX 先出，知道对手另 3 张牌中除第一张外的牌；
• 规则：有同花色必出同花色；比大小；赢一轮得一分，算总数。
• 分别讨论：第一张牌为红桃 4、方块 4、花色未知三种情形下的最优决策（详见原课件图，需对照原课件查看）。
• 应用：计算机德州扑克 (Texas Hold’em) 已达到/超越人类顶尖水平。

6.9 搜索方法小结（回顾全章搜索主题）

• 无信息搜索：BFS、一致代价、DFS、深度受限、迭代加深 (IDS)。
• 有信息搜索：最佳优先——贪心、A*；局部搜索——爬山、模拟退火等。
• 约束满足 (CSP)：回溯 = 每节点赋一个变量的 DFS；增强：变量/值排序启发、前向检查、约束传播。
• 对抗搜索（本章）：Minimax、α-β、Expectiminimax、MCTS。

作业（第三版）：5.9、5.8、5.13。

第二部分：蒙特卡洛树搜索 (MCTS)

7.1 蒙特卡洛方法 (Monte Carlo Method)

起源

1940 年代，冯·诺伊曼 (John von Neumann)、乌拉姆 (Stanislaw Ulam)、梅特罗波利斯 (Nicholas Metropolis) 在洛斯阿拉莫斯国家实验室 (Los Alamos National Laboratory) 为核武器计划工作时发明：

• 曼哈顿计划中中子扩散方程无法解析求解；
• 乌拉姆的灵感：用随机抽样替代精确计算（据传源自"乌拉姆叔叔在蒙特卡洛赌场欠债"的故事）；
• 冯·诺依曼建立计算机实现的理论框架；
• 1948 年在 ENIAC 上首次运行蒙特卡洛方法。
• 命名取自摩纳哥的蒙特卡洛赌场。

定义

蒙特卡洛方法 (Monte Carlo Method)，又称统计模拟方法：从确定性解析解到概率近似解的范式迁移。两个核心步骤：

1. 采样 (Sampling)：构造与目标相关的随机过程/随机变量，从其分布中独立重复抽样；
2. 估计 (Estimation)：用样本均值近似期望或积分，并评估准确度与置信度。

经典应用

(1) 求圆周率 π：在单位正方形内随机撒点，

$$\frac{\pi}{4}=\frac{\text{扇形面积}}{\text{正方形面积}},\quad \pi=4\times P(\text{落在扇形中})\approx 4\times\frac{\text{红色点数}}{\text{总点数}}$$

(2) 求定积分 $\theta=\int_a^b f(x)\,dx$（均匀采样 $x_i\in[a,b]$）：

$$\theta\approx\frac{b-a}{n}\sum_{i=1}^{n}f(x_i)$$

(3) 更一般形式（引入概率分布 $p(x)$）：

$$\theta=\int f(x)\,dx=\int\frac{f(x)}{p(x)}p(x)\,dx=\mathbb{E}_{x\sim p}\!\left[\frac{f(x)}{p(x)}\right]\approx\frac{1}{n}\sum_{i=1}^{n}\frac{f(x_i)}{p(x_i)},\ \ x_i\sim p$$

均匀分布 $p(x)=1/(b-a)$ 时即化简为经典公式。

理论保障：大数定律与中心极限定理

• 大数定律 (Law of Large Numbers, LLN)：大量独立同分布试验的平均值会越来越接近理论期望。$\bar X_n \to E[X_i]$
  • 弱大数定律：随 $n\to\infty$，样本均值与期望之差在概率意义上可任意小；$\lim_{n\to\to\infty} P(|\bar X_n - E[X]| < \epsilon) = 1$，即依概率收敛。
  • 强大数定律：样本均值几乎必然 (a.s., 以概率 1) 收敛到期望。即 $P(\lim_{n\to\infty} \bar X_n = E[X]) = 1$
• 中心极限定理 (Central Limit Theorem, CLT)（林德伯格-莱维 Lindeberg–Lévy 版本）：大量独立、同分布的随机效应相加，其总和/平均趋于正态分布，无论单个效应原本是什么分布。

$$\frac{S_n-n\mu}{\sigma\sqrt{n}}\to N(0,1)$$

收敛性与误差

• 收敛性：大数定律保证——只要能抽足够多独立样本且每个样本期望存在有限，样本均值即可逼近真实期望。
• 误差分布 / 收敛速度：由中心极限定理，蒙特卡洛估计量近似服从正态分布；收敛速度为 $O(1/\sqrt{n})$（即样本量翻 4 倍、误差减半），且与问题维数无关——这是蒙特卡洛在高维问题上的优势。
• 置信区间：可由正态近似给出估计量的置信区间$\hat{I}_{n}\pm z_{\frac{\alpha}{2}} \frac{\hat{\sigma}_{n}}{\sqrt{ n }}$

蒙特卡洛与（伪）随机数

计算机使用伪随机数 (pseudo-random numbers)——给定种子 (seed) 和算法后完全确定可重复。为何仍可用？

• 现代伪随机数生成器 (PRNG)（如 Mersenne Twister、PCG、Xorshift）经严格统计测试，满足：
  1. 分布均匀性 (Uniformity)：在 $[0,1)$ 通过均匀分布检验；
  2. 独立性与低自相关性 (Independence / Low Autocorrelation)：相邻样本统计上无明显相关；
  3. 极长周期 (Period)：在绝大多数模拟规模内不回绕。
• 大数定律/中心极限定理对"足够随机"的样本有容错性：少量偏差会被均值"平滑"掉。

7.2 博弈树与经典搜索回顾（衔接第一部分）

MCTS.pdf 用一张"博弈树 (Game Tree)"串起第一部分的概念：

• 节点 (Node)：游戏在某一步的局面/状态；
• 有向边 (Edge)：玩家在该状态下的一个可行动作，执行后进入下一节点；
• 根节点 (Root)：起始状态 (Initial State)；叶子节点 (Terminal State)：游戏结束，可评估胜负/收益；
• 通常交替层：一层 Player A 决策，下一层 Player B 决策。

回顾（详见第一部分）：

• Minimax：Max 层最大化、Min 层最小化，自底向上回溯；复杂度 $O(b^d)$；缺点是需遍历整棵树。
• Alpha-Beta 剪枝：用 α（下界）、β（上界）剪枝，当 $\alpha\ge\beta$ 剪除；完美排序下接近 $O(b^{d/2})$；剪枝不影响结果正确性。
• 深度受限的 Minimax/Alpha-Beta：限制搜索深度，到达阈值后用评估函数近似：

$$\text{Eval}(s)=w_1 f_1(s)+w_2 f_2(s)+\cdots+w_n f_n(s)$$

时间允许时可结合迭代加深 (Iterative Deepening)。

7.3 基于游戏树的蒙特卡洛搜索

动机

对极大规模博弈（如围棋），即使 α-β 剪枝也难以穷举大部分分支；同时难以得到准确的残局评估函数。蒙特卡洛方法通过随机抽样模拟后续对局，不必遍历整棵树即可估计当前局面好坏。可与 α-β 结合：浅层 α-β，深层蒙特卡洛评估。

纯粹蒙特卡洛搜索 (Pure Monte Carlo Search)

1. 在根节点（当前局面）列举所有可能的下一步行动；
2. 对每个可行行动，进行多次随机模拟 (Rollout)：从执行该行动后的局面出发，随机走子直到游戏结束（或某深度），记录终局输赢/得分；
3. 统计每个行动的平均收益（胜率或期望得分）；
4. 选择平均收益最高的行动。

优点：

• 实现简单，只需能模拟一次完整随机对局；
• 无评估函数依赖——终局自然给出胜/负/平或分数，不需要显式棋面评估；
• 可并行化：多次模拟可并行运行，模拟越多估计越稳定。

缺点：

• 深度大的游戏中，随机走子产生大量"无意义"路径；
• 局面相关信息不重复利用：对不同行动滚动时会对相同/相似局面重复模拟，浪费计算。

改进方向：把已模拟过的有价值的局面"记下来"，逐步生长一棵搜索树——即 MCTS。

7.4 探索与利用 (Exploration vs. Exploitation)

⭐ 核心权衡：如何平衡以使期望效用最大？

• 利用 (Exploitation)：在当前信息下选择已知收益最高的决策；
• 探索 (Exploration)：尝试尚不确定但可能有更高收益的决策，收集更多信息。

多臂老虎机 (Multi-Armed Bandit)

有 $k$ 台老虎机，每台中奖概率未知；在有限/无限轮内"拉杆"选择，累积最多奖励。

• 始终选历史平均最高的 → 可能错失其他机台潜在更高的奖励；
• 不断尝试新机台 → 浪费在低收益机台上。
• 分布模型：每个臂可服从伯努利分布 (Bernoulli Bandit) $f(x)=p^{x}(1-p)^{1-x},\ x\in\{0,1\}$；也可服从相互独立的高斯分布 $x\sim\mathcal{N}(\mu,\sigma^2)$。

平衡策略

⭐ UCB1 算法（基于 Hoeffding 不等式）

1. 对每个动作 $a$，维护平均奖励估计 $\hat{\mu}_a$，并给出表示不确定性的"置信区间"；
2. 计算上置信界 (Upper Confidence Bound)，基于霍夫丁不等式 (Hoeffding’s Inequality)：

$$\text{UCB}(a)=\hat{\mu}_a + c\sqrt{\frac{\ln t}{n_a}}$$

• $t$：总时间步（截至目前总试验数）；
• $n_a$：动作 $a$ 已被选择的次数；
• $c$：置信系数（通常设为 $\sqrt{2}$ 或 2，课件取 $c=2$）。
• 直觉：第一项 = 利用（已估计的均值），第二项 = 探索（被选次数少则不确定度大，项值大）。

3. 每轮 $t$ 选择使 $\text{UCB}(a)$ 最大的动作 $a$。
   • 当 $n_a=0$ 时 UCB 视为 $+\infty$，保证每个动作至少被尝试一次。

7.5 蒙特卡洛树搜索 (MCTS) ⭐⭐⭐

起源

• 2006，法国研究者 Rémi Coulom 首次提出"蒙特卡洛树搜索"核心方法，并在计算机围棋程序 Crazy Stone 中实践。
• UCT (Upper Confidence bounds applied to Trees)：由 Levente Kocsis 与 Csaba Szepesvári (2006) 提出，将多臂老虎机的 UCB1 与 MCTS 结合。
• 2020 年后，MCTS 跨学科应用于自动驾驶、医疗、OpenAI o1 推理模型等领域。

MCTS 四步循环 ⭐

不断重复下列四步。随迭代次数增加，搜索树逐渐扩展，节点胜率估计越来越准确。最终选择根节点下访问次数最多或平均奖励最高的子节点作为决策。

① 选择 (Selection)：从根节点出发，按策略（UCT 公式）选择子节点，递归向下直至抵达未完全展开的节点（即还有未尝试动作的节点）。

② 扩展 (Expansion)：为该未完全展开的节点添加一个或多个子节点——选一个未探索的动作 $a$，执行后生成新状态 $s'$，将 $s'$ 加入树。

③ 模拟 (Simulation / Rollout)：从新节点出发，以随机或半启发式方式走到游戏终局，获得最终胜负/奖励：

• 纯随机模拟：完全随机选动作直至终止（计算快、方差大），适合围棋这类只需最终胜负的游戏；
• 启发式模拟：用轻量级策略（规则库、快速策略网络）引导，适合围棋劫争等特定模式；
• 神经网络 / 策略网络：现代深度 MCTS 中用神经网络指导模拟的动作选择。

④ 回溯 (Backpropagation)：将本次模拟结果沿整条路径反向更新每个经过节点的统计量：访问次数 $N(s), N(a)$、平均收益 $Q(a)$。

⭐ UCT 公式（选择步骤所用）

在节点 $s$ 下，对动作 $a$ 计算：

$$\boxed{\ \text{UCT}(s,a)=Q(a)+c\sqrt{\frac{\ln N(s)}{N(a)}}\ }$$

• $Q(a)$：节点 $s$ 下动作 $a$ 的平均收益（利用项）；
• $N(s)$：节点 $s$ 的总访问次数；$N(a)$：$s$ 下动作 $a$ 的访问次数；
• $c$：探索权重常数（通常设为 2）；
• 第二项为探索项：被访问越少（$N(a)$ 小），不确定性越大，越值得探索。当 $N(a)=0$ 时取 $+\infty$。
• 这正是 UCB1 公式应用于树节点的形式。

算法步骤示例（MCTS.pdf 三次迭代）

• 初始化：根节点 $S_0$，每个节点存"价值 $T$"和"访问次数 $N$"。
• 第 1 次：$S_0$ 既是根又是叶且非终止 → 扩展。设 $S_0$ 后有两策略转移到 $S_1,S_2$。$N_1=N_2=0$，UCB 均为 $+\infty$，任选其一（选 $S_1$）模拟；结果 20，回溯更新。
• 第 2 次：从 $S_0$ 选择，$S_1$ 的 UCB 已有限而 $S_2$ 的 UCB 仍为 $+\infty$ → 选 $S_2$ 扩展并模拟；结果 10，回溯。
• 第 3 次：从 $S_0$ 计算 $S_1,S_2$ 的 UCB，选较大者（$S_1$）扩展；$S_1$ 已被探索过 → 枚举其所有可能动作加入树（如 $S_3,S_4$），随机选一个扩展、模拟，以此类推。

MCTS 的优缺点

优点：

• ⭐ 无需准确评估函数：MCTS 通过模拟自身评估局面优劣，不依赖人工设计的启发函数；
• 任意时间终止 (anytime algorithm)：MCTS 是渐进式深化的，可随时根据计算资源停止迭代并给出当前最好的决策；
• 逐步改进策略：随模拟进行不断修正各动作估计，多次尝试降低单次判断失误风险（与启发式搜索单次决定不同）；
• 可处理随机性和不完全信息：通过随机模拟环境，天然能处理随机游戏或对手的不确定行为；
• ⭐ 理论保证：当模拟次数趋于无穷时，UCT 算法选择的路径以概率 1 收敛到最优决策。

缺点：

• 计算代价高：需大量模拟；纯 MCTS 围棋接近职业水平需每步上亿次模拟，实际时间只够几万次，需改进模拟效率；
• 对模拟策略敏感：随机模拟可能与真实对抗相差很远——某状态在随机 playout 下胜率一般，但最佳对抗下其实是败局，MCTS 会被误导（AlphaGo 前的围棋程序就发现纯随机模拟对接近终局双方水平不敏感，需引入棋形等知识）；
• 内存占用：搜索树可能含成千上万节点，超大空间需剪枝/合并；过大分支数拖慢每次选择阶段遍历。

7.6 应用案例：AlphaGo (Zero)

围棋的挑战

• 分支因子：平均每步 200~300 个可选位置；
• 博弈树规模：$>10^{170}$；
• 传统 Minimax + α-β 几乎无法奏效：缺乏有效评估函数，也搜不到足够深度。

AlphaGo 的方法

• 强化学习方法：Actor-Critic、策略网络 (policy network)、价值网络 (value network)；
• 从人类数据学习 (learns from human data)、自我对弈 (self-play)、价值评估 (value evaluation)；
• 结合策略网络、价值网络进行 MCTS，最终下子。

⭐ MCTS in AlphaGo（Zero）—— PUCT

AlphaGo 中的 MCTS 一般称为 PUCT (Polynomial UCT)，与经典 UCT 略有差异，主要步骤：

① 选择：与经典 UCT 相似，但引入先验概率 $P(s,a)$（由策略网络给出）：

$$\text{PUCT}(s,a)=Q(s,a)+c\,P(s,a)\frac{\sqrt{N(s)}}{1+N(a)}$$

（先验概率 $P(s,a)$ 让搜索偏向策略网络认为有希望的着法。）

② 扩展：生成所有可能下一步走法的子节点，并以策略网络产生的先验概率 $P(s,a)$ 初始化各子节点。

③ 模拟：相比纯随机，结合价值网络 (value network) 大幅提高估计准确度、减少模拟步数：

• AlphaGo 早期版本：执行一定深度的随机模拟，再用价值网络评估终止前局面；
• AlphaGo Zero 及之后：常直接用价值网络评估叶节点价值，无需随机走到终局。

④ 回溯：将价值网络或模拟得到的胜率沿搜索路径回传。

AlphaGo 的搜索流程

1. 策略网络先给出"可能性分布"，让 MCTS 大概率选择更有希望的着法扩展；
2. 价值网络直接评估局面胜率，无需长串随机走子；
3. MCTS 在有限时间内执行数千到上万次模拟迭代，形成对各分支胜率较为准确的估计；
4. 输出动作：一般选取根节点子节点中访问次数最多的一步落子。

其他应用：基于 MCTS 的自动驾驶行为规划

• 目标函数：优化行驶安全、效率、舒适等（具体形式见原课件，需对照原课件查看）；
• 搜索树结构：
  • 节点 = 车辆及环境在当前离散时刻的状态；
  • 边 = 自车执行的一步动作（加速、减速、保持速度、换道）；
  • 根节点 = 当前时刻的环境状态；
• 典型场景：无保护左转、离开高速公路等；
• MCTS 选择采用 UCT 类公式（带场景特定奖励）。

关键概念速查表

本章关键概念清单

• [ ] 说明博弈与普通搜索的两个本质区别（对手不可预测 → 策略；时间限制 → 近似）
• [ ] 按"确定/随机 × 完全/不完全信息"对常见棋类分类
• [ ] 写出正常形式博弈元组定义与期望效用公式
• [ ] 解释最优反应 (Best-Response) 与 Nash 均衡，并知道"NFG 至少存在一个均衡"
• [ ] 陈述双人零和博弈的特点：均衡唯一/可互换、Minimax 定理、可作线性规划求解
• [ ] 默写 Minimax 值的递归定义与伪代码（MAX/MIN/终局三分支）
• [ ] 说出 Minimax 的完备性、最优性、时间 $O(b^m)$、空间 $O(bm)$
• [ ] 解释 α、β 的含义，写出剪枝条件 β<α
• [ ] 默写 α-β 算法伪代码，并说明"剪枝不影响最终结果"
• [ ] 说出 α-β 在完美排序下的复杂度 $O(b^{m/2})$ 及其意义（深度翻倍）
• [ ] 写出线性评估函数 $\text{Eval}=\sum w_i f_i$，解释"序数效用"
• [ ] 说明为何用迭代加深 (IDS) 应对时间限制
• [ ] 写出随机博弈元组 $(n,S,A,T,R)$
• [ ] 默写 Expectiminimax 的三分支定义（含 CHANCE 取期望）
• [ ] 解释"最大期望效用原则"为何是理性定义
• [ ] 说明不完全信息博弈如何用"期望极小极大 over deals"求解
• [ ] 用蒙特卡洛方法求 π 与定积分（一般形式含 $p(x)$）
• [ ] 陈述大数定律（弱/强）与中心极限定理，解释蒙特卡洛收敛性 $O(1/\sqrt n)$
• [ ] 说明伪随机数为何可用于蒙特卡洛（均匀性/独立性/长周期）
• [ ] 描述多臂老虎机与探索-利用权衡
• [ ] 比较三种平衡策略：ε-贪心、乐观初值、UCB
• [ ] 默写 UCB1 公式 $\hat{\mu}_a+c\sqrt{\ln t/n_a}$ 并解释利用项与探索项
• [ ] 列出 MCTS 四步：Selection / Expansion / Simulation / Backprop
• [ ] 默写 UCT 公式 $Q(a)+c\sqrt{\ln N(s)/N(a)}$
• [ ] 走一遍 MCTS 三次迭代示例
• [ ] 说出 MCTS 五大优点与三大缺点
• [ ] 说明 PUCT 与 UCT 的差异（引入 $P(s,a)$ 先验）
• [ ] 描述 AlphaGo(Zero) 如何用策略网络 + 价值网络 + MCTS 下棋