Let's build AlphaZero

本文是对于 Sunrise：从头理解 AlphaZero，MCTS，Self-Play，UCB 等文章、视频教程和代码实现的消化与理解。
本文将从 AlphaGo 的设计原理出发，通过深入理解 MCTS 和 Self-Play 这两个核心机制，逐步揭示如何构建一个能超越人类的 AI 五子棋（Gomoku）系统。

AlphaGo：从模仿到超越#

AlphaGo 的进化路径#

围棋的可能局面数超过宇宙中的原子数量，使得传统穷举搜索方法完全失效。AlphaGo 通过一个分阶段的方法解决这个问题：先学习人类知识，然后通过 self-play 不断进化。
Pasted image 20241116201853
这个进化过程可以分为三层：

模仿人类高手
自我博弈提升
学习评估局势

核心组件#

Pasted image 20241115170343

快速走子策略（Rollout Policy）#

最左边的一个轻量级策略网络，用于快速评估，准确性较低但计算效率高。

SL 策略网络#

监督学习策略网络 $P_{\sigma}$ 通过模仿人类棋谱学习下棋：

输入：棋盘状态
输出：模仿人类专家的下一步走法概率分布
训练数据：16 万场对局，约 3000 万个落子步骤

RL 策略网络#

类似当你棋艺达到一定水平时，开始自己复盘，自己和自己对战，发现新的战术和更深的策略。RL 网络 $P_{\rho}$ 从 SL 网络初始化，该网络已经远超人类，可以找到许多人类未曾发现的强力策略。

这个阶段生成了大量 self-play 的数据，输入依然是棋盘状态，输出是通过强化学习改进的走棋策略。
与历史版本的策略网络 $p_\pi$ 进行 self-play，网络通过 “赢棋” 信号来调整参数，通过 Policy Gradiant 强化那些导致胜利的走法。：

\sum_{t} z(\tau) \log p(a_t \mid s_t; \rho)

其中：

$\tau$ 是对局序列 $(s_0,a_0,s_1,a_1,...)$
$z(\tau)$ 是胜负标签（胜为正，负为负）

价值网络#

价值网络 $v_\theta$ 学习评估局势，可以是个 CNN：

训练目标：最小化均方误差

\sum_{i} (z - v_\theta(s))^2

$z$ ：最终胜负结果
$v_\theta(s)$ ：预测的获胜概率

补充解释#

关于 $P_\rho$ 和 $v_\theta$ 的关系：

策略网络 $P_\rho$ 提供具体的走子概率，用于指导搜索。
价值网络 $v_\theta$ 提供局面评估，减少搜索树中不必要的模拟。
两者配合，使 MCTS 不仅能更快地探索高胜率路径，还能显著提升整体的下棋水平。

AlphaGo 的 MCTS 实现#

Selection 阶段#

结合了探索与利用：

a_t = \arg\max_a Q(s_t, a) + u(s_t, a)

u(s_t, a) \propto \frac{P(s_t, a)}{1 + N(s_t, a)}

其中：

$Q(s_t, a)$ ：长期回报估计
$u(s_t, a)$ ：探索奖励
$P(s_t, a)$ ：策略网络输出的先验概率
$N(s_t, a)$ ：访问次数

Simulation 与评估#

在原始的 MCTS 算法中，模拟阶段 (Simulation) 的作用是通过快速 rollout 策略从叶子节点（扩展的新节点）进行随机对弈，直至游戏结束，然后根据对弈的胜负得到一个回报。这个回报被传递回搜索树中的节点，用于更新这些节点的值估计（即 $Q(s, a)$ ）。

这样的实现简单直接，但是 rollout 策略通常是随机或简单的规则，模拟质量可能较差。且只能给出短期信息，无法很好地结合全局的战略评估。

而 AlphaGo 在模拟阶段结合了 Value Network $v_\theta$ 和 rollout 策略。Value Network 提供了更高效的叶子节点估计和全局能力评估，rollout 策略通过快速模拟捕捉局部的短期效果。

