围棋游戏因其巨大的搜索空间以及评估棋盘位置和动作的难度，一直被视为人工智能经典游戏中最具挑战性的游戏。本文使用value network评估棋盘位置，并使用policy network选择行为。这些深度神经网络是通过人类专家游戏中的有监督学习和self-play中的强化学习的新颖组合来训练的。同时，本文还提出一种新的MCTS搜索算法，该算法将蒙特卡洛模拟与价值和策略网络相结合。

Introduction

围棋游戏的搜索空间巨大，但是有效的搜索空间可以通过两个通用原则来减少：

• 首先，可以通过位置评估来减少搜索的深度：
  即使用近似价值函数替代最优价值函数直接预测当前叶子节点的状态价值以对搜索树进行截断。
• 其次，可以通过从策略$p(a|s)$p(a∣s)采样动作来减小搜索的广度，$p(a|s)$p(a∣s)是位置$s$s上可能的行为$a$a的概率分布：
  例如，蒙特卡洛（Monte Carlo）rollouts使用policy $p$p为两个参与者采样long sequence of actions，搜索到最大深度而根本不需要分支。

对此类部署进行平均可以提供有效的位置评估。

MCTS使用蒙特卡罗rollouts在搜索树中评估每一个状态的价值，模拟的越多，搜索树就越大，相关的价值估计就越准确，在搜索中使用的策略也会得到改善。

AlphaGo中作者将棋盘位置表示为19x19的图像，使用卷积神经网络来构建位置的representation。同时，作者使用神经网络来减少搜索树的有效深度和广度：

• 使用价值网络评估位置；
• 使用策略网络来选择行为。

作者使用由多个阶段组成的pipline来训练神经网络，如图一所示。

• 首先使用监督学习（SL）训练一个策略网络$P_\sigma$Pσ​，训练数据为人类的专家知识，监督学习的方式使得梯度质量高，更新快；
• 其次，训练了一个快速策略网络$P_\pi$Pπ​，网络深度较浅，可以在蒙特卡罗rollouts中快速选择行为；
• 然后训练了一个强化学习（RL）策略网络$P_\rho$Pρ​，通过优化selfplay游戏的最终结果来改善SL策略网络，这将策略调整为赢得比赛，而不是最大化预测准确性；
• 最后训练了一个价值网络$V_\theta$Vθ​，预测RL策略网络与自己博弈时的赢家。

Supervised learning of policy networks

SL policy network $P_\sigma(a|s)$Pσ​(a∣s)用来预测专家行为，其在卷积层和rectifier nonlinearities间交替，输出层**函数为softmax，输出所有合理行为的概率分布。使用随机梯度上升对策略网络在随机采样的状态-动作对(s,a)上进行训练，以最大程度地提高人类在状态s中移动选定状态的可能性：


SL policy network 是一个13层的网络，预测准确率达到57%。如图2a所示，准确性的微小提高可以导致比赛的大幅提升。较大的网络可获得更高的准确性，但在搜索过程中评估速度较慢。因此，这里还训练了一个快速策略$P_\pi(a|s)$Pπ​(a∣s)，使用小图案特征的线性softmax，准确率只有24.2%，但预测时间从3ms缩减到2μs。

Reinforcement learning of policy networks

RL策略网络$P_\rho$Pρ​的网络结构与SL策略网络$P_\sigma$Pσ​一致，并使用$P_\sigma$Pσ​进行初始化。

selfplay方法如下：

• 一方为目前最新的RL策略网络$P_\rho$Pρ​；
• 一方为随机选择的之前某个迭代版本的RL策略网络。

通过这种方式，从对手群体中随机选择，可以通过防止过度适应当前策略来稳定训练。对于所有非终止时间步长t <T，$r(s_t)=0$r(st​)=0。从当前玩家的角度来看，结果$z_t =±r(s_T)$zt​=±r(sT​)是游戏结束时的终止奖励。 时间步t：+1代表赢，-1代表输。 然后，在每个时间步长t处，通过在最大预期结果方向上的随机梯度上升来更新权重：

实验结果表明，RL策略明显优于各种监督策略。

Reinforcement learning of value networks

价值函数通过对两个玩家都使用策略$P$P来预测所玩游戏的位置$s$s的输出：

理想情况下，我们想知道完美play（$P^*(a|s)$P∗(a∣s)）下的最优值函数$V^*(s)$V∗(s)，这里使用网络对其进行替代：

价值网络与RL策略网络结构相似，只是输出单个奖励。我们通过对state-outcome对(s,z)进行回归来训练价值网络的权重，使用随机梯度下降法来最小化预测值$v_θ(s)$vθ​(s)与相应结果$z$z之间的均方误差（MSE）：

