译文丨AlphaGo论文：精通围棋——深度神经网络和搜索树

王目宣 刘伟 人机与认知实验室

摘要

因为巨大的搜索空间、评价棋局局面和落子的困难性，围棋历来被认为是最具挑战人工智能的传统游戏。本文介绍了一种下围棋的新方法：使用价值网络来评估棋局局面，使用策略网络来选择落子。这些深度神经网络是由有监督学习和强化学习共同训练完成的，其中有监督学习是由人类专家的下棋记录训练的，强化学习是由计算机“自我弈棋”不断学习的。在没有任何前瞻性搜索的情况下，深度神经网路经过数以千计的自我对战就能达到蒙特卡洛搜索树围棋程序的最高水平。本文还介绍了一种综合使用蒙特卡洛搜索树、决策网络和价值网络的算法。通过本文使用的算法，AlphaGo以99.8%的胜率大胜其他围棋程序，而且以5:0完胜欧洲围棋冠军樊麾。这是计算机程序历史上第一次在“全尺寸”棋盘上战胜人类职业围棋棋手，完成了以前被认为是至少十年之遥历史创举！

0 前言

完全信息可知的游戏都有最优化价值函数，它在考虑所有游戏参与者完美决策的情况下，决定当前棋局局面下的最好输出。这些游戏可能通过包含的搜索树来递归的计算价值函数，其中b代表游戏的广度（每个棋局局面的合法落子总数），d代表游戏的深度（游戏前瞻的步数）。在一些大型游戏中穷举搜索（暴力搜索）是不可行的，比如国际象棋（、围棋（），但有效的搜索空间却可以用以下两个一般原则减少。第一，搜索的深度可以通过棋局位置的评估来减少：在棋局状态s的情况下，通过近似价值函数（评价当前棋局局面）对搜索树剪枝并替换子树。这种方法已经在国际象棋、跳棋、奥赛罗棋（黑白棋）等方面达到超人类水平，但是由于游戏的复杂性在处理围棋时还很棘手。第二，搜索的广度可以通过策略函数p(a|s)抽样着法来减少：p(a|s)是给定当前棋局状态s下着法的条件分布。例如，蒙特卡洛系列方法利用策略函数对双方棋手抽样长序列的棋局着法，在从而在不剪枝的情况下搜索到最大深度。这系列算法能提供有效的位置评价，并在西洋双陆棋（backgammon）、拼字游戏（Scrabble）方面达到超人类水平，但在围棋方面也就达到弱的业余水平。

蒙特卡洛树搜索算法使用蒙特卡洛方法来评估树中的每个状态，随着越来越多的棋局模拟被执行时，搜索树变的越来越大，相关值也变得越来越准确。用于选择着法的策略通过不断的选择更高得分的子树（来搜索最优解），决策水平也得到提高。渐渐地，弈棋策略收敛到最优着法，评价值也收敛到最优价值函数。当前最好的围棋弈棋程序是在蒙特卡洛方法的基础上，经过人类围棋大师训练的策略强化形成的。这些策略用于将搜索树的深度缩减到一些高概率的着法上，并且在弈棋时抽样着法。这种方法让围棋弈棋程序达到了强的业余水平。然而，现有的工作已被限制为基于输入特征的线性组合的浅的策略函数或价值函数。

最近，深度卷积神经网络在视觉领域取得了前所未有的表现：图像分类、面部识别、玩雅达利游戏。它们使用多层神经元构建了一个逐渐抽象、局部化的图像表示，其中每个神经元像重叠的瓦片一样排列。而我们在围棋弈棋程序中使用了类似的处理架构。我们将棋盘看做是19*19的图像，并使用卷积层来构建棋局的表示。我们使用这些神经网络来降低搜索树的有效深度和广度：价值网络评价棋局位置，策略网络抽样棋局着法。

