深入浅出解读并思考AlphaGo

2020-12-26 本文已影响0人 CristianoC

本文是对2016年发表在Nature的<< Mastering the game of Go with deep neural networks and tree search >>的解读与思考，即AlphaGo原版算法的解读与思考。

引言
监督学习策略网络（Supervised Learning of Policy Networks）与快速走子网络(Rollout Policy Networks)
强化学习策略网络（ Reinforcement Learning of Policy Networks）
强化学习价值网络（Reinforcement Learning of Value Networks）
蒙特卡洛搜索树（MCTS）
总结
参考

引言

2016年，Google Deepmind团队的AlphaGo战胜了欧洲冠军职业选手引起了不小的轰动，而后AlphaGo更是打败了韩国职业九段棋手李世石震惊全球。为什么AlphaGo在围棋上取得的成功会引起这么大的轰动？这是因为围棋的状态空间非常大，大约为 $2 × 10 ^ {170}$ 这么大，远远超过现在计算机的计算能力，即我们计算机无法通过无脑暴力穷举来下围棋。
假设现在轮到你下围棋，你需要从两个维度思考：首先你要先想一下有哪些位置可以下，我们把这种思考叫做思考的广度 $b$ ；其次我们要想一下我们下了某一步之后局面会怎么变化，对方会怎么下，我们又怎么接着对方的棋往下下，我们把这种思考叫做思考的深度 $d$ ；如果我们希望能下出“神之一手”，那么最理想的情况就是我们既考虑了广度又考虑了深度，即我们进行 $b^d$ 次思考。显然由于状态空间过大，这是不合理的。
那我们应该通过什么方法可以即减少我们思考的状态空间复杂度，又可以保证我们思考的完美呢？AlphaGo从两方面出发。首先对于我们思考的广度，我们使用策略分布 $P(a|s)$ （策略分布指的是在某个局面 $s$ 下，可能采取走的位置 $a$ ）来随机采样下一步走的位置，也就是我们希望下一步走的地方是那些高概率的地方，而不是随便走。其次对于思考的深度，AlphaGo提出通过棋局评估来降低，也就是通过一个近似的值来评估某个棋局的好坏而不用去思考这步棋下完之后的棋局演化，输或者赢。我们只要通过我们近似出来的值函数 $V$ ，将当前的棋局 $s$ 代入，就能知道这步棋下的有多好了 $V(s)$ 。
AlphaGo的总体结构可以分为下图的四个部分：
我们简要概括一下整个过程：我们首先构建一个监督学习的策略网络 $P_{\sigma}$ ，使用人类专家的棋谱数据进行训练，训练目的是学会人类在一些棋局下的走法。同时本文也会训练一个快速走棋策略网络（Rollout policy） $P_{\pi}$ ，这个快速走棋的策略网络牺牲了走棋的质量来获得更快的走棋时间，类似于我们下棋时候的第一感觉，虽然没那么准但还是有参考意义。接下来会训练一个强化学习策略网络 $P_p$ ，这个网络以刚才监督学习的策略网络为基础，不断和自己对弈，在监督学习的基础上调整优化目标，这里的优化目标是赢棋，而原始监督学习的目标是下出和专家一样的棋。同时在不断自我对弈的过程中也会产生新的数据集。紧接着会训练一个价值网络，用于从全局预测某个棋面下赢棋的概率。最后我们会把以上训练好的几个网络用蒙特卡洛搜索树组装在一起，就是我们AlphaGo的全部结构。
使用人类专家的棋谱进行训练的监督学习的策略网络 $P_{\sigma}$ 对于预测人类专家下棋的准确率有57%，这代表通过这个网络AlphaGo已经有一半概率以上下出和人类专家一样的棋。我们训练的快速走棋的策略网络对预测人类专家下棋的准确率也有24%，在下棋速度快了上千倍的前提下也算是不错的结果了。强化学习训练的不断自我对弈的策略网络在和前面监督学习的策略网络对弈的时候胜率高达80%，这说明通过不断自己跟自己下棋，AlphaGo的棋力也得到了巨大的提升。最后我们训练的价值网络在对全局胜率的预测中均方差也只有0.22左右，这说明AlphaGo对于全局走势也有一个比较准的判断。接下来我们就其中的细节慢慢展开。

