强化学习（八）—— AlphaGo 与蒙特卡洛树搜索

2016 年 3 月,当 AlphaGo 以 4:1 战胜世界围棋冠军李世石时,全球为之震撼——围棋曾被认为是 AI 最难攻克的堡垒,因为其搜索空间达到$10^{{170} $远超宇宙原子数$ 10}{80}$),传统的暴力搜索完全无效。 AlphaGo 的成功不是单一算法的胜利,而是蒙特卡洛树搜索(MCTS)、深度学习、强化学习三者的完美融合。更令人惊叹的是,一年半后的 AlphaGo Zero 完全抛弃人类棋谱,仅通过自我对弈从零开始学习,3 天内就超越了人类数千年的围棋智慧。随后 AlphaZero 将这一范式泛化到国际象棋和将棋,MuZero 进一步摆脱了游戏规则的限制,学会了在不知道环境动态的情况下规划。这一系列突破不仅改变了棋类 AI 的格局,也为强化学习与搜索的结合提供了全新的范式——如何在巨大的状态空间中高效规划,如何让 AI 自己发现知识,如何在没有模型的情况下进行前瞻规划。本章将从 MCTS 的数学基础讲起,逐步深入 AlphaGo 、 AlphaGo Zero 、 AlphaZero 、 MuZero 的核心设计,并通过完整代码实现帮助你真正理解这些算法的精髓。

¶蒙特卡洛树搜索：搜索与采样的平衡

¶为什么需要 MCTS？

在围棋中,每一步平均有 250 种可能的落子,一局棋平均 150 步,完整搜索树的分支数达到。国际象棋的分支因子约 35,平均 80 步,搜索空间"仅"——仍然是天文数字,但比围棋小得多。传统的 AlphaBeta 剪枝算法在国际象棋上有效,但在围棋上完全失效。 MCTS 的核心思想是:不要均匀地搜索所有分支,而是集中计算资源在最有希望的路径上。

¶MCTS 的四个步骤

![](./强化学习（八）—— AlphaGo 与蒙特卡洛树搜索/gif1_mcts.gif)

MCTS 通过迭代执行四个步骤构建搜索树:

1. 选择(Selection):从根节点开始,使用某种策略(如 UCT)选择子节点,直到到达叶子节点。

2. 扩展(Expansion):如果叶子节点不是终止状态,随机选择一个未探索的动作,添加新的子节点。

3. 模拟(Simulation):从新节点开始,使用快速策略(如随机策略或简单启发式)模拟到游戏结束,得到回报。

4. 回溯(Backpropagation):将回报沿路径反向传播,更新路径上所有节点的统计量(访问次数和累积价值)。

这四个步骤不断重复,搜索树逐渐向有希望的方向生长。最终,在根节点选择访问次数最多的动作作为实际决策。

¶UCT 算法

![](./强化学习（八）—— AlphaGo 与蒙特卡洛树搜索/fig2_ucb.png)

：探索与利用的数学平衡

选择步骤的关键是如何平衡探索(exploration)和利用(exploitation)。 UCT(Upper Confidence bounds applied to Trees)算法使用以下公式:

a^{*} = \arg\max_{a} \left( \frac{W(s,a)}{N(s,a)} + c \sqrt{\frac{\ln N(s)}{N(s,a)}} \right)
$$

其中:

:从状态选择动作的累积价值
:从状态选择动作的访问次数
:状态的访问次数
:探索常数(通常取)

第一项 是平均价值,代表利用——选择已知的好动作。

第二项 是置信上界,代表探索——鼓励尝试访问较少的动作。

这个公式有着深刻的数学根源——它来自**多臂老虎机(Multi-Armed Bandit)**问题的 UCB1 算法。当某个动作被访问次数很少时,第二项很大,算法倾向于探索它;当被访问很多次后,第二项减小,算法更依赖平均价值。

关键性质:UCT 保证了渐近最优性——随着模拟次数趋于无穷,UCT 选择的动作概率收敛到最优动作。数学上,这是通过 Hoeffding 不等式证明的:

P\left( \left| \frac{W(s,a)}{N(s,a)} - Q^{*}(s,a) \right| > \epsilon \right) \leq 2 e^{{-2N(s,a)\epsilon}2}
$$

这个不等式说明,随着增加,估计值以指数速率收敛到真实价值。

¶MCTS 的优势与局限

优势:

不需要领域知识:基础的 MCTS 只需要游戏规则(模拟器),不需要启发式评估函数
任何时间算法:可以随时停止并返回当前最佳动作,计算时间越长结果越好
自适应:自动在有希望的分支上投入更多计算资源

局限:

计算昂贵:需要大量模拟才能得到可靠的估计
随机策略效率低:在复杂游戏中,随机模拟很少到达有意义的状态
无法直接处理连续动作空间:UCT 假设动作是离散且有限的

AlphaGo 的突破正是解决了后两个问题——用神经网络替代随机模拟,并提供先验知识指导搜索。

¶AlphaGo：监督学习+强化学习+搜索

![](./强化学习（八）—— AlphaGo 与蒙特卡洛树搜索/fig1_alphago.png)

¶AlphaGo 的三阶段训练

AlphaGo 的训练分为三个阶段:

阶段 1:监督学习策略网络

使用 16 万局人类专家棋谱,训练一个 13 层卷积神经网络预测人类落子
输入: 的棋盘特征(当前棋子、历史棋子、合法性等)
输出:361 维的动作概率分布(19x19 的棋盘位置)
准确率:57.0%——与人类专家在测试集上的一致性

阶段 2:强化学习策略网络

