AlphaGo论文阅读

2019-12-05 本文已影响0人鲜橙

AlphaGo中的关键组件

论文的模型看似复杂，不过将其拆分为以下部件逐一理解会比较容易

有监督学习得到的策略网络。这一策略网络通过学习人类高手的棋盘，从而能够在给定某个棋盘状态时，以较高准确率预测人类高手的落子点
强化学习得到的策略网络。进行自我对弈，根据对弈的结果用policy gradient的方法更新策略网络
状态值评估网络。使用部件2进行自我对弈的数据集进行训练，因此也是由强化学习训练得到的，该网络在输入一个棋盘状态时，能给出该状态下获胜的概率。
改进的蒙特卡洛搜索树。用于做对弈的模拟演算，这个改进的版本将上述部件整合在一起，提供了更具智能的模拟。

上述部件的实现

有监督学习的策略网络

这一网络目的是学习预测人类高手的落子的概率分布，用于最终搜索算法的先验信息。使用的网络结构是卷积神经网络，由卷积层与非线性激活函数构成，最后的输出层是softmax层，该层的作用是将输出归一化，使之能表示所有合法落子点的概率，即 $P(a|s)$ , 其中s为输入网络的棋盘状态。

数据集是从KGS围棋服务器得到的3千万个棋局，每一个棋局包含一个棋盘状态s和一个人类落子的位置a。那么棋盘信息如何进行卷积操作呢，这里是将19x19的棋盘看成一个19x19的图像一样看待，这样就可以用图像的卷积方法了。

最终训练得到的网络能很好的预测人类在给定棋盘时的落子点的概率分布，概率越大表示人类越有可能在该点落子。这就得到了有监督的策略网络 $P_\sigma(a|s)$ ，这个网络的预测准确率能达到 $57.0\%$ 。不过于此同时，他们还训练了一个快速的但是准确率较低的策略网络 $P_\pi(a|s)$ ，这个快速策略在之后的蒙特卡洛搜索树中会用得到。

强化学习的策略网络

该部件旨在提升有监督的策略网络 $P_\sigma(a|s)$ ，它为之后的状态值评估网络提供了对弈的数据。在网络结构上，与有监督的网络的网络结构完全相同，并且其网络的初始权重就是 $P_\sigma(a|s)$ 网络学习到的权重。

该网络的学习是基于策略的学习，使用的是策略梯度算法。我们知道强化学习最常应用在游戏中，那么同样的，这里的“游戏”的过程是一个左右互博的过程，即当前的策略网络与某个对手策略进行相互博弈，这里的对手是随机的从训练过程中的前面一些迭代次数的策略网络中选择出来的，这里的随机选择能避免过拟合的情况。

定义在状态 $s_t$ 下执行 $a_t$ 的收益 $z_t$ 是：如果该局胜利则+1，如果该局失败则-1。则在时间t的期望收益为 $p_\rho(a_t|s_t)$ 。因此在每一个时间点t，网络的参数需要更新的梯度为
$\Delta\rho\propto\frac{\partial\log{p_\rho(a_t|s_t)}}{\partial\rho}z_t$
在对Pachi的对弈中，仅使用强化学习得到的策略 $P_\rho(a|s)$ 能获得85%的胜率，而仅使用有监督的策略网络 $P_\sigma(a|s)$ 只能得到15%的胜率

强化学习的状态值评估网络

该网络 $v_\theta(s)$ 在最终的搜索算法中会用于对节点的评估。它评估给定棋盘状态s和策略p时双方的收益值，即
$v^P(s)=E[z_t|s_t=s, a_t...T~p]$
该网络的网络架构与之前两个相似，但是不同的是网络最后只输出一个预测值而非概率分布。给定一组“状态s-结果z”的样本，该网络的损失函数为
$L_\theta=(v_\theta(s)-z)^2$
数据集是用前面介绍的强化学习的策略网络进行自我对弈得到的3千万个棋盘状态和对应的结果。另外为了避免因为棋盘之间有关联性而带来的模型过拟合问题，这些数据集的每一个样本都是从不同的一局对弈中获取的，也就是说3千万个棋盘状态对应的是3千万盘的独立的对弈。

蒙特卡洛树搜索

这是将前面的部件整合在一起的算法。由于下一节会详细展开，因此这里不赘述。

整合上述部件的蒙特卡洛树搜索

在学习本文的改进版蒙特卡洛树搜索之前，先了解以下原始的蒙特卡洛树搜索

原始的蒙特卡洛树搜索[1]

目的

该算法的目的是给定一个”游戏状态“并选择“胜率最高的下一步”
主要思想

众所周知，蒙特卡洛就意味着模拟，在这里也是一样，蒙特卡洛树搜索会多次模拟博弈，并尝试根据模拟结果预测最优的移动方案。

