AlphaGo原理浅析

要完全弄清AlphaGo背后的原理，首先需要了解一下AI在博弈游戏中常用到的蒙特卡洛树搜索算法——MCTS。

在一个完全信息下的博弈游戏中，如果所有参与者都采取最优策略，那么对于游戏中的任意一个局面\(s\)，总有一个确定性的估值函数\(v^*(s)\)可以直接计算出最终的博弈结果。理论上，我们可以通过构建一棵博弈树，递归地求解出\(v^*(s)\)。这就是Minimax算法。然而在有些问题中，这棵搜索树往往十分巨大（例如在围棋游戏中达到了\(250^{150}\)的搜索空间），以至于穷举的算法并不可行。

有两种策略可以有效地降低搜索空间的复杂度：1. 通过一个evalutaion function对当前局面进行价值的评估以降低搜索的深度；2. 剪枝以降低搜索的宽度。然而，这些策略都需要引入一些先验的知识。

于是，人们提出了蒙特卡洛树搜索（MCTS）算法。MCTS是一类通用博弈算法——理论上，它不需要任何有关博弈的先验知识。

想象一下，你站在一堆老虎 机面前，每一台老虎 机的reward都服从一个随机的概率分布。然而，一开始，你对这些概率分布一无所知。你的目标是寻找一种玩老虎 机的策略，使得在整个游戏的过程中你能获得尽可能多的reward。很明显，你的策略需要能够在尝试尽可能多的老虎 机（explore）与选择已知回报最多的老虎 机（exploit）之间寻求一种平衡。

一种叫做UCB1的策略可以满足这种需求。该策略为每台老虎 机构造了一个关于reward的置信区间：

其中，\(x_i\)是对第\(i\)台老虎 机统计出来的平均回报；\(n\)是试验的总次数；\(n_i\)是在第\(i\)台老虎 机上试验的次数。你要做的，就是在每一轮试验中，选择置信上限最大对应的那台老虎 机。显然，这个策略平衡了explore与exploit。你的每一次试验，都会使被选中的那台老虎 机的置信区间变窄，而使其他未被选中的老虎 机的置信区别变宽——变相提升了这些老虎 机在下一轮试验中被选中的概率。

蒙特卡洛树搜索（MCTS）就是在UCB1基础上发展出来的一种解决多轮序贯博弈问题的策略。它包含四个步骤：

可以看出，通过Selection步骤，MCTS算法降低了搜索的宽度；而通过Simulation步骤，MCTS算法又进一步降低了搜索的深度。因此，MCTS算法是一类极为高效地解决复杂博弈问题的搜索策略。

关于MCTS算法更多详细的介绍，可参见博客：Introduction to Monte Carlo Tree Search

围棋是一类完全信息的博弈游戏。然而，其庞大的搜索空间，以及局面棋势的复杂度，使得传统的剪枝搜索算法在围棋面前都望而却步。在AlphaGo出现之前，MCTS算法算是一类比较有效的算法。它通过重复性地模拟两个players的对弈结果，给出对局面\(s\)的一个估值\(v(s)\)（Monte Carlo rollouts）；并选择估值最高的子节点作为当前的策略（policy）。基于MCTS的围棋博弈程序已经达到了业余爱好者的水平。

然而，传统的MCTS算法的局限性在于，它的估值函数或是策略函数都是一些局面特征的浅层组合，往往很难对一个棋局有一个较为精准的判断。为此，AlphaGo的作者训练了两个卷积神经网络来帮助MCTS算法制定策略：用于评估局面的value network，和用于决策的policy network。（后面会看到，这两个网络的主要区别是在输出层：前者是一个标量；后者则对应着棋盘上的一个概率分布。）

首先，Huang等人利用人类之间的博弈数据训练了两个有监督学习的policy network：\(p_\sigma\)（SL policy network）和\(p_\pi\)（fast rollout policy network）。后者用于在MCTS的rollouts中快速地选择策略。接下来，他们在\(p_\sigma\)的基础上通过自我对弈训练了一个强化学习版本的policy network：\(p_\rho\)（RL policy network）。与用于预测人类行为的\(p_\sigma\)不同，\(p_\rho\)的训练目标被设定为最大化博弈收益（即赢棋）所对应的策略。最后，在自我对弈生成的数据集上，Huang等人又训练了一个value network：\(v_\theta\)，用于对当前棋局的赢家做一个快速的预估。

因此，用一句话简单概括一下AlphaGo的基本原理：在MCTS的框架下引入两个卷积神经网络policy network和value network以改进纯随机的Monte Carlo模拟，并借助supervised learning和reinforcement learning训练这两个网络。

接下来将对AlphaGo的细节进行展开讨论。

Huang等人首先训练了一个有监督的Policy Network用来模拟人类专家的走子。SL policy network是一个卷积神经网络；其输出层是一个Softmax分类器，用来计算在给定的棋面状态\(s\)下每一个位置的落子概率\(p_\sigma(a|s)\)。对一个棋面状态\(s\)的描述如下： （这里的Features对应着卷积神经网络里的Channels。）

经过人类高手三千万步围棋走法的训练后，SL policy network模拟人类落子的准确率已经达到了57%；相应地，网络的棋力也得到大大的提升。但是，如果直接用这个网络与人类高手，甚至是MCTS的博弈程序进行对弈，依然是输面居多。而且，这个网络的走子太慢了！平均每步\(3ms\)的响应时间，使得这个网络很难被直接用于MCTS的rollout中进行策略的随机。因此，Huang等人通过提取一些pattern features又训练了一个更快速（响应时间达到了\(2\mu s\)）但准确率有所降低（24.2%）的rollout policy network： \(p_\pi\)。

接下来，为了进一步提高policy network的对弈能力，Huang等人又采用一种policy gradient reinforcement learning的技术，训练了一个RL policy network：\(p_\rho\)。这个网络的结构与SL policy network的网络结构相同，依然是一个输出为给定状态下落子概率的卷积神经网络。网络的参数被初始化为\(p_\sigma\)的参数；接下来，通过不断地自我对弈（与历史版本），网络的权重向着收益最大化的方向进化。此时，网络的学习目标不再是模拟人类的走法，而是更为终极的目标：赢棋。

具体来说，我们定义了一个reward function \(r(s_t)\)：对于非终止的时间步\(t