【内容简介】蒙特卡洛树搜索(Monte Carlo Tree Search) ，是一种寻找最优决策的方法。
蒙特卡洛树搜索(Monte Carlo Tree Search) 是一种寻找最优决策的方法，在AlphaGo中被运用，其主要分为四步：选择(Selection)，拓展(Expansion)，模拟(Simulation)，反向传播(Backpropagation)。 本文以井字棋为例对这一方法进行介绍。
1 基础知识
介绍 MCTS 的具体搜索算法之前，先介绍一下 MCTS 的基础知识。
1.1 节点
在棋类问题中，MCTS 使用一个节点来表示一个游戏状态，换句话说，每一个节点都对应着井字棋中的一种情况。假设现在井字棋的棋盘上只有中间一个棋子，图中用 ○ 画出，我们用一个节点表示这个游戏状态，这个节点就是下图中的根节点。这时，下一步棋有 8 种下法，所以对应的，这个根节点就有 8 个子节点（受图片大小限制，图中只画出了 3 个）。
下完一步后，游戏还没有结束，棋盘上还可以继续下棋，继续按照刚才的方法，一个节点表示一个游戏状态，这些子节点又有子节点，所有的井字棋游戏状态都可以被这样表示，于是它们就构成了一个树。对于围棋或者其他更复杂的棋类也是一样，只不过这个树会更大、更复杂。蒙特卡洛树搜索就是要在这样一个树中搜索出下一步在哪个位置下棋最有可能获胜，即根节点的哪个子节点获胜概率最高。
1.2 节点的两个属性
在蒙特卡洛树搜索中，我们将节点记作 $v$，在搜索过程中需要记录节点的访问次数和累计奖励，它们的表示符号如下：
- $N(v)$：节点 $v$ 的访问次数，节点在搜索过程中被访问多少次，该值就是多少。
- $Q(v)$：节点 $v$ 的累计奖励，即节点在反向传播过程中获得的所有奖励(reward)求和。
所谓的**奖励(reward)**是一个数值，游戏结束时若获胜，奖励为 1，若失败，奖励为 0。
2 搜索过程
下面介绍 MCTS 的具体搜索算法。
给定当前游戏状态，如何获得下一步的最佳下法呢？对于井字棋来说，当然可以在整个决策树中遍历所有可能性，直接找出最优策略。但若换成围棋等复杂的棋类，遍历的方法是显然不可行的，这时就需要在决策树中有选择地访问节点，并根据现有的有限信息做出最优决策。
在介绍下面的搜索过程之前，我们首先要知道：蒙特卡洛树搜索搜的是什么？换句话说，假如我们先把 MCTS 看成一个黑盒子，那么它的输入和输出分别是什么？
输入：一个游戏状态
输出：下一步下棋的位置
也就是说，给 MCTS 一个棋局，它就告诉你下一步该怎么走。知道了输入输出分别是什么后，我们再来看看从输入到输出这中间，MCTS 到底做了什么。总的来说，MCTS 按顺序重复执行以下四个步骤：选择，拓展，模拟，反向传播。
2.1 选择(Selection)
根据上文所述，对于围棋等可能性非常多的问题，遍历的方法不可行，因此 MCTS 有选择地访问节点，这就是选择阶段。从根节点(就是输入)出发，根据一定的策略，向下选择一个节点进行访问，若被选择的节点未被访问过，则执行扩展；若被选择的节点已被访问，则访问该节点，并继续向下选择节点进行访问，直到遇见未被访问的节点，或遇见终止节点(游戏结束)。
选择的策略由该公式确定，对当前节点的每个子节点计算如下公式，并选择计算结果最大的节点。
$$
\underset{v’\in \text{children of }v}{\mathrm{argmax}}\frac{Q\left( v’ \right)}{N\left( v’ \right)}+c\sqrt{\frac{\text{2}\ln N\left( v \right)}{N\left( v’ \right)}}
$$
其中， $v$ 表示父节点，$v’$ 表示子节点。$c$ 是一个常数，用于权衡探索 (Exploration) 与利用 (Exploitation)。探索是指选择一些之前没有尝试过的下法，丰富自己的知识，新的知识可能带来不错的结果；而利用是指根据现有的知识选择下法。$c$ 越大，就越偏向于探索；$c$ 越小，就越偏向于利用。
2.2 扩展 (Expansion)
MCTS 在搜索的过程中是有选择地访问节点，并把所有访问过的节点构建成一个树。扩展就是把选择步骤中遇到的未访问节点添加到树中，然后对该节点执行模拟。
2.3 模拟 (Simulation)
模拟是一个粗略获取信息的过程。从被扩展的节点开始，对游戏进行模拟，也就是在棋盘上随机下棋，直到游戏结束。若此时游戏胜利，则奖励 (Reward) 记为 $1$；若游戏失败，奖励记为 $0$。
注：在其他应用中，奖励也可是其他值。
2.4 反向传播 (Backpropagation)
反向传播是将在模拟中得到的奖励更新的过程。为什么叫反向传播呢？回顾一下第一步选择，我们从根节点向下一步一步地选择节点进行访问，现在我们将沿着这条路逐一更新节点信息，重新回到根节点，所以叫反向传播。
将获得的奖励记作 $R$，对当前节点，及其路径上的所有节点 $v$，都执行以下操作。即，更新访问次数，对奖励进行累加。
$$
N(v)=N(v)+1 \\
Q(v)=Q(v)+R
$$
我们再回头看看选择步骤中的公式
$$
\underset{v’\in \text{children of }v}{\mathrm{argmax}}\frac{Q\left( v’ \right)}{N\left( v’ \right)}+c\sqrt{\frac{\text{2}\ln N\left( v \right)}{N\left( v’ \right)}}
$$
可以看到，式中第一项其实就是该节点在前面的过程中获得的平均奖励，自然第一项的值越大，在现有的知识下，选择该节点更有可能获胜。式中第二项，当该节点访问次数占父节点次数的比例越小时，该值越大，表示该节点访问次数很少，可以多进行尝试，获取新的知识，它们也可能获得更丰厚的回报。于是 $c$ 就是控制这两者重要程度的参数。
这就是**上限置信区间算法 (Upper Confidence Bound )**。
2.5 搜索过程展示
下面我们看一张动图以帮助理解，图中节点内数字表示 $Q(v)/N(v)$，加粗的线条表示正在访问的路径，折线表示模拟。
3 搜索结束
MCTS 的整个过程就是这样，那么什么时候结束呢？一般设置以下两个终止条件。
- 设置最大根节点搜索次数，达到该次数后结束搜索。
- 设置最大搜索时间，超过时间后结束搜索。
结束后，就输出当前状态下，下一步下棋的位置。
4 选择最佳节点
搜索结束后，如何选择下一步下棋的位置呢？
不是选择 $Q$ 最大的节点，也不是选择平均奖励最大的节点，而是选择访问次数最多的节点。这样，就得到了当前游戏状态(根节点)下的一个选择。或者，也可以将访问次数归一化，作为下一步的概率。
如果下一步还要进行决策，则又要将下一步的状态作为根节点，重新执行 MCTS，并选择访问次数最多的节点作为下一步的策略。(上一步的搜索结果可以保留)
以上只是 MCTS 的简单介绍，想更详细的了解 MCTS 可以参考论文 A Survey of Monte Carlo Tree Search Methods
另外，Github 上也已经有 MCTS 的 Python 实现源码 https://github.com/pbsinclair42/MCTS。文档比较全，有详细的例子。
