稀疏奖励游戏中AlphaZero的局限性与辅助监督

# 稀疏奖励游戏中的AlphaZero：局限性与辅助监督
来源：https://arxiv.org/html/2607.08984
Brent Kongbkong@caltech\.edu Department of Mathematics California Institute of TechnologyTejas Ramtram@caltech\.edu Department of Computer Science California Institute of TechnologyTony Yue Yutyy@caltech\.edu Department of Mathematics California Institute of Technology

###### 摘要

AlphaZero已经证明，神经引导的蒙特卡洛树搜索可以达到超人类水平的表现，但强棋力并不必然意味着完美对弈。我们在两个结构对比鲜明、可通过预言机评估的领域中研究这一差距：Connect Four（一个已求解的偏袒游戏，具有精确的博弈论值）和Chomp（一个公正游戏，其最优对弈由Grundy数结构支配）。在统一的自我对弈+蒙特卡洛树搜索（MCTS）流程下，我们比较了标准AlphaZero、一个多帧变体（仅限Chomp）以及一个AlphaZero辅助损失（AZAL）变体，后者加入了预言机导出的策略监督。我们发现，标准AlphaZero在两个领域中都实现了强棋力，但无法保持完美对弈所需的精确轨迹：在Connect Four中，它未能维持最优的着法线路；而在Chomp中，它未能持续恢复g=0不变性。在矩形Chomp棋盘上，仅凭多帧输入无法消除这一差距。尽管如此，AZAL在多个种子的整局棋谱追踪和采样状态评估中，显著提高了预言机一致性。在Chomp中，AZAL在10×11棋盘上达到了完美的整局预言机一致性，在9×10棋盘上达到了高一致性但非完全一致；在Connect Four中，AZAL提高了预言机匹配率，并延迟了首次预言机错误出现的时间，但未能达到完美对弈。

## 1 引言

AlphaZero将蒙特卡洛树搜索（MCTS）确立为现代游戏AI中的核心范式。基于规划与泛化的更广泛思想，AlphaGo Zero展示了搜索可以直接嵌入强化学习循环中，在自我对弈提供价值监督的同时改进策略目标。AlphaZero则将这一方案推广至围棋、国际象棋和将棋，表明一个由MCTS引导的策略-价值网络，仅需知晓游戏规则，便能在随机初始化后达到超人类水平的表现。

然而，超人类对弈并不等同于完美对弈。一个AlphaZero风格的系统可能从标准起始位置达到优秀的结果，却无法选择最优着法。这一区别在那些依赖稀疏全局特征而非密集局部战术的游戏中变得尤为重要。在此类设定中，策略和价值的估计误差不会孤立存在：它们会影响用于生成未来自我对弈数据的搜索目标。这削弱了AlphaZero所依赖的正反馈循环。

本文通过两个对比鲜明的领域——Connect Four和Chomp——来分析强棋力与完美对弈之间的差距。Connect Four是一个已求解的偏袒游戏，具有精确的博弈论值，允许直接与获胜轨迹进行比较。相比之下，Chomp是一个公正的组合游戏，其获胜结构自然地通过Grundy数来研究。尽管有经典的理论结果，Chomp的显式最优策略仍然难以刻画。总之，这些游戏提供了一个有用的测试，用于检验AlphaZero是否能在具有不同战略结构的游戏中未能恢复出精确对弈。

我们在一个标准的自我对弈+MCTS流程下，对两个领域的AlphaZero风格学习进行了实证研究。我们根据精确预言机来评估标准AlphaZero，将其与受Riis (2024)启发的多帧变体（仅限Chomp）进行比较，并引入了一种AlphaZero辅助损失（AZAL）变体，旨在提供更强的学习信号。在两个领域中，多种子和采样状态的预言机评估表明，标准AlphaZero距离精确的预言机一致性仍然很远。在我们的实验中，多帧输入未能解决Chomp矩形棋盘上的失败。AZAL显著提高了预言机一致性，在Chomp 10×11棋盘上实现了完美的整局一致性，在Chomp 9×10棋盘上达到了高一致性但非完全一致，而在Connect Four上则取得了不错但仍不完美的改善。

