the art of game of thrones_go deep

前言：

围棋的英文是 the game of Go，标题翻译为：《用深度神经网络和树搜索征服围棋》。译者简介：大三，211，计算机科学与技术专业，平均分92分，专业第一。为了更好地翻译此文，译者查看了很多资料。译者翻译此论文已尽全力，不足之处希望读者指出。

在AlphaGo的影响之下，全社会对人工智能的关注进一步提升。3月12日，AlphaGo 第三次击败李世石。在3月15日总比分定格为4：1，随后AlphaGo的围棋排名世界来到第二。

论文的英文原文点击这里拜读

编者按：2014年5月，人们认为至少需要十年电脑才能击败职业选手。笔者在翻译的时候忠实于原文，很少加入自己的理解（本人不敢说有啥深入理解可言）。最终翻译结果可能不好。但是对于本人而言，翻译这篇文论的过程大于结果：一篇一万字的中文翻译，背后是十万中英文资料的阅读。

译文

标题：用深度神经网络和树搜索征服围棋

作者：David Silver 1 , Aja Huang 1 , Chris J. Maddison 1 , Arthur Guez 1 , Laurent Sifre 1 , George van den Driessche 1 , Julian Schrittwieser 1 , Ioannis Antonoglou 1 , Veda Panneershelvam 1 , Marc Lanctot 1 , Sander Dieleman 1 , Dominik Grewe 1 , John Nham 2 , Nal Kalchbrenner 1 , Ilya Sutskever 2 , Timothy Lillicrap 1 , Madeleine Leach 1 , Koray Kavukcuoglu 1 , Thore Graepel 1 , Demis Hassabis 1
他们来自 Google DeepMind 英国团队（用1表示）, Google 总部（用2表示）
David Silver , Aja Huang是并列第一作者

摘要：人们长久以来认为：围棋对于人工智能来说是最具有挑战性的经典博弈游戏，因为它的巨大的搜索空间，评估棋局和评估落子地点的难度。我们给电脑围棋程序引入一种新的方法，这个方法使用估值网络来评估棋局，以及使用策略网络来选择如何落子。这些深度神经网络被一种新的组合来训练：使用了人类专业比赛数据的监督学习，以及自我对弈的强化学习。没有使用任何预测搜索的方法，神经网络下围棋达到了最先进的蒙特卡洛树搜索程序的水准，这程序模拟了数以千计的自我对弈的随机博弈。我们同时也引入了一种新的搜索算法，这算法把蒙特卡洛模拟和估值、策略网络结合在一起。运用了这个搜索算法，我们的程序AlphaGo在和其它围棋程序的对弈中达到了99.8%的胜率，并且以5：0的比分击败了欧洲冠军，这是史上第一次计算机程序在全尺寸围棋中击败一个人类职业棋手。在此之前，人们认为需要至少十年才会达成这个壮举。

引言

所有完全信息博弈都有一个最优估值函数v∗(s) v∗(s) 的采样动作来降低，这个策略是一个在位置 s 的可能下棋走子a 概率分布。比如蒙特卡洛走子方法搜索到最大深度时候根本不使用分歧界定法，它从一个策略 p 中采集双方棋手的一系列下棋走法。计算这些走子的平均数可以产生一个有效的棋局评估，在西洋双陆棋戏和拼字游戏中获得了超出人类的性能表现，并且在围棋中达到了业余低段水平。

蒙特卡洛树搜索使用蒙特卡洛走子方法，评估搜索树中每一个状态的估值。随着执行越来越多的模拟，这个搜索树成长越来越大，而且相关估值愈发精确。用来选择下棋动作的策略在搜索的过程中也会随着时间的推移而改进，通过选择拥有更高估值的子树。渐近的，这个策略收敛到一个最优下法，然后评估收敛到最优估值函数。目前最强的围棋程序是基于蒙特卡洛树搜索的，并且受到了策略的增强，这个策略被人训练用来预测专家棋手的下法。这些策略用来缩窄搜索空间到一束高可能性下棋动作，和用来在走子中采集下法动作。这个方法已经达到了业余高手的级别。然而，先前的工作已经受到了肤浅策略的限制或基于输入的线性组合的估值函数的限制。