蒙特卡洛树搜索的主要概念是搜索，即沿着博弈树向下的一组遍历过程。
1. 单次遍历会从当前节点根据节点的信息选择子节点向下遍历，直到一个没有完全展开的节点，未完全展开表示其子节点至少有一个未访问到。
2. 遇到未完全展开的节点时，它的一个未访问子节点将会作为单次模拟的根节点，从该节点开始模拟运行至产生游戏结果。
3. 模拟的结果将会反向传播回当前树的根节点并更新博弈树的节点统计数据。一旦搜索受限于时间或计算力而终止，下一步行动将基于收集到的统计数据进行决策。
算法
1. 遍历
  
  向下遍历的过程并不是随机的。对于已经未完全展开的节点，选择未访问的子节点，若当前节点已经完全展开那么对子节点有一个评估函数，每次向下遍历均选择评估值最大的子节点进行遍历。评估函数如下
  $uct(v_i, v)=\frac{Q(v_i)}{N(v_i)}+c\sqrt{\frac{\log{N(v)}}{N(v_i)}}$
  其中 $v$ 是当前节点， $v_i$ 是子节点， $Q(v_i)$ 是节点 $v_i$ 的模拟获胜次数， $N(v_i)$ 是节点 $v_i$ 的总模拟次数， $N(v)$ 是节点v的总模拟次数。c是一个可调节的参数。
  
  这个函数中的前一个加数表示的是该节点的模拟胜率，后一个加数表示的是访问次数的多寡。这两项结合在一起的意义则是遍历过程中会尽量选择胜率高的节点进行展开(这点与极大极小策略一致)，但是同时会鼓励探索很少访问的节点。
  
  综上所述，遍历环节的伪代码为：
```
while(完全展开(node)):
   node = best_uct(node)
return 未访问的子节点(node)
```
2. 模拟与反向传播
  
  前一个步骤遍历到了一个未访问（未评估）的节点 $v_u$ ，那么接下来就从该节点开始进行模拟，在原始算法中采用完全随机（即均匀分布）的方法向下模拟，直到游戏结束返回一个结果（例子：象棋中从某一棋盘状态开始随机走棋，直到自己被将死或者对方被将死）。
  
  接着将该结果记录在节点 $v_u$ 中，并且从节点 $v_u$ 向上传播，更新第一步的遍历路径上的所有节点的信息。举个例子，如果模拟的结果是获胜，那么路径上所有节点的获胜次数都会加一。
3. 算法结束与预测
  
  对于博弈树很大的游戏来说，上述算法可以执行特别久，那么什么时候终止 MCTS？答案是：只要资源允许，就可以一直运行 MCTS，因为与其他蒙特卡洛方法一样，模拟的次数越多，得到的结果通常会越准确。
  
  而MCTS 算法结束运行之后，算法预测的最好的一步是有最高访问量 $N(v_i)$ 的一步，因为它的奖励值评估结果最好

本文的蒙特卡洛树搜索

节点信息

与原始的算法不同，本文的搜索树中的节点不仅包含有动作值 $Q(s,a)$ ，访问计数 $N(s,a)$ ，还有另外的一个信息，即先验动作概率分布 $P(s,a)$ 。当一个节点第一次被访问到时，该节点对应的棋盘状态送入有监督学习到的策略网络 $P_\sigma(a|s)$ 中，得到该节点状态对应的动作概率分布，将其赋值给该节点的先验动作概率分布 $P(s,a)$
遍历

与原算法相同的是，对于已经完全展开的节点，需要有评估函数对其子节点进行评估，从而选择子节点进行向下遍历，不同的是这里的评估函数不同，变为如下的公式
$uct(a_t,s_t) = Q(s_t,a_t)+\frac{P(s_t,a_t)}{1+N(s_t,a_t)}$
也即由以下公式求下一步动作
$a_t=argmax(Q(s_t,a_t)+\frac{P(s_t,a_t)}{1+N(s_t,a_t)})$
模拟与反向传播

与原算法中只通过随机策略进行模拟的方法不同，本文方法对一个叶节点的评估有两个方面：
- 通过状态值估计网络直接进行评估
- 通过有监督的学习得到的快速走子策略 $P_\pi(a|s)$ 进行模拟，注意这里的模拟除了策略与原算法不一样以外，其余是完全一样的
最后的评估函数由上述两项加权求和得到：
$V(s_L)=(1-\lambda)v_\theta(s_L)+\lambda z_L$
其中 $\lambda$ 是一个可调节的参数， $v_\theta(s_L)$ 是状态值估计网络的评估， $z_L$ 是通过策略 $P_\pi(a|s)$ 进行模拟的结果。

反向传播时，对遍历的路径上的节点计数加一，并且对路径上的节点更新
$Q(s,a)=Q(s,a)+\frac{V(s_L)}{N(s,a)}$
注意我这里的公式与论文中的公式有所不同，是因为论文中是计算了所有模拟的评估值之和，而我这边只写了一次模拟，因此我这里的加法与论文中的求和本质上是一致的。
算法结束与预测

与原算法相同，当算法结束时，算法预测的最好的一步是有最高访问量 $N(s,a)$ 的一步

总结与思考

有监督学习得到的策略 $P_\sigma(a|s)$ 在最终的搜索中作为节点的先验信息，在节点的遍历中起了指导的作用。
有监督学习得到的快速走子策略 $P_\pi(a|s)$ 在搜索中被用作模拟的策略，使得对叶节点的评估更具准确。
强化学习得到的策略 $P_\sigma(a|s)$ 在搜索中没有直接的作用，而是间接通过状态值评估网络的方式在叶节点的评估中发挥作用
状态值评估网络 $v_\theta(s)$ 在搜索中对叶节点进行评估，部分代替了原始蒙特卡洛树搜索中的模拟评估，不仅加快了评估的速度，还能以更大局观的眼光评估叶节点状态
关于哪个部件使得算法能超越了人类的问题，我认为，有监督的学习得到的策略网络由于是用人类的棋谱学习的，因此无论学的多好，其结果也只能是接近人类而非超过人类。因此我认为使之超过人类的主要是强化学习和蒙特卡洛树搜索的功劳。

[1]. https://www.jiqizhixin.com/articles/monte-carlo-tree-search-beginners-guide