AlphaGo制胜绝招：蒙特卡洛树搜索入门指南

2018 年 4 月 28 日 AI前线 对弈

作者 | int8.io

编译 | 张健欣

编辑 | Emily Chen

AI 前线导读：本文是一篇关于蒙特卡洛树搜索的入门指南，介绍什么是蒙特卡洛树搜索及其各个细节的基本概念，然后通过一个简单的例子帮助读者更好地理解蒙特卡洛树搜索。

更多干货内容请关注微信公众号“AI 前线”，（ID：ai-front）

[github 代码]：https://github.com/int8/monte-carlo-tree-search

曾有很长一段时间，学术界普遍认为，机器在围棋游戏中达到人类大师水准是远不切实际的。学术界认为，这是人工智能的一个“圣杯”——一个我们在未来十年还远远达不到的里程碑。深蓝（Deep Blue）在 20 多年前大放异彩，但从那时起就没有围棋引擎更接近人类大师水准。关于围棋中“数字混沌”的观点太深入人心，以至于也出现在电影中。

令人惊讶的是，在 2016 年 3 月，由 Google Deepmind 发明的一种称为 Alpha Go 的算法，以 4-1 战绩击败了韩国世界围棋冠军，证明了现实怀疑论者是错误的。差不多一年之后，Alpha Go Zero——Alpha Go Lee（打败韩国大师）的第二代，被报道以 100-0 的战绩挫败它的前身，人类怕是已经很难再望其项背了。

Alpha Go/Zero 系统是一个伟大的工程作品，由多种方法混合组装而成。其中的核心组件是：

蒙特卡洛树搜索（用于树遍历的 PUCT 函数的一个变种）
残差卷积 神经网络——用于博弈评估和行动先验概率估算的策略和估值网络
强化学习——用于通过自我对弈来训练网络
在本文中，我们将 只聚焦于蒙特卡洛树搜索。

介绍

蒙特卡洛树搜索 是由雷米·库洛姆（Rémi Coulom）在 2006 年作为 Crazy Stone 的一部分提出的。Crazy Stone 是一个性能卓越的围棋博弈引擎。

蒙特卡洛树搜索有一个主要目的：给定一个 博弈状态，选择最可能赢的下一步。 在本文的其余部分，我们将试着带你看一看蒙特卡洛树搜索的细节，从而更好地理解蒙特卡洛树搜索。我们也将时不时地结合 Alpha Go/Zero，尝试解释在 Deepmind 的人工智能中已经应用了哪些蒙特卡洛树搜索的变种。

有限的两人零和序贯博弈

蒙特卡洛树搜索操纵的框架或环境所在的博弈本身就是一个非常抽象的广义术语，因此我们这里聚焦于单一一种博弈类型：有限的两人零和序贯博弈，这一开始听起来有点复杂，但实际上很简单。我们可以将它分解如下：

博弈意味着我们处理的是一个 互动的情景。参与者（一个或多个）之间存在互动
有限的一词表示，在任何时间点，参与者之间的互动方式是有限的
两人有限博弈表示博弈中有两位参与者
序贯因为选手依次行动——双方轮流
而最后，零和博弈——意味着参与双方的目标相反，换句话说：在博弈的任何终止状态，所有选手的收益之和等于零。有时候，这种博弈也称为严格竞争

围棋、象棋、井字棋是明显的有限的两人零和序贯博弈。有两位参与选手，每个人可能执行的棋步数量总是有限的，而且博弈是严格竞争的——双方选手的目标完全相反（博弈的所有产出之和为零）。

请注意，为了简化本教程，我们聚焦于特定的场景子集。蒙特卡洛树搜索是一个广泛得多的工具，并且可以应用到有限的两人零和博弈之外的场景。可以前往蒙特卡洛树搜索调研，进行全面的了解。

如何表示一个博弈？

正式来讲（查看这本免费书来大致了解博弈理论），一场博弈可以用一组基础数学实体表示。在一本博士级博弈理论书中，你会发现下述定义：

这个定义很复杂，可能对于一个数学家来说，钻研其中会其乐无穷。

从一个计算机程序员的角度来看，正式的定义可能有点儿令人不明所以，而且很难实际使用。幸运的是，我们可以用一种广为人知的数据结构来用一种简化的形式表示一个博弈：博弈树。