将监督学习的网络作为初始化
通过自我对弈进行策略梯度优化:
$$\nabla_\rho J(\rho) = \mathbb{E}{s \sim \rho, a \sim p\rho} \left[ \nabla_\rho \log p_\rho(a|s) z \right]
$$

其中是游戏结果(胜/负)

对手从历史版本的策略池中随机采样,防止过拟合
相比监督策略,RL 策略的胜率提升到 80%

阶段 3:价值网络

训练一个网络预测在状态下采用策略的胜率:
$$

v_\theta(s) \approx v^{p_\rho}(s) = \mathbb{E}{s’ \sim p\rho} [z | s]
$$- 数据生成:用 RL 策略自我对弈生成 3000 万个(状态,结果)对

关键技巧:每局棋只采样一个状态,避免同一局棋的状态高度相关导致过拟合
测试集 MSE:0.226(相比随机 baseline 的 0.5 大幅降低)

¶AlphaGo 的 MCTS 集成

AlphaGo 的 MCTS 不同于传统的四个步骤:

1. 选择(Selection):使用修改的 UCT 公式:
$$

a^{*} = \arg\max_{a} \left( Q(s,a) + u(s,a) \right)
$$

其中:

u(s,a) = c_{puct} P(s,a) \frac{\sqrt{N(s)}} {1 + N(s,a)}
$$

这里是监督策略网络的先验概率。注意:

先验引导搜索朝人类专家认可的方向
当时, 很大,鼓励探索高先验的动作
当增加, 减小,算法更依赖价值
2. 扩展(Expansion):到达叶子节点时,用策略网络初始化所有动作的先验:
$$

P(s_L, a) = p_\sigma(a | s_L)
$$

3. 评估(Evaluation):不再进行随机模拟,而是用价值网络和快速 rollout 策略(一个小的线性 softmax)的加权平均:
$$

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

其中是用模拟到终止状态的结果,。

4. 回溯(Backpropagation):更新路径上的节点统计:
$$

N(s,a) \leftarrow N(s,a) + 1
$

$$
W(s,a) \leftarrow W(s,a) + V(s_L)
$

最终决策:在根节点,选择动作的概率正比于访问次数:

其中温度参数控制探索度:

前 30 步取(成比例选择,保持探索)
之后(选择访问次数最多的动作)

¶AlphaGo 的网络架构细节

策略网络和:

输入: 特征平面
- 8 个历史时间步的己方/对方棋子(16 个平面)
- 1 个颜色特征(黑/白)
- 合法性、被吃子、征子等特征
卷积层:13 层,每层 256 个滤波器,ReLU 激活
输出: 的 softmax 分布

价值网络:

架构与策略网络类似,最后一层改为单个神经元输出值
输入特征增加一个旋转数据增强

快速 rollout 策略:

线性 softmax,只使用局部特征
每步只需 2 微秒(策略网络需 3 毫秒)
用于加速评估阶段的模拟

¶AlphaGo 对 Lee Sedol 的表现

AlphaGo 使用 1920 个 CPU 和 280 个 GPU,每步思考平均 40 秒,进行约 10 万次 MCTS 模拟。关键的第 37 手(Ledge 2, Game 2)和第 78 手(Ladder, Game 4)展现了 AlphaGo 的创造性——这些落子初看不合理,但实际上是全局最优的深度规划结果。 Lee Sedol 在第 4 局第 78 手的"神之一手"也证明了人类直觉仍有独特价值,AlphaGo 在那之后的 19 步内陷入混乱,表明其对某些罕见模式的泛化能力不足。

¶AlphaGo Zero：从零开始的自我对弈

![](./强化学习（八）—— AlphaGo 与蒙特卡洛树搜索/gif2_self_play.gif)

¶三大突破

AlphaGo Zero 在 2017 年 10 月发表于 Nature,相比 AlphaGo 有三大根本性改进:

1. 完全抛弃人类棋谱:只用黑白棋子和游戏规则,从完全随机的策略开始自我对弈学习。

2. 单一网络 ：将策略网络和价值网络合并为一个双头网络：

是动作概率向量
是胜率估计

这个设计基于直觉：策略和价值都依赖于对局面的理解，共享表示可以加速学习。

3. 不使用快速 rollout：完全依赖价值网络评估叶子节点，不再进行随机模拟。这使得评估更准确，也简化了算法。

¶训练流程

AlphaGo Zero 的训练是一个自我对弈的闭环：

步骤 1：自我对弈

使用当前最佳网络，通过 MCTS 生成自我对弈数据
每一步，MCTS 运行次模拟，计算改进的策略：

保存三元组:状态、改进策略、最终结果

步骤 2:训练网络

从 replay buffer 中采样 mini-batch,优化损失函数:
$$

L = (z - v)^2 - \pi^T \log p + c |\theta|^2
$$

第一项是价值损失(MSE),第二项是策略损失(交叉熵),第三项是 L2 正则化。

步骤 3:评估与更新

让新网络与当前最佳网络对弈 400 局
如果新网络胜率>55%,则更新最佳网络

¶AlphaGo Zero 的 MCTS

选择步骤的 UCT 公式变为:

a^{*} = \arg\max_{a} \left( Q(s,a) + c_{puct} P(s,a) \frac{\sqrt{N(s)}} {1 + N(s,a)} \right)
$$

其中来自网络输出,而非监督学习的先验。

评估步骤直接使用:
$$

V(s_L) = v(s_L)
$$

没有 rollout 混合。

¶为什么自我对弈有效？

自我对弈的成功依赖于课程学习(Curriculum Learning):

初期:双方都是随机策略,游戏很快结束,梯度信号强
中期:策略逐渐变强,对手也变强,始终保持适度挑战
后期:双方都接近完美策略,探索微妙的战术细节

