AlphaGo

Mastering the game of Go without Human Knowledge

写在最前：本人还是小菜一枚，本文只简要描述了alphago zero中的关键技术，而且也都是我个人的理解，理解不对的地方还请大神指出，如果大家有什么问题的话，也可以直接在评论区留言

1. 文章简介

这是一篇deepmind发在nature上的paper，论文描述了最新版本的AlphaGo，命名为AlphaGo

Zero，AlphaGo Zero在与战胜李世石版的AlphaGo lee的对局中，打出了100:0的惊人战绩。

如图1所示，AlphaGo Zero在训练3天之后就超越了AlphaGo

Lee，在训练了不到30天的时候就超越了AlphaGo Master，之后，AlphaGo Zero的性能还在进一步缓慢提升。

1.1 AlphaGo Zero的主要改进

相比于之前的AlphaGo，AlphaGo Zero主要的改进有：

1. 将之前的AlphaGo中的两套网络合并为一套，在之前的AlphaGo中，采用了actor网络和critic网络，而在AlphaGo Zero中，这两套网络合二为一，同时输出所有动作的选择概率和状态s的价值。

2. AlphaGo Zero中没有使用任何人工经验，也就是没有使用supervised learning来做预训练，完全使用reinforcement learning自学习。而在之前的AlphaGo中，先使用很多盘人类高手之间的对局作为training data来预训练AlphaGo中的网络，训练完之后再让AlphaGo使用reinforcement learning进一步学习。

3. 之前的AlphaGo中，状态s的维度比较高（19*19*n，n是多少忘记了，好像是48），这是因为其中包含了很多维人工设计的特征，而在AlphaGo Zero中，状态s的维度是19*19*17，并没有人工设计的特征。

1.2 本文中的一些参数

动作空间：362维（19*19+1），每个交叉点上都可以落子，而且还有一个pass动作（跳过这一步，让对手下），但是有些交叉点上可能已经有棋子了，那为啥每个交叉点上都可以落子呢？不要急，在MCTS时会忽略那些非法的动作。

对弈规则：本文中，棋局会在博弈的双方都选择pass时，或者到了最大步数19*19*2时终止。

状态：本文中的状态的维度是19*19*17，状态s由 组成，其中 表示本方上一步走棋之后的棋局状态， 表示对方上一步走棋之后的棋局状态， 用来表示当前该哪一方走棋。

reward：围棋是零和游戏，因此赢的一方可以得到1的reward，而失败的一方得到-1的reward。

2. 方法细节

2.1 neural Network

AlphaGo Zero使用了resnet的网络结构，网络结构如下：

其中p表示362个动作的概率，整个neural Network的计算可用下面公式表示，其中 表示network的参数。

2.2 search算法

MCTS的tree中的每个节点s都存储当前节点所有可行的动作对应的edges：（s，a），每个edge包含如下的信息：

其中 表示在节点s选择动作a的次数， 是由MCTS算出的该edge的累计行为价值， 表示MCTS计算出的该edge的平均价值， 表示状态s下，选择行为a的先验概率（这个概率由network输出，并添加了一定的噪声）。这4个值在MCTS开始时，初始化为

search的整个流程可由下图表示：

其中a、b、c三个过程重复执行1600次，最后的d是在搜索结束之后真实的选择行为。在论文中，作者使用了多线程来搜索。

a. Select

首先从root节点 执行搜索，向下搜索L次，得到叶子节点 ，注意，这里的L次是针对每个搜索线程的，不是所有线程的全部搜索次数。每次搜索时选择一个当前节点的可执行动作a（根据围棋规则），而不是从362个动作空间中选，因为这362个动作中有一些动作是不能选的。动作的选择由下面公式来确定

其中 由下面公式计算

参数 代表了select动作时的exploration的程度（如果exploration太小的话，select的动作的空间就被局限在一小部分空间中了，可能无法select到最优的行为）。

当MCTS第一次开始搜索时，由于所有edge的 被初始化为0，因此，此时行为的选择由 决定，而 又主要由 和 决定，所以在MCTS的搜索初期， 越大， 越小，那么行为a被选择的可能就会增大，保证了搜索算法的exploration性能。MCTS的搜索后期，由于 被持续更新趋向于真实值，因此，在后期，搜索主要由 决定。