博弈树是一种树型数据结构，其中每个节点表示博弈的特定状态。从一个节点到它的所有子节点（如果存在的话）的转变就是一次行动（move）。一个节点的子节点数目称为分支因子。树的根节点表示博弈的初始状态，而树的叶子节点（没有子节点的节点）表示博弈的终止状态。

让我们尝试描述井字棋游戏，你可以（部分）看到：

在最上面，你可以看到树的 根节点，代表井字棋游戏的初始状态，空板子（标为绿色）
从一个节点到另一个节点的任何转变代表 一次行动
井字棋的 分支因子 不断变化——它取决于树的深度
游戏在一个 叶子节点 位置结束（标为红色）
从树的根节点遍历到叶子节点代表一场游戏的完整过程。

为了限制游戏树的大小，只有访问过的状态被展开显示，没有展开的节点用灰色表示

博弈树是一种递归数据结构，因此，在选择了最佳一步之后，你其实是选中了一个子节点，而这个子节点就是它的子树的根节点。因此，你可以将一场博弈当作一串“最有胜算的下一步”问题，每一步都可以用一个（拥有不同根节点的）博弈树表示。在实践中，通常你并不需要记忆导致当前状态的路径，因为它并不影响当前博弈状态。

什么是最有胜算的下一步？关于极小化极大算法和 Alpha-beta 剪枝算法

再次强调，我们的最终目的是，根据假定的博弈状态及其隐含的博弈树，找到最有胜算的下一步。但是，那到底意味着什么？

对此，没有直截了当的答案。首先，你不能提前知道你的对手的策略——他 / 她可能玩的很好，也可能很差。我们以国际象棋为例。知道你的对手是一名业余选手（数学家称之为“知道你的对手的混合策略”），你可以选择简单的策略来诱他上钩而快速获胜。但是，在一名强大的对手面前，如果你采用同样的策略，那明显会让你一败涂地。

如果你完全不了解你的对手，有一种激进策略，称作极小化极大（minimax）。这个策略假定你的对手发挥了最好的博弈水平，然后以此调整策略来最大化你的收益。在 A 和 B 之间的两人有限零和序贯博弈中（A 想最大化自己的效用，而 B 想最小化 A 的效用），极小化极大算法可以用如下递归公式描述：

其中

和分别代表选手 A 和选手 B 的效用函数（效用 = 收获、收益）
是一个函数，根据当前状态和状态时的行动，生成下一个博弈状态（当前节点的一个子树）

是判定最终博弈状态（在叶子节点）的函数
ŝ 是任何最终博弈状态（一个叶子节点）
终止状态中的减号表示博弈是一个零和游戏——不需要担心！

简单地说，给定状态，你想要找到一个能产生最大收益的 move ，假定你的对手想要最小化你的收益（最大化他自己的收益）。因此，名字叫作极小化极大。这听起来就能大概明白其意思。我们所需做的就是展开整个博弈树，然后根据我们的递归公式所给出的规则，向后推演节点的值。

上面的博弈树演示了在极小化极大算法中的最佳一步选择。白王后想要游戏结果变得越暗（冷）越好（回报 = 像素强度），而暗王后则想要游戏结果的颜色变得越亮（暖）越好。每层的每个选择都是极小化极大意义上的最优。最下面的叶子节点的结果已经很明显，我们可以从那里开始倒推。暗王后总会挑选最亮的颜色。然后白王后会追求她的最大回报而选择导向最暗颜色的路径。以此类推... 直到代表当前游戏状态的节点。这就是极小化极大算法如何工作的。

极小化极大算法的最大劣势是，需要扩展整个博弈树。对于分支因子较高的博弈（例如围棋或者国际象棋），这会导致庞大的博弈树从而失败。

对此，有什么补救方法吗？

有一些方法。其中一种可行的方法是，只将我们的博弈树推导到一定的阈值深度。但是那样，我们就不能保证任何在我们的阈值层的树节点是叶子节点。因此，我们需要一个用来评估非终止博弈状态的函数。这对于人类来说是很自然的：通过观察国际象棋或围棋棋盘，你就可以预测出获胜者，即使游戏还没有结束。例如：下面的游戏是可以提前宣布结束的。

