【专栏】谷歌资深工程师深入浅析AlphaGo Zero与深度强化学习

【AI WORLD 2017世界人工智能大会倒计时 12 天】

“AI达摩”齐聚世界人工智能大会，AI WORLD 2017议程嘉宾重磅发布 

即将于2017年11月8日在北京国家会议中心举办的AI World 2017世界人工智能大会，我们请到CMU教授、冷扑大师发明人Tuomas Sandholm，百度副总裁王海峰，微软全球资深副总裁王永东，阿里巴巴副总裁、iDST副院长华先胜，亚马逊AWS机器学习总监Alex Smola，科大讯飞执行总裁胡郁，华为消费者事业群总裁邵洋等国内外人工智能领袖参会并演讲，一起探讨中国与世界AI的最新趋势。

点击文末阅读原文，马上参会！

抢票链接：http://www.huodongxing.com/event/2405852054900?td=4231978320026

大会官网：http://www.aiworld2017.com

  新智元专栏  

作者：王晶

【新智元导读】AlphaGo的巨大成功掀起了围棋界三千年未有之大变局，也使得深度强化学习(Deep Reinforcement Learning)渐为大众熟悉。尤其是最新推出的AlphaGo Zero完全摒弃了人类知识，并且三天内碾压了早期版本的AlphaGo，更足显强化学习和深度学习结合的巨大威力。AlphaGo Zero的论文侧重于描述效果，对于方法的论述比较简短，没有相关背景的人读起来可能会有一些困难。本文对强化学习以及AlphaGo Zero算法做了详细描述。

作者简介：王晶，Google广告大数据部门资深工程师，从事机器学习算法研发，2014年博士毕业于波士顿大学，主要研究方向强化学习。2010年本科毕业于华中科技大学。

1.     AlphaGo Zero无需任何人类历史棋谱，仅使用深度强化学习，从零开始训练三天的成就已远远超过了人类数千年积累的围棋知识。

2.   强化学习能够考虑到算法对于环境的影响, 特别适合解决多回合博弈问题。

3.   在强化学习中，数据在运行过程中自主收集，这是AlphaGo Zero能摈弃人类棋谱的原因。

4.   强化学习的速度限制通常来源于环境给予反馈的时延。弈棋类问题可以通过左右互搏得到即时反馈，所以弈棋类问题对于强化学习来说是比较容易的一类问题。

5.   在强化学习中知识存储在值函数中，深度强化学习就是利用深度神经网络来逼近值函数的一类强化学习方法。AlphaGo Zero使用了华人提出的ResNet进行深度学习，提升达到600Elo。

6.   AlphaGo Zero使用的强化学习方法称为Policy Iteration （策略迭代法）。Alphago Zero交替使用深度学习评估策略(policy evaluation)和蒙特卡洛树搜索优化策略(policy improvement)。

强化学习介绍

强化学习（Reinforcement Learning）是机器学习里面一个分支。如果说强化学习在AlphaGo之前版本里面还是初试牛刀的话，那在AlphaGo zero里面就真正大显神威了。根据deepmind的论文，新版本AlphaGo Zero经过三天的训练轻易达到对老版本的100:0的胜率，并且完全无需人类棋谱。可以说，AlphaGo Zero仅仅三天的成就就远远超过了人类数千年的围棋探索。

为什么强化学习能够这么强？这要和它的特点有关系。强化学习和传统机器学习的区别有如下几点：

• 传统机器学习假设算法本身对于环境无影响，强化学习破除了这个限制，能够考虑到了算法对于环境的影响, 这使得强化学习特别适合解决多回合博弈或者顺序决策问题（sequential decision making）问题。事实上，这类问题在生活中是非常普遍的，比如股市的交易。传统机器学习可以预测股票价格，但是只有不使用结果进行买卖模型才会长期有效。如果你预测完了之后你根据据测去做多或着做空这个股票，那么其他的股票买家可能因为你的行为改变了自身行为，你原来的训练的模型便会失效，而强化学习可以考虑到这点。

