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（策略网络）来对动作进行抽样。

（编辑：云计算网_泰州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!