最近，深度卷积神经网络已经在计算机视觉中达到了空前的性能：比如图像分类，人脸识别，和玩雅达利的游戏。它们使用很多层的神经网络，层与层之间像瓦片重叠排列在一起，用来构建图片的愈发抽象的局部代表。我们为围棋程序部署了类似的体系架构。我们给程序传入了一个19*19大小棋局的图片，然后使用卷积神经网络来构建一个位置的代表。我们使用这些神经网络来降低搜索树的有效的深度和广度：通过估值网络来评估棋局，和使用策略网络来博弈取样。

我们使用一个包含多个不同阶段的机器学习方法的管道来训练神经网络。我们开始使用一个监督学习（SL）策略网络 pδ pδ ，它预测博弈的赢者，通过和RL策略网络和自己对弈。我们的AlphaGo程序有效的把策略网络、估值网络，和蒙特卡洛搜索树结合在一起。

1 策略网络的监督学习

在训练管道的第一阶段，我们在先前工作的基础上，使用了监督学习来预测人类专家下围棋。监督学习（SL）策略网络pδ(a∣s) pδ(a∣s) 的小型模式特征的线性softmax。它达到了24.2%的精确度，每选择下一步棋只用2微秒，与之相比，策略网络需要3毫秒。

图1：神经网络训练管道和体系结构。a：在一个棋局数据集合中，训练一个快速走子策略pπ pπ 后的结局。

图2：策略网络和估值网络的能力和精确度。a图显示了策略网络的下棋能力随着它们的训练精确度的函数。拥有128，192，256，384卷积过滤每层的策略网络在训练过程中得到周期性的评估；这个图显示了AlphaGo使用不同策略网络的赢棋概率随着的不同精确度版本的AlphaGo的变化。b：估值网络和不同策略网络的评估对比。棋局和结局是从人类专家博弈对局中采样的。每一个棋局都是由一个单独的向前传递的估值网络vθ vθ 。图中，预测估值和博弈实际结局之间的平均方差随着博弈的进行阶段（博弈总共下了多少步）的变化而变化。

2 策略网络的强化学习

训练管道第二阶段的目标是通过策略梯度强化学习（RL）来提高策略网络。强化学习策略网络pρ pρ 进行取样。我们自己面对面博弈，RL策略网络对 SL策略网络的胜率高于80%。我们也测试了和最强的开源围棋软件 Pachi 对弈，它是一个随机的蒙特卡洛搜索程序，在KGS中达到业余2段。在没有使用任何搜索的情况下，RL策略网络对 Pachi的胜率达到了85%。与之相比，之前的最先进的仅仅基于监督学习的卷积网络，对 Pachi的胜率仅只有11%，对稍弱的程序 Fuego的胜率是12%。

3 估值网络的强化学习

训练管道的最后一个阶段关注于棋局评估，评估一个估值函数 vp(s) vp(s) 的蒙特卡洛走子的精确度，不过计算量是原来的15000分之一。

4 运用策略网络和估值网络搜索

AlphaGo在把策略网络、估值网络和MCTS算法结合，MCTS通过预测搜索选择下棋动作。每一个搜索树的边（s，a）存储着一个动作估值 Q(s, a)，访问计数 N(s, a)，和先验概率 P(s, a)。这棵树从根节点开始，通过模拟来遍历（比如在完整的博弈中沿着树无没有备份地向下搜索）。在每一次模拟的时间步骤 t，在状态 s的时候选择一个下棋动作at at ，

在模拟的结尾 n，更新所有被遍历过的边的下棋动作估值和访问次数。每一条边累加访问次数，和求出所有经过该边的模拟估值的平均值。

其中siL sLi 是第 i 次模拟的叶节点，1(s, a, i) 代表一条边 (s, a) 在第 i 次模拟时是否被遍历过。一旦搜索完成，算法选择从根节点开始，被访问次数最多的节点。

在AlphaGo中，SL策略网络pδ pδ 

评估策略网络和估值网络和传统的启发式搜索相比，需要多几个数量级的计算量。为了高效的把 MCTS 和深度神经网络结合在一起，AlphaGo 在很多CPU上使用异步多线程搜索技术进行了模拟，在很多GPU上计算策略网络和估值网络。最终版本的 AlphaGo使用了40个搜索线程，48个CPU，和8个GPU。我们也实现了一个分布式的AlphaGo版本，它利用了多台电脑，40个搜索线程，1202个CPU，176个GPU。在方法部分提供了关于异步和分布MCTS的全部的细节。

