Mastering the game of Go with deep neural networks and tree search
David Silver1 *, Aja Huang1 *, Chris J. Maddison1 , Arthur Guez1 , Laurent Sifre1 , George van den Driessche1 , Julian Schrittwieser1 , Ioannis Antonoglou1 , Veda Panneershelvam1 , Marc Lanctot1 , Sander Dieleman1 , Dominik Grewe1 , John Nham2 , Nal Kalchbrenner1 , Ilya Sutskever2 , Timothy Lillicrap1 , Madeleine Leach1 , Koray Kavukcuoglu1 , Thore Graepel1 & Demis Hassabis1
主要贡献
本文针对围棋游戏的巨大搜索空间和棋盘位置评估难度，提出了一种新的计算机围棋方法，使用“价值网络”评估棋盘位置和“策略网络”选择走法。这些深度神经网络通过从人类专家对局的监督学习和自博弈的强化学习相结合的方式进行训练。在不使用前瞻搜索的情况下，这些神经网络的围棋水平达到了最先进的蒙特卡洛树搜索程序的水平，这些程序模拟了数千次自博弈的随机对局。本文还引入了一种新的搜索算法，将蒙特卡洛模拟与价值和策略网络相结合。使用该搜索算法，程序AlphaGo对其他围棋程序的胜率达到了99.8%，并以5比0击败了人类欧洲围棋冠军。这是计算机程序首次在完整尺寸的围棋游戏中击败人类职业选手，此前认为这一成就至少还需要十年。
所有完美信息游戏都有一个最优价值函数v(s)，它决定了从每个棋盘位置或状态s开始，在所有玩家完美博弈下的游戏结果。这些游戏可以通过在包含大约b^d个可能移动序列的搜索树中递归计算最优价值函数来求解，其中b是游戏的宽度（每个位置的合法移动数），d是其深度（游戏长度）。在大型游戏中，如国际象棋（b≈35，d≈80）【1，Allis, L. V. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Univ. Limburg, Maastricht, The Netherlands, 1994】和尤其是围棋（b≈250，d≈150）【1，Allis, L. V. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Univ. Limburg, Maastricht, The Netherlands, 1994】，穷举搜索不可行【2，van den Herik, H., Uiterwijk, J. W. & van Rijswijck, J. Games solved: now and in the future. Artif. Intell. 134, 277–311, 2002】【3，Schaeffer, J. The games computers (and people) play. Advances in Computers 52, 189–266, 2000】，但可以通过两个通用原则减少有效搜索空间。首先，通过位置评估减少搜索深度：在状态s处截断搜索树，并用近似价值函数v(s)≈v(s)替换s下面的子树，该函数预测从状态s开始的结果。这种方法在国际象棋【4，Campbell, M., Hoane, A. & Hsu, F. Deep Blue. Artif. Intell. 134, 57–83, 2002】、跳棋【5，Schaeffer, J. et al. A world championship caliber checkers program. Artif. Intell. 53, 273–289, 1992】和黑白棋【6，Buro, M. From simple features to sophisticated evaluation functions. In 1st International Conference on Computers and Games, 126–145, 1999】中取得了超人表现，但由于围棋的复杂性，被认为在围棋中不可行【7，Müller, M. Computer Go. Artif. Intell. 134, 145–179, 2002】。其次，通过从策略p(a|s)采样动作来减少搜索宽度，该策略是位置s中可能移动a的概率分布。例如，蒙特卡洛 rollout【8，Tesauro, G. & Galperin, G. On-line policy improvement using Monte-Carlo search. In Advances in Neural Information Processing, 1068–1074, 1996】通过从策略p采样双方玩家的长序列动作，完全不分支地搜索到最大深度。通过平均这些 rollout 可以提供有效的立场评估，在十五子游戏【8，Tesauro, G. & Galperin, G. On-line policy improvement using Monte-Carlo search. In Advances in Neural Information Processing, 1068–1074, 1996】和Scrabble【9，Sheppard, B. World-championship-caliber Scrabble. Artif. Intell. 134, 241–275, 2002】中取得了超人表现，在围棋中达到了弱业余水平【10，Bouzy, B. & Helmstetter, B. Monte-Carlo Go developments. In 10th International Conference on Advances in Computer Games, 159–174, 2003】。
蒙特卡洛树搜索（MCTS）【11，Coulom, R. Efficient selectivity and backup operators in Monte-Carlo tree search. In 5th International Conference on Computers and Games, 72–83, 2006】【12，Kocsis, L. & Szepesvári, C. Bandit based Monte-Carlo planning. In 15th European Conference on Machine Learning, 282–293, 2006】使用蒙特卡洛 rollout 来估计搜索树中每个状态的价值。随着执行更多模拟，搜索树变得更大，相关价值变得更准确。用于在搜索中选择动作的策略也随着时间改进，通过选择更高价值的子节点。渐近地，这个策略收敛到最优博弈，评估收敛到最优价值函数【12，Kocsis, L. & Szepesvári, C. Bandit based Monte-Carlo planning. In 15th European Conference on Machine Learning, 282–293, 2006】。当前最强的围棋程序基于MCTS，并通过训练预测人类专家移动的策略进行增强【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】。这些策略用于将搜索缩小到高概率动作的束，并在 rollout 中采样动作。这种方法达到了强业余水平【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】【14，Baudiš, P. & Gailly, J.-L. Pachi: State of the art open source Go program. In Advances in Computer Games, 24–38, Springer, 2012】【15，Müller, M., Enzenberger, M., Arneson, B. & Segal, R. Fuego – an open-source framework for board games and Go engine based on Monte-Carlo tree search. IEEE Trans. Comput. Intell. AI in Games 2, 259–270, 2010】。然而，先前工作局限于浅层策略【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】【14，Baudiš, P. & Gailly, J.-L. Pachi: State of the art open source Go program. In Advances in Computer Games, 24–38, Springer, 2012】【15，Müller, M., Enzenberger, M., Arneson, B. & Segal, R. Fuego – an open-source framework for board games and Go engine based on Monte-Carlo tree search. IEEE Trans. Comput. Intell. AI in Games 2, 259–270, 2010】或基于输入特征线性组合的价值函数【16，Gelly, S. & Silver, D. Combining online and offline learning in UCT. In 17th International Conference on Machine Learning, 273–280, 2007】。
最近，深度卷积神经网络在视觉领域取得了前所未有的表现：例如图像分类【17，Krizhevsky, A., Sutskever, I. & Hinton, G. ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, 1097–1105, 2012】、人脸识别【18，Lawrence, S., Giles, C. L., Tsoi, A. C. & Back, A. D. Face recognition: a convolutional neural-network approach. IEEE Trans. Neural Netw. 8, 98–113, 1997】和玩Atari游戏【19，Mnih, V. et al. Human-level control through deep reinforcement learning. Nature 518, 529–533, 2015】。它们使用多层神经元，每层排列成重叠的瓦片，来构建图像的越来越抽象、局部化的表示【20，LeCun, Y., Bengio, Y. & Hinton, G. Deep learning. Nature 521, 436–444, 2015】。本文在围棋游戏中采用了类似的架构。我们将棋盘位置作为19×19图像传入，并使用卷积层构建位置表示。我们使用这些神经网络来减少搜索树的有效深度和宽度：使用价值网络评估位置，使用策略网络采样动作。
我们使用由几个机器学习阶段组成的管道训练神经网络（图1）。我们首先从专家人类移动直接训练监督学习（SL）策略网络pσ。这提供了快速、高效的学习更新，具有即时反馈和高品质梯度。类似于先前工作【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】【15，Müller, M., Enzenberger, M., Arneson, B. & Segal, R. Fuego – an open-source framework for board games and Go engine based on Monte-Carlo tree search. IEEE Trans. Comput. Intell. AI in Games 2, 259–270, 2010】，我们还训练了一个快速策略pπ，可以在 rollout 中快速采样动作。接下来，我们训练强化学习（RL）策略网络pρ，通过优化自博弈游戏的最终结果来改进SL策略网络。这将策略调整到赢得游戏的正确目标，而不是最大化预测准确性。最后，我们训练价值网络vθ，预测由RL策略网络与自身对弈的游戏的获胜者。我们的程序AlphaGo高效地将策略和价值网络与MCTS相结合。
背景知识/关键Observation/设计原则
训练管道和架构：快速 rollout 策略 pπ 和监督学习 (SL) 策略网络 pσ 被训练来预测位置数据集中的人类专家移动。强化学习 (RL) 策略网络 pρ 被初始化为 SL 策略网络，然后通过策略梯度学习改进，以最大化对先前版本策略网络的结果（即赢得更多游戏）。通过使用 RL 策略网络进行自博弈游戏生成新数据集。最后，通过回归训练价值网络 vθ 来预测自博弈数据集中的预期结果（即当前玩家是否获胜）。
神经网络架构的示意图表示用于 AlphaGo 的神经网络架构。策略网络将棋盘位置 s 的表示作为输入，通过许多具有参数 σ (SL 策略网络) 或 ρ (RL 策略网络) 的卷积层，并输出合法移动 a 的概率分布 pσ(a|s) 或 pρ(a|s)，表示为棋盘上的概率图。价值网络类似地使用许多具有参数 θ 的卷积层，但输出标量值 vθ(s′)，预测位置 s′ 中的预期结果。
图1 | 神经网络训练管道和架构。a, 快速 rollout 策略 pπ 和监督学习 (SL) 策略网络 pσ 被训练来预测位置数据集中的人类专家移动。强化学习 (RL) 策略网络 pρ 被初始化为 SL 策略网络，然后通过策略梯度学习改进，以最大化对先前版本策略网络的结果（即赢得更多游戏）。通过使用 RL 策略网络进行自博弈游戏生成新数据集。最后，通过回归训练价值网络 vθ 来预测自博弈数据集中的预期结果（即当前玩家是否获胜）。b, 用于 AlphaGo 的神经网络架构的示意图表示。策略网络将棋盘位置 s 的表示作为输入，通过许多具有参数 σ (SL 策略网络) 或 ρ (RL 策略网络) 的卷积层，并输出合法移动 a 的概率分布 pσ(a|s) 或 pρ(a|s)，表示为棋盘上的概率图。价值网络类似地使用许多具有参数 θ 的卷积层，但输出标量值 vθ(s′)，预测位置 s′ 中的预期结果。
策略和价值网络的强度和准确性：图显示了策略网络的博弈强度作为其训练准确性的函数。每层具有128、192、256和384个卷积滤波器的策略网络在训练期间定期评估；图显示了使用该策略网络的AlphaGo对AlphaGo匹配版本的胜率。价值网络与不同策略的 rollout 之间的评估准确性比较。
从人类专家游戏中采样位置和结果。每个位置由价值网络 vθ 的单个前向传递评估，或由使用均匀随机 rollout、快速 rollout 策略 pπ、SL 策略网络 pσ 或 RL 策略网络 pρ 进行的100次 rollout 的平均结果评估。预测价值与实际游戏结果之间的均方误差绘制为游戏阶段的函数（给定位置中已走多少步）。
图2 | 策略和价值网络的强度和准确性。a, 图显示了策略网络的博弈强度作为其训练准确性的函数。每层具有128、192、256和384个卷积滤波器的策略网络在训练期间定期评估；图显示了使用该策略网络的AlphaGo对AlphaGo匹配版本的胜率。b, 价值网络与不同策略的 rollout 之间的评估准确性比较。
从人类专家游戏中采样位置和结果。每个位置由价值网络 vθ 的单个前向传递评估，或由使用均匀随机 rollout、快速 rollout 策略 pπ、SL 策略网络 pσ 或 RL 策略网络 pρ 进行的100次 rollout 的平均结果评估。预测价值与实际游戏结果之间的均方误差绘制为游戏阶段的函数（给定位置中已走多少步）。
图3 | AlphaGo中的蒙特卡洛树搜索。a, 每个模拟通过选择具有最大动作价值Q加上依赖于该边存储先验概率P的奖金u(P)的边来遍历树。b, 叶节点可以扩展；新节点由策略网络pσ处理一次，输出概率存储为每个动作的先验概率P。c, 在模拟结束时，叶节点以两种方式评估：使用价值网络vθ；并通过使用快速 rollout 策略pπ 运行到游戏结束的 rollout，然后使用函数r计算获胜者。d, 动作价值Q更新为跟踪该动作下面子树中所有评估r(·)和vθ(·)的平均价值。
方法细节
监督学习策略网络：在训练管道的第一阶段，我们基于先前在围棋中预测专家移动的监督学习工作【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】【21，Stern, D., Herbrich, R. & Graepel, T. Bayesian pattern ranking for move prediction in the game of Go. In International Conference of Machine Learning, 873–880, 2006】【22，Sutskever, I. & Nair, V. Mimicking Go experts with convolutional neural networks. In International Conference on Artificial Neural Networks, 101–110, 2008】【23，Maddison, C. J., Huang, A., Sutskever, I. & Silver, D. Move evaluation in Go using deep convolutional neural networks. 3rd International Conference on Learning Representations, 2015】【24，Clark, C. & Storkey, A. J. Training deep convolutional neural networks to play go. In 32nd International Conference on Machine Learning, 1766–1774, 2015】构建。SL策略网络pσ(a|s) 在具有权重σ的卷积层和整流器非线性之间交替。最终的softmax层输出所有合法移动a的概率分布。策略网络的输入s是棋盘状态的简单表示（见扩展数据表2）。策略网络在随机采样的状态-动作对(s, a)上训练，使用随机梯度上升最大化状态s中人类选择的移动a的似然。
我们从KGS围棋服务器的3000万个位置训练了一个13层策略网络，我们称之为SL策略网络。使用所有输入特征，该网络在保留测试集上预测专家移动的准确率为57.0%，仅使用原始棋盘位置和移动历史作为输入时为55.7%，相比其他研究组的最先进水平44.4%（提交日期）【24，Clark, C. & Storkey, A. J. Training deep convolutional neural networks to play go. In 32nd International Conference on Machine Learning, 1766–1774, 2015】（完整结果见扩展数据表3）。准确性的小改进导致博弈强度的巨大改进（图2a）；更大的网络实现了更好的准确性，但搜索期间评估更慢。我们还训练了一个更快但准确性较低的 rollout 策略 pπ(a|s)，使用小模式特征的线性softmax（见扩展数据表4），权重为π；这达到了24.2%的准确性，使用2 μs选择一个动作，而不是策略网络的3 ms。
强化学习策略网络：训练管道的第二阶段旨在通过策略梯度强化学习（RL）【25，Williams, R. J. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8, 229–256, 1992】【26，Sutton, R., McAllester, D., Singh, S. & Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, 1057–1063, 2000】改进策略网络。RL策略网络pρ在结构上与SL策略网络相同，其权重ρ初始化为相同值，ρ=σ。我们在当前策略网络pρ和随机选择的先前迭代策略网络之间进行游戏。从对手池中随机化以防止过拟合当前策略，从而稳定训练。我们使用奖励函数r(s)，对于所有非终端时间步t<T为零。从时间步t当前玩家的视角，游戏结束时的终端奖励z=±r(s)是+1为获胜，-1为失败。然后，在每个时间步t通过随机梯度上升更新权重，朝着最大化预期结果的方向【25，Williams, R. J. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8, 229–256, 1992】。
我们评估了RL策略网络在游戏中的表现，从其输出动作概率分布采样每个移动a~p(·|s)。在对决中，RL策略网络对SL策略网络赢得了80%以上的游戏。我们还对最强的开源围棋程序Pachi【14，Baudiš, P. & Gailly, J.-L. Pachi: State of the art open source Go program. In Advances in Computer Games, 24–38, Springer, 2012】进行了测试，这是一个复杂的蒙特卡洛搜索程序，在KGS上排名2业余段位，每步执行100,000次模拟。不使用任何搜索，RL策略网络对Pachi赢得了85%的游戏。相比之下，先前基于仅监督学习卷积网络的最先进水平，对Pachi赢得了11%的游戏【23，Maddison, C. J., Huang, A., Sutskever, I. & Silver, D. Move evaluation in Go using deep convolutional neural networks. 3rd International Conference on Learning Representations, 2015】，对稍弱的程序Fuego赢得了12%【24，Clark, C. & Storkey, A. J. Training deep convolutional neural networks to play go. In 32nd International Conference on Machine Learning, 1766–1774, 2015】。
强化学习价值网络：训练管道的最终阶段专注于位置评估，估计价值函数vp(s)，它预测使用策略p的双方玩家从位置s开始的游戏结果【28，Schraudolph, N. N., Dayan, P. & Sejnowski, T. J. Temporal difference learning of position evaluation in the game of Go. Adv. Neural Inf. Process. Syst. 6, 817–824, 1994】【29，Enzenberger, M. Evaluation in Go by a neural network using soft segmentation. In 10th Advances in Computer Games Conference, 97–108, 2003】【30，Silver, D., Sutton, R. & Müller, M. Temporal-difference search in computer Go. Mach. Learn. 87, 183–219, 2012】。理想情况下，我们希望知道完美博弈下的最优价值函数v(s)；在实践中，我们反而估计我们最强策略的价值函数vρp，使用RL策略网络pρ。我们使用具有权重θ的价值网络vθ(s)近似价值函数，vθ(s)≈vρp(s)≈v(s)。这个神经网络的架构类似于策略网络，但输出单个预测而不是概率分布。我们通过状态-结果对(s, z)的回归训练价值网络的权重，使用随机梯度下降最小化预测价值vθ(s)和相应结果z之间的均方误差 (MSE)。
从完整游戏的数据预测游戏结果的朴素方法会导致过拟合。问题是连续位置高度相关，仅相差一子，但回归目标在整个游戏中共享。以这种方式在KGS数据集上训练时，价值网络记忆了游戏结果而不是泛化到新位置，在测试集上达到了0.37的最小MSE，相比训练集的0.19。为了缓解这个问题，我们生成了一个新的自博弈数据集，包含3000万个独特位置，每个从单独游戏中采样。每个游戏在RL策略网络与自身之间进行，直到游戏终止。在这个数据集上训练导致训练集和测试集的MSE分别为0.226和0.234，表示最小过拟合。图2b显示了价值网络的位置评估准确性，与使用快速 rollout 策略pπ的蒙特卡洛 rollout 相比；价值函数始终更准确。vθ(s)的单个评估也接近了使用RL策略网络pρ的蒙特卡洛 rollout 的准确性，但计算量少了15,000倍。
使用策略和价值网络搜索：AlphaGo在MCTS算法中结合策略和价值网络（图3），通过前瞻搜索选择动作。搜索树的每个边(s, a)存储动作价值Q(s, a)、访问计数N(s, a)和先验概率P(s, a)。树通过模拟遍历（即在完整游戏中下降树而不备份），从根状态开始。在每个模拟的时间步t，一个动作at从状态st中选择，以最大化动作价值加上奖金。
理想情况下，我们希望知道完美博弈下的最优价值函数v(s)；在实践中，我们反而估计我们最强策略的价值函数vρp，使用RL策略网络pρ。我们使用具有权重θ的价值网络vθ(s)近似价值函数，vθ(s)≈vρp(s)≈v(s)。这个神经网络的架构类似于策略网络，但输出单个预测而不是概率分布。我们通过状态-结果对(s, z)的回归训练价值网络的权重，使用随机梯度下降最小化预测价值vθ(s)和相应结果z之间的均方误差 (MSE)。
当遍历到达叶节点s在步L时，叶节点可以扩展。叶位置sL仅由SL策略网络pσ处理一次。输出概率存储为每个合法动作a的先验概率P(s, a)=p(a|s)。叶节点以两种非常不同的方式评估：首先，由价值网络vθ(s)；其次，由使用快速 rollout 策略pπ直到终端步T进行的随机 rollout 的结果z；这些评估使用混合参数λ组合成叶评估V(sL)。
在模拟结束时，所有遍历边的动作价值和访问计数更新。每个边累积通过该边的所有模拟的访问计数和平均评估，其中si是第i次模拟的叶节点，1(s, a, i)表示边(s, a)是否在第i次模拟中遍历。一旦搜索完成，算法从根位置选择访问最多的移动。
值得注意的是，SL策略网络pσ在AlphaGo中的表现优于更强的RL策略网络pρ，可能因为人类选择多样化的有前景移动束，而RL优化单个最佳移动。然而，从更强的RL策略网络导出的价值函数vθ(s)≈vρp(s)在AlphaGo中的表现优于从SL策略网络导出的价值函数vθ(s)≈vσp(s)。
评估策略和价值网络需要比传统搜索启发式多几个数量级的计算。为了高效地将大型神经网络集成到AlphaGo中，我们实现了异步多线程搜索，在CPU上执行模拟，并在GPU上并行计算策略和价值网络。AlphaGo的最终版本使用了40个搜索线程、48个CPU和8个GPU。我们还实现了AlphaGo的分布式版本，利用多个机器、40个搜索线程、1202个CPU和176个GPU。方法部分提供了异步和分布式MCTS的完整细节。
以最大化动作价值加上奖金。
奖金与先验概率成比例，但随着重复访问衰减以鼓励探索。当遍历到达叶节点s在步L时，叶节点可以扩展。叶位置sL仅由SL策略网络pσ处理一次。输出概率存储为每个合法动作a的先验概率P(s, a)=p(a|s)。叶节点以两种非常不同的方式评估：首先，由价值网络vθ(s)；其次，由使用快速 rollout 策略pπ直到终端步T进行的随机 rollout 的结果z；这些评估使用混合参数λ组合成叶评估V(sL)。
在模拟结束时，所有遍历边的动作价值和访问计数更新。每个边累积通过该边的所有模拟的访问计数和平均评估。
其中si是第i次模拟的叶节点，1(s, a, i)表示边(s, a)是否在第i次模拟中遍历。一旦搜索完成，算法从根位置选择访问最多的移动。
值得注意的是，SL策略网络pσ在AlphaGo中的表现优于更强的RL策略网络pρ，可能因为人类选择多样化的有前景移动束，而RL优化单个最佳移动。然而，从更强的RL策略网络导出的价值函数vθ(s)≈vρp(s)在AlphaGo中的表现优于从SL策略网络导出的价值函数vθ(s)≈vσp(s)。
图4 | AlphaGo锦标赛评估。a, 不同围棋程序之间锦标赛的结果（见扩展数据表6–11）。每个程序每步使用大约5 s计算时间。为了给AlphaGo更大的挑战，一些程序（浅色上条）对所有对手给予四个让子（即游戏开始时的免费移动）。程序在Elo量表上评估：230点差距对应79%的胜率，这大致对应KGS上的一个业余段位优势；还显示了对人类段位的近似对应，水平线显示该程序在线上达到的KGS段位。还包括了对人类欧洲冠军樊麾的游戏；这些游戏使用了更长的时限控制。显示95%置信区间。b, AlphaGo在单一机器上不同组件组合的表现。仅使用策略网络的版本不执行任何搜索。c, AlphaGo中MCTS的可扩展性研究，使用搜索线程和GPU，进行异步搜索（浅蓝）或分布式搜索（深蓝），每步2 s。
图5 | AlphaGo（黑方，下一步）在一场非正式游戏中对樊麾如何选择其移动。对于以下每个统计，最大值的位置由橙色圆圈表示。a, 使用价值网络vθ(s′)评估根位置s的所有后继s′；显示顶级评估的估计胜率百分比。b, 树中从根位置s的每个边(s, a)的动作价值Q(s, a)；仅平均价值网络评估(λ=0)。c, 动作价值Q(s, a)，仅平均 rollout 评估(λ=1)。d, 直接来自SL策略网络的移动概率p(a|s)；报告为百分比（如果高于0.1%）。e, 模拟期间从根选择的动作的百分比频率。f, AlphaGo搜索树的主要变体（访问计数最大路径）。移动以编号序列呈现。AlphaGo选择了红圈指示的移动；樊麾以白方方块指示的移动回应；在赛后评论中，他更喜欢AlphaGo预测的移动（标记为1）。
第3局 樊麾（黑方），AlphaGo（白方） AlphaGo 以弃权获胜
图6 | AlphaGo与欧洲冠军樊麾比赛中的游戏。移动以编号序列显示，对应玩的顺序。同一交点的重复移动在棋盘下方以对显示。第一对中的移动编号表示重复移动何时玩，在由第二个移动编号标识的交点（见补充信息）。
方法：
问题设置：许多完美信息游戏，如国际象棋、跳棋、黑白棋、十五子游戏和围棋，可以定义为交替马尔可夫游戏【39】。在这些游戏中，有状态空间S（状态包括当前玩家的指示）；动作空间A(s)定义给定状态s∈S中的合法动作；状态转移函数f(s, a, ξ)定义在状态s选择动作a后的后继状态和随机输入ξ（例如骰子）；以及奖励函数ri(s)描述玩家i在状态s收到的奖励。我们限制关注两人零和游戏，r1(s)=-r2(s)=r(s)，具有确定性状态转移f(s, a, ξ)=f(s, a)，除终端时间步T外奖励为零。从时间步t当前玩家的视角，游戏结束时的结果zt=±r(sT)是终端奖励。策略p(a|s)是合法动作a∈A(s)的概率分布。价值函数是如果所有玩家的所有动作根据策略p选择时的预期结果，即vp(s)=E[zt|st=s, a_t...T ~ p]。零和游戏有唯一的最优价值函数v(s)，它决定了双方完美博弈下从状态s的结果。
先前工作：最优价值函数可以通过minimax（或等价negamax）搜索递归计算【40】。大多数游戏太大，无法穷举minimax树搜索；相反，游戏通过使用近似价值函数v(s)≈v(s)代替终端奖励来截断。带有alpha-beta剪枝的深度优先minimax搜索在国际象棋【4，Campbell, M., Hoane, A. & Hsu, F. Deep Blue. Artif. Intell. 134, 57–83, 2002】、跳棋【5，Schaeffer, J. et al. A world championship caliber checkers program. Artif. Intell. 53, 273–289, 1992】和黑白棋【6，Buro, M. From simple features to sophisticated evaluation functions. In 1st International Conference on Computers and Games, 126–145, 1999】中取得了超人表现，但它在围棋中无效【7，Müller, M. Computer Go. Artif. Intell. 134, 145–179, 2002】。
强化学习可以直接从自博弈游戏中学习近似最优价值函数【39】。大多数先前工作聚焦于特征ϕ(s)与权重θ的线性组合vθ(s)=ϕ(s)·θ。权重使用时间差学习在国际象棋【42】【43】、跳棋【44】【45】和围棋【30，Silver, D., Sutton, R. & Müller, M. Temporal-difference search in computer Go. Mach. Learn. 87, 183–219, 2012】中训练；或使用线性回归在黑白棋【6，Buro, M. From simple features to sophisticated evaluation functions. In 1st International Conference on Computers and Games, 126–145, 1999】和Scrabble【9，Sheppard, B. World-championship-caliber Scrabble. Artif. Intell. 134, 241–275, 2002】中训练。时间差学习还用于训练神经网络近似最优价值函数，在十五子游戏中达到了超人表现【46】；并在小棋盘围棋中达到了弱kyu水平【28，Schraudolph, N. N., Dayan, P. & Sejnowski, T. J. Temporal difference learning of position evaluation in the game of Go. Adv. Neural Inf. Process. Syst. 6, 817–824, 1994】【29，Enzenberger, M. Evaluation in Go by a neural network using soft segmentation. In 10th Advances in Computer Games Conference, 97–108, 2003】【47】使用卷积网络。
minimax搜索的替代是蒙特卡洛树搜索 (MCTS)【11，Coulom, R. Efficient selectivity and backup operators in Monte-Carlo tree search. In 5th International Conference on Computers and Games, 72–83, 2006】【12，Kocsis, L. & Szepesvári, C. Bandit based Monte-Carlo planning. In 15th European Conference on Machine Learning, 282–293, 2006】，它通过双重近似V(s)≈vnPn(s)≈v(s)估计内部节点的最优价值。第一近似V(s)≈vnPn(s)使用n次蒙特卡洛模拟估计模拟策略Pn的价值函数。第二近似v(s)≈vnPn(s)使用模拟策略Pn代替minimax最优动作。模拟策略根据搜索控制函数 argmax_a (Qn(s, a) + u(s, a)) 选择动作，如UCT【12，Kocsis, L. & Szepesvári, C. Bandit based Monte-Carlo planning. In 15th European Conference on Machine Learning, 282–293, 2006】，它选择更高动作价值Qn(s, a)=-Vn(f(s, a))的孩子，加上鼓励探索的奖金u(s, a)；或在状态s没有搜索树时，从快速 rollout 策略 p(a|s) 采样动作。随着执行更多模拟和搜索树变深，模拟策略由越来越准确的统计信息告知。在极限下，两个近似都变得精确，MCTS（例如UCT）收敛到最优价值函数【12，Kocsis, L. & Szepesvári, C. Bandit based Monte-Carlo planning. In 15th European Conference on Machine Learning, 282–293, 2006】。当前最强的围棋程序基于MCTS【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】【14，Baudiš, P. & Gailly, J.-L. Pachi: State of the art open source Go program. In Advances in Computer Games, 24–38, Springer, 2012】【15，Müller, M., Enzenberger, M., Arneson, B. & Segal, R. Fuego – an open-source framework for board games and Go engine based on Monte-Carlo tree search. IEEE Trans. Comput. Intell. AI in Games 2, 259–270, 2010】【36，Gelly, S. et al. The grand challenge of computer Go: Monte Carlo tree search and extensions. Commun. ACM 55, 106–113, 2012】。
MCTS先前与用于缩小搜索树到高概率移动的策略结合【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】；或将奖金项偏向高概率移动【48】。MCTS还与用于初始化新扩展节点中动作价值的价值函数结合【16，Gelly, S. & Silver, D. Combining online and offline learning in UCT. In 17th International Conference on Machine Learning, 273–280, 2007】，或混合蒙特卡洛评估与minimax评估【49】。相比之下，AlphaGo对价值函数的使用基于截断蒙特卡洛搜索算法【8，Tesauro, G. & Galperin, G. On-line policy improvement using Monte-Carlo search. In Advances in Neural Information Processing, 1068–1074, 1996】【9，Sheppard, B. World-championship-caliber Scrabble. Artif. Intell. 134, 241–275, 2002】，这些算法在游戏结束前终止 rollout 并使用价值函数代替终端奖励。AlphaGo的位置评估混合完整 rollout 和截断 rollout，在某些方面类似于著名的时差学习算法TD(λ)。AlphaGo还不同于先前工作，使用更慢但更强大的策略和价值函数表示；评估深度神经网络比线性表示慢几个数量级，因此必须异步发生。
MCTS的表现在很大程度上由 rollout 策略的质量决定。先前工作聚焦于手工模式【50】或通过监督学习【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】、强化学习【16，Gelly, S. & Silver, D. Combining online and offline learning in UCT. In 17th International Conference on Machine Learning, 273–280, 2007】、模拟平衡【51】【52】或在线适应【30，Silver, D., Sutton, R. & Müller, M. Temporal-difference search in computer Go. Mach. Learn. 87, 183–219, 2012】【53】学习 rollout 策略；然而，已知基于 rollout 的位置评估经常不准确【54】。AlphaGo使用相对简单的 rollout，而是更直接地使用价值网络解决具有挑战的位置评估问题。
搜索算法：为了高效地将大型神经网络集成到AlphaGo中，我们实现了异步策略和价值MCTS算法 (APV-MCTS)。搜索树中的每个节点s包含所有合法动作a∈A(s)的边(s, a)。每个边存储一组统计，P(s, a)是先验概率，Wv(s, a)和Wr(s, a)是累积Nv(s, a)和Nr(s, a)叶评估和 rollout 奖励的蒙特卡洛总动作价值估计，Q(s, a)是该边的组合平均动作价值。在单独的搜索线程上并行执行多个模拟。APV-MCTS算法在图3概述的四个阶段进行。
- 选择 (图3a)：每个模拟的树内阶段从搜索树的根开始，当模拟到达叶节点时结束。在每个时间步 t < L，一个动作根据搜索树中的统计选择，使用PUCT算法的变体 a_t = argmax_a (Q(s_t, a) + u(s_t, a))，其中 u(s, a) = c_puct P(s, a) / (1 + N(s, a))，c_puct是确定探索水平的常数；这个搜索控制策略最初偏好高先验概率和低访问计数的动作，但渐近偏好高动作价值的动作。
- 评估 (图3c)：叶位置sL添加到价值网络评估vθ(sL)的队列中，除非它先前已被评估。每个模拟的第二 rollout 阶段从叶节点s开始，继续到游戏结束。在每个时间步 t ≥ L，双方玩家根据 rollout 策略 a ~ pπ(·|s) 选择动作。当游戏到达终端状态时，从最终分数计算结果 z_t = ± r(s_T)。
- 备份 (图3d)：在模拟的每个树内步 t ≤ L，rollout 统计更新为好像它输了 n_vl 局游戏，Nr(st, at) ← Nr(st, at) + n_vl；Wr(st, at) ← Wr(st, at) - n_vl；这个虚拟损失【55】阻止其他线程同时探索相同变体。在模拟结束时，通过每个步 t ≤ L 的后向传递更新 rollout 统计，用结果替换虚拟损失，Nr(st, at) ← Nr(st, at) - n_vl + 1；Wr(st, at) ← Wr(st, at) + n_vl + z_t。异步地，当叶位置sL的评估完成时启动单独的后向传递。价值网络的输出vθ(sL)用于在通过每个步 t ≤ L 的第二个后向传递中更新价值统计，Nv(st, at) ← Nv(st, at) + 1，Wv(st, at) ← Wv(st, at) + vθ(sL)。每个状态动作的整体评估是蒙特卡洛估计的加权平均 Q(s, a) = (1-λ) Wv(s, a)/Nv(s, a) + λ Wr(s, a)/Nr(s, a)，它使用权重参数λ混合价值网络和 rollout 评估。所有更新无锁执行【56】。
- 扩展 (图3b)：当访问计数超过阈值 Nr(s, a) > n_thr 时，后继状态 s' = f(s, a) 添加到搜索树。新节点初始化为 {N(s', a)=Nr(s', a)=0, W(s', a)=Wr(s', a)=0, P(s',a)=pτ(a|s')}，使用树策略 pτ(a|s') （类似于 rollout 策略但有更多特征，见扩展数据表4）提供动作选择的占位符先验概率。位置 s' 也插入异步GPU评估的策略网络队列。先验概率由SL策略网络 (β p(·|s')) 计算，softmax温度设置为β；这些替换占位符先验概率，P(s', a) ← β p(a|s')，使用原子更新。阈值 n_thr 动态调整，以确保位置添加到策略队列的速率匹配GPU评估策略网络的速率。位置使用 mini-batch 大小1由策略网络和价值网络评估，以最小化端到端评估时间。
我们还实现了分布式APV-MCTS算法。这个架构包括执行主搜索的单个主机器，许多执行异步 rollout 的远程工作者CPU，以及许多执行异步策略和价值网络评估的远程工作者GPU。整个搜索树存储在主机器上，它仅执行每个模拟的树内阶段。叶位置传达给工作者CPU，它们执行模拟的 rollout 阶段，以及工作者GPU，它们计算网络特征并评估策略和价值网络。策略网络的先验概率返回到主机器，在新扩展节点处替换占位符先验概率。来自 rollout 的奖励和价值网络输出各自返回到主机器，并备份到原始搜索路径。
在搜索结束时，AlphaGo选择最大访问计数的动作；这比最大化动作价值对异常值不那么敏感【15，Müller, M., Enzenberger, M., Arneson, B. & Segal, R. Fuego – an open-source framework for board games and Go engine based on Monte-Carlo tree search. IEEE Trans. Comput. Intell. AI in Games 2, 259–270, 2010】。搜索树在后续时间步复用：对应所玩动作的孩子节点成为新根节点；该孩子下面的子树保留所有统计，而树的其余部分丢弃。AlphaGo的匹配版本在对手移动期间继续搜索。如果最大访问计数和最大动作价值的动作不同，它扩展搜索。时限控制否则塑造为在中局使用最多时间【57】。当其整体评估降到估计10%胜率以下时，AlphaGo弃权，即 max_a Q(s_0, a) < -0.8。
AlphaGo不采用大多数蒙特卡洛围棋程序使用的 all-moves-as-first【10，Bouzy, B. & Helmstetter, B. Monte-Carlo Go developments. In 10th International Conference on Advances in Computer Games, 159–174, 2003】或快速动作价值估计【58】启发式；当使用策略网络作为先验知识时，这些偏置启发式似乎不提供额外益处。此外，AlphaGo不使用渐进拓宽【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】、动态komi【59】或开局库【60】。樊麾匹配中AlphaGo使用的参数列在扩展数据表5。
Rollout 策略： rollout 策略 pπ(a|s) 是基于快速、增量计算的局部基于模式的特征的线性softmax策略，包括导致状态s的前一移动周围的“响应”模式，以及状态s中候选移动a周围的“非响应”模式。每个非响应模式是匹配以a为中心的特定3×3模式的二进制特征，由每个相邻交点的颜色（黑、白、空）和自由度计数（1,2,≥3）定义。每个响应模式是匹配前一移动周围12点菱形模式【21，Stern, D., Herbrich, R. & Graepel, T. Bayesian pattern ranking for move prediction in the game of Go. In International Conference of Machine Learning, 873–880, 2006】中颜色和自由度计数的二进制特征。此外，一小部分手工本地特征编码常识围棋规则（见扩展数据表4）。类似于策略网络， rollout 策略的权重π从Tygem服务器上800万个位置训练，通过随机梯度下降最大化对数似然。Rollout 在空棋盘上每CPU线程大约1000次模拟每秒执行。
我们的 rollout 策略 pπ(a|s) 包含比最先进围棋程序【13，Coulom, R. Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208, 2007】更少的手工知识。相反，我们利用MCTS中更高的动作选择质量，由搜索树和策略网络告知。我们引入了一种新技术，缓存搜索树的所有移动，然后在 rollout 期间玩类似移动；“last good reply”启发式的泛化【53，Baier, H. & Drake, P. D. The power of forgetting: improving the last-good-reply policy in Monte Carlo Go. IEEE Trans. Comput. Intell. AI in Games 2, 303–309, 2010】。在树遍历的每一步，最可能的动作插入哈希表，连同前一移动和当前移动周围的3×3模式上下文（颜色、自由度和石头计数）。在 rollout 的每一步，模式上下文与哈希表匹配；如果找到匹配，则以高概率玩存储的移动。
对称性：先前工作通过在卷积层中使用旋转和反射不变滤波器利用围棋的对称性【24，Clark, C. & Storkey, A. J. Training deep convolutional neural networks to play go. In 32nd International Conference on Machine Learning, 1766–1774, 2015】【28，Schraudolph, N. N., Dayan, P. & Sejnowski, T. J. Temporal difference learning of position evaluation in the game of Go. Adv. Neural Inf. Process. Syst. 6, 817–824, 1994】【29，Enzenberger, M. Evaluation in Go by a neural network using soft segmentation. In 10th Advances in Computer Games Conference, 97–108, 2003】。虽然这在小神经网络中有效，但在大网络中实际上损害性能，因为它阻止中间滤波器识别特定不对称模式【23，Maddison, C. J., Huang, A., Sutskever, I. & Silver, D. Move evaluation in Go using deep convolutional neural networks. 3rd International Conference on Learning Representations, 2015】。相反，我们在运行时通过使用八个反射和旋转的二面体群动态变换每个位置s，d1(s), …, d8(s)来利用对称性。在显式对称集成中，所有8个位置的 mini-batch 传入策略网络或价值网络并并行计算。对于价值网络，输出值简单平均 vθ(s) = (1/8) ∑j vθ(dj(s))。对于策略网络，输出概率平面旋转/反射回原始方向，并平均以提供集成预测 pσ(·|s) = (1/8) ∑_j d_j^{-1} (pσ(·|dj(s)))；这种方法用于我们的原始网络评估（见扩展数据表3）。相反，APV-MCTS使用隐式对称集成，为每个评估随机选择单个旋转/反射 j ∈ [1,8]。我们仅为该方向计算一个评估；在每个模拟中，我们通过 vθ(dj(sL)) 计算叶节点sL的价值，并允许搜索过程平均这些评估。类似地，我们为单个随机选择的旋转/反射计算策略网络 d_j^{-1} (pσ(·|dj(s)))。
策略网络：分类：我们训练策略网络 pσ 根据KGS数据集中的专家移动分类位置。这个数据集包含来自160,000局游戏的2940万个位置，由KGS 6到9段人类玩家玩；35.4%的游戏是让子游戏。数据集分为测试集（前100万个位置）和训练集（剩余2840万个位置）。通过移动被排除在数据集外。每个位置由原始棋盘描述s和人类选择的移动a组成。我们将数据集扩充为包括每个位置的所有八个反射和旋转。对称扩充和输入特征为每个位置预计算。对于每个训练步，我们从扩充KGS数据集采样随机选择的 mini-batch m样本，并应用异步随机梯度下降更新以最大化动作的对数似然 Δσ = (α/m) ∑_k ∂ log pσ(a_k | s_k) / ∂σ。步长α初始化为0.003，每8000万训练步减半，无动量项，mini-batch大小 m=16。更新在50个GPU上使用DistBelief【61】异步应用；超过100步的梯度被丢弃。训练大约3周，34000万训练步。
策略网络：强化学习：我们通过策略梯度强化学习进一步训练策略网络【25，Williams, R. J. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8, 229–256, 1992】【26，Sutton, R., McAllester, D., Singh, S. & Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, 1057–1063, 2000】。每个迭代包括并行玩的n局游戏的 mini-batch，在被训练的当前策略网络 pρ 和使用先前迭代参数 ρ- 的对手 p- 之间，从对手池随机采样，以增加训练稳定性。权重初始化为 ρ = ρ- = σ。每500迭代，我们将当前参数 ρ 添加到对手池。每个 mini-batch 中的游戏 i 玩到终止步 Ti，然后从每个玩家的视角评分以确定结果 z_i = ± r(s_i)。然后重放游戏以确定策略梯度更新 Δρ = (α / n) ∑_i ∑_t=1^{T_i} (z_i - v(s) / ∂ρ，使用带有基线 v(s_i) 的REINFORCE算法【25，Williams, R. J. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8, 229–256, 1992】进行方差减少。在训练管道的第一遍，基线设置为零；在第二遍，我们使用价值网络 vθ(s) 作为基线；这提供了小性能提升。策略网络以这种方式训练10,000个128局游戏的 mini-batch，使用50个GPU，一天。})) ∂ log pρ(a_{ti} | s_{ti
价值网络：回归：我们训练价值网络 vθ(s) ≈ vρp(s) 来近似RL策略网络 pρ 的价值函数。为了避免过拟合游戏内高度相关位置，我们构建了一个新的不相关自博弈位置数据集。这个数据集包含超过3000万个位置，每个从独特自博弈游戏中抽取。每个游戏通过随机采样时间步 U ~ unif{1,450} 生成三个阶段，前 t=1,...U-1 步从SL策略网络采样 a_t ~ pσ(·|s_t)；然后从可用移动均匀随机采样一移动 a_U ~ unif{1,361}（重复直到 a_U 合法）；然后从RL策略网络采样剩余移动序列 t=U+1,...T, a_t ~ pρ(·|s_t)。最终，游戏评分以确定结果 z = ± r(s)。每个游戏仅添加单个训练示例 (s_{U+1}, z_{U+1}) 到数据集。这个数据提供价值函数的无偏样本 vρp(s_{U+1}) = E[z_{U+1} | s_{U+1}, a_{U+1}...T ~ pρ]。在生成的前两个阶段，我们从更噪声分布采样以增加数据集多样性。训练方法与SL策略网络训练相同，除了参数更新基于预测值和观察奖励之间的均方误差 Δθ = (α/m) ∑_k (z_k - vθ(s_k)) ∂ vθ(s_k) / ∂θ。价值网络训练5000万个32位置的 mini-batch，使用50个GPU，一周。
策略/价值网络的特征：每个位置s预处理为19×19特征平面的集合。我们使用的特征直接来自游戏规则的原始表示，指示围棋棋盘每个交点的状态：石头颜色、自由度（石头链的相邻空点）、吃子、合法性、石头玩后转数，以及（仅价值网络）当前颜色玩。此外，我们使用一个简单战术特征计算梯子搜索的结果【7，Müller, M. Computer Go. Artif. Intell. 134, 145–179, 2002】。所有特征相对于当前颜色玩表示；例如，每个交点的石头颜色表示为玩家或对手而不是黑或白。每个整数特征值拆分为多个19×19二进制值平面（one-hot编码）。例如，使用单独的二进制特征平面表示交点是否有1自由度、2自由度、...、≥8自由度。完整特征平面集列在扩展数据表2。
神经网络架构：策略网络的输入是19×19×48图像栈，包括48个特征平面。第一隐藏层将输入零填充为23×23图像，然后用步幅1的5×5内核卷积k个滤波器并应用整流器非线性。随后隐藏层2到12将各自先前隐藏层零填充为21×21图像，然后用步幅1的3×3内核卷积k个滤波器，再次跟随整流器非线性。最终层用步幅1的1×1内核卷积1个滤波器，每个位置不同偏置，并应用softmax函数。AlphaGo的匹配版本使用k=192滤波器；图2b和扩展数据表3还显示了使用k=128、256和384滤波器的训练结果。
价值网络的输入也是19×19×48图像栈，具有描述当前颜色玩的额外二进制特征平面。隐藏层2到11与策略网络相同，隐藏层12是额外卷积层，隐藏层13用步幅1的1×1内核卷积1个滤波器，隐藏层14是具有256整流器单元的全连接线性层。输出层是具有单个tanh单元的全连接线性层。
评估：我们通过运行内部锦标赛并测量每个程序的Elo评级评估计算机围棋程序的相对强度。我们通过逻辑函数 p(a beats b) = 1 / (1 + exp(c (e(b) - e(a)))) 估计程序a击败程序b的概率，并通过BayesElo程序使用标准常数 c_elo=1/400 计算贝叶斯逻辑回归估计评级 e(·)【37，Coulom, R. Whole-history rating: A Bayesian rating system for players of time-varying strength. In International Conference on Computers and Games, 113–124, 2008】。量表锚定到专业围棋玩家樊麾的BayesElo评级（提交日期2908）【62】。所有程序每步最多5 s计算时间；游戏使用中国规则，komi 7.5点（补偿白方后手的额外点）。我们还玩了让子游戏，其中AlphaGo玩白方对现有围棋程序；对于这些游戏，我们使用了非标准让子系统，其中保留komi但黑方在通常让子点上给予额外石头。使用这些规则，K个石头的让子等价于给黑方K-1个免费移动，而不是使用标准无komi让子规则的K-1/2个免费移动。我们使用这些让子规则因为AlphaGo的价值网络专门训练使用komi 7.5。
除分布式AlphaGo外，每个计算机围棋程序在其自己的单一机器上执行，具有相同规格，使用最新可用版本和该程序支持的最佳硬件配置（见扩展数据表6）。在图4中，计算机程序的大致段位基于该程序达到的最高KGS段位；然而，KGS版本可能不同于公开可用版本。
对樊麾的比赛由公正裁判仲裁。玩了五局正式游戏和五局非正式游戏，komi 7.5，无让子，中国规则。AlphaGo分别以5-0和3-2获胜（图6和扩展数据表1）。正式游戏时限为1小时主时加三个30秒读秒。非正式游戏时限为三个30秒读秒。时限控制和玩条件由樊麾在比赛前选择；还同意整体比赛结果仅由正式游戏确定。为了大致评估樊麾相对于计算机围棋程序的评级，我们将所有十局游戏的结果附加到我们的内部锦标赛结果，忽略时限控制差异。
实验环境
数据集：KGS围棋服务器数据集，包含来自160,000局游戏的2940万个位置，由KGS 6到9段人类玩家玩；35.4%为让子游戏。用于SL策略网络训练，测试集前100万个位置，训练集剩余2840万个。用于价值网络的自博弈数据集，3000万个独特位置，每个从单独自博弈游戏采样。
模型架构关键参数：策略网络为13层卷积网络，每层192滤波器（匹配版本），输入19×19×48特征平面；价值网络类似但额外层和输出tanh单元。Rollout 策略为线性softmax，使用局部模式特征。
硬件配置：单一机器版本使用48 CPU和8 GPU；分布式版本使用多个机器、1202 CPU和176 GPU。每个程序每步最多5 s计算时间。
软件配置：基于DistBelief的异步随机梯度下降；训练使用50 GPU；语言和库未指定，但涉及深度卷积神经网络和MCTS实现；操作系统未指定。
实验结果
内部锦标赛评估AlphaGo的博弈强度，包括AlphaGo变体和其他围棋程序，如商业程序Crazy Stone和Zen，开源程序Pachi、Fuego和GnuGo。所有程序每步5 s计算时间。结果显示单一机器AlphaGo对其他程序赢得了494/495局（99.8%），分布式版本更强，对单一机器AlphaGo赢77%，对其他程序100%。在让四个子的游戏中，AlphaGo对Crazy Stone、Zen和Pachi分别赢77%、86%和99%（图4a，扩展数据表6-11）。
变体评估使用仅价值网络(λ=0)、仅rollout(λ=1)或混合(λ=0.5)，有/无策略网络。混合评估表现最佳，对其他变体≥95%胜率，显示价值网络和rollout互补（图4b，扩展数据表7）。
可扩展性研究显示使用更多线程/GPU的异步/分布式搜索提升性能，分布式版本在2 s/步时Elo更高（图4c，扩展数据表8-11）。
对樊麾的正式比赛AlphaGo 5-0获胜，非正式3-2（图6，扩展数据表1）。
策略网络准确性：SL网络在测试集57.0%（所有特征），55.7%（仅棋盘和历史），优于先前44.4%；更大网络更好但更慢（图2a，扩展数据表3）。RL网络对SL赢80%，对Pachi无搜索赢85%。
价值网络MSE：自博弈数据集0.226训练/0.234测试，优于KGS过拟合0.37测试。更准确于pπ rollout（图2b）。
图5可视化真实游戏位置评估，显示价值、Q值、策略概率和访问计数如何指导移动选择。
结论
本文开发了一个基于深度神经网络和树搜索结合的围棋程序，达到了最强人类玩家的水平，从而实现了人工智能的“重大挑战”之一。我们首次开发了有效的围棋移动选择和位置评估函数，基于通过监督和强化学习新型结合训练的深度神经网络。我们引入了一种成功结合神经网络评估与蒙特卡洛rollout的新搜索算法。我们的程序AlphaGo将这些组件大规模集成到一个高性能树搜索引擎中。在对樊麾的比赛中，AlphaGo评估的位置比Deep Blue对卡斯帕罗夫的国际象棋比赛少数千倍；通过使用策略网络更智能地选择位置，并使用价值网络更精确地评估它们来补偿——这种方法可能更接近人类下棋方式。而且，虽然Deep Blue依赖手工评估函数，但AlphaGo的神经网络直接从游戏中通过通用监督和强化学习方法训练。围棋在许多方面是人工智能面临困难的典范：具有挑战的决策任务、不可处理的搜索空间，以及如此复杂的 最优解决方案，似乎不可能直接使用策略或价值函数近似。先前计算机围棋的重大突破，MCTS的引入，导致了许多其他领域的相应进步；例如通用游戏玩、经典规划、部分可观察规划、调度和约束满足。通过将树搜索与策略和价值网络结合，AlphaGo终于在围棋中达到了职业水平，为在其他看似不可处理的 人工智能领域实现人类水平表现提供了希望。
附录
扩展数据表1 | AlphaGo与樊麾比赛细节：比赛包括五个正式游戏（较长时限）和五个非正式游戏（较短时限）。时限控制和玩条件由樊麾在比赛前选择。
扩展数据表2 | 神经网络输入特征：策略网络（除最后特征）和价值网络（所有特征）使用的特征平面。
扩展数据表3 | 策略网络监督学习结果：策略网络架构包括卷积层中的128、192或256滤波器；2、4或8对称的显式对称集成；仅使用扩展数据表1中列出的前4、12或20输入特征平面。结果包括KGS数据集上的测试和训练准确性；以及给定策略网络对AlphaGo策略网络的胜率百分比（突出行2）：直接使用策略网络选择移动（raw wins）；或使用AlphaGo搜索选择移动（AlphaGo wins）；以及策略网络单个评估的计算时间。
扩展数据表4 | rollout 和树策略输入特征：rollout 策略（第一组）和树策略（第一和第二组）使用的特征。模式基于石头颜色（黑/白/空）和每个图案交点的自由度（1,2,≥3）。
扩展数据表5 | AlphaGo使用的参数：
扩展数据表6 | 不同围棋程序之间锦标赛结果：每个程序每步最多5 s思考时间；对樊麾的游戏使用方法中描述的更长时限控制。CN4、ZN4和PC4给予4个让子；所有游戏komi 7.5。由BayesElo计算Elo评级。
扩展数据表7 | AlphaGo不同变体之间锦标赛结果：使用仅rollout评估位置(αrp, αr)、仅价值网络(αvp, αv)或混合(αrvp, αrv)；使用策略网络pσ(αrvp, αvp, αrp)或无策略网络(αrv, αv, αr)，即改为全程使用树策略pτ的占位符概率。每个程序在单一机器上每步5 s，使用48 CPU和8 GPU。由BayesElo计算Elo评级。
扩展数据表8 | AlphaGo和分布式AlphaGo之间锦标赛结果，测试硬件可扩展性：每个程序每步最多2 s思考时间。由BayesElo计算Elo评级。
扩展数据表9 | 程序之间胜率百分比交叉表：灰色为95% Agresti–Coull置信区间。每个程序每步最多5 s思考时间。CN4、ZN4和PC4给予4个让子；所有游戏komi 7.5。分布式AlphaGo对αrvp得分77% [70;82]，对所有其他程序100%（无让子游戏）。
扩展数据表10 | 单一机器可扩展性研究中程序之间胜率百分比交叉表：灰色为95% Agresti–Coull置信区间。每个程序每步2 s；所有游戏komi 7.5。
扩展数据表11 | 分布式可扩展性研究中程序之间胜率百分比交叉表：灰色为95% Agresti–Coull置信区间。每个程序每步2 s；所有游戏komi 7.5。