我们使用包含多阶段机器学习的流水线来训练神经网络（图1）。首先，我们利用围棋大师的下棋记录有监督的训练策略网络（SL策略网络）。它通过高质量的梯度、即时反馈完成参数的更新，从而提供快速有效的学习方案。和现有方案相同，我们也训练了快速策略，它能在众多方案中抽样着法。然后，我们训练了一个基于强化学习的策略网络（RL策略网络），它能通过最大化自我对战的胜率来优化SL策略网络。这样能够把策略网络调整为赢得比赛，而不是最大化预测的准确率。最后，我们训练了一个价值网络，用于预测策略网络在自我对战中的获胜者。我们的程序AlphaGo使用MCTS（蒙特卡洛树搜索）成功地融合了策略网络和价值网络。

图1：神经网络训练流水线和体系结构

A：使用围棋大师着法记录的数据集训练的快速部署策略和SL策略网络，RL策略网络首先被初始化为SL策略网络，然后通过策略梯度来不断改进：与上一版本的策略网络对战来最大化成果（胜率更高）。新数据集由RL策略网络自我对战产生。最后，价值网络使用回归在新数据集上训练，来预测期望成果（是否当前选手是否会取得胜利）。

B：AlphaGo中使用的神经网络结构的示意图。策略网络棋盘状态s的表示作为输入，经过SL策略网络（参数为）和RL策略网络（参数为）中卷积层的处理，输出合法着法a的条件概率和，从而将棋盘状态映射为一个概率值。价值网络同样采用带参数的许多卷积层，但是输出的是一个用来预测在状态时的预期结局的纯量。

1 有监督学习之策略网络

对于整个训练流水线的第一阶段，我们使用了现有的研究成果：用有监督的学习方式预测围棋大师的下一步着法。SL策略网络在权值为的卷积层和非线性矫正器之间交替进行。最后的激活函数输出所有合理着法的条件概率。策略网络的输入s是棋局状态的特征表示。策略网络是用随机抽样的(s,a)对训练的，使用随机梯度上升法来最大化给定状态s情况下着法a的条件概率，

我们用KGS围棋服务器上的3千万(s,a)对训练了一个13层的神经网络——有监督策略网络。这个神经网络在使用所有输入特征的情况下，能在测试集上以57.0%的准确率预测围棋大师的下一步着法；如果输入仅是棋局的原始对战历史（棋局状态和着法顺序）的话，准确率能达到55.7%；然而当前最先进的其他弈棋程序准确率只能达到44.4%。准确率小的提高就可以带来棋力的大幅提高（参见图2,a），规模越大的神经网络具有越高的准确率，但是评价每一步的棋局也会更慢。我们也训练了一个快速但低准确率的快速策略网络，它使用了以为参数的小特征的线性激活函数；它的准确率能达到24.2%，但仅需2，而不是SL策略网络的3ms，就能选择合适的着法。

图2 策略网络和价值网络的棋力和准确度

A：折线图反应了以KGS训练集上精确度为自变量、以策略网络棋力为因变量的函数关系。策略网络在训练时每层分别以384、256、192、128个卷积过滤器进行处理；折线图反应了使用策略网络的AlphaGo与相应版本对战时的胜率。

B：价值网络和不同策略快速部署的评价准确度的对比图。“位置-结果”对是从围棋大师的游戏中采样获得的。每个位置是由价值网络的报酬值（纯量）评价的，或者由100个快速部署的平均结局评定，并分别使用均匀随机快速部署、快速部署策略、RL策略网络的结构和SL策略网络，预测值和棋局实际输出的均方误差在棋局（在给定棋局位置有多少种着法）的各个阶段以点状图的形式展示出来。

2 强化学习之策略网络

整个训练流水线的第二阶段旨在通过策略梯度强化学习来提升SL策略网络。RL策略网络的结构和SL策略网络的结构完全相同，并且它的初始参数。我们令RL策略网络与该策略网络上某一迭代版本对弈。通过从对手池中随机选择对手来保证算法的鲁棒性，而不是过拟合于当前策略。我们将报酬函数r(s)的所有非终点状态对应的函数值设置为0，而输出是在时刻T时的状态的最终奖惩，其中棋局最终状态时的奖惩：胜者得+1分，败者得-1分。每个时刻t时的权重是使用随机梯度上升法更新权值的：