图3：AlphaGo中的蒙特卡洛树搜索。a 每一次模拟遍历搜索树，通过选择拥有最大下棋动作估值 Q的边，加上一个额外奖励 u(P)（依赖于存储的该边的先验概率 P） 。b叶节点可能被展开，新的结点被策略网络pθ pθ 

5 评估AlphaGo的下棋能力

为了评估 AlphaGo 的水平，我们举办了内部比赛，成员包括不同版本的 AlphaGo 和几个其它的围棋程序，包括最强的商业程序 CrazyStone和Zen，和最强的开源程序Pachi和Fuego。所有这些程序都是基于高性能蒙特卡洛树搜索算法的。此外，我们的内部比赛还包括了开源程序GnuGo，它使用了最先进搜索方法的蒙特卡洛树搜索。所有程序每次执行下一步棋允许5秒钟。

比赛的结果如图4,a，它预示着单击版本的AlphaGo比先前任何一个围棋程序强上很多段，在495场比赛中，AlphaGo赢了其中的494场比赛。我们也在让对手4目棋的情况下进行了比赛：AlphaGo和CrazyStone，Zen，Pachi的胜率分别是77%，86%，99%。分布式版本的AlphaGo强大很多：和单机版本的AlphaGo对弈的胜率是77%，和其他的围棋程序对弈的胜率是100%。

我们也评估了不同版本的AlphaGo，不同版本仅仅使用估值网络（λ=0 λ=0 来精确的评估博弈的结局。图5将AlphaGo在真实博弈棋局中评估能力可视化了。

最终，我们把分布式版本的AlphaGo和樊麾进行了评估，他作为一个职业2段棋手，是2013，2014，2015年的欧洲围棋冠军。在2015年10月5-9日，AlphaGo和樊麾在真实比赛中下了5盘棋。AlphaGo以5：0的比分赢了比赛（图6和扩展数据表1）。这是史上第一次，在人类不让子和完整棋盘的情况下，一个围棋程序在赢了一个人类职业棋手。这个壮举之前认为需要至少十年才能达到。

图4：AlphaGo的比赛评估。a 和不同围棋程序比赛的结果（见扩展数据表6-11）。每个程序使用接近5秒每走一步棋的速度。为了给AlphaGo更高的挑战难度，一些程序得到了所有对手让4步子的优势。程序的评估基于ELO体系：230分的差距，这相当于79%的胜率差距，这大致相当于在KGS中高一个业余等级。一个和人类接近的相当也显示了，水平的线显示了程序在在线比赛中达到的KSG等级。和欧洲冠军樊麾的比赛也包括在内。这些比赛使用更长的时间控制。图中显示了95%的置信区间。b 单机版本的AlphaGo在组成部分的不同组合下的性能表现。其中仅仅使用了策略网络的版本没有使用任何搜索算法。c 蒙特卡洛搜索树算法关于搜索线程和GPU的可扩展性研究，其中使用了异步搜索（浅蓝色）和分布式搜索（深蓝色），每下一步时间两秒。

图5：AlphaGo（执黑）是在一个和樊麾的非正式的比赛中选择下棋走子的。接下来的每一个统计中，估值最大的落子地点用橘黄色标记。a根节点 s 的所有后继结点 s’ 的估值，使用估值网络 vθ(s′) vθ(s′) ；如果大于0.1%的话，以百分比的形式报告出来。e 从根节点开始的模拟过程中下棋走子地点选择的频率百分比。f AlphaGo的树搜索的理论上的走子选择序列（一个搜索过程中访问次数最多的路径）。下棋走子用一个数字序列表示。AlphaGo选择下棋的落子地点用红色圆圈标记出来；樊麾下在白色方形的地方作为回应；在他的复盘过程中，他评论道：下在地点 1 应该是更好的选择，而这个落子地点正好是AlphaGo预测的白棋的落子地点。

6 讨论