从包含完整游戏的数据中预测游戏outcome的这种原始方法会导致过度拟合。 因为连续位置之间存在很强的相关性，相差仅一石之差，但是回归目标在整个游戏中都是相同的。 当以这种方式在KGS数据集上进行训练时，价值网络会记住游戏outcomes，而不是将其推广到新位置，从而使测试集的最小MSE为0.37，而训练集的最小MSE为0.19。

为了缓解这个问题，本文生成了一个新的selfplay数据集，该数据集包含3000万个不同的位置，每个位置都是从单独的游戏中采样的。 每个游戏都在RL策略网络与其自身之间进行，直到游戏终止。 在此数据集上进行的训练分别导致训练集和测试集的MSE分别为0.226和0.234，这表明最小的过度拟合。图2b显示了价值网络的位置评估精度。

Searching with policy and value networks

AlphaGo在MCTS算法（图3）中组合了策略和价值网络，该算法通过Lookahead搜索选择行动。搜索树的每一个边(s,a)储存有行为价值$Q(s,a)$Q(s,a)，访问次数$N(s,a)$N(s,a)和先验概率$P(s,a)$P(s,a)。

从根状态开始，通过仿真遍历该树（That is, descending the tree in complete games without backup）。在每一次模拟的每一个时刻t，状态$s_t$st​下的行为$a_t$at​根据下式进行选择：

即与先验概率成正比，但随着访问次数而衰减以鼓励探索。

在第L步，当遍历到达了叶子节点$s_L$sL​时，叶子节点可能需要expanded（即搜索树内没有遇到过当前(s,a)）。叶子位置$s_L$sL​仅由SL策略网络$P_σ$Pσ​处理一次。输出概率被存储为每个合理行为a的先验概率$P$P，$P(s,a)=P_σ(a|s)$P(s,a)=Pσ​(a∣s)。 对叶节点的评估有两种截然不同的方式：

• 首先，通过值网络$V_θ(s_L)$Vθ​(sL​)直接计算；
• 其次，使用快速推出策略$P_π$Pπ​，生成随机rollout直到终止步骤T得到输出$z_L$zL​。 使用混合参数$λ$λ将这些评估合并为叶子节点的评估$V(s_L)$V(sL​)。
  
  在模拟结束时，更新所有遍历边的动作值和访问计数。每个边累积通过该边的所有模拟的访问计数和平均评估：
  
  $s_L^i$sLi​是叶子节点的第i次模拟，1(s,a,i)表示边(s,a)是否在第i次模拟时遍历到。当搜索完成时，算法会从根位置选择访问次数最多的行为。 值得注意的是，SL策略网络$P_σ$Pσ​在AlphaGo中的性能优于更强的RL策略网络$P_ρ$Pρ​，这可能是因为人类选择了多种有希望的移动，而RL优化了单个最佳移动。然而，由更强的RL策略网络导出的值函数$V_θ(s)≈V^{P_ρ}(s)$Vθ​(s)≈VPρ​(s)在AlphaGo中的性能优于由SL策略网络导出的值函数$V_θ(s)≈V^{P_\sigma}(s)$Vθ​(s)≈VPσ​(s)。

Evaluating the playing strength of AlphaGo

4b展示了仅使用价值网络(λ= 0）或仅使用rollouts(λ= 1）评估位置。即使没有使用rollouts，AlphaGo的性能也超过了其他所有Go程序，这表明价值网络为Go中的蒙特卡洛评估提供了可行的选择。 但是，混合评估（λ= 0.5）表现最好，在对抗其他变体的情况下赢得了≥95％的比赛。 这表明这两种位置评估机制是互补的：价值网络近似于强但不切实际的慢pρ的游戏的结果，而rollouts可以准确地评分和评估弱但快的推出政策pπ的游戏的结果 。 图5可视化了AlphaGo对真实游戏位置的评估。

METHODS

Problem setting.

本文方法所解决的问题：Two-player，zero-sum，deterministic state transitions，zero reward except at a terminal time step T，discrete。

从当前玩家在时间步t的角度来看，游戏的结果$z_t=±r(s_T)$zt​=±r(sT​)是游戏结束时的最终奖励。 策略$P(a | s)$P(a∣s)是合理行为$a∈A(s)$a∈A(s)上的概率分布。如果根据策略$P$P选择了两个参与者的所有行动，则价值函数是预期的结果，即：

零和游戏具有唯一的最优值函数$V^*(s)$V∗(s)，该函数确定两个玩家完美玩法后的状态$s$s的outcome：

(当前状态下的最优策略应是使得对方下一步的状态价值最小，所以带负号)