蒙特卡洛树搜索（MCTS）学习笔记

蒙特卡洛树搜索（英语：Monte Carlo tree search；简称：MCTS）是一种用于某些决策过程的启发式搜索算法，最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序，它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

本文所述的蒙特卡洛树搜索可能不是最原始最标准的版本。

蒙特卡洛树搜索

蒙特卡洛树

和暴搜 / Min-Max 搜索类似，蒙特卡洛树也是这样一棵搜索树：每个节点代表一个游戏局面（包括每个棋子的位置、当前的先后手等信息），根节点代表当前局面（待决策的局面），叶节点代表游戏结束时的局面，每个节点的子节点代表其后继局面。

除此之外，蒙特卡洛树的每个节点还会记录搜索过程中当前节点被访问到的次数和对于父节点而言的胜利次数。

在实际编写程序时，当然是无法将整棵搜索树建出来的。只需建出访问过的节点所构成的这部分搜索树，并在需要访问子节点时计算出子节点有哪些即可。

蒙特卡洛树搜索的大致流程

每次搜索是从根节点起向下进行搜索，直到访问到某个叶节点为止。在向下搜索的过程中，会根据后文所述的方法选择访问哪个子节点。

到了叶节点后，会向上更新这次搜索所经过的路径上的每个节点的被访问次数和胜利次数。例如，一次搜索的结果是叶节点处黑棋获胜，那么这条搜索路径上每个节点的被访问次数都加一，其中每个白先的节点的“对于父节点而言的胜利次数”加一。

蒙特卡洛树搜索基于这样一个设定：每次搜索其实就是在模拟玩家的选择，搜索时某个子节点的被访问次数更多，实际游戏中选择这个子节点就更优；而搜索次数越多，对玩家最优选择的模拟就越准确。这样的话，当搜索次数足够多时，每次选择都是对于当前节点的先手玩家而言最优的，就收敛到了 Min-Max 搜索。

因此，在决策时，会先进行尽量多次搜索（例如，到了时间限制就停止搜索），然后选择根节点的子节点中被访问次数最多的。

向下搜索时的节点选择

在理想状态下，应当选择胜率最高的子节点进行搜索。但是，只有有了足够多的搜索次数，才能较为准确地估计每个节点的胜率。于是，选择子节点时要在开发（搜索被访问次数较少的节点）与利用（选择胜率高的节点）之间进行权衡。根据前人的研究，一般会基于如下规则选择要访问的子节点：

1. 如果存在没有被访问过的子节点，在这些节点中随机选择一个；

2. 如果所有子节点都被访问过，根据下面这个公式选择要移动到的子节点：

   $$ v \text{ is a child of } u, \mathrm{UCT}(v) = \frac{w_v}{n_v}+c\sqrt{\frac{\ln n_u}{n_v}} $$

   其中，$w_v$ 表示节点 $v$ 对于节点 $u$（的先手玩家）而言 的胜利次数，$n_x$ 表示节点 $x$ 被搜索的次数，而 $c$ 是一个常数，一般取 $\sqrt 2$ 左右，可以根据实际情况调参。

   这个公式的意义在于：前半部分是胜率，而后半部分是一个访问次数越少值越大的函数。于是，选择 UCT 最高的子节点，就可以做好开发与利用之间的平衡。

对平局的处理

当遇到平局时，有两种处理方式：1. 将双方的胜利次数各增加 0.5；2. 均匀随机地选择一个玩家获胜。

具体应用时的优化方式

使用启发式估价函数

在有未访问的子节点时，比起完全随机地选择，也可以根据启发式估价函数来优先选择更好的子节点。一般来说，只要根据估价函数将子节点排序，然后按顺序依次选择未访问的子节点即可。可以在排序前进行 random_shuffle 以在估价相同的子节点中随机选择。

除此之外，也可以修改 UCT 的计算方式，使估价影响 UCT 的值。

限制搜索的深度以及每个节点的度数

虽然 MCTS 对随机采样的利用使其能够在较大的搜索空间内搜索，但如果搜索空间太大，实际上很多时候就是纯随机。此时，如果限制搜索的深度以及每个节点的度数，就能减小搜索空间，使得节点更加充分地被访问，可能能够更加准确地估计每个节点的胜率。

限制深度时，可以视具体游戏而定，将达到深度的节点视作平局或者依据局面来估测获胜的玩家。

在不同落子顺序的相同局面之间共享搜索结果

在搜索树中，每个节点代表的不仅是游戏局面，还是落子顺序。因此，对一个游戏局面的模拟可能能够应用到多个节点上。

多线程计算

由于蒙特卡洛树搜索是由多次搜索合并而成的，多线程计算非常容易。最容易实现的多线程计算方式是，构建多棵蒙特卡洛树，分别在上面搜索，最后将根节点的子节点的被访问次数合并，再进行选择。

使用深度学习对未访问节点进行模拟

你可以问问 DeepMind 的工程师这个具体怎么操作（x

蒙特卡洛树搜索的优缺点

MCTS 最主要的优点有两点：

1. 如果你完全不会一个游戏，只知道它的规则，也可以使用 MCTS。而 Min-Max 搜索必须有一个估价函数。当然，如果完全使用原始的基于随机选择的 MCTS，棋力不一定足够高。（学会MCTS 后：我要在 Botzone 上混分！实际上：如果没有估价函数还是不太混的到分…）
2. 由于对随机采样的利用，可以胜任较大的搜索空间。

但是，如果在某个局面下，大多数下法都会输，只有一步妙招能赢，由于 MCTS 的随机采样，可能会认为这个局面必输。