使用超参数 $\lambda$ 权衡 $v_\theta(s_L)$ 和 $z_L$ ，兼顾局部模拟和全局评估。评估函数：

V(s_L) = (1 - \lambda)v_\theta(s_L) + \lambda z_L

Backpropagation#

n 次 MCTS 时节点访问次数更新（ $\mathbb{I}$ 是指示函数，访问则为 1）：

N(s_t, a) = \sum_{i=1}^{n} \mathbb{I}(s, a, i)

Q 值更新，即执行 a 到节点 $s_t$ 的长期预期回报：

Q(s_t, a) = \frac{1}{N(s_t, a)} \sum_{i=1}^{n} \mathbb{I}(s, a, i) V(s_L^i)

总结#

结构创新：
- 策略网络提供先验知识
- 价值网络提供全局评估
- MCTS 提供战术验证
训练创新：
- 从监督学习起步
- 通过强化学习超越教师
- 自我博弈产生新知识
MCTS 改进：
- 使用神经网络指导搜索
- Policy Network 提了探索方向的先验概率，Value Network 提升了叶子节点评估的准确性。
- 这样结合价值网络和 rollout 的评估，不仅减少了搜索宽度和深度，还显著提高了整体性能。
- 高效的探索 - 利用平衡

这种设计使 AlphaGo 能在庞大的搜索空间中找到高效的解决方案，最终超越人类水平。

启发式搜索与 MCTS#

MCTS 就像是一个不断进化的探索者，在决策树中寻找最佳路径。

核心思想#

MCTS 的本质是什么？简单来说，它是一个 "边玩边学" 的过程。想象你在玩一盘全新的棋类游戏：

开始时，你会尝试各种可能的走法（探索）
慢慢发现某些走法效果更好（利用）
在探索新策略和利用已知好策略之间取得平衡

这正是 MCTS 所做的，只不过它用数学的方式来系统化这个过程。其是一种 rollout 算法，通过累计蒙特卡洛模拟的价值估计来引导策略选择。

算法流程#

Monte Carlo Tree Search - YouTube这个老师对于 MCTS 的流程讲的很好。

MCTS 的优雅之处在于它的四个简单但强大的步骤，这里我用 A、B 两种理解方式来介绍：

选择 (Selection)
- A：你知道小孩子是怎么学习的吗？他们总是在已知和未知之间徘徊。MCTS 也是如此：从根节点开始，使用 UCB (Upper Confidence Bound) 公式来权衡是选择已知的好路径，还是去探索新的可能。
- B：从根节点出发，依据特定策略从当前节点中选择一个后续节点。该策略通常基于树的搜索历史，选取最具潜力的路径。例如，我们在每个节点依据当前的策略 $\pi(s)$ 执行动作 $a$ ，以平衡探索与利用，逐步深入。
扩展 (Expansion)
- A：就像探险家在地图上开辟新的区域，当我们到达一个叶节点时，我们会向下扩展，创建新的可能性。
- B：当选中的节点尚有未探索的子节点时，我们在此节点下依据可行动作集扩展新节点。这一过程的目的是增加决策树的广度，逐步生成可能的决策路径。通过这一扩展操作，我们确保搜索涵盖更多可能的 state action pair $(s,a)$ 。
模拟 (Simulation)
- A：这是最有趣的部分。从新节点开始，我们进行一次 "假想" 的游戏，直到游戏结束。这就像下棋时在脑中推演 "如果我这样走，对手那样走..."。
- B：从当前拓展的节点出发，执行随机模拟（rollout），在 MDP 环境中沿着当前策略 $\pi(s)$ 进行采样直至终止状态。此过程提供了从当前节点出发到终点的回报估计，为路径的优劣提供数值依据。
回溯 (Backpropagation)
- A：最后，我们把得到的结果沿路径返回，更新每个节点的统计信息。这就像在说："嘿，我试过这条路，效果还不错（或不太好）"。
- B：完成模拟后，将该模拟的估计回报回溯到经过的所有节点，以更新这些节点的价值。这一过程累积了历史回报信息，使得未来的选择更加精确地趋向高收益路径。