监督学习策略网络（Supervised Learning of Policy Networks）与快速走子网络(Rollout Policy Networks)

监督学习策略网络（Supervised Learning of Policy Networks）

我们知道这个监督学习策略网络（以下简称SL网络）的目的是为了模仿人类专家下棋，在具体介绍是如何学习之前我们先介绍一下模型的输入和使用的训练数据。

数据

既然我们要模仿人类专家下棋，那我们就需要大量人类专家的棋谱。得益于网络时代，DeepMind从外国围棋对战平台KGS获得16万局6至9段人类选手的围棋对弈棋谱，总共有3000万个棋谱供给SL进行训练。
有了数据之后监督学习还需要构建我们数据的标签，标签其实就是某个棋面 $s$ 下人类专家下一步下棋的位置 $a$ ，我们的棋谱其实就是一个有时间序列的下棋矩阵，所以我们很轻松就可以构建出大量的数据标签对 $<s,a>$

模型输入输出

我们知道围棋本质上就是一个 $19 × 19$ 的矩阵，其中每个位置有三种情况，白子（1），黑子（-1），无子（0）。理论上我们每个棋盘输入 $19 × 19$ 的矩阵就足以表达所有的特征，如下所示：
尽管我们的神经网络可以表达出非线性的特征，但是围棋实在是太复杂了，如果我们可以手动输入一些我们已知的先验知识，增加我们输入特征的维度，那显然可以大大提高训练的效率。那怎么增加特征维度呢？那就需要围棋领域的一些知识，比如围棋中的气，目，空，打吃等的特征，具体如下：
最后我们SL网络选择了48种特征，即我们SL网络输入的维度是 $19 × 19 × 48$ 。我们SL网络输入是 $19 × 19 × 48$ 的棋局特征，输出则是在 $19 × 19$ 的棋盘下各个位置下子的概率。得到每个位置下子的概率后我们取最大的就是我们预测的下棋位置。

SL网络

有了数据和模型输入的维度之后，我们来思考我们要怎么构建我们的网络。我们发现，一个围棋棋盘 $19 × 19$ 的矩阵，其实不就是一个 $19 × 19$ 像素的图片吗，对于图片我们使用最多的就是卷积神经网络，得益于我们构建的输入特征，AlphaGo仅仅使用13层的卷积神经网络就达到了57%的准确率。

快速走子网络(Rollout Policy Networks)

快速走子网络可以理解为训练一个简化版的SL网络，形成一种下棋的直觉，具体用处会在后面蒙特卡洛搜索树中提及。
快速走子网络使用更少的输入特征，线性的softmax来构建网络，最后预测人类专家下子的准确率为24.2%，下棋速度仅需要2微秒，是SL网络需要3毫秒的千分之一，非常快。

思考

以上SL网络和快速走子网络的效果虽然可以接受，但远没到可以跟李世石挑战的地步，我们仔细思考一下原因有哪些。
首先，虽然我们的数据是充足的，但是这些棋谱毕竟是业余选手下的，质量参差不齐。正如我们经常说的数据决定了上限，而算法只是去逼近这个上限，所以我们训练出来算法的水平最高也就是和这些业余棋手差不多。而现实中顶尖棋手的棋局相对来说也是不多的，那我们能否考虑让算法自己跟自己下来补充高水平的棋局呢？
其次，我们现在都只考虑下的和专家下的一不一样，并没有考虑输赢，往往输的棋我们也学了，数据的标签里面只有下一步棋的位置而没有这局棋的胜负关系。
现实生活中，我们说一个人下棋厉害往往说的是他能推演到几步之后的对局，目前为止我们都没有进行推演，如果能加上推演应该就能向职业水平发展。

强化学习策略网络（ Reinforcement Learning of Policy Networks）

强化学习策略网络 $P_p$ （以下简称RL策略网络）通过自我对弈可以为我们的AlphaGo提供更多更高质量的样本，接下来介绍一下其中实现的各种细节。

网络结构

