[译]方法论：AlphaGo Zero--如何不依赖人类知识也能成为围棋专家（一）

10月19日，DeepMind在《Nature》杂志发表了最新成果AlphaGo Zero，本文为对其原文的翻译加上部分自述理解，希望可以帮助大家理解其内容。论文正文篇上次已发表了，感兴趣的同学请戳：[译]AlphaGO Zero--如何不依赖人类知识也能成为围棋专家（一），本文为方法篇。

▲强化学习

策略迭代是一种经典的算法，通过交替执行策略评估（估计当前策略的价值函数）和策略强化（用当前的价值函数来生成更好的策略），来生成一列不断强化的策略。一种简单的策略评估方法是根据采样的动作轨迹的输出估计价值函数，一种简单的策略强化方法是根据价值函数贪婪（贪婪算法）的选择动作。在很大目标状态空间中（例如围棋的落棋子的可选位置），使用回归算法来评估每个策略的价值和表示策略的价值优化度是必要的。

基于分类的强化学习用简单的蒙特卡洛搜索算法来优化策略。每一个动作都要进行很多次推演；计分均值最大的动作做为一个正例训练样本，而其它所有的动作做为负例训练样本；然后一个策略被训练用来把动作分类为正例或负例，用来进行下一步推演。这种方法可以视为当τ→0时Alpha Go Zero的策略处理单元的前身。

最近的基于分类的改进策略迭代算法（CBMPI），也通过回归价值函数到（部分）推演结果来实现策略评估，类似AlphaGo Zero的价值评估单元；在俄罗斯方块游戏上达到了最高水准。但这个方法的局限是：简单的推演过程以及使用人工设计的特征表达的线性函数进行回归运算。

AlphaGo Zero自对弈的算法可以被近似理解为一个用蒙特卡洛树搜索做策略优化和策略评估进行优化迭代的策略框架。策略优化从一个神经网络的策略开始，执行蒙特卡洛树搜索，得到优化后的搜索策略，然后将其规划到神经网络的函数空间中。策略评估使用优化后的搜索策略产生动作，同时将动作输出也规划到神经网络的函数空间中。通过分别训练神经网络参数来匹配搜索概率和自我对抗游戏动作的输出来实现规划。

Guo及其它人的研究也是通过蒙特卡洛树搜索的输出到神经网络中，以搜索结果回归价值评估网络，或对蒙特卡洛树搜索选择的动作进行分类。这种方法被用来训练一个神经网络玩Atari游戏，但这个方法蒙特卡洛树搜索是固定的（没有策略的迭代），也没有使用经过训练的网络。

▲游戏中的自对弈强化学习
我们的方法可以很直接的用于具有完整信息的零和游戏中。借鉴了前人研究的交替马尔可夫链形式进行游戏，注意基于值和策略迭代的算法会自然的扩展成这个形式。

自我对抗优化学习之前已经被用在围棋游戏中，NeuroGo用一个神经网络来表达价值函数（基于围棋知识的（空、眼等）的精巧的架构）。这个神经网络通过时序差分学习训练来预测自我对抗中的棋盘布局（空）。一个相关的实现，RLGO，用特征的线性组合来表达价值函数，穷尽枚举所有的棋子的3*3布局，用时序差分学习训练来预测游戏赢家。NeuroGo和RLGO达到了初等业余水平。

蒙特卡洛树搜索也可以被视为一种自我对抗优化学习。搜索树中的节点包含了在搜索中发现的每个位置对应的值（代表棋子移动的价值），这些值被更新来预测自我对抗模拟游戏的赢家。蒙特卡洛树搜索程序之前实现了围棋高等业余水平，但使用了全面的专业知识：

1.基于人工设计的特征快速推演策略，评估直到游戏结束，模拟游戏经过的所有位置。

2.基于人工设计的特征树策略，选择了搜索树中的棋子移动方式。

自我对抗优化学习方法已经在其它游戏中达到了高级别水平：国际象棋，跳棋，西洋双陆棋，奥赛罗，英语文字图版游戏和扑克。在所有这些例子中，一个价值函数用自我对抗生成的训练数据通过回归或时序差分学习训练。训练的价值函数用来做为博弈树搜索，简单蒙特卡罗搜索或虚拟条件反悔最小化的评估函数。但这些方法使用了人工设计的特征输入或人工设计的特征模板。同时使用监督学习来初始化权重值，人工选择每部分值的权重，人工限制动作的空间，或使用之前已经做好的电脑程序来作为训练对手或生成游戏记录数据。

很多非常成功的，广泛使用的强化学习方法是第一次被引入零和游戏环境中：当蒙特卡洛树搜索被引入围棋游戏时，时序差分学习才第一次引入国际象棋程序中。无论如何，近似算法接着出现在了许多领域，比如：视频游戏，机器人，工业控制和在线推荐系统，并且均实现了很好的效果。

▲AlphaGo的版本
我们比较了三个独立版本的AlphaGo：
1.之前发布的AlphaGo Fan，在2015年10月和Fan Hui进行了对弈，这个分布式的程序部署在很多机器上，用到了176个GPU。

2.AlphaGo Lee是在2016年三月份以4:1击败李世石那个版本。它虽之前并未公开发布，但它与AlphaGo Fan那个版本是类似的。然而，我们强调了几个关键的差异以促进公平的比较。第一，价值网络是用AlphaGo的快速自弈的数据进行训练的，而不是用策略网络的自弈数据。

