酷应用

专栏 | AlphaGo Zero：笔记与伪代码

百家作者：机器之心 2017-11-02 08:32:12

机器之心专栏

作者：Yuxi Li

编译：Panda

近日，Google DeepMind 在 Nature 上发表了一篇论文，介绍了这家世界顶级人工智能机构在计算机围棋方面的最新研究成果 AlphaGo Zero（参阅机器之心文章《无需人类知识，DeepMind 新一代围棋程序 AlphaGo Zero 再次登上 Nature》）。这个在学习过程中没有使用任何人类知识的人工智能程序可以轻松地以 100 比 0 的成绩击败去年 3 月战胜了李世乭的 AlphaGo 版本。AlphaGo Zero 论文发布之后，阿尔伯塔大学 Yuxi Li 博士对该程序的工作原理进行了分析，并使用伪代码的方式对其训练过程进行了描述。原文链接请点击「阅读原文」查看。

1 引言

2016 年 3 月，AlphaGo（Silver et al., 2016）击败了带有 18 个国际冠军头衔的人类顶级围棋手，造就了人工智能领域的一大里程碑。AlphaGo Zero（Silver et al., 2017）则实现了更进一步的提升，在不使用人类知识的情况下学习到了一个超人水平的计算机围棋程序。

AlphaGo（Silver et al., 2016; 2017）立足于深度学习、强化学习（RL）和蒙特卡洛树搜索（MCTS）。这一波深度强化学习浪潮起始于深度 Q 学习（Mnih et al., 2015）；全面概述请参阅 Li (2017) https://arxiv.org/abs/1701.07274。

Sutton 和 Barto (2017) 对 AlphaGo 进行了详细且直观的描述。关于 AlphaGo 和 AlphaGo Zero 的介绍参阅 DeepMind 的官方博客：https://deepmind.com/research/alphago/ 和 https://deepmind.com/blog/alphago-zero-learning-scratch/。强化学习综述可参阅 Littman (2015)。

2 伪代码

我们提供了一个用于训练 AlphaGo Zero 的简要的概念性的伪代码，有助于你更轻松地理解 AlphaGo Zero 的原理；参见后文算法 1。详细情况请参阅原论文（Silver et al., 2017）。

AlphaGo Zero 可以被理解成是一种近似策略迭代（approximation policy iteration），并在其训练循环中集成了 MCTS 以改进策略和评估策略。MCTS 可以被看作是一种策略改进算子（policy improvement operator），可以输出比神经网络的原始概率更强的走子概率。使用搜索的自我对弈可以被看作是一种策略评估算子（policy evaluation operator）。它使用了 MCTS 来选择走子，并将对弈赢家看作是价值函数的样本。然后这个策略迭代过程会更新神经网络的权重，从而将走子的概率和价值与提升后的搜索概率和自我对弈赢家更紧密地匹配起来，然后再在下一次迭代中使用更新后的神经网络权重执行自我对弈，以使其搜索更加强大。

与 AlphaGo 相比，AlphaGo Zero 的特性有：

1. 它是从随机对弈学习的，使用了自我对弈强化学习，没有使用人类数据或监督；

2. 它使用了棋盘上的黑白子作为输入，而没有使用任何人类参与的特征工程；

3. 它使用了单个神经网络来同时表征策略和价值，而没使用单独的策略网络和价值网络；

4. 它的局面评估使用了神经网络，MCTS 使用了走子采样，而没有执行蒙特卡洛 rollout。

AlphaGo Zero 使用了神经网络领域近年来的多种成就：残差卷积神经网络（ResNet）、批规范化（batch normalization）和非线性整流函数（rectifier nonlinearities）。

AlphaGo Zero 的自我对弈训练流程中有三个主要部门以异步的方式并行执行：

1. 根据近期的自我对弈数据持续地优化神经网络的权重；

2. 持续地评估棋手；

3. 使用最强的棋手来生成新的自我对弈数据。

当 AlphaGo Zero 与对手下棋时，MCTS 会搜索当前的状态，根据训练后的神经网络权重生成走子概率，然后选择一种走子方式。

3 讨论

AlphaGo Zero 是一种强化学习算法。AlphaGo Zero 既不是监督学习，也不是无监督学习。对弈分数是奖励信号，而不是监督标签。对损失函数 l 的优化是监督学习。但是，它会在策略迭代的单次迭代中执行策略评估和策略改进。

AlphaGo Zero 不仅是一种启发式搜索算法。AlphaGo Zero 更是一种策略迭代过程，其中启发式搜索算法（尤其是 MCTS）发挥了关键性的作用，但这个过程处于强化学习策略迭代的方案之中，如算法 1 中的伪代码所示。MCTS 可以被看作是一种策略改进算子。

AlphaGo 达到了超人类的水平。也许可以确定职业棋手已经开发出了一些有效的策略。但是，AlphaGo 并不需要模仿职业棋手的下法。因此它也不需要正确预测他们的走子。

AlphaGo Zero 的输入包括棋盘局面、历史记录和要下的颜色的原始棋盘表示，是以 19×19 的图像形式提供的；游戏规则；一个对弈评分函数；在旋转和翻转时的游戏规则不变性以及颜色转换情况下的不变性（除了贴目情况）。另外的关键输入是坚实的研究和开发经验。

AlphaGo Zero 使用了 64 个 GPU 工作站（每一个都有多个 GPU）和 19 个 CPU 参数服务器（每一个都有多个 CPU）进行训练，使用了 4 个 TPU 进行比赛时的执行。

AlphaGo 的训练需要巨量数据，所以它仍然是一个大数据问题。但是，因为计算机围棋有一个完美的模型或精确的游戏规则，这些数据就可以通过自我对弈生成。

由于计算机围棋存在完美模型或精确游戏规则，所以 AlphaGo 算法有局限性。比如在医疗健康、机器人和自动驾驶等问题上，通常难以收集到大量数据，得到足够接近甚至完美的模型就更难甚至完全不可能了。因此，我们不能直接将 AlphaGo 算法应用到这些应用上。

另一方面，AlphaGo 算法，尤其是其底层的技术（即深度学习、强化学习和蒙特卡洛树搜索），则有很多应用。Silver et al. (2016) 和 Silver et al. (2017) 推荐了以下应用：通用的游戏问题（尤其是视频游戏）、经典的规划问题、仅观察到部分信息的规划问题、调度问题、约束满足问题、机器人、工业控制和在线推荐系统。AlphaGo Zero 博客还提到了以下结构化问题：蛋白质折叠、降低能耗和搜寻革命性的新材料。参阅 Li (2017) 了解更多 AlphaGo 算法的应用和底层技术（尤其是深度强化学习）。

AlphaGo 已经取得了惊人的进展并为人工智能建立了一个里程碑。但是，我们离实现通用人工智能（AGI）的目标仍然相距甚远。

参考文献

Li, Y. (2017). Deep Reinforcement Learning: An Overview. ArXiv e-prints.

Littman, M. L. (2015). Reinforcement learning improves behaviour from evaluative feedback. Nature, 521:445–451.

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou,I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540):529–533.

Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484–489.

Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T., and Hassabis, D. (2017). Mastering the game of go without human knowledge. Nature, 550:354–359.

Sutton, R. S. and Barto, A. G. (2017). Reinforcement Learning: An Introduction (2nd Edition, in preparation). MIT Press.

算法 1：AlphaGo Zero 训练过程的伪代码，基于 Silver et al. (2017)

AlphaGo Zero 伪代码原版：