RL策略网络结构和SL网络结构一致，其权重也是用SL网络权重进行初始化，即RL策略网络是以SL网络为基础训练的。

训练过程

随机选择前面某个迭代周期得到的SL网络，然后使用当前的RL策略网络和其对弈，目标是战胜选择的SL网络。随机的从一系列不同迭代周期的监督学习策略网络Pσ中选择对手是为了防止过拟合。
在前面的思考中提过，我们之前完全没考虑到棋局的胜负。所以这里将棋局和棋局的胜负都考虑进来，用强化学习算法Poliicy Gradient以最大化赢的期望的目标更新参数。Policy Gradient算法简单来说就是如果在当前棋局下某步棋导致最后奖励变多（赢了），那就加大在这个棋局下下这步的概率，反之亦然，如果有读者感兴趣阅读我之前有关Policy Gradient的讲解文章。
每隔500步就复制现在的参数进入我们的对手阵营中供第二步使用。

在这里规定赢棋奖励就是1，输棋就是-1，和棋或者没下完奖励就是0。在每局中有很多时间步 $t$ , 每个时间步对应一个 $t$ 时刻的棋面 $S_t$ ，不断使用前一轮训练的强化学习策略网络进行自我对弈，一直到时间步 $T$ 决出了该局的胜负奖励 $r(S_T)$ 。此时进行神经网络参数更新，也就是回过头将该胜负标签 $r(S_T)$ 贴到该局前面每个时间步对应的棋面 $S_t$ 的标签上。

实验结果

最终经过不断自我对弈，我们训练出来的RL策略网络在和SL策略网络对弈的时候胜率高达80%，取得巨大突破！

强化学习价值网络（Reinforcement Learning of Value Networks）

正如前面提到的，我们的RL价值网络可以判断当前棋面下双方的胜率。

网络结构

RL价值网络的结构和RL策略网络结构近似，但是RL策略网络结构的输出是某一棋面下下棋动作的概率分布，用来下棋；但是RL价值网络的输出则是某个棋面下是否赢棋的预测值。

训练过程

RL价值网络的训练很直接，就是直接使用一个棋局的胜负进行回归训练，以最小化均方误差为目标进行随机梯度下降。
这里要注意，如果我们直接从人类完整棋局中学习价值网络会导致过拟合。因为不同的棋面之间存在很强的相关性，有的甚至只有一个落子不同，导致价值网络学习时直接记住最后的输赢，对同一对局而言输入稍有不同而输出都相同，而不能泛化到新的棋局。
所以RL价值网络训练使用的三千万棋面来自三千万局棋，即每局棋我们只取其中一个棋面进行训练，有效防止过拟合。
RL价值网络的训练数据也不是单纯由强化学习自我对弈而来，在每局对弈的过程中先使用SL网络下子，然后随机下子，最后再使用RL策略网络下子，充分保障了数据的多样性。

实验结果

经实验，RL价值网络预测的均方差在0.22左右，还是很不错的。

蒙特卡洛搜索树（MCTS）

经过上面的讲解，想必读者对这四个网络已经有了深刻的认识，但是以上的几个网络都没有解决我们思考中提出的一点：如何进行棋局推演？这个答案就是用MCTS蒙特卡洛搜索树将这几个网络作为部件组合在一起，这就是AlphaGo的全貌了。在训练好了以上介绍的四个部分后，MCTS蒙特卡洛搜索树将这四个部分结合在了一起，在能进行棋局推演的同时，策略网络减少了思考的广度，价值网络减少了思考的深度，可谓叹为天人。

核心要素

MCTS的核心要素包括两点，节点和边。
MCTS中的每个节点就是一个棋面 $s$ ，在每个棋面下完一步棋就变成下一个棋面，也就是变成当前节点的子节点。
MCTS中的每条边就是在当前节点（棋面） $s$ 下的一步棋（动作） $a$ ，其中还保存了该动作的效益值 $Q(s,a)$ , 访问次数 $N(s,a)$ , 和先验概率 $P(s,a)$ 。

MCTS搜索模拟过程