我们在弈棋时评价RL策略网络的表现，利用概率分布在所有着法中抽样每个着法。当与SL策略网络直接对战时，RL策略网络能取得80%的胜率。在不使用搜索的情况下，RL策略网络与Pachi对战能取得85%的胜率。Pachi是一个复杂的使用蒙特卡罗搜索的开源围棋弈棋程序，每次着法需要进行100,000次模拟，在KGS上的排名是业余2段。相比之下，SL策略网络与Pachi弈棋能取得11%的胜率，而与另一个棋力稍次的围棋程序Fuego对弈能取得12%的胜率。

3 强化学习之价值网络

整个训练流水线的最后一阶段聚焦于棋局位置的评价——价值函数，它用于预测在状态s时弈棋双方使用策略p的结局（报酬值），

理想情况下，我们想知道完美决策下的最优价值函数；但实际上，我们估计的是最好决策（RL策略网络）下的最优价值函数，我们使用了价值网络来近似价值函数，其中是参数，。价值网络具有和策略网络相同的体系结构，但是输出的是一个预测值（纯量的），而不是概率分布值。我们在“状态-结果”对(s, z)上使用回归来训练价值网络的参数，使用随机梯度下降法来最小化输出和标准输出之间的均方误差（MSE），

用包含完整游戏信息的数据来预测游戏结果的朴素解决方案会导致过拟合。问题是连续的位置是强相关的：仅一子不同，但回归目标是针对整个游戏共享的。当以这种方式对KGS数据集进行训练时，价值网络存储的是棋局结果而不是推断下一步的着法。这种方式在测试集上取得0.37的均方误差而在训练集上取得0.19的均方误差。为了缓解这一问题，我们通过RL策略网络自我对战产生新的数据集，它包含3千万不同位置信息，其中每一个都是从独立的游戏中采集出来的。新数据集上的训练方式在测试集上取得0.226的均方误差而在训练集上取得0.234的均方误差，很明显最小化了过拟合。图2,b显示了价值网络相比较于蒙特卡洛方法快速部署策略的位置评价的精度，从中可以看出价值函数一直更准确。在少于蒙特卡洛方法15000次计算的情况下，使用RL策略网络的单一价值函数就能达到它的准确度。

4 搜索之策略网络和价值网络的应用

AlphaGo通过MCTS（蒙特卡洛树搜索 图3）算法将策略网络和价值网络结合起来，并通过前瞻搜索的方式选择着法。搜索树种的每一条边（s,a）都存储了一个着法价值Q(s,a)、访问次数N(s,a)、先验概率P(s,a)。搜索树从根节点开始，通过模拟（无备份完整游戏下递减搜索树）进行遍历。在每次模拟的每个时间步长t时，以如下方式在状态选择着法

以最大化着法价值、偏置之和，其中
，即它与先验概率P(s,a)成正比，与访问次数N(s,a)成反比以鼓励探索新的着法。当搜索树在第L步遍历到叶子节点，而这个叶子节点被探索到。将输出概率将作为先验概率存储起来，即。叶子节点以以下两种方式评价：第一是价值网络，第二是使用快速部署策略弈棋的结局。其评价公式如下

只有当每一局结束时，才更新价值函数、搜索树边的访问次数，其更新公式如下：

其中代表第i次模拟时的叶子节点，1(s,a,i)表示在第i次模拟时边(s,a)是否被访问到，一旦搜索完成，该算法选择从根位置访问量最大的着法。

图3：AlphaGo中的蒙特卡洛树搜索

A：搜索树在遍历时选择边（s,a）时，选择着法价值与偏置和的最大值，其中偏置依赖于该边的先验概率P。

B：叶节点可以得到扩展；如果新节点被SL策略网络处理过，那么其输出概率将作为先验概率P存储在每一个着法当中。

C：在模拟的最后阶段，叶子节点以以下两种方式评价：价值网络；使用快速部署策略弈棋结束，并使用报酬函数r计算获胜者。

D：着法价值函数更新时与该着法下子树的和r(*)的平均值有关。