在这个工作中，我们基于一个深度神经网络和树搜索的结合开发了一个围棋程序，它的下棋水平达到了人类最强的水平，因此成功战胜了一项人工智能领域的伟大挑战。我们首次，对围棋开发了一个有效的下棋走子选择器和棋局评估函数，它是基于被一个创新型的监督学习和强化学习的组合训练的深度神经网络。我们引入了新的搜索算法，它成功的把神经网络评估和蒙特卡洛走子结合在一起。我们的程序AlphaGo把这些组成部分按照比例集成在一起，成为了一个高性能的树搜索引擎。

在和樊麾的比赛中，AlphaGo对棋局评估的次数和深蓝对卡斯帕罗夫下国际象棋的时候的次数相比，是其千分之一。作为补偿的，是更加智能的棋局选择能力，使用了更加精确的评估棋局的能力，使用了估值网络（一个也许是更加接近于人类下棋方式的方法）。此外，深蓝使用的是人类手工调参数的估值函数，然而AlphaGo 的神经网络是直接从比赛对弈数据中训练出来的，纯通过一个通用目的的监督学习和强化学习方法。

围棋在很多方面是横亘在人工智能面前的困难：一个有挑战性的决策任务；一个难以对付的解空间；和一个非常复杂的最优解，以至于它看上去不可能世界使用策略或者估值函数逼近。之前的关于围棋程序的重大突破，蒙特卡洛树搜索，在其它领域导致了相应的进步：比如通用的博弈比赛，经典的规划问题，局部观察规划问题，调度问题，和约束满足问题。通过把树搜索和策略网络、估值网络结合在一起，AlphaGo 最终达到了围棋职业选手的水平，并且提供了希望：在其它看似难以解决的人工智能领域里，计算机现在是可以达到人类水平的。

图6： AlphaGo 和欧洲冠军樊麾的博弈棋局。下棋走的每一步按照下棋顺序由数字序列显示出来。重复落子的地方在棋盘的下面成双成对显示出来。每一对数字中第一个数字的落子，重复下到了第二个数字显示的交叉地方。

参考文献
略

其他贡献者
略

感谢
我们感谢樊麾答应和AlphaGo进行比赛；感谢T.M担当比赛的裁判；感谢R.M和T.S给予有帮助的讨论和建议；感谢A.C和M.C在可视化方面的工作；感谢P.D, G.W, D.K, D.P, H.vH, A.G和G.O修订了这篇论文；感谢 DeepMing 团队其它的成员的支持，想法，和鼓励。

后记

理解 AlphaGo 有两个关键部分：

1. 深度神经网络的训练过程，文章把这个过程描述成为一个管道。所谓管道，很像Linux系统中的管道命令，把前者的输出作为后者的输入
2. 蒙特卡洛树搜索的过程，看这个搜索是如何把 SL策略网络，估值网络，快速走子策略结合在一起的。

先谈谈 1：
输入人类的棋谱，经过监督学习，输出SL策略网络
输入SL策略网络，经过强化学习，输出RL策略网络
输入RL策略网络，经过强化学习，输出估值网络

再谈谈 2：
蒙特卡洛树搜索是模拟下棋，并且评估的过程。蒙特卡洛就是“随机”的意思，只不过逼格更高而已。如果你“随机”下棋，肯定输呀，怎么办？使用 SL策略网络来预测人类是如何下棋的。AlphaGo每次要下棋的时候，先运行 SL策略网络一遍，得到一个概率分布，在此基础上进行“随机”：更有可能在概率更大的地方落子。
AlphaGo一边模拟自己下棋，一边模拟对手下棋，最后，下完了。所谓下完了，就是在树搜索的时候达到了叶节点。下完了之后，对棋局进行评估。结合估值网络和快速走子策略，得到一个估值函数，该函数的值越高，越好。
模拟很多很多遍。模拟结束之后，进行“统计”工作。统计每一条边走过的次数，和估值函数的估值。最后，AlphaGo做出选择：现在是棋局 s，如果在 a 地方，结合 a 在模拟过程中走过的次数，以及 a 下面的叶节点的估值函数，累加起来最高，那么AlphaGo选择在 a 地方落子。

最后来一个知乎上关于AlphaGo的评论，里面有李开复老师的赛前预测~