《自然》论文详解：AlphaGo 背后的深度神经网络和树搜索
Nature 封面论文：Mastering the game of Go with deep neural networks and tree search（通过深度神经网络和树搜索，学会围棋游戏）
AlphaGo 给围棋带来了新方法，它背后主要的方法是 Value Networks（价值网络）和 Policy Networks（策略网络），其中 Value Networks 评估棋盘位置，Policy Networks 选择下棋步法。这些神经网络模型通过一种新的方法训练，结合人类专家比赛中学到的监督学习，以及在自己和自己下棋（Self-Play）中学到强化学习。这不需要任何前瞻式的 Lookahead Search，神经网络玩围棋游戏的能力，就达到了最先进的蒙特卡洛树搜索算法的级别（这种算法模拟了上千种随机自己和自己下棋的结果）。我们也引入了一种新搜索算法，这种算法将蒙特卡洛模拟和价值、策略网络结合起来。
通过将 Value Networks、Policy Networks 与树搜索结合起来，AlphaGo 达到了专业围棋水准，让我们看到了希望：在其他看起来无法完成的领域中，AI 也可以达到人类级别的表现！
DeepMind 团队对围棋项目的介绍（新智元翻译）
论文简介
所有完全信息（perfect information）博弈都有一个最优值函数（optimal value function），
，它决定了在所有参与博弈的玩家都做出了完美表现的情况下，博弈的结果是什么：无论你在棋盘的哪个位置落子（或者说是状态s）。这些博弈游戏是可能通过在含有大约b^{d} 个可能行动序列（其中b是博弈的宽度，也就是在每个位置能够移动的步数，而d是博弈的深度）的搜索树（search tree）上反复计算最优值函数来解决的。在象棋（
）和围棋之类（
）的大型博弈游戏中，穷尽地搜索是不合适的，但是有效搜索空间是可以通过2种普遍规则得到降低的。首先，搜索的深度可能通过位置估计（position evaluation）来降低：在状态s时截取搜索树，将随后的子树部分（subtree）替换为根据状态s来预测结果的近似的值函数
。这种方法使程序在象棋、跳棋、翻转棋（Othello）的游戏中表现超越了人类，但人们认为它无法应用于围棋，因为围棋极其复杂。其次，搜索的宽度可能通过从策略概率
——一种在位置s时表示出所有可能的行动的概率分布——中抽样行动来降低。比如，蒙特卡洛法通过从策略概率p中为博弈游戏双方抽样长序列的行动来让搜索达到深度的极限、没有任何分支树。将这些模拟结果进行平均，能够提供有效的位置估计，让程序在西洋双陆棋（backgammon）和拼字棋（Scrabble）的游戏中展现出超越人类的表现，在围棋方面也能达到低级业余爱好者水平。
译者注：围棋为何如此复杂？
围棋难的地方在于它的估值函数非常不平滑，差一个子盘面就可能天翻地覆，同时状态空间大，也没有全局的结构。这两点加起来，迫使目前计算机只能用穷举法并且因此进展缓慢。但人能下得好，能在几百个选择中知道哪几个位置值得考虑，说明它的估值函数是有规律的。这些规律远远不是几条简单公式所能概括，但所需的信息量还是要比状态空间本身的数目要少得多（得多）。一句话，穷举状态并不是最终目标，就算以后超超级计算机能做到这一点，也不能说解决了人工智能。只有找到能学出规律的学习算法，才是解决问题的根本手段。By 田渊栋
蒙特卡洛树搜索（MCTS）使用蒙特卡洛算法的模拟结果来估算一个搜索树中每一个状态（state）的值。随着进行了越来越多的模拟，搜索树会变得越来越庞大，而相关的值也会变得越来越精确。通过选取值更高的子树，用于选择行动的策略概率在搜索的过程中会一直随着时间而有所改进。目前最强大的围棋程序都是基于蒙特卡洛树搜索的，通过配置经训练后用于预测人类棋手行动的策略概率进行增强。这些策略概率用于将搜索范围缩小到一组概率很高的行动、以及在模拟中抽样行动。这种方法已经取得了高级业余爱好者水平的表现。然而，先前的工作仅局限于基于输入特征（input features）的线性组合的粗浅策略概率和值函数。
近期，深度卷积神经网络在视觉领域有很多前所未有的表现：例如，图像分类、脸部识别、玩雅特丽游戏等。他们使用很多层神经元，每个被安排在交叠的区块（Tiles）中来构建越来越抽象和本地化的图片表示。我们在围棋游戏中采用了一个相似的构架。我们用19X19的图像来传递棋盘位置，使用卷积层来构建位置的表示。我们使用这些神经网络来减少搜索树的有效深度和宽度（breadth）：使用一个Value Networks（价值网络）来估算位置，使用Policy Network（策略网络）来对动作进行抽样。
我们使用由若干机器学习阶段（Stages）构成的流水线来训练神经网络（例1）。我们直接使用人类专家的步法来训练监督学习策略网络pσ。这为快速而有效的学习更新（Learning Updates）提供了高质量的梯度和即时反馈。与之前的工作相似，我们也训练了一个快速策略网络pπ，它可以快速地在模拟中对动作进行抽样。接下来，我们训练了强化学习（RL）策略网络pρ，这个网络通过优化“自己对抗自己”的最终结果来改善监督学习策略网络。这将策略调整到赢棋这一正确目标上，而非让预测精确率最大。最后，我们训练了价值网络vθ，它可以预测出RL策略网络通过模拟“自己对抗自己”而得出的策略中哪种是最佳策略。我们的程序AlphaGo高效地结合将策略和价值网络与蒙特卡洛树搜索结合起来。
实现过程
为了评估AlphaGo，我们在诸多AlphaGo变体和一些其他围棋程序中进行了内部比赛，这其中包括了最强大的商业程序Crazy Stone和Zen，还有最大的开源程序Pachi和Fuego。所有这些程序都是基于高性能MCTS算法。此外，比赛也包含了开源程序GnuGo，这个程序使用了在MCTS之前出现的最先进的方法。规定所有程序每次落子有5秒的计算时间。
比赛的结果表明单机AlphaGo领先任何之前的围棋程序很多段位，取得了495局比赛中494次胜利的成绩（99.8%）。为了给AlphaGo提出更大的挑战，我们也让AlphaGo让四子（让子，即对手自由落子）来比赛；AlphaGo让子竞赛中对阵Crazy Stone、Zen和Pachi时分别取得了77%、86%和99%的成绩。分布式AlphaGo明显更强大，对阵单机AlphaGo取得77%的成绩，完胜其他程序。
详解：AlphaGo 如何在对弈中选择步法
黑色棋子代表AlphaGo正处于下棋状态，对于下面的每一个统计，橙色圆圈代表的是最大值所处的位置。
a.用价值网络（value network）
估测根节点s处的所有子节点s’，展示了几个最大的获胜概率估计值。
b.计算树中从根节点s处伸出来的边（其中每条边用(s,a)来表示）的动作值Q（s,a），仅当（λ=0）时，取价值网络估值的平均值。
c.计算了根位置处伸出的边的动作值Q(s,a),仅当（λ=1）时，取模拟估计值的平均值。
d.直接从SL策略网络
中得出的落子概率，（如果这个概率高于0.1%）则结果以百分比形式表示出来。
e.计算了在模拟过程中，从根节点选出的某个动作的频率百分比。
f.表示来自于AlphaGo搜索树的主要变异性（principal variation）（最大访问数路径），移动路径以序号形式呈现出来。
红色圆圈表示AlphaGo选择的步法；白方格表示樊麾作出的回应；樊麾赛后评论说：他特别欣赏AlphaGo预测的（标记为1）的步法。
AlphaGo与樊麾的比赛结果
以编号形式展示了AlphaGo和樊麾进行围棋比赛时各自的落子顺序。棋盘下方成对放置的棋子表示了相同交叉点处的重复落子。每对中的第一个棋子上的数字表示了何时发生重复落子，而落子位置由第二个棋子上的数字决定。（见补充信息 Supplementary Information）
第一盘：AlphaGo 以 2 目半获胜
第二盘：AlphaGo 中盘胜
第三盘：AlphaGo 中盘胜
第四盘：AlphaGo 中盘胜
第五盘：AlphaGo 中盘胜
最终，我们评估了分布式AlphaGo与樊麾的比赛，他是专业2段位选手，2013、14和15年欧洲围棋赛冠军。在2015年10月5日到9日，AlphaGo和樊麾正式比赛了5局。AlphaGo全部获胜。这是第一次一个电脑围棋程序，在没有让子、全尺寸（19X19）的情况下击败人类专业选手，这一成果过去认为至少需要 10 年才能实现。
讨论
在我们的工作中，我们开发了围棋程序，它将深度神经网络和树搜索结合起来。这个程序可以达到最强的人类选手的表现，因此完成了一个人工智能“伟大挑战”。我们也为围棋首创了高效步法选择和位置评估函数，这是通过具有创新性地将监督和强化学习两种方法结合起来从而训练深度神经网络。我们也引入了一个新搜索算法，这一算法成功的整合了神经网络评估和蒙特卡洛树模拟算法。我们的程序AlphaGo在高性能树搜索引擎中从一定规模上将这些成分整合在一起。
在和樊麾的比赛中，AlphaGo在评估位置方面要比深蓝与Kasparov4比赛时所评估的位置少几千倍，这是由于我们使用了策略网络更智能地选择那些位置，还使用了价值网络更精确地评估它们，而价值网络更接近人类的下棋方式。另外，深蓝依靠手工设计评估方程，而AlphaGo的神经网络是直接通过纯比赛数据训练，也使用了通用监督和强化学习方法。
围棋代表了很多人工智能所面临的困难：具有挑战性的决策制定任务、难以破解的查找空间问题和优化解决方案如此复杂以至于用一个策略或价值函数几乎无法直接得出。之前在电脑围棋方面的主要突破是引入MCTS，这导致了很多其他领域的相应进步：例如，通用博弈，经典的计划问题，计划只有部分可观测问题、日程安排问题和约束满足问题。通过将策略和价值网络与树搜索结合起来，AlphaGo终于达到了专业围棋水准，让我们看到了希望：在其他看起来无法完成的领域中，AI也可以达到人类级别的表现。