在AlphaGo程序中，SL策略网络比强RL策略网络表现得好，大概是因为人类的选择了多种有前途的着法，而RL策略网络只是优化了单次着法。然而，在AlphaGo中，从强RL策略网络推导出的价值函数比由SL策略网络推导出的价值函数表现得要好。

评估价值网络和策略网络比传统的启发式搜索要多几个数量级的计算量。为了有效的融合MCTS（蒙特卡洛树搜索）和深度神经网络，AlphaGo在CPU上使用异步多线程搜索执行模拟，在GPU上并行计算政策网络和价值网络。AlphaGo的最后一个版本共使用了40个搜索线程，48个CPU和8个GPU。我们还利用了多台机器实现了AlphaGo的分布式版本：40个搜索线程，1202个CPU和176个GPU。这个方法提供了异步分布式MCTS的所有细节。

5 评估AlphaGo的棋力

为了评估AlphaGo，我们用AlphaGo的变体和其他几个围棋程序组织了一场内部赛，其中包括最强商业程序——Crazy Stone和Zen，还有最强开源程序——Pachi和Fuego。所有这些程序均都是基于高性能MCTS算法，此外，我们还使用了开源程序GnuGo——使用MCTS搜索方法得最先进的围棋程序。比赛过程中，弈棋双方均有5s的搜索计算时间。

从比赛（详见图4,a）的结果来看，单机版的AlphaGo程序比以往其他围棋程序高出好几段：在495场比赛中胜了494场（99.8%的胜率）。为了增加难度，我们令AlphaGo在“让”（对手随意下）4子的情况下与Crazy Stone、 Zen和分别Pachi对弈，并取得77%、86%、99%的胜率。AlphaGo的分布式版本更是强的离谱：与单机版AlphaGo对战能取得77%的胜率而与其他围棋程序对弈能取得100%的胜率。

图4 AlphaGo的比赛评价

A:不同围棋程序的对战结果。每个程序在每次落子时有5s的计算时间。为了给AlphaGo增加难度，它在“让”（对弈开始时对手随意下）4子的情况下与其他程序对弈。程序使用Elo规模进行评价：230个点的差距意味着赢得概率为79%，那差不多意味着在KGS上能达到业余1段。与人类围棋段位等级的对应关系也如图所示，横线表示了围棋程序在KGS上取得的棋力等级（段位）。AlphaGo与欧洲围棋冠军樊麾的对战结果也包含其中，这些棋局使用了更长的控制时间。以95％置信区间展示。

B:融合不同模块的单机版AlphaGo的表现。这个版本只使用策略网络而不使用任何搜索。

C:AlphaGo中使用蒙特卡洛树搜索的线程和GPU的扩展性研究。在每次落子时分别使用异步搜索（浅蓝）和分布式搜索（深蓝）。

我们也评估了AlphaGo的只使用价值网络（=0）和只使用快速部署（
=1）的两个变种（详见图4,b）。即使在AlphaGo中没有使用快速部署，它也超越了其他所有围棋程序的棋力，这说明价值网络是围棋程序中蒙特卡洛方法的一种有效的替代方案。然而，当=0.5时AlphaGo表现最好，在与其他变种对战时能取得95%的胜率。这说明这两种位置评价机制是互补的：价值网络通过功能强大但搜索慢的可以近似棋局结局，而快速部署方法可以通过功能弱但搜索快速的来准确评估棋局结局。图5可视化了AlphaGo对于真实围棋棋局位置的评价。

图5 AlphaGo（黑子，将要落子）在与樊麾的非正式对战中是怎么选择着法的，对于每个棋局，得分最高的位置被标为橘黄色。

a：使用价值网络对根节点s各个候选落子点的评价。获胜的概率被显示在棋盘位置上。

b：搜索树从根节点开始的边(s,a)的着法价值函数Q(s,a)；只使用价值网络的平均值（=0）

c：着法价值函数Q(s,a)；只使用快速部署策略的平均值（=1）

d：SL策略网络着法的概率，以百分比呈现（如果均大于0.1%）

e：从根节点开始模拟，哪个着法被选择的百分频率

