深度学习笔记——“Mastering the game of Go with deep neural networks and tree search”论文学习

题目

“通过深度神经网络和树搜索征服围棋游戏”，英文原文链接点击这里。

摘要

围棋游戏一直被视为人工智能经典游戏中最具挑战性的游戏，因为它具有巨大的搜索空间和评估棋盘盘面和移动的难度。在这里，我们介绍一种新的计算方法，它使用“价值网络”(value networks)来评估棋盘盘面，并使用“策略网络”(policy networks)来选择走法。这些深度神经网络采用了一种新颖的方法进行训练，即将有监督学习（从人类职业比赛中学习）和强化学习（从自我对抗的比赛中学习）相结合。在没有使用任何前瞻性搜索的情况下，这些神经网络的水平已经相当于最先进的使用蒙特卡罗树搜索(MCTS：Monte Carlo tree search)的程序，这些程序模拟了成千上万的随机的自我对抗盘局。我们还引入了一种新的搜索算法，将蒙特卡罗模拟与价值和政策网络相结合。使用这种搜索算法后，我们的程序AlphaGo在和其它围棋程序的对弈中达到了99.8%的胜率，并且以5比0击败了欧洲围棋冠军。这是计算机程序首次在全尺寸的围棋对抗中击败人类职业围棋选手，这是一项以前被认为至少需要十年才能完成的壮举。

• 笔记：需要掌握的有：“价值网络”(value networks)、“政策网络”(policy networks)、蒙特卡罗树搜索(MCTS：Monte Carlo tree search)、将蒙特卡罗模拟与价值和政策网络相结合的搜索算法

引言

所有完美信息博弈(games of perfect information)[^1]都有一个优值函数， v*(s)，它从每一个棋局或者说状态s中决定了最终的博弈结果（在所有对手都完美发挥的情况下）。可以通过在搜索树中递归计算优值函数来解决这个博弈，它大约需要计算 b d b^{d} bd个可能的落子序列，其中，b是博弈的宽度（每次下棋时合法的落子个数），d是它的深度（博弈步数的长度）。在大型博弈中，比如国际象棋（b≈35，d≈80）、以及尤其是围棋中（b≈250，d≈150），穷举搜索是不可行的，但是有效的搜索空间可以通过两种通用的原则减少。首先是，可以通过棋局评估来减少搜索的深度： 在状态 s 时对搜索树进行剪枝，并且通过一个近似的估值函数 v(s) ≈ v*(s) 来替换 s 下面的子树，从而预测状态 s 的结果[^2]。这种方法在国际象棋、跳棋、黑白棋中都获得了超人的表现，但在围棋中却被认为是难以驾驭的，因为围棋实在是太复杂。其次是，搜索的广度可以通过来自策略 p(a∣s) 的采样动作来降低，该策略 p(a | s) 是在某一位置 s 处可能的落子位置 a 的概率分布[^3]。例如，比如蒙特卡洛走子方法搜索到最大深度时候根本不使用分枝界定法，它通过策略 p 对双方棋手的一系列下棋走法进行采样。计算这些走子的平均数可以产生一个有效的棋局评估，在西洋双陆棋戏和拼字游戏中获得了超出人类的性能表现，并且在围棋中达到了业余低段水平。

• 笔记：
• [^1]感觉“完美信息”和“完全信息”两个概念不是很好区分，我觉得可能用反面例子来解释会比较好理解。
  • 在博弈的每个行动时点上，参与人可能无法获悉决策所需的全部信息。这包括相关的外部环境——比如天气——的不确定性，以及对方先前或当前的行动，这类情况称为不完美信息(imperfect information) ；
  • 当一个参与人比另一个参与人了解更多信息时，这类情况称为不完全信息(incomplete information)，或者更恰当的称呼是非对称信息(asymmetric information)
  • 所以，下棋时，双方既知道目前的战况以及过去的棋步，也没有不确定的外部环境，而且双方了解的信息同样多，因此应该认为下棋为一种完美信息博弈。