• 在强化学习中，数据是在运行过程中自主收集。这解决了机器学习中常见的训练数据难于获取的问题。AlphaGoZero之所以能够完全摒弃人类知识就是因为所有的数据都是通过机器互博生成。从这个意义上来说，强化学习的算法具有自主学习能力。这就是强化学习在机器人领域里面使用比较广泛的原因。但是要注意到的是，通常强化学习的速度限制并不是来自于算法的训练，而是来自于环境给予反馈的延时。比如说股票交易里，股票的涨跌必须过一段时间才能发生，股市关闭的时候也不可能有反馈。所以就不可能像AlphaGo Zero这么快。

具有强化学习能力的程序或机器人被称为代理（Agent）。代理所解决的问题被抽象为环境（environment）。注意，这里的并不是说我们通常意义的环境，而实际上是一个具有特定行为的另一个代理。环境可以处于多种状态，状态之间的转换可以用马科夫过程表述（markovian decision process）。代理的目标是通过与环境的交互学会环境的内在状态和与环境打交道的最优策略。

代理算法和环境的一次交互称为迭代。算法需要有一个基本的策略（policy），在每次迭代过程中，算法会根据这个策略选择一个动作（action）。在接收到算法的动作之后，环境会返回一个信号（reward），正代表奖励，负代表惩罚。代理会根据这个信号来评价自己先前策略是否好。下图是一个强化学习的示意图：

用强化学习解决问题，我们需要首先把要解决的问题转化成为一个环境（environment）。环境需要如下的要素：

• 状态空间（state space）：对于围棋来说，每一个棋盘布局（记为s）就是一个状态。所有可能的棋盘布局就是状态空间。

• 动作空间 （action space）：对于围棋来说，所有可能落子的位置就是一个动作空间

• 可行动作 （allowable action）： 在给定状态下，什么动作是可行，什么是不可以的。在围棋里，就是给定一个棋盘，哪里可以落子，哪里不可以。

• 状态转化：你落子之后，对手可能会下的子。如果是两台alpha zero互搏的话，相互是对方环境的一个部分。

• 奖励函数：你落子之后得到的信号。在围棋里面，就是胜率的一个正函数。胜率越大，奖赏越大。

在强化学习里面，知识可以通过一个称为状态－动作值函数（state-action value function) 的结构的存储。通常大家用符号Q(s,a)来表示这个函数，这就是所谓Q-learning的来历。简而言之，Q(s,a)是对于状态s，采取动作a的期望奖励(expectedreward)。

在最早期的强化学习算法里面，Q(s,a)就是一张表的形式来存储的。每次算法会查这个表，然后选取能够带来期望收益最大的动作。需要注意的是，实际过程中算法还需要考虑到过早收敛的问题（可以用探索exploration来解决，我们会稍后聊到）。显而易见，如果状态空间很大，或者是连续空间，那么查表就不管用了，需要使用函数逼近的方式，这就是神经网络的强项了。

在深度强化学习就是利用深度神经网络来逼近值函数的一类强化学习方式。而AlphaGo就是深度强化学习的代表。

下面开始正式的介绍AlphaGo Zero的实现。

深度神经网络

在AlphaGo里面，并没有直接用神经网络逼近状态－动作值函数Q(s,a)，而且用来逼近另外一种值函数－－状态值函数。简而言之：

•  V(s)是棋盘布局s下自己的平均胜率。

V的定义域要远远小于Q，所以逼近起来容易一些。但是V中的信息需要一定的转化才能用来决定落子位置。

先介绍一种经典的方式（虽然AlphaGo Zero没有采用这种方式）：大概的方式是先通过V重建出Q，然后再用查表法类似的概念来确定落子位置。如何重建呢？要点在于如下公式：