f：AlphaGo搜索树的主要变例（具有最大访问次数的路径），着法序列以数字序列展示在图上。AlphaGo选择的下一步着法以红色圆圈表示；樊麾的应对着法以白色正方形表示；他赛后评论说他更倾向于选择AlphaGo为它预测的着法（1）

最后，我们通过与樊麾对战来评估AlphaGo的分布式版本，樊麾是围棋职业2段并且是2013/2014/2015年的欧洲围棋冠军。2015年10月5号~9号，AlphaGo和樊麾进行了5场正式比赛，而AlphaGo以5:0完胜樊麾。这是第一次围棋程序在全棋盘无让子的情况下战胜人类专业棋手，而这以前被认为是至少10年才能完成的壮举。

6 讨论

在这个工作中我们综合使用了深度神经网络和搜索树算法并开发了一个围棋弈棋程序，它的棋力达到最强玩家等级，从而实现人工智能的“大挑战”之一。我们使用有监督学习和强化学习方法训练了一套神经网络系统，并开发了一种围棋着法选择和位置的评价函数，这也是历史上第一次使用这种方法。我们还介绍了一种成功融合了MTCT和神经网络的搜索算法。我们的程序AlphaGo将这些组件组合成为一个高性能的树搜索引擎。

AlphaGo与樊麾的对战中的计算次数比深蓝与卡斯帕洛夫对战中少了数千次。通过策略网络更智能的选择可能的着法，通过价值网络更准确的评估棋盘位置；而这种方式更接近于人类下棋。此外，深蓝依赖于人工制作的评价函数，而AlphaGo的神经网络是从实战中用有监督学习和强化学习训练产生的。

图6 AlphaGo与欧洲冠军樊麾的围棋对战记录

棋子上的数字顺序代表了对弈双方的下棋顺序，在同一位置的着法在棋盘下方以对的形式展示，其中对的第一个棋子代表第二次落在此位置，而对中的第二个棋子代表第一次落在此位置。

围棋是人工智能领域的几个典型难题之一：具有挑战性的决策任务；棘手的搜索空间；使用策略网络和价值网络来逼近最优的解决方案是否是不可行的。上次围棋的重大突破来自于MCTS，也导致相应的许多其他领域有了很大发展：例如玩游戏通用策略，经典规划，部分可观测计划，调度和约束满足。通过融合搜索树与策略网络和价值网络，AlphaGo达到围棋专业水平，为达到人类水平提供了希望，而这被以前认为是至少十年才能完成的壮举。

7 文献参考

1. Allis, L. V. Searching for Solutions in Games and ArtificialIntelligence. Ph.D. thesis,University of Limburg, Maastricht, The Netherlands (1994).

2. van den Herik, H., Uiterwijk, J. W. & van Rijswijck, J. Gamessolved: Now and in the future. Artificial Intelligence 134, 277–311 (2002).

3. Schaeffer, J. The games computers (and people) play. Advances inComputers 50, 189–266 (2000).

4. Campbell, M., Hoane, A. & Hsu, F. Deep Blue. ArtificialIntelligence 134, 57–83 (2002).

5. Schaeffer, J. et al. A world championship caliber checkers program. ArtificialIntelligence 53, 273–289 (1992).

6. Buro, M. From simple features to sophisticated evaluation functions. In1stInternational Conference on Computers and Games, 126–145 (1999).

7. M¨uller, M. Computer Go. Artificial Intelligence 134, 145–179 (2002).

8. Tesauro, G. & Galperin, G. On-line policy improvement usingMonte-Carlo search. In Advances in Neural Information Processing, 1068–1074 (1996).

9. Sheppard, B. World-championship-caliber Scrabble. ArtificialIntelligence 134, 241–275 (2002).

10. Bouzy, B. & Helmstetter, B. Monte-Carlo Go developments. In 10thInternational Conference on Advances in Computer Games, 159–174 (2003).

11. Coulom, R. Efficient selectivity and backup operators in Monte-Carlotree search. In 5^th International Conference on Computer and Games, 72–83 (2006).

