[数据结构与算法]与 AI 博弈：从 AlphaGo 到 MuZero（三）

• AlphaGo 论文地址：https://www.nature.com/articles/nature16961
• AlphaGo Zero 论文地址：https://www.nature.com/articles/nature24270
• AlphaZero 论文地址：https://arxiv.org/abs/1712.01815
• MuZero 论文地址：https://arxiv.org/abs/1911.08265

DeepMind 官网介绍：https://deepmind.com/research/case-studies/alphago-the-story-so-far

4. AlphaZero

2017 年底，DeepMind 推出了 AlphaZero，这是一个从零开始自学如何掌握国际象棋、日本将棋（Shogi）和围棋游戏的单一系统，在这些游戏中都能击败世界冠军程序。并且人类在 AlphaZero 的游戏中看到了一种开创性的、高度动态的、非传统的游戏风格，与之前的任何游戏程序都与众不同。

AlphaGo Zero 算法在围棋比赛中取得了超人的表现，它通过使用深度卷积神经网络来表示围棋知识，该网络完全是通过从自我博弈中进行强化学习来训练的。而 AlphaZero 应用了一个类似但通用的算法。

1997 年，深蓝在国际象棋击败了人类世界冠军，实现了人工智能的里程碑。在接下来的二十年里，计算机国际象棋程序继续稳步超越人类水平。这些程序使用专家手工制作的特征和仔细调整的权重来评估位置，并结合高性能的 alpha-beta 搜索，该搜索使用大量巧妙的启发式方法和特定领域的适应来扩展庞大的搜索树。

就计算的复杂性而言，将棋是一个比国际象棋难得多的游戏：它是在一个更大的棋盘上进行的，任何被吃掉的对手的棋子都会改变方向，并可能次第地被丢在棋盘的任何地方。之前最强的将棋程序，如计算机象棋协会（CSA）的世界冠军 Elmo，最近才打败了人类冠军。这些程序使用与计算机国际象棋程序类似的算法，同样是基于高度优化的 alpha-beta 搜索引擎和许多特定领域的适应性。

围棋非常适合 AlphaGo 中使用的神经网络架构，因为游戏规则是平移不变的（与卷积网络的权重共享结构相匹配），以棋盘上各点之间的相邻关系所对应的自由度来定义（与卷积网络的局部结构相匹配），并且是旋转和反射对称的（允许数据增强和组合）。此外，行动空间很简单（在每个可能的位置都可以放置一块棋子），游戏结果被限制为二进制的胜利或失败，这两点都有助于神经网络的训练。

国际象棋和将棋不太适合 AlphaGo 的神经网络结构。这些规则与位置有关和不对称。规则包括远距离的互动。国际象棋的行动空间包括棋盘上所有棋手棋子的所有合法目的地；将棋还允许将被吃掉的棋子放回棋盘上。国际象棋和将棋除了赢和输之外，还可能导致平局；事实上，人们认为国际象棋的最佳解决方案是平局。

AlphaZero 是 AlphaGo Zero 的一个更通用的版本，该算法是在围棋的背景下首次推出的。它用深度神经网络和零样本强化学习算法（ Tabula rasa reinforcement learning ）取代了传统对弈程序中使用的人工知识和特定领域的增强功能。

4.1 AlphaZero 网络结构

AlphaZero 利用参数为 $\theta$ 的深度神经网络 $(P,V)=f_{\theta }(s)$ ，而不是人工设计的评估函数和移动排序启发法。这个神经网络将棋盘上的位置 $s$ 作为输入，并输出一个移动概率向量 $p$ ，其中每个行动 $a$ 的成分 $p_a=Pr(a|s)$，以及一个估计来自位置 $s$ 的预期结果 $z$ 的标量值 $v$ ，$v\approx \mathbb{E}[z|s]$。AlphaZero 完全从自我博弈中学习这些行动概率和价值估计；然后用这些来改进其搜索。

AlphaZero 使用通用蒙特卡洛树搜索 (MCTS) 算法，而不是具有特定领域增强功能的 alpha-beta 搜索。每次搜索都由一系列模拟的自我博弈组成，这些游戏从根到叶遍历一棵树。根据当前神经网络 $f_{\theta }$，每个模拟通过在每个状态 $s$ 中选择具有低访问次数、高移动概率和高价值（在从 $s$ 中选择 $a$ 动作的模拟的叶子节点状态上平均值）的移动 $a$ 来进行。搜索返回一个向量 $\pi$，表示移动的概率分布，与根状态的访问计数成比例或贪心。

AlphaZero 中深度神经网络的参数 $\theta$ 是通过自我博弈强化学习训练的，从随机初始化的参数 $\theta$ 开始。通过 MCTS 为两个玩家选择移动来玩游戏 $a_t～{\pi }_t$。游戏结束时，根据游戏规则对终局位置 $s_T$ 进行评分，以计算游戏结果 $z$ (-1 为负，0 为平局，+1 为赢)。更新神经网络参数 $\theta$ 以最小化预测结果 $v_t$ 和游戏结果 $z$ 之间的误差，并使策略向量 $p_t$ 与搜索概率 ${\pi }_t$ 的相似度最大化。具体来说，参数 $\theta$ 通过损失函数 $l$ 的梯度下降进行调整，该损失函数 $l$ 为均方误差和交叉熵损失求和，