这比从固定的人类棋谱学习更高效,因为:

人类棋谱覆盖的状态空间有限(主要是开局定式)
人类有偏见和错误,AI 可能学到这些缺陷
自我对弈可以持续探索未知的局面

数学上,自我对弈类似于虚拟策略迭代(Fictitious Self-Play):

在双人零和博弈中,这个迭代会收敛到 Nash 均衡。 AlphaGo Zero 的 MCTS 正是在每一步计算一个"局部 best-response",然后用监督学习将其提炼到网络中。

¶性能对比

AlphaGo Zero 用 3 天训练(490 万局自我对弈)就以 100:0 击败 AlphaGo Lee 版本;用 40 天训练后,以 89:11 击败 AlphaGo Master 版本(曾在网上 60 连胜人类顶尖棋手)。更惊人的是,AlphaGo Zero 的 Elo 等级分增长曲线几乎是线性的——从 0 到 5000 点只用了 72 小时,而人类从入门到职业需要数年。

¶AlphaZero：泛化到国际象棋与将棋

¶从专用到通用

AlphaZero 在 2018 年 Science 论文中展示了相同算法在三种棋类(围棋、国际象棋、将棋)上的统治力。唯一的修改是:

1. 游戏规则编码:每个游戏使用不同的状态表示

围棋:
国际象棋:(包括棋子类型、移动历史、王车易位权限等)
将棋:(包括持有的被吃棋子)

2. 超参数调整:

国际象棋和将棋的 MCTS 模拟次数减少到 800(因为分支因子更小)
探索常数针对每个游戏调优

3. 网络架构:统一为 20 个残差块,每块 256 个滤波器,总参数约 4600 万。

¶训练细节与结果

围棋:70 万步(相当于 2100 万局自我对弈),Elo 5018,超越 AlphaGo Zero
国际象棋:30 万步(4400 万局),4 小时后超越 Stockfish(传统最强引擎),9 小时后达到 Elo 4450
将棋:10 万步(400 万局),2 小时后超越 Elmo(日本冠军程序),训练后 Elo 4650

AlphaZero 对 Stockfish 的 100 局对决中,胜 28 局,和 72 局,无一败绩。更重要的是,AlphaZero 的棋风更"人类化"——愿意牺牲子力换取位置优势,而传统引擎更依赖物质计算。 Chess.com 的大师们评价 AlphaZero"像来自未来的棋手"。

¶为什么能泛化？

AlphaZero 的泛化能力来自:

通用的搜索框架:MCTS 不依赖游戏特定的启发式
强大的表示学习:残差网络自动学习特征,无需手工设计
自我对弈的鲁棒性:不受人类偏见限制,探索更广阔的策略空间

这一范式的成功表明:搜索+学习比单纯的记忆(如开局库)或纯暴力计算更接近通用智能。

¶MuZero：无需规则的规划

¶核心挑战

AlphaZero 依赖游戏规则进行 MCTS 模拟——在国际象棋中,它知道"马走日"、"吃过路兵"等规则。但许多实际问题(如机器人控制、视频游戏)的规则未知或难以编程。 MuZero 的突破在于:学习一个隐式模型,在隐空间中进行规划。

¶三个学习的函数

MuZero 学习三个函数:

1. 表示函数:将观测映射到隐状态

s^0 = h_\theta(o)
$$

2. 动态函数:预测下一个隐状态和即时奖励

注意: 不是真实环境的状态,而是学习的抽象表示。不需要预测真实的下一个观测,只需足够用于规划。

3. 预测函数:输出策略和价值

三个函数共享参数,联合训练。

¶MuZero 的 MCTS

在根节点,MuZero 执行 MCTS:

选择:与 AlphaZero 相同的 UCT 公式:

a^k = \arg\max_{a} \left( Q(s^k, a) + c_{puct} P(s^k, a) \frac{\sqrt{N(s^k)}} {1 + N(s^k, a)} \right)
$$

扩展:到达叶子节点时,展开一个新动作,用动态模型生成虚拟下一状态:

然后用预测函数初始化:

评估:直接使用,回溯时累积路径上的奖励:
$$

G^k = r^k + \gamma G^{k+1}
$$

关键区别:整个搜索树在隐空间中展开,不需要真实的环境模拟器。和都是学习的神经网络。

¶训练目标

MuZero 的损失函数包括三项:

L = \sum_{k=0}^{K} \left[ l^p(\pik, p^k) + l^v(zk, v^k) + l^r(uk, r^k) \right]
$$

:策略损失,MCTS 改进策略与网络预测的交叉熵
$l^{v $价值损失真实回报$ z}k $与预测$ v^k$ 的 MSE
$l^{r $奖励损失真实即时奖励$ u}k $与预测$ r^k$ 的 MSE

其中是展开步数(Atari 游戏中通常取 5)。注意:

只有时, 来自真实观测
时, 来自动态模型的递归预测
真实的来自 replay buffer 中的实际经验

这个设计巧妙地将 Model-Based 和 Model-Free 结合:

在规划时使用学习的模型(Model-Based)
在训练时用真实经验监督(Model-Free 的数据效率)

¶重构损失(Reanalysis)

MuZero 引入一个关键技巧:Reanalysis——用新网络重新分析旧经验:

Replay buffer 中存储的是,即观测、动作、奖励、回报
训练新网络时,用重新运行 MCTS,得到改进策略
这让旧数据的价值随着网络变强而增加,类似 Dyna-2 的思想

¶MuZero 的表现