另外一种克服博弈树规模问题的方法是，通过 Alpha-beta 剪枝算法对博弈树进行剪枝。Alpha-beta 剪枝算法强化了极小化极大算法。它用极小化极大方法遍历博弈树，只不过避免展开其中一些博弈树分支。最好情况下，其结果和极小化极大算法的结果相同——Alpha-beta 剪枝算法通过减少搜索区域提高了性能。

在这里可以找到对极小化极大算法和 Alpha-beta 剪枝算法的直观介绍。极小化极大算法 /Alpha-beta 剪枝算法已经是非常成熟的解决方案，并且已经成功被用在如今各种游戏引擎，例如 Stockfish——Alpha Go 在 2017 年末举行的一系列游戏中的主要竞争对手（虽然这么说颇有争议）。

蒙特卡洛树搜索 - 基本概念

在（我们今天本文所讲的范围内的）蒙特卡洛树搜索算法中，最优行动是用不同的方式计算出来的。顾名思义（特别是它的蒙特卡洛组件）——蒙特卡洛树搜索模拟游戏很多次，然后尝试基于模拟结果预测出最优决策。

蒙特卡洛树搜索的主要概念是搜索。搜索是指对博弈树的一系列向下遍历。单次遍历是指从根节点（当前博弈状态）到一个没有完全展开的节点。没有完全展开的节点意味着这个节点的子节点中至少有一个没有被访问过。一旦遇到没有完全展开的节点，它的其中一个没有访问过的子节点就会被选中成为单次模拟的根节点。然后，模拟的结果会被传回当前树的根节点，更新博弈树节点统计。一旦搜索（受限于时间或者计算能力）终止，就可以基于收集到的统计信息进行决策。

这段定义出现了很多信息点，但是你还不能很好地将所有信息点融会贯通，是吗？

我们可以试着问一些关键性问题来简化上述描述，从而慢慢理解所有的信息点：

展开的博弈树节点和没有完全展开的博弈树节点分别是什么？
在搜索过程中“向下遍历”是什么意思？下一个（子）节点是如何被选中的？
什么是一次模拟？
什么是反向传播？
在展开的博弈树节点中，哪些统计数据被反向传播和更新？
最终行动是如何选择的？

集中注意力，我们会一点儿一点儿地把这些都搞明白。

模拟 / 推演

我们可以先集中精力搞明白模拟这个概念，因为它不怎么依赖于其它的术语定义。模拟推演是一场博弈的单次行为——从当前节点（代表博弈状态）开始到可以计算出博弈结果的终止节点的一系列行动。模拟通过从一个节点随机运行的博弈来计算出那个节点的近似评估。

在模拟过程中，每一步是如何选择的？

在模拟过程中，每一步是根据一个叫做 rollout policy 的函数选择的：

这个函数接受一个表示博弈状态的参数，然后返回下一步行动。实际上，它被设计得非常快，从而可以让很多模拟快速进行——默认的 rollout policy 函数是一个均衡分布的随机数生成函数。

Alpha Go 和 Alpha Zero 中的模拟

在 Alpha Go Lee 中，叶子结点的估值是两个组件的加权之和：

采用自定义快速走棋策略的标准走棋评估，那是一种带有手工特征的浅层 softmax 神经网络
基于 13 层卷积神经网络的位置评估，称为估值网络，提炼自 Alpha Go 自我对弈的三千万个不同位置（没有任何两个点来自同一场游戏）

在 Alpha Zero， Deepmind 的工程师们迈出了更远的一步，他们根本就不执行模拟，而是用一个 19 层 CNN 残差神经网络直接评估当前节点。（在 Alpha Zero 中有一个网络 0，可以输出位置评估并立即移动概率向量）

最简单形式的模拟，就是从给定的游戏状态开始，进行一系列随机行动，然后终止。模拟通常会得到一个评估——对于我们讨论的游戏来说，它会是一场胜利、失败或者平局，但是通常任何值都是一场模拟的合理结果。

在蒙特卡洛树搜索中，模拟通常从先前没有访问过的节点开始——我们将稍后解释访问过的节点是什么意思。

博弈树节点展开——完全展开和访问过的节点

在围棋或国际象棋这类游戏中，人类是如何思考的呢？