更广泛的教训是，搜索改进的自我对弈可以产生经验上强大但在结构上与精确最优性不一致的策略，而可通过预言机评估的游戏为区分这两个概念提供了有用的诊断环境。

我们的贡献如下：

1. 我们在Connect Four和Chomp中表明，标准AlphaZero可以学习强大的自我对弈策略，但无法常规地恢复预言机一致的对弈，这通过多种子的整局棋谱追踪和随机采样状态的精确预言机评估来衡量。
2. 我们在统一的自我对弈+MCTS框架下比较了两种可能的补救措施：多帧表示（用于Chomp）和辅助损失变体AZAL。
3. 我们发现，AZAL在整局和采样状态评估中显著提高了预言机一致性，尤其是在Chomp中，这表明标准的AlphaZero搜索-学习信号可能是恢复精确对弈的一个合理瓶颈。

## 2 相关工作

### 2.1 AlphaZero与专家迭代

AlphaZero属于一个广泛的工作线索，该线索将规划与函数近似结合在自我对弈强化学习中。专家迭代利用树搜索作为强大的专家，神经网络作为快速学习者。AlphaGo Zero将这一思想整合到一个端到端的自我对弈框架中，其中MCTS改进策略目标，而游戏结果则监督价值学习。AlphaZero随后将相同的方案推广至围棋、国际象棋和将棋，表明一个单一的搜索引导的策略-价值网络，无需人工评估或人类示范数据，即可达到超人类的表现。

### 2.2 强棋力与完美对弈

强的经验性对弈并不意味着收敛到完美对弈。Zhou和Riis认为，AlphaZero风格的智能体可能成为有效的“冠军”，但未能成为真正的“专家”，尤其是在那些最优行为依赖于难以从自我对弈中推断出的稀疏全局结构的公正游戏中。Riis进一步指出，单帧表示不足以恢复像Nim这样的游戏中的此类结构，并提出了多帧输入作为一种可能的补救措施。相关地，Trudeau和Bowling识别了标准AlphaZero风格训练中的搜索效率低下问题，其中从初始位置开始的自我对弈可能会削弱对更深层关键状态的监督。Go-Exploit针对深层状态监督不足和样本效率问题。然而，我们的工作不同，因为它逐着地诊断预言机一致性，而不是提出一种样本高效的训练方案。因此，目标不是击败Go-Exploit，而是测试标准的自我对弈是否恢复了精确的预言机轨迹。

总之，这些文献激励我们评估AlphaZero是否实际上恢复了完美对弈所需的精确结构规律。

## 3 问题设定与预言机评估

我们的目标是研究AlphaZero风格智能体中“超人类”与“完美”对弈之间的差异。我们在两个结构对比鲜明的、可通过预言机评估的领域中这样做：Connect Four和Chomp。在两种游戏中，预言机允许我们评估学习到的智能体是否保持了最优对弈所需的轨迹。

### 3.1 超人类对弈与完美对弈

在本文中，我们区分“超人类”对弈和“完美”对弈。所谓超人类对弈，我们指的是经验性表现超过了强大的实践基线或人类水平的表现。所谓完美对弈，我们指的是从每个合法状态中选择最优着法，由精确求解器或预言机判断。这一区别是我们研究的核心：一个AlphaZero风格的智能体可能实现高胜率，但未能保持精确对弈所需的预言机最优轨迹。在Connect Four中，两个玩家都可以根据精确的博弈论值进行评估，而在Chomp中，玩家则通过他们是否能够通过移动到g=0状态来保持获胜不变性来评估。

### 3.2 游戏

Connect Four和Chomp都是完美信息、回合制的棋盘游戏，但它们在规则和战略结构上差异很大。在Connect Four中，两个玩家轮流将圆盘放入一个垂直的6×7网格的列中。目标是将四个自己的圆盘水平、垂直或对角线地连成一线。

图1：一个示例性的Connect Four局面，在标准的6×7网格上有红色和黄色圆盘。

在Chomp中，游戏从一个矩形的方格网格开始。一步棋选择一个剩余的方格，并移除该方格及其下方和右方的所有方格。因此，棋盘随时间单调缩小。在正常玩法约定下，被迫吃掉有毒的左上角方格的玩家输。这些对比鲜明的规则使得这些游戏成为在偏袒和公正设置中比较AlphaZero风格学习的有效测试平台。