其中P(s, a, s') 是在布局s的情况下，落子a处，对方落子之后，布局会变为s'的概率。r(s,a) 是这一步的收益（但是在AlphaGoZero里面实际是一个常量，只取决于最终的胜负）。这个公式的意思是，如果一个落子能够平均意义上将我的带到一个更好的布局，那么这个落子的平均期望收益就更好。如果我们有办法知道转化概率P(.,.,.)的话，那么就可以通过V来重建出Q。

那么我们怎么才能够知道概率呢？一个方式是尝试很多次在布局s的情况下落子到位置a，然后用真正跳到布局s'的频数除以总共试的次数就是估计的概率了。不幸的是，这个方法对于仿真次数要求很高，不是很实用。

• 在AlphaGo早期版本里面，利用了另外一个神经网络来解决这个问题。大概的思路是把估计Q和根据Q的信息预测下一步的落子位置的这个两个部分合起来当作一个黑箱，用来逼近值函数V的神经网络被称为 Value Network

• 用来预测落子位置的神经网络被称为 Policy Network

AlphaGo Zero在此基础上又进一步改进。将两个网络融合称为一个神经网络。对于每一个可能的棋盘布局s，这个神经网络输出如下两个结果：

• 当前胜率(v)：在当前的盘面下己方取胜的概率。v就是之前版本里value network的输出

• 落子概率(p)：这是一个向量，每一个维度对应棋盘上的一个位置，向量的第a个元素是落子到位置a的概率。p就是之前版本里policynetwork的输出。

蒙特卡洛树搜索MCTS

前一部分提到的落子概率也被称为策略（policy）。有了落子概率，非常简单的方式是直接按照这个概率进行落子。但是事实上这会导致神经网络总是原地踏步。这是因为Policy Network的训练数据是自己和自己下棋（self-play）生成的输出，仅仅自己学习自己是不会有改进的。

所以这里需要有一个办法来利用值函数V的信息来优化这个策略。在AlphaGo系列算法里面是使用蒙特卡洛树搜索（Monte Carlo TreeSearch）来进行策略优化的。上图是AlphaGo的结构图，MCTS的输出是依据值函数V得到的一个更优策略，它将被用于通过self－play来生成数据供深度神经网络学习。MCTS也是AlphaGo能够通过self－play不断变强的最重要的原因。

这一种强化学习方法被称为 PolicyIteration （策略迭代法）。这个方法里面交替执行如下两步：

• 策略评估（policy evaluation）：估计当前policy的value function。也就是神经网络在做的事情

• 策略优化（policy improvement）：使用蒙特卡洛树搜索根据估计的valuefunction改进的policy

下面详细介绍一下这个策略优化是怎么进行的。在围棋行棋的过程中，每一次落子都有多种变化，可以用一个多叉树来表示。树的每一个节点代表了一种棋盘布局s，每一个边代表了在一种布局s下的一种落子方式a。

在MCTS里面，每一个边存储四个信息

•  Q(s, a): 平均收益：这个就是前文提到的状态－动作值函数。

• N(s, a)：访问次数

•  W(s,a): 总收益

• P(s,a): 出现状态s并且选择了动作a的先验概率。这个先验概率就是神经网络预测的落子概率。

AlphaGo Zero的MCTS有如下的四个步骤。我们会依次介绍：

推演落子规则 (Select)

在每一个节点s，AlphaGo Zero会根据如下的公式来选择下一次落子位置

其中U(s,a)=cpuctP(s,a)bN(s,b)1+N(s,a)。 U(s,a)是一个confidence interval 的upbound。cpuct决定探索（exploration）的程度。

MCTS在进行搜索的过程中，尝试重建状态动作值函数Q。然后根据查表法类似的原理选择能使期望收益最大的动作。注意到这个增加了一个额外的选项U(s,a)。为什么这个选项重要呢？有两个原因

• 即使我们Q的估计完全准确，如果我们每次都选最优的，那么算法很快会收敛到一个局部解跳不出来了，所以我们需要避免让算法老走一样的棋，增加一些探索其他选项的机会。这就跟小孩子学习一样，必须通过适当的犯错才能够学习到更多。

• 我们里的值函数只是一个估计值，不一定准确。

推演和判定 (Expand and Evaluate)

AlphaGo Zero会根据前面的落子规则不断的落子，这就相当于棋手在脑海中进行推演。但是围棋的搜索空间即使对于计算机来说也是太大，alphago zero只会推演（仿真）到一定步数就停止了。假设最后的布局是s', 那么AlphaGo Zero会调用深度神经网络来预测这局推演结束时自己的胜率v(s') 。这样的推演过程会进行多次。

复盘 (Backup)

等一次推演结束后，AlphaGo Zero会根据推演的结果更新自己的知识，也就是值函数Q（s，u）。对于任意棋盘布局s和任意一种可能落子方案，AlphaGo Zero会依据最终的胜率调整落子的知识（存储在值函数Q(s, a) 里面）。值函数的更新公式如下：

对于这个公式的理解重点在于这个求和符号。