这个过程重复了多次--这是实现此论文中的空白算法（tabula rasa algorithm）的初始步骤。策略价值网络比原论文中描述的要大，使用了256个平面上的12个卷积层，而且训练了更多深层遍历数据。这个程序分开部署在很多机器上，总共使用了48个TPU，而不是GPU，这让它在搜索的过程中可以更快地评价神经网络。

3.AlphaGo Master是在2017年1月以60-0的不败战绩战胜了人类的顶尖棋手的那个版本。它之前也是没有公开发布的，它使用了和本论文中所描述的相同的神经网络架构，加强的学习算法，和MCTS算法。然而，它使用了和AlphaGo Lee一样的相同的手动功能和棋谱，它的训练也是用人类对弈数据来初始化的。

4.AlphaGo Zero是本论文中提到的程序。它用加强的自弈学习方式学习，从最基本的随机概率开始，没有使用棋谱，没有人类干预，只使用原始棋盘对弈记录作为输入。它仅仅使用了一台4TPU的谷歌云服务器。（AlphaGo Zero也是分布式的，但是我们选择使用最简单的搜索算法）

▲专业领域知识

AlphaGo Zero最主要的贡献是证明了在没有人类先验知识的情况下，计算机程序也可以在性能上超越人类。为了阐述这种贡献，我们列举了AlphaGo Zero使用的领域知识，明确地或者是不明确的，不管是在它的训练过程中，还是MCTS算法中。这些就是那些如果AlphaGo要学一个新游戏（alternating Markov）要被替换的知识：
1.AlphaGo Zero被提供了完美的关于游戏规则的背景知识，这些在MCTS算法中用到，去模拟一连串走法，在终局时让一方能赢下这盘模拟对弈的棋局。游戏在双方棋手都放弃行棋或者走了19*19*2=722步的时候终止。另外，机器棋手能下的任一合法的走法已经被提供出来。

2.AlphaGo Zero在用MCTS仿真和自弈的时候用到了Tromp-Taylor scoring算法。这是因为，如果棋局在边界没有完全划分清楚时就结束，人类的计分方法（中日韩的规则）有一定的不确定性。但是，锦标赛或者评估的棋局是用中国规则计分的。

3.输入功能将行棋位置描述为19乘19的结构化的图片，这就是说神经网络结构已经匹配了棋盘的网格结构。

4.围棋的规则是不变的，不管是旋转还是镜面。这些知识在AlphaGo Zero用MCTS算法训练时生成每一个棋盘上的位置的旋转还是镜面的时候和为特定位置生成样例随机旋转还是镜面用到了。撇开贴目，围棋的规则在颜色置换的情况下也不变。这些背景知识都是很明确的，当你用主观视角来看棋盘的时候（参考神经网络架构）。

AlphaGo Zero没有使用任何超越以上各点专业领域知识。它只是用它的深度神经网络去评估页节点和去选择走法（参考查找算法）。它没有用到rollout 策略或者树策略，而且MCTS也没有使用其他启发式或者特定规则进行。没有任何合法的走法被排除掉，甚至包括往“眼”里面下（一个用在其他以前版本上的启发式规则）。

整个算法从随机初始化神经网络参数开始。神经网络架构（参考神经网路架构）是基于图像识别的艺术的现有状态然后训练的超参数被相应的选择。（参见自弈训练流程）MCTS搜索的超参数由高斯过程优化决定，所以优化使用神经网络的AlphaGo Zero自弈性能处在早期尝试中。对于一个大规模网络的训练过程（40个残差模块，40天），使用一个小规模网络（20个残差模块，3天）来反复优化MCTS搜索的超参数，整个训练过程没有任何人工干预。

▲自对弈工作流
AlphaGo Zero的工作流由三个模块构成，可以异步多线程进行：
▪ 深度神经网络θi参数根据自对弈数据持续优化；
▪ 持续对棋手αθi棋力值进行评估；
▪ 使用表现最好的αθ*来产生新的自对弈数据。

优化
每个神经网络fθi都在谷歌云的TensorFlow上进行了优化，其配备了64块GPU节点和19块CPU参数服务器。每个工作节点的批次（Batch）是32，每一个mini-batch是2048。每个mini-batch都是从最近的50万场自弈比赛中棋谱状态中随机抽样。通过具有动量和学习率退火的随机梯度下降，神经网络参数得到优化。学习率根据扩展数据表3的标准时间进行退火。

动量参数设置为0.9。互熵和MSE损失平均加权（因为回馈是单位规模的，所以这是合理的，r∈{ - 1，+ 1}），L2正则化参数设置为c=10¯4 。每1000个训练步优化过程生成一个新的检查点。这个检查点由评估器进行评估，可用于生成下一批自弈游戏，下文会有说明。

▲评估器
为了保证生成数据的质量，在使用新的神经网络fθ*去生成自对弈棋谱前，用现有的最好网络fθ*来对它进行评估神经网络fθi通过MCTS搜索αθi性能进行评估，该搜索用fθi来估算叶位和先验概率（参见搜索算法）。每个评估包括400盘对局，MCTS搜索使用1600次模拟来选择每次走子，将温度参数设为无穷小τ→0（即我们确定性地选择最大访问次数的走子发挥最大的可能性）。

如果新玩家在这400盘对局中胜率大于55%，（为避免在噪声中选择），那么它将成为最好的玩家αθ*用来产生下一轮的自对弈棋谱，并且设为下一轮的比较对象。

下篇文章我们会继续讲解关于AlphaGo Zero关于搜索算法、神经网络等方法论问题，有兴趣的同学可以与我们一起探讨人工智能方面的问题。