摘要

长期以来，由于巨大的搜索空间以及难以评估棋盘状态和每次走子的价值，围棋被认为是古典游戏中对于人工智能来说最有挑战性的一个。这里我们介绍一种新的电脑围棋方法；这种方法用“价值网络”来评估棋盘状态，用“策略网络”来选择走子。这些深度神经网络通过一种新颖的方式训练得到；这种方式结合了基于人类高手对弈记录的监督学习和基于自我对局的强化学习。无需向前搜索，这些神经网络达到了目前最强的蒙特卡洛树搜索程序（模拟自我对局数千次）的水准。我们也介绍一种新的结合了蒙特卡洛模拟和价值与策略网络的搜索算法。使用这种搜索算法，我们的程序 AlphaGo 在与其它围棋软件对局时达到了 99.8% 的胜率，并且以五比零战胜了欧洲围棋冠军。这是电脑程序第一次在全尺寸棋盘的围棋上战胜人类职业选手，尽管之前人们认为至少还需要十年。

引言

所有完美信息游戏都有个最优价值函数，\(\nu^\ast(s)\)，决定了从每个棋盘的状态 \(s\) 开始，在全部参与者完美表现下游戏的结局。可以通过在搜索树里递归计算最优价值函数得到；搜索树包含大约 \(b^d\) 个走子序列，这里 \(b\) 是游戏的宽度 (每个状态的合法走子数)，\(d\) 是深度 (游戏的长度）。对于大型游戏，比如国际象棋，\(b\approx35\), \(d\approx80\), 以及围棋, \(b\approx250\), \(d\approx150\), 穷竭搜索是不现实的，但有效搜索空间可以通过两个原理来约简。首先，搜索深度可以通过状态评估来降低：将状态 \(s\) 处的搜索树截断，并把 \(s\) 以下的子树用一个预言从 \(s\) 开始的结局的近似价值函数 \(\nu(s) \approx \nu^\ast(s)\) 来替代 (译者注：没太懂具体怎么弄的，反正对围棋不管用就是了)。这个方法用到国际象棋，西洋棋，黑白棋上战胜了人类，但在围棋上被认为没法实现，因为围棋太复杂了。其次，搜索宽度可以通过从一个策略 \(p(a|s)\) 采样来降低，这里 \(p(a|s)\) 是状态 \(s\) 上可能走法 \(a\) 的概率分布。比如，蒙特卡洛展开战术基于从策略 \(p\) 采样的方法搜索到最大深度而不分支。对许多这样的展开求平均，可得到一个有效的状态评估，从而在双陆棋、拼字游戏，以及较弱的业余围棋中获得超越人类的表现。

蒙特卡洛树搜索 (MCTS) 利用蒙特卡洛展开来为搜索树中的每个状态估值。执行的蒙特卡洛模拟越多，搜索树越大，相应的估值约准确。用来在搜索过程中制定行动的策略函数也通过选择较高估值的子代的方法随着时间改进。这种方法渐进趋近于最优玩法，而估值也收敛到最优估值函数。目前最强的围棋程序是基于 MCTS 的，并通过被训练得可以预测人类高手走子的策略来强化。这些策略用来让搜索范围缩小到一束高概率的走子上，并且用来在展开过程中采样。这种方法达到了较强的业余水准。但是，之前的工作限于基于输入特征线性组合的浅层策略和价值函数。

最近，深度卷积神经网络在视觉领域获得前所未有的表现：比如，图像分类，面孔识别，以及玩 Atari 游戏。这种方法用许多层神经元，按互相重叠的块排列，由此构造出越来越抽象和局部化的图形表征。我们为围棋引进了类似的架构。我们把棋盘状态作为 \(19\times19\) 的图形输入，用卷积层构造一个状态表征。我们用这些神经网络降低搜索树的有效深度和宽度：用价值网络评估状态，用策略网络采样走法。

我们用由几个机器学习阶段组成的流程来训练这些神经网络 (图 1)。我们先直接从人类高手走子训练出一个有监督学习的策略网络 \(p_\sigma\)。这提供了一个快速有效的即时反馈的拥有高质量梯度的学习更新。与之前的工作类似，我们也训练了一个快速的策略 \(p_\pi\)，用来在展开阶段快速对走法采样。接下来，我们训练一个强化学习策略网络 \(p_\rho\)，通过优化自我对局的结果来改进监督学习的策略网络。这么做把策略朝着赢棋的方向调节，而不是朝着最大化预测精度的方向调节。最后，我们训练一个价值网络 \(\nu_\theta\)，用来预言强化学习的自我对局中的胜者。我们的程序 AlphaGo 通过 MCTS 高效地结合了策略和价值网络。

策略网络的监督学习

策略网络的强化学习

价值网络的强化学习

通过策略和价值网络来搜索

评估 AlphaGo 的实力

讨论

参考文献

致谢

作者贡献

技术细节 (方法)

问题的设置

许多完美信息游戏都可定义为交替的 Markov 游戏。在这些游戏中，存在一个状态空间 \(S\) (这里，一个态包含该哪个玩家出手的信息)；行动空间 \(A(s)\) 定义每个态 \(s\in S\) 里的合法走法。状态转移函数 \(f(s, a, \epsilon)\) 定义了选择行为 \(a\) 和随机输入 \(\epsilon\) (比如扔骰子) 之后的后继态；最后，奖励函数 \(r^i(s)\) 定义了玩家 \(i\) 在状态 \(s\) 的收益。