在 Atari 57 个游戏中,MuZero 达到 AlphaZero 同级别的性能,但不需要知道游戏规则。更重要的是,MuZero 在一些高度随机的游戏(如 Ms. Pac-Man)上超越了 Model-Free 的 Agent57,因为规划帮助它在长期策略上更一致。

在围棋和国际象棋上,MuZero 与 AlphaZero 持平——这证明了隐式模型足够表达游戏的关键结构,即使它不预测像素级的下一帧。

¶完整代码实现： MCTS+神经网络下五子棋

下面的代码实现一个简化版的 AlphaZero,在五子棋上训练。完整包括:

MCTS 的四个步骤
策略-价值双头网络
自我对弈数据生成
训练循环

import torch
import torch.nn as nn
import torch.optim as optim
import numpy as np
from collections import deque
import random

# ============ 五子棋环境 ============
class GomokuEnv:
    def __init__(self, board_size=15):
        self.size = board_size
        self.reset()
    
    def reset(self):
        self.board = np.zeros((self.size, self.size), dtype=np.int8)
        self.current_player = 1  # 1=黑, -1=白
        self.done = False
        self.winner = 0
        return self.get_state()
    
    def get_state(self):
        """返回 3 通道状态: [当前玩家棋子, 对手棋子, 颜色指示]"""
        state = np.zeros((3, self.size, self.size), dtype=np.float32)
        state[0] = (self.board == self.current_player).astype(np.float32)
        state[1] = (self.board == -self.current_player).astype(np.float32)
        state[2] = np.full((self.size, self.size), self.current_player)
        return state
    
    def legal_actions(self):
        """返回合法动作的坐标列表"""
        return list(zip(*np.where(self.board == 0)))
    
    def step(self, action):
        """执行动作(row, col)"""
        if self.board[action] != 0:
            raise ValueError(f"非法落子: {action}")
        
        self.board[action] = self.current_player
        
        # 检查胜利
        if self._check_win(action):
            self.done = True
            self.winner = self.current_player
            return self.get_state(), self.winner, True
        
        # 检查平局
        if len(self.legal_actions()) == 0:
            self.done = True
            return self.get_state(), 0, True
        
        self.current_player *= -1
        return self.get_state(), 0, False
    
    def _check_win(self, last_move):
        """检查 last_move 是否形成五子连珠"""
        directions = [(0,1), (1,0), (1,1), (1,-1)]  # 横竖斜四个方向
        player = self.board[last_move]
        
        for dr, dc in directions:
            count = 1  # 包括 last_move 自己
            # 正方向
            r, c = last_move[0] + dr, last_move[1] + dc
            while 0 <= r < self.size and 0 <= c < self.size and self.board[r,c] == player:
                count += 1
                r += dr
                c += dc
            # 反方向
            r, c = last_move[0] - dr, last_move[1] - dc
            while 0 <= r < self.size and 0 <= c < self.size and self.board[r,c] == player:
                count += 1
                r -= dr
                c -= dc
            
            if count >= 5:
                return True
        return False

# ============ 策略-价值网络 ============
class PolicyValueNet(nn.Module):
    def __init__(self, board_size=15, num_channels=128):
        super().__init__()
        self.size = board_size
        
        # 公共表示
        self.conv1 = nn.Conv2d(3, num_channels, 3, padding=1)
        self.conv2 = nn.Conv2d(num_channels, num_channels, 3, padding=1)
        self.conv3 = nn.Conv2d(num_channels, num_channels, 3, padding=1)
        
        # 策略头
        self.policy_conv = nn.Conv2d(num_channels, 2, 1)
        self.policy_fc = nn.Linear(2 * board_size * board_size, board_size * board_size)
        
        # 价值头
        self.value_conv = nn.Conv2d(num_channels, 1, 1)
        self.value_fc1 = nn.Linear(board_size * board_size, 64)
        self.value_fc2 = nn.Linear(64, 1)
    
    def forward(self, x):
        # 公共层
        x = torch.relu(self.conv1(x))
        x = torch.relu(self.conv2(x))
        x = torch.relu(self.conv3(x))
        
        # 策略头
        p = torch.relu(self.policy_conv(x))
        p = p.view(-1, 2 * self.size * self.size)
        p = torch.log_softmax(self.policy_fc(p), dim=1)
        
        # 价值头
        v = torch.relu(self.value_conv(x))
        v = v.view(-1, self.size * self.size)
        v = torch.relu(self.value_fc1(v))
        v = torch.tanh(self.value_fc2(v))
        
        return p, v

# ============ MCTS 节点 ============
class MCTSNode:
    def __init__(self, prior, parent=None):
        self.prior = prior  # P(s,a)
        self.parent = parent
        self.children = {}  # action -> MCTSNode
        
        self.visit_count = 0
        self.value_sum = 0.0
    
    def value(self):
        if self.visit_count == 0:
            return 0
        return self.value_sum / self.visit_count
    
    def is_expanded(self):
        return len(self.children) > 0
    
    def select_child(self, c_puct=1.0):
        """UCT 选择"""
        best_score = -float('inf')
        best_action = None
        best_child = None
        
        for action, child in self.children.items():
            # Q(s,a) + c_puct * P(s,a) * sqrt(N(s)) / (1 + N(s,a))
            u = c_puct * child.prior * np.sqrt(self.visit_count) / (1 + child.visit_count)
            score = child.value() + u
            
            if score > best_score:
                best_score = score
                best_action = action
                best_child = child
        
        return best_action, best_child
    
    def expand(self, actions, priors):
        """扩展节点"""
        for action, prior in zip(actions, priors):
            if action not in self.children:
                self.children[action] = MCTSNode(prior, parent=self)
    
    def backup(self, value):
        """回溯更新"""
        self.visit_count += 1
        self.value_sum += value
        if self.parent:
            self.parent.backup(-value)  # 对手视角价值相反