给定博弈树的一个根节点与博弈规则，博弈树的其余部分也就暗示出来了。我们无需记住整个树就可以遍历它。在它最初的形式，它还完全没有展开。在最初的博弈状态，我们位于博弈树的根节点，而且其余的节点是未访问的。一旦我们考虑一步落子，我们会想象这步落子会导致我们在博弈树所处的位置，即我们访问了一步落子所对应的博弈树位置的节点。那些你从未考虑访问的博弈状态仍然是未访问的，它们的潜力仍留待发觉。

蒙特卡洛树搜索博弈树也可以这样区分。节点分为访问过的节点或者未访问过的节点。什么时候，一个节点是访问过的呢？如果已经有一次模拟从那个节点开始，即它已经至少被评估过一次，那这个节点就被认为是访问过的。如果一个节点的所有子节点都是访问过的节点，那么它就是一个完全展开的节点，否则，它就是一个未完全展开的节点，可以继续展开。

在实际中，一次搜索刚开始的时候，根节点的所有子节点都是未访问过的——一旦选中其中一个子节点，第一次模拟就会马上开始。

请注意，在模拟过程中，被 rollout policy 函数选中的节点，不会被认为是访问过的节点。它们仍然是未访问过的，即使一次 rollout 经过了它们。只有模拟开始的节点被标记为访问过的。

反向传播——向后传播模拟结果

一旦一个刚刚访问的节点（有时称为叶子节点）的模拟过程结束，模拟结果就可以向后传播到当前博弈树的根节点。然后，这次模拟开始的节点被标记为访问过的。

反向传播是从叶子结点（模拟开始的节点）遍历回根节点。模拟结果被传递到根节点，而且对于反向传播路径上的每个节点来说，特定的统计数据被计算或更新。反向传播保证了每个节点的统计数据会反映所有从它的后辈节点开始的模拟的结果（因为模拟结果被传递到博弈树的根节点）。

节点统计

反向传播模拟结果的目的是更新反向传播路径上的所有节点（包含模拟开始的节点）的模拟总回报和访问总次数。

——模拟总回报，节点的一个属性，简单来说，是经过节点的所有模拟结果的汇总。
——访问总次数，节点的另一个属性，表示有多少次反向传播路径经过这个节点（以及它向模拟的总回报贡献了多少次）。

每个访问过的节点都维持这两个值，一旦特定数量的模拟结束，访问过的节点将会存储一些信息，表明它们是如何被探索利用的。

换句话说，如果你查看随机节点的统计数据，这两个值将反映出这个节点的胜算怎么样（模拟总回报）以及它被探索的频繁程度（访问次数）。高回报的节点是可以利用的不错选项，但是那些访问数量低的节点可能也是不错的选项（因为它们还没有被很好地探索）。

还有一个难题。我们如何从一个根节点到一个未访问的节点来开始一次模拟？

博弈树遍历

在最开始搜索的时候，由于我们还没有进行任何模拟，因此首先选择没有访问过的节点。从这些节点各自开始一次模拟，结果反向传播回根节点，然后根节点被认为是完全展开的。

但是，我们接下来要做什么？我们现在如何从一个完全展开的节点转到一个未访问过的节点？我们必须经过已访问的节点层，而接下来如何进行，目前为止还没有很好的办法。

通过完全展开的节点来挑选我们路径上的下一个节点，从而开始下一次模拟，我们需要考虑的所有子节点：的信息以及节点本身的信息。让我们想想，现在有什么信息可用：

我们的当前节点（标为蓝色），是完全展开的，因此它肯定已经被访问过并且存储在节点统计数据中：模拟总回报和访问总次数，同样可用于它的子节点。这些值是我们前面提到的值的复合物：上限置信区间算法（Upper Confidence Bound applied to trees），或者简称 UCT。

上限置信区间算法

UCT 是一个函数，让我们从已访问过的节点中选择下一个要遍历的节点。它是蒙特卡洛树搜索的核心函数。

在蒙特卡洛树搜索遍历中，选择最大化 UCT 的节点作为下一个节点。让我们看看 UCT 函数做了什么：

首先，我们的函数是针对节点的一个子节点定义的。它是两部分的总和——第一个部分，也被称为利用组件（exploitation component），可以理解为胜负率——模拟总回报除以访问总次数，这个值预测了在节点上的获胜率。这部分看起来已经很有胜算了——最终我们将遍历那些胜率高的节点。