图2：一个在3×4棋盘上的小型Chomp进程。选择一个方格会移除该方格以及其下方和右方的所有方格；必须避免有毒角落P。

### 3.3 Connect Four预言机

对于Connect Four，我们使用Pascal Pons的完美求解器。由于Connect Four是一个偏袒游戏，自然的预言机量是精确的“博弈论分数”。设σ(s, a)表示在状态s下采取着法a的精确分数，并设

m(s) := nbMoves(s)  (1)

表示已经在局面s中下的圆盘数量。求解器计算

σ(s, a) = { (WH+1-m(s))/2, 如果a立即获胜; -v(T(s, a)), 否则 }

其中W和H是棋盘尺寸，T(s, a)是应用着法a后的后续局面。一个状态的精确值则为

v(s) = max_{a∈A(s)} σ(s, a),

其中A(s)是合法动作集合。

正值对应逼迫胜，负值对应逼迫负，零对应逼迫和。幅度反映了距离结局的远近：更大的正分数意味着更快的胜利，而更大的（更负的）失败分数意味着更慢的失败。求解器和编码的更多细节见附录A.1。

### 3.4 Chomp预言机

对于Chomp，我们使用一个递归的Grundy数求解器。由于Chomp是一个公正的正常玩法游戏，每个状态s都有一个Grundy数g(s)∈N，其中g(s)=0当且仅当该局面对于要移动的玩家是输局。预言机递归定义如下

g(s) = mex({g(s′): s′∈N(s)}),

其中N(s)是合法后续局面的集合，mex(·)是最小排除的非负整数。从任何获胜局面（g(s)≠0）出发，一个最优着法是指到达一个Grundy数为零的后续局面的着法。

在正文中，这个预言机用于确定在获胜回合中是否保持了g(s)≠0 → g(s′)=0的转移。棋盘编码、着法索引和记忆化细节见附录A.2。

## 4 方法

我们比较三个密切相关的AlphaZero风格智能体：标准AlphaZero、一个多帧变体（限于Chomp）和AlphaZero辅助损失（AZAL）。在所有情况下，自我对弈游戏均由策略-价值网络引导的MCTS生成，从这些游戏中收集重放元组，并根据搜索改进的策略目标和游戏结果更新网络。因此，这些方法仅在提供给网络的表示以及监督信号的强度上有所不同。

##### 标准AlphaZero。

我们的基线遵循标准的AlphaZero方案：一个策略-价值网络从自我对弈数据中训练，其中MCTS产生改进的策略目标，而终端结果提供价值目标。策略仅通过搜索改进的自我对弈来学习。完整的架构、搜索和优化细节见附录B.1。

##### 多帧AlphaZero。

为了测试主要瓶颈是否在于状态表示，我们评估了一个受Riis (2024)启发的多帧变体。训练循环、搜索过程和优化目标与标准AlphaZero相同；唯一的区别在于网络接收一个由最近几个状态组成的短堆栈，而不是单个棋盘快照。因此，我们将多帧AlphaZero视为表示消融，而非一种独特的学习算法。详见附录B.2。

##### AlphaZero辅助损失 (AZAL)。

为了强化训练信号，AZAL用预言机导出的辅助策略损失增强了标准的AlphaZero目标：

L = L_策略 + L_价值 + λ_aux L_aux。

这一辅助项在训练期间有利于预言机一致的动作，但保持自我对弈、MCTS和价值目标不变。因此，AZAL是对标准AlphaZero的最小修改，改变了监督而非搜索。对于有标签的状态，辅助项是一个针对软化的预言机目标分布的交叉熵损失

q(a|s) ∝ (1[a∈B(s)] + ε) 1[a∈A(s)]，

其中B(s)是预言机最优动作集，A(s)是合法动作集。我们对所有AZAL实验使用辅助目标平滑ε=10^{-3}。每个状态的辅助损失为

L_aux(s) = -∑_a q(a|s) log p_θ(a|s)，

其中p_θ(a|s)是网络输出的策略概率。