Screenshot 2024-10-31 at 15.19.31

UCB1：探索与利用的完美平衡#

这里要特别提到 UCB1 公式，它是 MCTS 的灵魂：

UCB1 = X̄ᵢ + C × \sqrt{(ln(N)/nᵢ)}

让我们解构一下：

$X̄ᵢ$ 是平均收益（利用项）
$\sqrt{(ln(N)/nᵢ)}$ 是不确定性度量（探索项）
$C$ 是探索参数

就像一个优秀的投资组合，既要关注已知的好机会，也要保持对新机会的开放（探索 - 利用权衡）。

Best Multi-Armed Bandit Strategy? (feat: UCB Method) 这个视频对 Multi-Armed Bandit 和 UCB Method 讲的很好，我这里借鉴这个老师用的例子：

一个吃货尝试理解 UCB#

想象你刚到一个城市，有 100 家餐厅可选择，你有 300 天时间。每天你都要选择一家餐厅就餐，希望在这 300 天里平均吃到最好的美食。

ε-greedy 策略：简单但不够智能#

这就像是用掷骰子决定：

90% 的时间 (ε=0.1)：去已知最好的餐厅（利用）
10% 的时间：随机尝试一家新餐厅（探索）

def epsilon_greedy(restaurants, ratings, epsilon=0.1):
    if random.random() < epsilon:
        return random.choice(restaurants)  # 探索
    else:
        return restaurants[np.argmax(ratings)]  # 利用

这样的效果是：

探索完全随机，可能重复访问已知很差的餐厅
探索比例固定，不会随时间调整
不考虑访问次数的影响

UCB 策略：更智能的选择权衡#

UCB 公式在餐厅选择中的含义如下：

评分 = 平均得分 + C × \sqrt{ln(总访问天数)/该餐厅访问次数}

例如，考虑两家餐厅在第 100 天时的情况：

A 餐厅：

访问 50 次，平均分 4.5
UCB 分数 = $4.5 + 2×\sqrt{ln(100)/50} ≈ 4.5 + 0.6 = 5.1$

B 餐厅：

访问 5 次，平均分 4.0
UCB 分数 = $4.0 + 2×\sqrt{ln(100)/5} ≈ 4.0 + 1.9 = 5.9$

虽然 B 餐厅平均分较低，但因为访问次数少，不确定性高，所以 UCB 给予更高的探索奖励。

Screenshot 2024-11-07 at 13.24.48

代码实现：

class Restaurant:
    def __init__(self, name):
        self.name = name
        self.total_rating = 0
        self.visits = 0
        
def ucb_choice(restaurants, total_days, c=2):
    # 确保每家餐厅至少访问一次
    for r in restaurants:
        if r.visits == 0:
            return r
            
    # 使用UCB公式选择餐厅
    scores = []
    for r in restaurants:
        avg_rating = r.total_rating / r.visits
        exploration_term = c * math.sqrt(math.log(total_days) / r.visits)
        ucb_score = avg_rating + exploration_term
        scores.append(ucb_score)
        
    return restaurants[np.argmax(scores)]

为什么 UCB 更好？#

自适应探索
- 访问次数少的餐厅获得更高的探索奖励
- 随着总天数增加，探索项会逐渐减小，以更好地进行利用
平衡时间投资
- 不会在明显较差的餐厅上浪费太多时间
- 会在潜力相近的餐厅之间合理分配访问次数
理论保证
- Regret Bound（与最优选择的差距）随时间呈对数增长
- 300 天的探索足够找到最好的几家餐厅

我们回到 MCTS。

为什么 MCTS 如此强大？#

无需领域知识
它不需要任何特定的游戏策略知识，仅通过自我探索就能找到好的行动。
可随时停止
任何时候中断搜索都能给出当前最佳选择。这在实时系统中特别有用。
天然的探索 - 利用平衡
通过 UCB 机制，自动在探索新策略和利用已知好策略之间取得平衡。

Nagi-ovo