为什么我们不能只用利用组件？因为（如果只用利用组件），我们就只会一昧探索那些在早期带来一次模拟获胜的节点，（而忽视了节点在整个游戏过程中的胜率潜力）。

一个例子：

假设我们只使用 UCT 利用组件来进行一次蒙特卡洛树搜索。从根结点开始，我们对所有子节点运行一次模拟，然后在下一步只访问那些模拟结果至少有一轮获胜的节点。那些第一次模拟就不幸失败的节点（请记住，在实践中默认的策略函数通常是随机的），将立刻被废弃而没有机会去提高它的获胜率。

因此，我们需要第二个 UCT 组件，称为探测组件（exploration component）。探测组件有利于那些没有被探索的节点——那些相对不常被访问的节点（即比较低的节点）。我们可以看一下 UCT 函数的探测组件的形状——它随着一个节点的访问次数的增加而减少，会给那些更少被访问的节点更高选中的机会，从而使得搜索方向倾向于探索较少被访问的节点。

最后，UCT 公式中的参数控制在蒙特卡洛树搜索中利用组件和探索组件的平衡。

UCT 函数的一个重要评论：在竞争性博弈中，它的利用组件总是相对于移动到节点的选手计算的——这意味着，在遍历博弈树的过程中，观点随着遍历的节点变化：对于任何两个连续的节点，其观点是相反的。

Alpha Go 和 Alpha Zero 中的 UCT

在 Alpha Go Lee 和 Alpha Zero 中，树遍历都遵循那些最大化以下 UCT 变种的节点：

是移动的先验概率（从到的转换），它的值来自称为策略网络（Policy Network）的深度神经网络的结果。策略网络是一种根据博弈状态计算出可能移动的概率分布（请注意，策略网络与快速走棋策略不同）。这个策略的目的是减少合理移动的搜索范围——将它添加到探索组件引导搜索时朝着合理的移动方向探索。

Alpha Go 和 Alpha Zero 中的策略网络训练

在 Alpha Go 中有两种策略网络

SL（Supervise Learning，监督学习）策略网络，基于人类游戏数据集的受监督学习。
RL（Reinforcement Learning，强化学习）策略网络，增强的 SL 策略网络，它的架构相同，但是通过强化学习（自我对弈）进行深入训练。

有趣的是，在 Deepmind 的蒙特卡洛树搜索变种里，由于监督学习策略网络在实际中表现更好，因此它的结果被用来估测行动先验概率（作者认为，基于人类的数据在探索性活动中更丰富）。那么强化学习策略网络的目的又是什么呢？更强的强化学习策略网络用来生成 3 千万位置数据集，用于训练估值网络（而估值网络用于博弈状态评估）。

另一方面，在 Alpha Zero 中只有一个网络，它既是估值网络也是策略网络。它完全通过从随机初始状态开始进行自我对弈训练。并行训练多个网络，在每个检查点，基于当前最优的神经网络，评选出最优的网络用来生成训练数据。

终止蒙特卡洛树搜索

现在，我们知道了成功实现蒙特卡洛树搜索的几乎所有细节，但还是有一些我们需要回答的问题。首先，我们什么时候来终止蒙特卡洛树搜索程序？这个问题的答案是：这依赖于上下文。如果你构建一个博弈引擎，那么你的“思考时间”可能是有限的，此外，你的计算能力也是有限的。因此，最稳妥的办法是在你的资源允许的情况下尽可能久地运行蒙特卡洛树搜索。

一旦蒙特卡洛树搜索周期结束，最优的移动通常是访问次数的值最大的那步，因为它的值已经评为最佳（评估值最高的移动，也一定最经常被访问）。

在使用蒙特卡洛树搜索选出你的移动之后，你的节点选择会成为你的对手开始移动的博弈状态。一旦他选择了他的移动，你又会再次从你的对手选中的节点代表的博弈状态开始蒙特卡洛树搜索。一些从先前轮次的蒙特卡洛树搜索中获得的统计数据可能还在你正在考虑的新分支中。这就带来一个新的理念，即复用统计数据而不是从头开始构建新的博弈树。事实上，Alpha Go 和 Alpha Zero 的创造者就是这么做的。

蒙特卡洛树搜索——总结

介绍了所有的细节之后，让我们回顾下一开始关于蒙特卡洛树搜索的简化描述并附上伪代码：