12. Kocsis, L.&Szepesv´ari, C. Bandit based Monte-Carlo planning. In 15th EuropeanConference on Machine Learning, 282–293 (2006).

13. Coulom, R. Computing Elo ratings of move patterns in the game of Go. InternationalComputer Games Association Journal 30, 198–208 (2007).

14. Baudiˇs, P. & Gailly, J.-L. Pachi: State of the art open source Goprogram. In Advances in ComputerGames, 24–38(Springer, 2012).

15. M¨uller, M., Enzenberger, M., Arneson, B. & Segal, R. Fuego — anopen-source framework for board games and Go engine based on Monte-Carlo treesearch. IEEETransactions on Computational Intelligence and AI in Games 2, 259–270 (2010).

16. Gelly, S. & Silver, D. Combining online and offline learning inUCT. In 17thInternational Conference on Machine Learning, 273–280 (2007).

17. Krizhevsky, A., Sutskever, I. & Hinton, G. ImageNet classificationwith deep convolutional neural networks. In Advances in Neural InformationProcessing Systems, 1097–1105 (2012).

18. Lawrence, S., Giles, C. L., Tsoi, A. C. & Back, A. D. Facerecognition: a convolutional neural-network approach. IEEE Transactions on NeuralNetworks 8, 98–113 (1997).

19. Mnih, V. et al. Human-levelcontrol through deep reinforcement learning. Nature 518, 529– 533 (2015).

20. LeCun, Y., Bengio, Y. & Hinton, G. Deep learning. Nature 521, 436–444 (2015).

21. Stern, D., Herbrich, R. & Graepel, T. Bayesian pattern ranking formove prediction in the game of Go. In International Conference of Machine Learning, 873–880 (2006).

22. Sutskever, I. & Nair, V. Mimicking Go experts with convolutionalneural networks. In International Conference on Artificial Neural Networks, 101–110 (2008).

23. Maddison, C. J., Huang, A., Sutskever, I. & Silver, D. Moveevaluation in Go using deep convolutional neural networks. 3rdInternational Conference on Learning Representations (2015).

24. Clark, C. & Storkey, A. J. Training deep convolutional neuralnetworks to play go. In 32^nd International Conference on MachineLearning, 1766–1774(2015).

25. Williams, R. J. Simple statistical gradient-following algorithms forconnectionist reinforcement learning. Machine Learning 8, 229–256 (1992).

26. Sutton, R., McAllester, D., Singh, S. & Mansour, Y. Policygradient methods for reinforcement learning with function approximation. In Advances inNeural Information Processing Systems, 1057–1063 (2000).

27. Schraudolph, N. N., Dayan, P. & Sejnowski, T. J. Temporaldifference learning of position evaluation in the game of Go. Advances inNeural Information Processing Systems 817–817 (1994).

28. Enzenberger, M. Evaluation in Go by a neural network using softsegmentation. In 10^th Advances in Computer Games Conference, 97–108 (2003).

29. Silver, D., Sutton, R. & M¨uller, M. Temporal-difference search incomputer Go. Machine learning87, 183–219 (2012).

30. Coulom, R. Whole-history rating: A Bayesian rating system for playersof time-varying strength. In International Conference on Computers and Games, 113–124 (2008).

31. KGS: Rating system math. URL http://www./help/rmath.html.

32. Levinovitz, A. The mystery of Go, the ancient game that computersstill can’t win. Wired Magazine (2014).

33. Mechner, D.All Systems Go. The Sciences 38 (1998).

34. Mandziuk, J. Computational intelligence in mind games. In Challengesfor Computational Intelligence, 407–442 (2007).

35. Berliner, H. A chronology of computer chess and its literature. ArtificialIntelligence 10, 201–214 (1978).

36. Browne, C. et al. A survey ofMonte-Carlo tree search methods. IEEE Transactions of Computational Intelligence and AI inGames 4, 1–43 (2012).

37. Gelly, S. et al. The grandchallenge of computer Go: Monte Carlo tree search and extensions. Communicationsof the ACM 55, 106–113 (2012).