代表的是一次推演出现了在布局s的情况下AlphaGo Zero选择了落子a处，并且这次推演最终布局是s'。N(s, a)是说有多少次这种情况发生。v(s')是最终盘面的胜率，相当于最终的奖励。这个奖励被平均分配到每次决策中。

真正落子(Play)

在不断的推演复盘再推演的过程中，行棋会不断的优化。经过一段时间优化，推演的落子概率就是一个更加好的策略。MCTS的输出

其中\pi_a是落子到位置a的概率，是一个参数，\tau用来指定温度。如果温度越高，落子越随机，温度越低落子越确定。

深度学习训练

在AlphaGo Zero里使用的是有监督的深度学习。而训练样本来自于自己和自己博弈的训练数据（self play）。每一步Alpha Zero都会根据MCTS来选择落子处，直到分出胜负。胜者的单步奖励（记为z）是＋1，负者的单步奖励是－1。

前文提到AlphaGo Zero里面的神经网络实际上是把AlphaGo里面的Policy Network和Value Network糅合在一起了，所以这个神经网络也有两个目标

• 让输出的落子概率p和MCTS的输出越接近越好

•  让预测的值函数v和实际的奖励z越接近越好

最终的要优化的损失函数是

损失函数l包含三项：第一项是为了优化值函数的预测，第二项是为了优化落子概率的预测，第三项是为了防止过拟合。

AlphaGo Zero每1000步会将一个神经网络存档，并且把这个存档和历史最优版本比较，如果胜率超过历史最优的55%，这个版本将会被更新为历史最优。并且在生成数据时，只使用历史最优的神经网络的self－play数据作为深度网络的训练数据。这样可以增加算法的优化速度。

AlphaGo Zero里使用的是深度残差网络（ResNet），论文里面提到ResNet带来了600 Elo的提升。这个方法是何凯明，Xiangyu Zhang, Shaoqing Ren, 孙剑等人在微软亚洲研究院工作期间提出，孙剑是旷视(face++)的首席科学家，何凯明现在在facebook AI部门。这可以看出华人科学家在现在在深度学习领域里面有相当举足轻重的地位。

论文里面还提到了很多工程实现和调参的细节。我暂时还没有自己实现，但这些细节应该对AlphaGo Zero最终效果起到了至关重要的帮助。这边文章主要描述方法，有机会我会另辟文描述工程实现。

关于新老AlphaGo的区别和AlphaGo Zero意义的个人看法

新版方法上面并没有增加，反而是减少了很多部分：依据人类棋谱学习的监督学习部分，快速走子部分都被拿掉了。两个神经网络被融合成一个。在我看来，少就是多，这就是AlphaGo Zero最重大的意义。

第一版本由好几个部分拼凑起来，像是接力跑一样，到底是哪个部分最核心最关键也说不好。许多人会认为基于人类历史棋谱的学习是最重要的部分。但是这边文章证明的是，人类历史棋谱不仅不帮忙，很有可能是限制算法效率的因素。人类的围棋知识可能陷入了一个局部最优。如果从这个点出发优化，可以做到比人好一些，但是不可能达到望尘莫及的地步。

AlphaGoZero直接用强化学习从头开始学习，没有条条框框，可以探索出完全不同的方式。我认为这就是为什么新版会强很多的原因。

另外为什么新版会快很多？第一拿掉了很多无用的部分，计算效率当然更高。第二应该是团队的工程能力和对工具的熟悉度都有了很大提升，Deepmind2014年加入Google，2016年初第一版的时候对于Google的架构很有可能还不是那么熟悉，这一版本肯定进行了大量的优化。

Reference

·       https://deepmind.com/blog/alphago-zero-learning-scratch/

·       https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf

·       Deep Residual Learning for Image Recognition： https://arxiv.org/abs/1512.03385

感谢张瑶琪帮助校订文稿

深入了解AI 技术进展和产业情况，参加新智元世界人工智能大会，马上抢票！

【AI WORLD 2017世界人工智能大会倒计时 12 天】点击图片查看嘉宾与日程。

大会门票销售火热，抢票链接：http://www.huodongxing.com/event/2405852054900?td=4231978320026

【扫一扫或点击阅读原文抢购大会门票】

AI WORLD 2017 世界人工智能大会购票二维码：