AlphaZero背后的算法原理解析

作者：一然（好贷网首席架构师）

AlphaGo战胜人类围棋冠军已经好几年过去了，这个话题已经不热，但是这个项目背后的原理仍然值得我们去学习，尤其是AlphaZero的诞生，纯粹靠自己跟自己下棋这样的“左右互搏”就练成了高手，战胜了前辈AlphaGo，令人炫目。好消息是，以现在机器学习框架及工具的发展水平来看，我们自己动手写一个简单的AlphaGo-Simple也应该不是不可能了。于是出于对深度神经网络和强化学习的学习目的，本文我们就来讨论下理论基础。

我们就从最先进的AlphaZero入手开始讨论，这个模型总体结构其实是比较简单的，但是深入到细节方面，却又有很多值得学习之处。架构大体上如下图：

总体上有两个重要的部分发挥着作用，一个是蒙特卡洛搜索树MCTS，一个是卷积神经网络CNN。我们分别来讨论两者，先看蒙特卡洛树，这个树跟普通多分支树结构没有不同，但是每一个节点代表一个下棋的策略，从“根”节点开始，去遍历子节点，理论上穷举所有的节点为止，每一个叶子节点代表一盘棋的结果，输了、赢了或者平了（围棋里面极难出现平局，要看围棋的规则怎么定）。然后基于当前棋盘的局势，选择一个可行的胜利的路线。为了计算方便，每一个节点上都有两个值，一个分值W，W等于所有子节点的W值的和，这个定义是递归的。而N代表这个节点的被访问次数，等于所有子节点的N值的和，这个定义也是递归的。

那么，我们就可以这样评判一个节点（下棋策略，或者叫做棋盘上的棋形）的好坏，也就是价值：

这个式子代表第 i 个节点的评分，它由两部分组成，一个是节点价值Wi/Ni ；另一部分是节点被访问的频度，其中Np代表父节点被访问频度。结合以上两者就是说节点的价值越高或者被访问的频度越低，就倾向于访问这个节点。可是这两者又不能完全等权重，所以就给以折扣因子C，来平衡一下两方面的权重。

凭借上面的公式似乎解决了策略选择的问题。但是，当我们开始实施这个公式的时候，问题就来了：初始化蒙特卡洛树时候W和N都是0，怎么选择呢？一个自然的想法就是引入人类的“专家经验”，毕竟人类下棋已经上千年了，有不少经验，可以把这些经验用来启动蒙特卡洛树。这个主意不错，但是不能完全解决上面的问题，因为以围棋为例子，19乘19的棋盘，可谓变化“无穷”，蒙特卡洛树是非常非常大的，也就是说搜索空间极其大，人类经验覆盖了只有一点点而已。于是，我们想，要是能够用一种方法直接给出每个节点的选择概率，是不是选择起来就方便很多。不管谁来扮演这个预言“概率”的角色，姑且就算这个角色必然存在，我们看看有了这个概率以后，上面的公式变成了啥样子：

引入一个概率，同时为了防止未访问的节点分母为零，所以加了一个1，这个1在浩如烟海的搜索空间里面应该是微不足道的。

接下来，就要讨论这个核心P了，谁来贡献这个概率？

既然要基于一堆数据生产出一个概率，我们自然想到了神经网络，没错，卷积神经网络CNN就被引进来了。为什么是CNN，因为棋盘上的棋形就很方便用一个照片来记录嘛，那自然就用卷积神经网络来处理这个图像嘛。

于是，就有了最上面那个架构，卷积神经网络根据棋盘上的棋形给出某一种策略的概率，没错，这不是一个概率，而是一组概率，相当于多分类问题。把这个概率给到蒙特卡洛搜索树里面去，就可以帮助选择某个“策略”。直到一盘棋下完，又可以回去更新蒙特卡洛搜索树的W和N（因为这两个概念都是递归的，所以更新的过程就是从叶子节点一路走到根节点）。从而形成了一个循环：神经网络的输出作为蒙特卡洛树的参数，反过来，蒙特卡洛树的搜索结果可以用来训练神经网络，自反馈……自我意识……原谅我胡说八道，并没有自我意识。

实际实现中，这个神经网络输出俩部分，一个是概率，一个是值，也就是W的估计值，都作为蒙特卡洛树的参数来用。

最后一个问题，如果初始的时候一点外部经验数据都不引入进来，那么怎么设置概率P呢，对了，就是随机就好啦，反正自己跟自己下棋的过程可以更新W，N，P。

有了这个架构，可以给出损失函数了：