# ============ MCTS ============
class MCTS:
    def __init__(self, model, c_puct=1.0, num_simulations=400):
        self.model = model
        self.c_puct = c_puct
        self.num_simulations = num_simulations
    
    @torch.no_grad()
    def search(self, env):
        """执行 MCTS,返回改进策略"""
        root = MCTSNode(prior=0)
        
        # 初始化根节点
        state = env.get_state()
        legal_actions = env.legal_actions()
        log_probs, value = self.model(torch.FloatTensor(state).unsqueeze(0))
        probs = torch.exp(log_probs).squeeze(0).numpy()
        
        # 只考虑合法动作
        action_probs = []
        for action in legal_actions:
            idx = action[0] * env.size + action[1]
            action_probs.append(probs[idx])
        action_probs = np.array(action_probs)
        action_probs /= action_probs.sum()
        
        root.expand(legal_actions, action_probs)
        
        # 模拟
        for _ in range(self.num_simulations):
            node = root
            env_copy = self._copy_env(env)
            search_path = [node]
            
            # 1. 选择
            while node.is_expanded() and not env_copy.done:
                action, node = node.select_child(self.c_puct)
                search_path.append(node)
                env_copy.step(action)
            
            # 2&3. 扩展和评估
            if not env_copy.done:
                state = env_copy.get_state()
                legal_actions = env_copy.legal_actions()
                log_probs, value = self.model(torch.FloatTensor(state).unsqueeze(0))
                probs = torch.exp(log_probs).squeeze(0).numpy()
                
                action_probs = []
                for action in legal_actions:
                    idx = action[0] * env_copy.size + action[1]
                    action_probs.append(probs[idx])
                action_probs = np.array(action_probs)
                action_probs /= action_probs.sum()
                
                node.expand(legal_actions, action_probs)
                value = value.item()
            else:
                # 终止状态,使用真实结果
                value = env_copy.winner * env_copy.current_player
            
            # 4. 回溯
            for node in reversed(search_path):
                node.backup(value)
                value = -value  # 交替玩家
        
        # 返回改进策略
        visit_counts = np.zeros(env.size * env.size)
        for action, child in root.children.items():
            idx = action[0] * env.size + action[1]
            visit_counts[idx] = child.visit_count
        
        return visit_counts / visit_counts.sum()
    
    def _copy_env(self, env):
        """深拷贝环境"""
        new_env = GomokuEnv(env.size)
        new_env.board = env.board.copy()
        new_env.current_player = env.current_player
        new_env.done = env.done
        new_env.winner = env.winner
        return new_env

