Introduction

完全信息博弈
有完全信息博弈都有一个最优估值函数V*(s)，它在判断了每个棋局或状态 s 之后的博弈结果的优劣（在所有对手完美发挥的情况下）。解决这些博弈可以通过在搜索树中递归调用最优估值函数，这个搜索树包含大约 b^d 种可能的下棋序列，其中 b 是博弈的广度（每一次下棋时候的合法落子个数）d 是的深度（博弈的步数长度）。

为了减少搜索的计算代价，第一，搜索的深度可以通过棋局评估降低：在状态 s 时对搜索树进行剪枝，然后用一个近似估值函数v(s)≈v^∗(s) 取代状态 s 下面的子树，这个近似估值函数预测状态 s 之后的对弈结果。第二，搜索的广度可以通过来自策略 p(a∣s) 的采样动作来降低，这个策略是一个在位置 s 的可能下棋走子a 概率分布。

蒙特卡洛树搜索
蒙特卡洛树搜索使用蒙特卡洛走子方法，评估搜索树中每一个状态的估值。随着执行越来越多的模拟，这个搜索树成长越来越大，而且相关估值愈发精确。用来选择下棋动作的策略在搜索的过程中也会随着时间的推移而改进，通过选择拥有更高估值的子树。渐近的，这个策略收敛到一个最优下法，然后评估收敛到最优估值函数。

更详细介绍
蒙特卡洛树搜索简介与实现

深度卷积神经网络
深度卷积神经网络已经在计算机视觉中达到了空前的性能：比如图像分类，人脸识别，和玩雅达利的游戏。它们使用很多层的神经网络，层与层之间像瓦片重叠排列在一起，用来构建图片的愈发抽象的局部代表。我们为围棋程序部署了类似的体系架构。我们给程序传入了一个19*19大小棋局的图片，然后使用卷积神经网络来构建一个位置的代表。我们使用这些神经网络来降低搜索树的有效的深度和广度：通过估值网络来评估棋局，和使用策略网络来博弈取样。

整体架构
我们用一种由机器学习若干阶段组成的管道来训练这些神经网络（图1）。开始阶段，我们直接使用人类高手的落子弈法训练一种有监督学习（SL）型走棋策略网络pσ。此阶段提供快速、高效的带有即时反馈和高品质梯度的机器学习更新数据。类似以前的做法13，15，我们也训练了一个快速走棋策略pπ，能对走子时的弈法快速采样。接下来的阶段，我们训练一种强化学习（RL）型的走棋策略网络pρ，通过优化那些自我博弈的最终结果，来提高前面的SL策略网络。此阶段是将该策略调校到赢取比赛的正确目标上，而非最大程度的预测准确性。最后阶段，我们训练一种估值网络Vθ，来预测那些采用RL走棋策略网络自我博弈的赢家。我们的程序AlphaGo，用MCTS有效结合了策略和估值网络。

Supervised learning of policy networks

训练管道第一阶段，我们按以前的做法用监督学习预测围棋中高手的落子情况13，21–24。此SL策略网络pσ（a|s）在带有权重数组变量σ和整流器非线性特征值数组的卷积层间交替使用。最终的softmax层输出一个所有合法落子情况的概率分布a。此策略网络的输入变量s是一个棋局状态的简单标识变量（见扩展数据表2）。策略网络基于随机采样的棋盘情形-操作对（s，a）做训练：采用随机梯度升序法，在选定状态s时，取人类落子a的最大相似度，

Reinforcement learning of policy networks

训练管道第二阶段，旨在用策略梯度型增强学习（RL）来提高之前的策略网络25，26。这种RL策略网络pρ在结构上与SL策略网络相同，其权重ρ被初始化为相同值：ρ=σ。我们使其在当前策略网络pρ和某个随机选择的上次迭代产生的策略网络之间进行对弈。这种方法的训练，要用随机化的存有对手稳定态的数据池，来防止对当前策略的过度拟合。我们使用报酬函数r（s），对所有非终端时间步长t<T时，赋值为0。其结果值zt = ± r（sT）是博弈结束时的终端奖励：按照当前博弈者在时间步长t时的预期，给胜方+1、败方−1。权重在每一次步长变量t时，按照预期结果最大值的方向，进行随机梯度升序更新25。

Reinforcement learning of value networks

最后阶段的训练管道聚焦在对棋局的评估，用一个估值函数vp（s）做估计，给棋局s中两个使用策略p的博弈者预测结果28，29，30。

理想情况下，我们想知道完美博弈v*（s）中的该最优值函数；实践中，我们用值函数代替做估算，作为最强策略用在RL策略网络pρ。我们用带权重数组θ的估值网络vθ（s）对此估值函数做近似。

该神经网络具有一种与此估值函数相似的结构，但输出一个单一预测，而不是一个概率分布。我们用状态-结果对（s， z）回归，训练该估值网络权重，使用随机梯度降序来最小化该预测值vθ（s）和相应结果z间的均方差（MSE）

棋局是紧密相关的，不同处只有一枚棋子，但其回归目标被该完整对弈所共用。为了缓解这个问题，我们生成了一个新的含有3000万明显不同棋局的自我博弈数据集，其每个采样都来自于某一单独对弈。每一场对弈都是在上述RL策略网络与自身之间进行，直到博弈结束。在该数据集上的训练，采用训练和测试数据集分别可达到0.226和0.234的均方差，这表明最小的过拟合。

Searching with policy and value networks

AlphaGo combines the policy and value networks in an MCTS algorithm
(Fig. 3) that selects actions by lookahead search. Each edge (s, a) of the search tree stores an action value Q(s, a), visit count N(s, a), and prior probability P(s, a). The tree is traversed by simulation (that is, descending the tree in complete games without backup), starting from the root state. At each time step t of each simulation, an action at is selected from state st

so as to maximize action value plus a bonus

that is proportional to the prior probability but decays with repeated visits to encourage exploration. When the traversal reaches a leaf node sL at step L, the leaf node may be expanded. The leaf position sL is processed just once by the SL policy network pσ. The output probabilities are stored as prior probabilities P for each legal action a,

The leaf node is evaluated in two very different ways: first, by the value network vθ(sL); and second, by the outcome zL of a random rollout played out until terminal step T using the fast rollout policy pπ; these evaluations are combined, using a mixing parameter λ, into a leaf evaluation V(sL)

At the end of simulation, the action values and visit counts of all traversed edges are updated. Each edge accumulates the visit count and mean evaluation of all simulations passing through that edge

where sLi is the leaf node from the ith simulation, and 1(s, a, i) indicates whether an edge (s, a) was traversed during the ith simulation. Once the search is complete, the algorithm chooses the most visited move from the root position.