• [^2]不是很懂，棋局评估如何完成？ v(s) ≈ v*(s) 又是如何得到的呢？这里是不是就是所谓的中间评估函数(intermediate valuation function)，因为由于博弈树的巨大，我们并不能预测整个游戏的结局，而又只有终点结才被赋予了由博弈规则所刻画的支付(payoff)，所以我们必须赋予我们所能预见到的非终点结以某种支付，这种赋予非终点结支付的规则被称为中间评估函数(intermediate valuation function)，（参考自《策略博弈》中国人民大学出版社 第三章 序贯行动博弈），所以依靠它，我们可以减少搜索的深度。它的改进可以通过反复的实战经验和对棋盘上错综复杂的关系的认知而得来，这种就是我们所说的微妙的弈棋思维，这对人类来说很容易获取，但对计算机来说就不那么容易了，是否这就会用到该篇论文之后介绍的深度神经网络来完成？
• [^3]这个概率分布是如何得到的？

蒙特卡洛树搜索（MCTS）[^4]使用蒙特卡洛走子方法（Monte Carlo rollouts）[^5]，评估搜索树中每一个状态的估值。随着模拟的次数越来越多，搜索树也越来越大，而且相关估值愈发精确。在搜索过程中用于选择下棋动作的策略，也随着时间的推移有所改进，这种改进也就是选择具有更高价值的子树。渐渐地，该策略收敛于最优下法，并且评估也收敛到最优值函数。目前最强的围棋程序是基于MCTS的，通过训练来预测人类棋手的落子，从而越来越强。这些策略过去是用来缩小搜索范围的，使搜索范围成为一束高概率的下棋动作，并且用来在快速走棋中对动作进行采样。这种方法达到了较好的业余段位水平，但是，以前的工作仅局限于基于对输入特征进行线性组合的估值函数或者浅层策略的限制。

• 笔记：
• [^4]参考链接可以大致明白MCTS的原理，以及我在github上找到了一个简单实现MCTS的小项目，能帮助更好的理解MCTS，其中函数TREEPOLICY、EXPAND和BESTCHILD实现前两步，选择和扩展，之后DEFAULTPOLICY完成模拟，最后BACKUP完成回溯。UCTSEARCH函数中，反复迭代这几个过程，使得最后的“胜率”收敛。
• [^5]Rollout：在西洋双陆棋中，每一个位置的期望值就叫做这个位置的期望(“equity”)，通过蒙特卡洛采样对"equity"进行估计就叫做进行"rollout"。论文中一般称为快速走棋。

最近，深度卷积神经网络在视觉领域取得了前所未有的成绩，例如图像分类、人脸识别和Atari游戏。它们使用许多层神经元，层与层之间像瓦片一样排列重叠在一起，来构造逐渐抽象的、局部的图像表示。我们采用类似的架构来进行围棋游戏。我们将棋局以一个19*19大小的图片传入，然后使用卷积层来构造位置的表示。我们使用这些神经网络来降低搜索树的有效的深度和广度：使用价值网络评估棋局，使用策略网络对落子动作进行取样[^6]。

• 笔记：[^6]所以价值网络应该与第三步模拟，即上述github项目中的DEFAULTPOLICY完成的功能类似，或者说与快速走子策略完成的功能类似，策略网络应该与上述github项目中的BESTCHILD完成的功能类似。

我们使用由几个机器学习阶段组成的管道来训练神经网络（图1）。我们首先直接利用人类专业棋手的落子来训练监督学习（SL）策略网络pσ 。这通过即时的反馈和高质量的梯度，提供了快速、高效的学习更新。与以前的工作类似，我们还训练了快速策略网络 pπ ，它能够在rollout期间迅速对动作进行采样。接下来，我们训练强化学习（RL）策略网络pρ ，它能够通过优化自我博弈的最终结果，来改善SL策略网络的性能。这会将策略调整到以赢棋为正确目标，而不是最大化提高预测精度。最后，我们训练一个价值网络 vθ，来预测RL策略网进行自我博弈的结果。我们的AlphaGo程序利用MCTS将上述策略网络和价值网络有效地结合在一起。