# ============ AlphaZero 训练器 ============
class AlphaZeroTrainer:
    def __init__(self, board_size=15, num_simulations=100):
        self.env = GomokuEnv(board_size)
        self.model = PolicyValueNet(board_size)
        self.mcts = MCTS(self.model, num_simulations=num_simulations)
        self.optimizer = optim.Adam(self.model.parameters(), lr=1e-3, weight_decay=1e-4)
        
        self.replay_buffer = deque(maxlen=10000)
        self.batch_size = 256
    
    def self_play(self, num_games=10, temperature=1.0):
        """自我对弈生成数据"""
        for _ in range(num_games):
            states, policies, current_players = [], [], []
            self.env.reset()
            
            step = 0
            while not self.env.done:
                state = self.env.get_state()
                policy = self.mcts.search(self.env)
                
                states.append(state)
                policies.append(policy)
                current_players.append(self.env.current_player)
                
                # 温度采样
                if step < 30:
                    action_probs = policy ** (1.0 / temperature)
                    action_probs /= action_probs.sum()
                    action_idx = np.random.choice(len(policy), p=action_probs)
                else:
                    action_idx = np.argmax(policy)
                
                action = (action_idx // self.env.size, action_idx % self.env.size)
                self.env.step(action)
                step += 1
            
            # 保存数据
            winner = self.env.winner
            for state, policy, player in zip(states, policies, current_players):
                # 从当前玩家视角的价值
                value = winner * player
                self.replay_buffer.append((state, policy, value))
    
    def train_step(self):
        """训练一步"""
        if len(self.replay_buffer) < self.batch_size:
            return None
        
        batch = random.sample(self.replay_buffer, self.batch_size)
        states, target_policies, target_values = zip(*batch)
        
        states = torch.FloatTensor(np.array(states))
        target_policies = torch.FloatTensor(np.array(target_policies))
        target_values = torch.FloatTensor(np.array(target_values)).unsqueeze(1)
        
        # 前向传播
        log_probs, values = self.model(states)
        
        # 损失
        policy_loss = -torch.mean(torch.sum(target_policies * log_probs, dim=1))
        value_loss = torch.mean((target_values - values) ** 2)
        loss = policy_loss + value_loss
        
        # 反向传播
        self.optimizer.zero_grad()
        loss.backward()
        self.optimizer.step()
        
        return {
            'loss': loss.item(),
            'policy_loss': policy_loss.item(),
            'value_loss': value_loss.item()
        }
    
    def train(self, num_iterations=100, games_per_iter=10, train_steps_per_iter=100):
        """完整训练循环"""
        for i in range(num_iterations):
            print(f"\n=== Iteration {i+1}/{num_iterations} ===")
            
            # 自我对弈
            print("自我对弈中...")
            self.self_play(num_games=games_per_iter)
            
            # 训练
            print("训练网络中...")
            losses = []
            for _ in range(train_steps_per_iter):
                loss_dict = self.train_step()
                if loss_dict:
                    losses.append(loss_dict['loss'])
            
            if losses:
                print(f"平均损失: {np.mean(losses):.4f}")
                print(f"Buffer 大小: {len(self.replay_buffer)}")

# ============ 人机对弈 ============
def play_against_ai(model, board_size=15):
    """与训练好的 AI 对弈"""
    env = GomokuEnv(board_size)
    mcts = MCTS(model, num_simulations=400)
    
    print("你是黑棋(X),AI 是白棋(O)")
    print("输入坐标如: 7 7")
    
    while not env.done:
        # 显示棋盘
        print("\n 当前棋盘:")
        for i in range(board_size):
            row = []
            for j in range(board_size):
                if env.board[i,j] == 1:
                    row.append('X')
                elif env.board[i,j] == -1:
                    row.append('O')
                else:
                    row.append('.')
            print(' '.join(row))
        
        if env.current_player == 1:
            # 人类回合
            while True:
                try:
                    r, c = map(int, input("你的落子: ").split())
                    if (r, c) in env.legal_actions():
                        break
                    else:
                        print("非法位置!")
                except:
                    print("输入格式: 行 列")
            action = (r, c)
        else:
            # AI 回合
            print("AI 思考中...")
            policy = mcts.search(env)
            action_idx = np.argmax(policy)
            action = (action_idx // board_size, action_idx % board_size)
            print(f"AI 落子: {action}")
        
        env.step(action)
    
    # 游戏结束
    print("\n 最终棋盘:")
    for i in range(board_size):
        row = []
        for j in range(board_size):
            if env.board[i,j] == 1:
                row.append('X')
            elif env.board[i,j] == -1:
                row.append('O')
            else:
                row.append('.')
        print(' '.join(row))
    
    if env.winner == 1:
        print("\n 你赢了!")
    elif env.winner == -1:
        print("\nAI 赢了!")
    else:
        print("\n 平局!")

# ============ 主程序 ============
if __name__ == "__main__":
    # 训练
    trainer = AlphaZeroTrainer(board_size=9, num_simulations=100)
    trainer.train(num_iterations=50, games_per_iter=5, train_steps_per_iter=50)
    
    # 保存模型
    torch.save(trainer.model.state_dict(), "alphazero_gomoku.pth")
    
    # 人机对弈
    # model = PolicyValueNet(board_size=9)
    # model.load_state_dict(torch.load("alphazero_gomoku.pth"))
    # model.eval()
    # play_against_ai(model, board_size=9)

¶代码解析

环境部分:

GomokuEnv实现五子棋,包括状态表示、合法动作、胜利检测
get_state()返回 3 通道张量:当前玩家棋子、对手棋子、颜色指示

网络部分:

PolicyValueNet是双头网络:策略头输出,价值头输出
使用 3 层卷积提取特征,然后分别接策略和价值的全连接层

MCTS 部分:

MCTSNode存储先验、访问次数、价值和
select_child()实现 UCT 公式
expand()添加子节点并初始化先验
backup()沿路径回溯更新

训练部分:

self_play()生成数据,前 30 步用温度采样,之后贪心
train_step()优化策略损失和价值损失
运行示例:
在棋盘上,100 次模拟,训练 50 轮后 AI 已有一定水平
在棋盘上,400 次模拟,训练数百轮可接近业余水平

¶深度问答：理解 MCTS 与 AlphaGo 系列

¶Q1: UCT 公式中的项从何而来?

直觉:这来自统计学中的置信区间(Confidence Interval)。假设动作的真实价值是,我们观测到次样本,平均值。根据中心极限定理,样本均值的标准误差是。为了以高置信度保证不错过好动作,我们加上的上界。

数学推导:UCT 基于 Hoeffding 不等式:

P(|\hat{\mu} - \mu| > \epsilon) \leq 2 e^{-2N\epsilon2}
$$

令右侧等于(即以的置信度):

$$2 e^{{-2N(s,a)\epsilon}2} = \frac{1}{N(s)^2}
$$

解得:

因此置信上界是:

这正是 UCT 的形式(忽略常数因子)。

物理意义:

当很小时, 很大,算法"乐观"地认为这个动作可能很好
当增加而不变, 增加,算法被"好奇心"驱动去探索
当很大, 很小,算法"自信"地依赖经验估计

¶Q2: AlphaGo 为什么需要快速 rollout 策略?

历史原因:AlphaGo 开发时(2015-2016),价值网络的训练还不够成熟,容易过拟合到训练分布。快速 rollout 提供了一个独立的评估信号,相当于"投票"机制:

:深度学习的全局判断(慢但准)
的 rollout:蒙特卡洛采样的局部验证(快但噪)

混合使用降低了单一估计的方差。

为什么 AlphaGo Zero 不需要?:到 2017 年,残差网络和批归一化技术成熟,价值网络的泛化能力大幅提升。更重要的是,AlphaGo Zero 使用的自我对弈数据覆盖了更广的状态空间,而 AlphaGo 的数据主要来自人类棋谱(有偏)。实验表明,纯价值网络的评估已经足够准确,rollout 反而引入噪声。

数值对比:AlphaGo 的每次 MCTS 模拟耗时约 5ms(其中 2ms 是 rollout),AlphaGo Zero 的纯价值评估只需 3ms,且 Elo 提升了 600 分。

¶Q3: 自我对弈会不会陷入局部最优?

理论担忧:在博弈论中,自我对弈类似于虚拟自我博弈(Fictitious Self-Play):

其中是最佳响应(best response)。这个迭代在一般博弈中不保证收敛到 Nash 均衡,可能出现循环(如石头剪刀布)。

为什么 AlphaGo Zero 成功?:

双人零和完全信息博弈的特殊性:这类博弈的 Nash 均衡唯一且可由极小极大值获得。虚拟自我博弈在这类博弈中有收敛保证。
探索机制:MCTS 的 UCT 公式强制探索所有动作,避免策略过早崩塌到单一走法。
随机初始化:早期的随机策略导致多样化的对局,奠定了广泛的基础。
对手池:虽然 AlphaGo Zero 主要与当前最佳网络对弈,训练时的 mini-batch 采样了不同时期的数据,相当于隐式的对手池。

实验证据:论文的消融实验显示,如果移除探索(令),训练会陷入僵局。但只要,策略的多样性足以支撑持续改进。

¶Q4: AlphaZero 对 Stockfish 的胜利公平吗?

争议点:

Stockfish 运行在单核 CPU,AlphaZero 使用 4 个 TPU(相当于数千核算力)
Stockfish 使用固定深度的 AlphaBeta 搜索(约 6000 万节点/秒),AlphaZero 只搜索 8 万节点/秒,但每个节点用神经网络评估
Stockfish 有开局库和残局表,AlphaZero 完全依赖实时计算

DeepMind 的辩护:

对局时间固定(每方 1 分钟),计算资源不是主要因素
Stockfish 的节点搜索虽快,但大部分是无效探索;AlphaZero 的搜索深度更深(平均 60 层 vs 30 层)
后续测试用多核 Stockfish,AlphaZero 仍保持优势

更深层的问题:这反映了两种 AI 范式的差异:

符号 AI:Stockfish 用手工启发式(如"控制中心"、“王的安全”)和暴力搜索
连接主义 AI:AlphaZero 用学习的隐式知识和高质量的选择性搜索

AlphaZero 的棋风更接近人类大师——愿意牺牲子力换取长期位置优势,而传统引擎更"物质主义"。

¶Q5: MuZero 的隐状态到底表示什么?

关键洞察：不需要表示完整的环境状态，只需足够用于规划的抽象表示。例如在 Atari 的 Ms. Pac-Man 中：

完整状态包括像素、敌人位置、分数、关卡信息等
但规划只需要知道"下一步往哪走不会被抓"这类高层信息
可能只编码"安全区域的方向"和"豆子的大致分布"，忽略无关细节（如背景图案）

数学上：定义真实环境的转移函数为，奖励函数为。MuZero 学习的满足：

$存在隐轨迹使得：$

其中与真实策略和价值在规划意义上等价——即用展开的搜索树与用真实展开的树产生相同的最优动作。

为什么不直接预测下一帧？

像素级预测需要建模无关的视觉细节（如云彩飘动），浪费容量
隐空间的转移可以更抽象，类似人类的"心智模拟"——我们规划不需要想象逼真的画面，只需要功能性的因果关系

实验验证：论文显示，的维度（如 512 维）远小于观测（如的图像），但足以支撑 50 步的展开规划，证明了抽象的有效性。

¶Q6: MCTS 与 Model-Free RL（如 PPO）的本质区别？

规划 vs 学习：

MCTS：在每一步决策时，实时执行搜索，计算该状态下的局部最优动作。这是规划（planning）——使用模型前瞻未来。
PPO 等 Model-Free：通过大量经验训练一个策略网络，执行时直接查询网络。这是学习（learning）——记忆过去的经验。

计算开销：

MCTS：每步决策需要数百到数千次模拟，计算昂贵，但不需要训练
PPO：训练阶段需要百万次环境交互，但执行时只需一次前向传播，极快

泛化能力：

MCTS：只要有模型，可以立即适应新的状态（如中局变化）
PPO：只能泛化到训练分布附近的状态，遇到全新局面可能失效

AlphaZero 的融合：结合了两者优势：

训练时用 MCTS 生成高质量的策略（规划）
用监督学习将提炼到网络中（学习）
执行时用网络加速 MCTS 的搜索（两者协同）

这种"System 1（快速直觉）+ System 2（慢速推理）"的双系统架构，与人类认知科学的模型不谋而合。

¶Q7: 为什么 AlphaGo 的价值网络需要每局只采样一个状态？

过拟合风险：同一局棋的不同状态高度相关——前 10 步的价值都依赖于最终结果。如果全部采样，会出现：

训练集中同一局棋贡献了上百个样本
这些样本不是独立同分布（i.i.d.），违反了监督学习的假设
网络会记住特定对局的模式，而非学习通用的价值估计

数学上：假设一局棋有步，全部采样会产生个样本，它们的标签相同。这导致梯度估计的方差虚假地减小：

因为样本不独立。实际方差远小于右侧，优化器会过分自信，过早停止探索。

论文实验：对比了三种采样策略：

每局采样所有状态：价值网络在训练集上 MSE=0.01，测试集 MSE=0.37（严重过拟合）
每局采样一个状态：训练集 MSE=0.19，测试集 MSE=0.23（泛化良好）
每局采样固定比例（如 10%）：介于两者之间

最终选择策略 2,用 3000 万局生成 3000 万个独立样本。

¶Q8: AlphaZero 的残差网络有多少参数?如何训练?

架构细节:

20 个残差块,每块包含:
- 卷积,256 个滤波器
- 批归一化
- ReLU 激活
- 跳跃连接
总参数约4600 万

训练配置:

批大小:4096(使用 64 个 TPU 并行)
优化器:SGD,动量 0.9
学习率:初始 0.2,每 10 万步衰减到 0.02,然后 0.002
权重衰减:
训练时间:围棋 72 小时,国际象棋 9 小时,将棋 13 小时

关键技巧:

数据增强:围棋/将棋使用 8 重对称(旋转+翻转),国际象棋使用左右翻转
温度退火:训练前 30 步用,之后3. Dirichlet 噪声:在根节点的先验上加噪声,鼓励探索:
$$

P(s, a) = (1 - \epsilon) p(a|s) + \epsilon \eta_a, \quad \eta \sim \text{Dir}(0.3)
$$

其中

¶Q9: MuZero 如何避免模型误差累积?

挑战:在 Model-Based RL 中,模型预测误差会随规划步数指数增长:

其中是单步误差, 是展开步数。这导致长期规划不可靠。

MuZero 的解决方案:

隐空间建模: 是抽象表示,不需要预测像素级细节,减小了单步误差2. 短期展开:训练时只展开 5 步,而非几十步,限制了误差累积
价值引导:模型不需要完美预测未来,只需保证价值估计准确。即使的预测有偏,只要修正了这个偏差,规划仍然有效
端到端训练:损失函数直接优化策略和价值,而非重构精度。模型自动学会忽略不影响决策的细节

数学上:传统 Model-Based RL 优化重构误差:

L_{\text{recon}} = \mathbb{E}\left[ | o_{t+1} - \hat{o}_{t+1} |^2 \right]
$$

MuZero 优化决策质量:

L_{\text{decision}} = \mathbb{E}\left[ (z - v)^2 - \pi^T \log p \right]
$$

后者允许模型在不影响的地方"作弊",避免浪费容量。

¶Q10: MCTS 能否用于连续动作空间?

挑战:UCT 假设动作集有限,可以枚举所有子节点。在连续空间(如机器人关节角度),动作数无穷多,无法展开。

可能的扩展:

Progressive Widening:逐步增加展开的动作数,每当节点被访问次,添加个新动作(从策略分布采样)
局部优化:在叶子节点用梯度优化找到最佳动作,而非遍历
离散化:将连续空间划分为网格,但会引入离散化误差

AlphaGo 系列的选择:目前所有版本都只应用于离散动作(围棋、国际象棋、 Atari)。 DeepMind 的机器人项目(如灵巧手操作)使用的是 Model-Free 的 DDPG/SAC,而非 MCTS 。

未来方向:将 MCTS 与连续控制结合是开放问题,可能需要新的树结构或搜索策略。

¶相关论文与资源

¶核心论文

MCTS 基础:
Kocsis & Szepesv á ri (2006). “Bandit based Monte-Carlo Planning”. ECML.
https://arxiv.org/abs/cs/0703062
AlphaGo:
Silver et al. (2016). “Mastering the game of Go with deep neural networks and tree search”. Nature.
https://www.nature.com/articles/nature16961
AlphaGo Zero:
Silver et al. (2017). “Mastering the game of Go without human knowledge”. Nature.
https://www.nature.com/articles/nature24270
AlphaZero:
Silver et al. (2018). “A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play”. Science.
https://arxiv.org/abs/1712.01815
MuZero:
Schrittwieser et al. (2020). “Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model”. Nature.
https://arxiv.org/abs/1911.08265
EfficientZero:
Ye et al. (2021). “Mastering Atari Games with Limited Data”. NeurIPS.
https://arxiv.org/abs/2111.00210
将 MuZero 的样本效率提升 100 倍
Gumbel AlphaZero:
Danihelka et al. (2022). “Policy Improvement by Planning with Gumbel”. ICLR.
https://arxiv.org/abs/2106.06613
用 Gumbel 采样改进 MCTS 的探索
Sampled MuZero:
Hubert et al. (2021). “Learning and Planning in Complex Action Spaces”. ICML.
https://arxiv.org/abs/2104.06303
将 MuZero 扩展到大型离散动作空间

¶开源实现

AlphaZero 通用框架:https://github.com/suragnair/alpha-zero-general
MuZero PyTorch:https://github.com/werner-duvaud/muzero-general
KataGo(超越 AlphaGo 的围棋引擎):https://github.com/lightvector/KataGo

¶总结与展望

从 MCTS 到 AlphaGo 系列的演进,展示了 AI 如何在人类智慧的巅峰——围棋上实现超越。这一成功不是单一技术的胜利,而是搜索、学习、规划三者的完美融合:

MCTS提供了探索与利用的数学平衡,让有限的计算资源聚焦在最有希望的路径上。

深度学习通过策略网络和价值网络,将人类数千年的围棋智慧(AlphaGo)或纯粹的自我对弈(AlphaGo Zero)压缩到神经网络的权重中,为搜索提供高质量的先验和评估。

自我对弈构建了一个持续改进的闭环——策略变强,对手也变强,始终保持适度挑战,最终突破人类棋谱的天花板。

AlphaZero的泛化证明了这一范式的通用性——相同的算法在围棋、国际象棋、将棋上都达到超人水平,展示了"搜索+学习"作为通用智能基础的潜力。

MuZero进一步摆脱了规则的限制,通过学习隐式模型实现规划,向"无需了解世界即可规划世界"的终极目标迈进。

未来的方向包括:

扩展到连续空间:将 MCTS 与机器人控制结合
迁移学习:在一个游戏上训练的模型能否快速适应新游戏?
多智能体博弈:从双人零和扩展到多方合作竞争
开放式环境:在没有明确胜负定义的任务中如何规划?

AlphaGo 的胜利不是终点,而是强化学习与搜索结合的起点。它告诉我们:智能不仅是记忆,更是规划;不仅是模仿,更是创造。从 AlphaGo 到 MuZero 的演进,正是这一理念的最佳诠释。