更通俗的解释：人在下棋过程中也会向前推演几步，人在推演的过程中所依据的就是直觉（类似于AlphaGo Zero网络输出的动作选择概率），比如在root节点处，人类感觉走哪一步会比较好，就会在推演中走这一步，然后再自己分析对方可能会走在哪里，然后再自己根据直觉再走一步...，但是在推演的过程中，可能走了几步之后感觉局面变差了（AlphaGo Zero网络输出的状态价值比较低），于是重头推演，重头推演的时候，动作的选择就不一样了，当走了几步之后发现局面变好了，那人类就会认为这样的下棋走法比较好，但是又怕自己推演的还不够全面，可能还有更好的走法，于是就推演很多种不同的走法（exploration），最后，人类会发现一种比较好的走法，但是在实际中，这样的推演对计算能力的要求太高，也就只有计算机能够完成，人类也只能推演少数走法。

b. Expand and evaluate

将select到的叶子节点 加入到队列中，通过neural network计算该叶子节点的价值，如：

其中 表示对节点 的变换（起data augmentation的作用，在围棋中，棋局旋转90°的整数倍、棋局翻转不会影响棋局）。

注意当网络在计算节点的状态价值时，搜索线程需要被暂时lock。

叶子节点处的向下搜索的edges被初始化为

c. Backup

将上一步中计算出的叶子节点的价值向后传播，传播的结果就是从root节点 到叶子节点 的整个搜索路径上搜索到的节点都被更新了一遍，更新公示如下：

d. Play

在a、b、c循环执行了1600次之后，AlphaGo Zero在root节点处选择真实的落子动作，动作选择的概率如下式所示

参数 用于控制动作选择的随机性，用于控制exploration的程度。

对该公式的理解就是，在之前的搜索模拟过程中，哪个动作被更多的采用，那么在真实的动作选择时，这个动作就更容易被选择到，因为在搜索的后期，动作的选择主要由 决定，所以，在搜索过程中， 大的动作的 也会更大一些，那么在选择真实动作时，就会间接的更倾向于选择 大的动作。

在执行完这真实的一步动作之后，当前的新节点变为MCTS的新root节点，重新回到前面的a、b、c阶段，从新的root节点往下搜索。

2.3 self play

Self play包括3部分，每一部分都使用多线程并行执行，如下：

1. optimisation：

neural network的参数 不断地使用最新的self play的数据来优化更新，使得网络输出的动作选择概率以及状态价值更可靠（类似于人的直觉，专业棋手的直觉相对于业余棋手对于棋局的判断的直觉更准确，这是因为专业棋手经过了更多的训练），本文使用了64个GPU线程（workers），每个线程都有自己的网络参数，所以就有64个 ，每个worker的训练数据是从最近的50万盘self play的棋局中随机抽取的，其batch_size是32。每训练1000步，保存一个checkpoint。

2. evaluator：

为了保证self play的棋局数据是目前最优的，我们需要评估每个worker的性能，假如某个worker优于现在最好的worker，那么就让这个worker作为当前最好的worker，并让这个最好的worker生成后续的self play的棋局数据。评估的办法就是让这两个worker对弈，如果参数为 的worker对参数为 的worker的取胜概率超过了55%，那么就认为这个 的worker优于 的worker。

3. self-play：

当前最好的worker用于生成25000局的self-play data，在self play过程中，每一步都执行1600个MCTS来选择最终的真实动作，作者说这1600个MCTS仿真大约需要执行0.4s，在每一局中的前30步，将 设置为1，之后将 设置为一个很小的数，用于改变exploration的程度。另外，作者还通过给root节点的动作选择概率添加噪声的方法来增加exploration。另外，作者为了降低计算量，会有90%的几率将肯定会输的棋局提前放弃。

2.4 learning

通过search方法，可以得到很多训练数据 ，每个状态s都对应一个由search输出的动作选择概率 和该状态的价值 ，就可以使用这些training data来训练neural Network，公式如下：

参数c用于防止neural Network的过拟合。