Google人工智能击败欧洲围棋冠军， AlphaGo 究竟是怎么做到的？
编者按：本文由新智元原创翻译自Nature。如果觉得此文深奥，关于机器学习，还可看雷锋网早期文章：《机器自学72小时堪比国际大师，深度学习到底有多厉害？》
围棋一直被视为人工智能最难破解的游戏。就在今天，《Nature》杂志以封面论文的形式，介绍了 Google DeepMind 开发的人工智能程序 AlphaGo，它击败了欧洲围棋冠军樊麾，并将在 3 月和世界冠军李世乭对战！Google 特地为此准备了 100 万美元奖金。
从国际象棋的经验看，1997 年人工智能第一次打败人类后，2006 年成为了人类在国际象棋的绝唱，自此之后人类没有战胜过最顶尖的人工智能国际象棋选手。在 AlphaGo 打败了欧洲围棋冠军后，世界冠军李世乭和 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，神经网络玩围棋游戏的能力，就达到了最先进的蒙特卡洛树搜索算法的级别（这种算法模拟了上千种随机自己和自己下棋的结果）。我们也引入了一种新搜索算法，这种算法将蒙特卡洛模拟和价值、策略网络结合起来。
通过这种搜索算法，AlphaGo 在和其他围棋程序比赛的胜率达到了 99.8%，并以 5：0 的比分击败了人类欧洲围棋冠军樊麾。这是电脑程序第一次在全尺寸（19X19）的棋盘上击败了人类专业选手，这一成果过去认为至少需要 10 年才能实现。
欧洲围棋冠军樊麾：2005 年樊麾被正式聘任为法国围棋队和少年围棋队的总教练，那一年的他才 24 岁。他是 2013、2014 和 2015 欧洲围棋赛冠军。
通过将Value Networks、Policy Networks与树搜索结合起来，AlphaGo 达到了专业围棋水准，让我们看到了希望：在其他看起来无法完成的领域中，AI 也可以达到人类级别的表现！
关于DeepMind 团队对围棋项目的介绍，可进入新智元查看。
所有完全信息（perfect information）博弈都有一个最优值函数（optimal value function），它决定了在所有参与博弈的玩家都做出了完美表现的情况下，博弈的结果是什么：无论你在棋盘的哪个位置落子（或者说是状态s）。
这些博弈游戏是可能通过在含有大约个bd可能行动序列（其中b是博弈的宽度，也就是在每个位置能够移动的步数，而d是博弈的深度）的搜索树（search tree）上反复计算最优值函数来解决的。在象棋（b≈35，d≈80）和围棋之类（b≈250，d≈150）的大型博弈游戏中，穷尽地搜索是不合适的，但是有效搜索空间是可以通过2种普遍规则得到降低的。
首先，搜索的深度可能通过位置估计（position evaluation）来降低：在状态s时截取搜索树，将随后的子树部分（subtree）替换为根据状态s来预测结果的近似的值函数v(s)≈v*(s)。这种方法使程序在象棋、跳棋、翻转棋（Othello）的游戏中表现超越了人类，但人们认为它无法应用于围棋，因为围棋极其复杂。
其次，搜索的宽度可能通过从策略概率p(a|s)——一种在位置s时表示出所有可能的行动的概率分布——中抽样行动来降低。比如，蒙特卡洛法通过从策略概率p中为博弈游戏双方抽样长序列的行动来让搜索达到深度的极限、没有任何分支树。将这些模拟结果进行平均，能够提供有效的位置估计，让程序在西洋双陆棋（backgammon）和拼字棋（Scrabble）的游戏中展现出超越人类的表现，在围棋方面也能达到低级业余爱好者水平。
围棋为何如此复杂？
围棋有3361 种局面，而可观测到的宇宙，原子数量才1080。
围棋难的地方在于它的估值函数非常不平滑，差一个子盘面就可能天翻地覆，同时状态空间大，也没有全局的结构。这两点加起来，迫使目前计算机只能用穷举法并且因此进展缓慢。
但人能下得好，能在几百个选择中知道哪几个位置值得考虑，说明它的估值函数是有规律的。这些规律远远不是几条简单公式所能概括，但所需的信息量还是要比状态空间本身的数目要少得多（得多）。一句话，穷举状态并不是最终目标，就算以后超超级计算机能做到这一点，也不能说解决了人工智能。只有找到能学出规律的学习算法，才是解决问题的根本手段。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正处于下棋状态，对于下面的每一个统计，橙色圆圈代表的是最大值所处的位置。
红色圆圈表示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也可以达到人类级别的表现。
| 新智元特约专家评论我认为AI技术征服人类不需要太长时间，可能就发生在今年，AI技术征服人类。
——微软亚洲工程院院长刘震
I thought AI won't beat human in Go for a long time... It may be this year! Google's AlphaGo beats European professional champion 5:0; next on deck: 李世石九段 in March for M Google prize.
——陈雷，万同科技CEO，留德MBA，连续创业者，现致力于人工智能+围棋的互联网服务，围棋网络9段
对于人而言，围棋竞技是智力、心理和灵性三个维度的综合比拼。根据Deep Mind现有的计算机围棋解决方案描述，可以判断程序在智力维度取得了很大的进展。在智力方面，计算机围棋研究领域中要解决的核心问题是如何对盘面做形势判断，即专家评估系统的解决方案，专家评估系统能力的显著提高会导致围棋AI水准的本质提升。Deep Mind的计算机围棋解决方案其实可归结为精确的专家评估系统（value network）、基于海量数据的深度神经网络（policy network），及传统的人工智能方法蒙特卡洛树搜索的组合。有理由相信这个程序已经达到与标准业余6段棋手或中国职业棋手等级分200位之后的棋手实力相当的地步。从经验上看，由于缺少心理和灵性维度的突破，AlphaGo战胜人类最顶尖的围棋高手尚需时日。
| 关于 Google DeepMindGoogle DeepMind是一家英国人工智能公司，创立于2010年，名为DeepMind Technologies，2014年被谷歌收购，更名为Google DeepMind。
这家公司由Demis Hassabis、Shane Legg和Mustafa Suleyman创立。公司目标是“解决智能”，他们尝试通过合并机器学习最好的方法和系统神经科学来构建强大的通用学习算法。他们试图形式化智能，进而不仅在机器上实现它，还要理解人类大脑。当前公司的焦点在于研究能玩游戏的电脑系统，研究的游戏范围很广，从策略型游戏围棋到电玩游戏。
创始人介绍
Demis Hassabis，人工智能研究人员，神经科学家，电脑游戏设计者，毕业于剑桥大学，并在伦敦大学获得PhD，研究兴趣：机器学习、神经科学。
Shane Legg，计算学习研究人员，DeepMind创始人，研究兴趣：人工智能、神经网络、人工进化、强化学习和学习理论。
Mustafa Suleyman，英国企业家，DeepMind Technologies的共同创始人和产品运营主管，同时也是Reos Partners的共同创始人，被谷歌收购后，他成为Google DeepMind的应用AI部门主管。