MCTS搜索模拟过程分为四步，分别是Selection选择，Expansion扩展，Evaluation评估，Backup反馈更新。

Selection选择：从根节点也就是初始棋面出发，选择在这个棋面 $s$ 下最好的下法 $a$ 。那什么叫好呢？这里有一个公式：我们提倡选择动作效益值 $Q(s,a)$ 加奖励 $\mu$ 最大的动作

其中 $\mu(s_t,a)$ 正比于：
我们可以看到，奖励正比于该动作的先验概率，反比于这个动作的访问次数。这说明我们的MCTS鼓励探索那些看起来还行（先验概率P高）而且还没怎么尝试过的下棋方法（访问次数低）。

Expansion扩展：当 $L$ 时刻我们遍历到了一个叶子节点 $S_L$ ，而这个叶子节点的访问次数又超过一定阈值后，我们进行扩展。（如果一遇到叶子节点就扩展，计算量太大，而且等于你什么情况都要考虑，没必要）我们把要扩展的这个棋面输入到我们的SL网络中，会返回各个棋子位置的概率，我们把下一步各个棋子的位置变成当前棋面的子棋面，而各个棋子的概率存进我们新扩展边里面（即先验概率P(s,a)）。
Evaluation评估：对上述叶子节点进行胜率的评估，判断当前棋面的局势。这里我们使用两种方法进行评估，一种则是我们前面介绍的价值网络预测胜率，得到 $V_{\theta}(S_L)$ ；第二种则是通过快速走子策略，从叶子节点出发，快速行棋至最后，每一次行棋结束后都会有个输赢结果，因为速度很快所以可以进行多轮行棋，然后综合统计得出该策略网络预测的胜率 $z_L$ 。通过综合这两个指标，得到这个叶子节点的胜率评估值 $V(s_L)$
Backup反馈更新：上述对叶子节点评估完，代表着1次模拟结束。此时反向更新在此次模拟过程中到达上述叶子节点所经过的边的动作效益值 $Q(s,a)$ 以及访问次数 $N(s,a)$ 。 $n$ 次模拟后，每条边累积的 $Q(s,a)$ 值更新量和访问次数更新量如下：

其中 $1（s,a,i）$ 表示在第i次模拟中，是否经过这条边。其中第二条公式也体现出为啥这种搜索叫做蒙特卡洛搜索（平均回报）。

经过n次模拟搜索后，算法从根节点（当前棋面）选择访问次数最多的边对应的动作作为最终决策。

细节

前面提到扩展使用的是SL策略网络而不是RL策略网络。因为人类选择的是a diverse beam of promising moves，即人类下的棋比较有多样性，这点利于MCTS的扩展；而RL学的是当前步的最优下法（whereas RL optimizes for the single best move），不利于扩展。
前面我们一直没提到快速走子网络的用处，在这里终于体现了：用来评估某个棋面的胜率。这里读者可能会想，RL价值网络不是已经可以很好地预测局面了吗，为什么还要通过快速走子网络来预测胜率？按我理解这就是思考中不同纬度的融合。RL价值网络考察到目前为止的形势判断，快速走子网络模拟到终局的形势判断，二者综合起来性能更优。

总结

仔细解读完AlphaGo的原理后最大的体会就是每个部分单单来看都没有很创新，像蒙特卡洛搜索更是传统的方法，但是AlphaGo却将他们很好的融合在了一起，这种合起来的思路某种意义上来说就是自己要学习的“学术直觉”，与读者共勉。

深入浅出解读并思考AlphaGo

目录

引言

监督学习策略网络（Supervised Learning of Policy Networks）与快速走子网络(Rollout Policy Networks)

监督学习策略网络（Supervised Learning of Policy Networks）

数据

模型输入输出

SL网络

快速走子网络(Rollout Policy Networks)

思考

强化学习策略网络（ Reinforcement Learning of Policy Networks）

网络结构

训练过程

实验结果

强化学习价值网络（Reinforcement Learning of Value Networks）

网络结构

训练过程

实验结果

蒙特卡洛搜索树（MCTS）

核心要素

MCTS搜索模拟过程

细节

总结

参考

猜你喜欢

热点阅读