$$(p,v)=f_{\theta }(s),$$

$$l=(z?v{)}^2?{\pi }^{?}\log P+c||\theta |{|}^2(1)$$

其中 $c$ 是控制 $L_2$ 权重正则化水平的参数。更新后的参数用于后续的自我博弈。

AlphaZero 算法在以下几个方面与原始的 AlphaGo Zero 算法不同:

• AlphaGo Zero 估计并优化获胜的概率，假设二元输赢结果。相反，AlphaZero 会估计和优化预期结果，同时考虑平局或潜在的其他结果。
• 围棋的规则对旋转和反射（reflection）是不变的。AlphaGo 和 AlphaGo Zero 以两种方式利用了这个事实。首先，通过为每个位置生成 8 个对称点来增加训练数据。其次，在 MCTS 搜索期间，棋盘位置在被神经网络评估之前，使用随机选择的旋转或反射进行转换，这样蒙特卡洛评估在不同的偏差上是平均的。国际象棋和将棋的规则是不对称的，通常来说，不能假设对称性。AlphaZero不增加通过这种方式训练数据，也不在 MCTS 搜索期间转换棋盘位置。
• 在 AlphaGo Zero 中，自我博弈的棋局是由之前所有迭代中的最佳棋手生成的。在每次迭代训练之后，新网络的表现都要与最佳网络进行比较；如果新网络以 55% 的优势获胜，那么它就会取代最佳网络，随后由这个新网络生成自我博弈对局。相比之下，AlphaZero 只是维护了一个不断更新的单一神经网络，而不是通过迭代完成。自我博弈通过使用该神经网络的最新参数，省略了评估步骤和最佳网络的选择。
• AlphaGo Zero 通过贝叶斯优化调整了搜索的超参数。在 AlphaZero 中，作者为所有游戏重用相同的超参数，而无需针对游戏进行调整。唯一的例外是添加到先前策略中以确保探索的噪音；这与该游戏典型合法动作数成比例。
• AlphaZero 与 AlphaGo Zero 一样，棋盘状态由空间平面编码，只基于每个游戏的基本规则。动作由空间平面或平面向量编码，同样仅基于每个游戏的基本规则。

4.2 AlphaZero 训练及效果

作者将 AlphaZero 算法应用于国际象棋、将棋和围棋。除非有特殊的设置，三款游戏均使用相同的算法设置、网络架构和超参数。作者为每个游戏训练了一个单独的 AlphaZero 实例。训练进行了 700,000 步（大小为 4,096 的小批量），从随机初始化的参数开始，使用 5,000 个第一代 TPU 生成自玩游戏，并使用 64 个第二代 TPU 来训练神经网络。

在国际象棋中，AlphaZero 在 4 小时后首次超越 Stockfish；在将棋中，AlphaZero 在 2 小时后首次超越了 Elmo；而在围棋中，AlphaZero 在 30 小时后首次超越了 2016 年击败传奇棋手李世石的 AlphaGo 版本。每个训练步骤代表 4,096 个棋盘位置。

在每次评估中，AlphaZero 都毫无悬念地击败了其他冠军程序：

• 在国际象棋中，AlphaZero 击败了 2016 年 TCEC（第 9 季）世界冠军 Stockfish，赢得了 155 场比赛，但在 1,000 场比赛中仅输了 6 场。为了验证 AlphaZero 的稳健性，作者还进行了一系列的比赛，从常见的人类开局开始。在每个开局中，AlphaZero 都击败了 Stockfish。作者还玩了一场从 2016 年 TCEC 世界锦标赛中使用的开局位置开始的比赛，同时还进行了一系列额外的比赛，对阵的是 Stockfish 的最新开发版本，以及使用强大开局的 Stockfish 变体。在所有的比赛中，AlphaZero 都赢了。
• 在将棋中，AlphaZero 击败了 2017 年 CSA 世界冠军版的 Elmo，赢得了 91.2% 的比赛。
• 在围棋中，AlphaZero 击败了 AlphaGo Zero，赢得了 61% 的对局。

值得关注的是对于每一步，AlphaZero 只搜索传统国际象棋引擎考虑的一小部分位置。例如，在国际象棋中，它每秒仅搜索 6 万个国际象棋位置，而 Stockfish 大约为 6000 万个。

参考资料

• http://tromp.github.io/go.html
• https://towardsdatascience.com/the-upper-confidence-bound-ucb-bandit-algorithm-c05c2bf4c13f
• https://en.wikipedia.org/wiki/AlphaGo
• https://deepmind.com/blog/article/alphago-zero-starting-scratch
• https://towardsdatascience.com/the-evolution-of-alphago-to-muzero-c2c37306bf9