蒙特卡洛树是什么算法？

点击上方“小白学视觉”，选择加"星标"或“置顶”

重磅干货，第一时间送达

编辑：忆臻

https://www.zhihu.com/question/39916945

本文仅作为学术分享，如果侵权，会删文处理

 

蒙特卡洛树是什么算法？

作者：陆君慨
https://www.zhihu.com/question/39916945/answer/83799720

蒙特卡罗树搜索(Monte Carlo Tree Search)并不是一种"模拟人"的算法。而是通过随机的对游戏进行推演来逐渐建立一棵不对称的搜索树的过程。可以看成是某种意义上的强化学习，当然这一点学界还有一些争议。

蒙特卡罗树搜索大概可以被分成四步。选择(Selection)，拓展(Expansion)，模拟(Simulation)，反向传播(Backpropagation)。

在开始阶段，搜索树只有一个节点，也就是我们需要决策的局面。

搜索树中的每一个节点包含了三个基本信息：代表的局面，被访问的次数，累计评分。

在选择阶段，需要从根节点，也就是要做决策的局面R出发向下选择出一个最急迫需要被拓展的节点N，局面R是是每一次迭代中第一个被检查的节点；

对于被检查的局面而言，他可能有三种可能：

1)该节点所有可行动作都已经被拓展过

2)该节点有可行动作还未被拓展过

3)这个节点游戏已经结束了(例如已经连成五子的五子棋局面)

对于这三种可能：

1)如果所有可行动作都已经被拓展过了，那么我们将使用UCB公式计算该节点所有子节点的UCB值，并找到值最大的一个子节点继续检查。反复向下迭代。

2)如果被检查的局面依然存在没有被拓展的子节点(例如说某节点有20个可行动作，但是在搜索树中才创建了19个子节点)，那么我们认为这个节点就是本次迭代的的目标节点N，并找出N还未被拓展的动作A。执行步骤[2]

3)如果被检查到的节点是一个游戏已经结束的节点。那么从该节点直接执行步骤{4]。

每一个被检查的节点的被访问次数在这个阶段都会自增。

在反复的迭代之后，我们将在搜索树的底端找到一个节点，来继续后面的步骤。

[2]拓展(Expansion)

在选择阶段结束时候，我们查找到了一个最迫切被拓展的节点N，以及他一个尚未拓展的动作A。在搜索树中创建一个新的节点Nn作为N的一个新子节点。Nn的局面就是节点N在执行了动作A之后的局面。

[3]模拟(Simulation)

为了让Nn得到一个初始的评分。我们从Nn开始，让游戏随机进行，直到得到一个游戏结局，这个结局将作为Nn的初始评分。一般使用胜利/失败来作为评分，只有1或者0。

[4]反向传播(Backpropagation)

在Nn的模拟结束之后，它的父节点N以及从根节点到N的路径上的所有节点都会根据本次模拟的结果来添加自己的累计评分。如果在[1]的选择中直接发现了一个游戏结局的话，根据该结局来更新评分。

每一次迭代都会拓展搜索树，随着迭代次数的增加，搜索树的规模也不断增加。当到了一定的迭代次数或者时间之后结束，选择根节点下最好的子节点作为本次决策的结果。

一次迭代的图例[1]:

上面描述的是UCT (UCB for Tree)算法，可以说是最经典的蒙特卡罗树搜索算法了。但随着算法的发展，MCTS已经有了非常大的改变。例如很多围棋AI都已经不再使用纯粹的UCB公式而改用效果更好的UCB1-Tuned了[2]，而搜索方法上也有了非常多的改动了。

Reference:

[1]:Browne C B, Powley E, Whitehouse D, et al. A Survey of Monte Carlo Tree Search Methods[J]. IEEE Transactions on Computational Intelligence & Ai in Games, 2012, 4:1(1):1-43.

[2]:P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time Analysis  of the Multiarmed Bandit Problem,” Mach. Learn., vol. 47, no. 2,  pp. 235–256, 2002.

作者：vczh
https://www.zhihu.com/question/39916945/answer/247549008

传统意义上讲，算法名字带有蒙特卡洛的意思就是，他对搜索空间的搜索都是随机给一个方向的，譬如说蒙塔卡罗算圆周率，就是在一个正方形里面随机取点，看看落在圆里面有多少。蒙特卡洛光线追踪，在需要对环境积分的时候随机取角度射光线。蒙特卡洛走迷宫，随便走。

作者：Xiaohu Zhu
https://www.zhihu.com/question/39916945/answer/247549008

什么是 MCTS？

全称 Monte Carlo Tree Search，是一种人工智能问题中做出最优决策的方法，一般是在组合博弈中的行动（move）规划形式。它结合了随机模拟的一般性和树搜索的准确性。

MCTS 受到快速关注主要是由计算机围棋程序的成功以及其潜在的在众多难题上的应用所致。超越博弈游戏本身，MCTS 理论上可以被用在以 {状态 state，行动 action} 对定义和用模拟进行预测输出结果的任何领域。

基本算法

基本的 MCTS 算法非常简单：根据模拟的输出结果，按照节点构造搜索树。其过程可以分为下面的若干步：

选择 Selection：从根节点 R 开始，递归选择最优的子节点（后面会解释）直到达到叶子节点 L。

1. 扩展 Expansion：如果 L 不是一个终止节点（也就是，不会导致博弈游戏终止）那么就创建一个或者更多的字子节点，选择其中一个 C。

2. 模拟 Simulation：从 C 开始运行一个模拟的输出，直到博弈游戏结束。

3. 反向传播 Backpropagation：用模拟的结果输出更新当前行动序列。

参看Tutorial 了解关于这个过程更多的信息。

每个节点并需包含两个重要的信息：一个是根据模拟结果估计的值和该节点已经被访问的次数。

按照最为简单和最节约内存的实现，MCTS 将在每个迭代过程中增加一个子节点。不过，要注意其实根据不同的应用这里也可以在每个迭代过程中增加超过一个子节点。

 

节点选择

Bandits 和 UCB

在树向下遍历时的节点选择通过选择最大化某个量来实现，这其实类似于 Multiarmed bandit problem，其中的参与者必须选择一个 slot machine（bandit）来最大化每一轮的估计的收益。我们可以使用 Upper Confidence Bounds（UCB）公式常常被用来计算这个：

其中 v_i 是节点估计的值，n_i 是节点被访问的次数，而 N 则是其父节点已经被访问的总次数。C 是可调整参数。

Exploitation 和 Exploration

UCB 公式对已知收益的 exploitation 和鼓励接触那些相对未曾访问的节点的 exploration 进行平衡。收益估计基于随机模拟，所以节点必须被访问若干次来缺包估计变得更加可信；MCTS 估计会在搜索的开始不大可靠，而最终会在给定充分的时间后收敛到更加可靠的估计上，在无限时间下能够达到最优估计。

MCTS 和 UCT

Kocsis 和 Szepervari 在 2006 年首先构建了一个完备的 MCTS 算法，通过扩展 UCB 到 minimax 树搜索，并将其命名为 Upper Confidence Bounds for Trees（UCT）方法。这其实是用在当前众多 MCTS 实现中的算法版本。

UCT 可以被描述为 MCTS 的一个特例：UCT = MCTS + UCB。

优点

MCTS 提供了比传统树搜索更好的方法。

Aheuristic

MCTS 不要求任何关于给定的领域策略或者具体实践知识来做出合理的决策。这个算法可以在没有任何关于博弈游戏除基本规则外的知识的情况下进行有效工作；这意味着一个简单的 MCTS 实现可以重用在很多的博弈游戏中，只需要进行微小的调整，所以这也使得 MCTS 是对于一般的博弈游戏的很好的方法。

Asymmetric

MCTS 执行一种非对称的树的适应搜索空间拓扑结构的增长。这个算法会更频繁地访问更加有趣的节点，并聚焦其搜索时间在更加相关的树的部分。

这使得 MCTS 更加适合那些有着更大的分支因子的博弈游戏，比如说 19X19 的围棋。这么大的组合空间会给标准的基于深度或者宽度的搜索方法带来问题，所以 MCTS 的适应性说明它（最终）可以找到那些更加优化的行动，并将搜索的工作聚焦在这些部分。

任何时间算法可以在任何时间终止，并返回当前最有的估计。当前构造出来的搜索树可以被丢弃或者供后续重用。简洁算法实现非常方便

缺点

MCTS 有很少的缺点，不过这些缺点也可能是非常关键的影响因素。

行为能力

MCTS 算法，根据其基本形式，在某些甚至不是很大的博弈游戏中在可承受的时间内也不能够找到最好的行动方式。这基本上是由于组合步的空间的全部大小所致，关键节点并不能够访问足够多的次数来给出合理的估计。

速度

MCTS 搜索可能需要足够多的迭代才能收敛到一个很好的解上，这也是更加一般的难以优化的应用上的问题。例如，最佳的围棋程序可能需要百万次的交战和领域最佳和强化才能得到专家级的行动方案，而最有的 GGP 实现对更加复杂的博弈游戏可能也就只要每秒钟数十次（领域无关的）交战。对可承受的行动时间，这样的 GGP 可能很少有时间访问到每个合理的行动，所以这样的情形也不大可能出现表现非常好的搜索。

幸运的是，算法的性能可以通过一些技术显著提升。

提升

很多种 MCTS 强化的技术已经出现了。这些基本上可以归纳为领域知识或者领域独立两大类。

领域知识

特定博弈游戏的领域知识可以用在树上来过滤掉不合理的行动或者在模拟过程中产生重要的对局（更接近人类对手的表现）。这意味着交战结果将会更加的现实而不是随机的模拟，所以节点只需要少量的迭代就能给出一个现实的收益值。

领域知识可以产生巨大的性能提升，但在速度和一般性上也会有一定的损失。

领域独立

领域独立强化能够应用到所有的问题领域中。这些一般用在树种（如 AMAF），还有一些用在模拟（如 在交战时倾向于胜利的行动）。领域独立强化并不和特定的领域绑定，具有一般性，这也是当前研究的重心所在。

背景和历史

1928：John von Neumann 的 minimax 定理给出了关于对手树搜索的方法，这形成了计算机科学和人工智能的从诞生至今的决策制定基础。
1940s：Monte Carlo 方法形成，作为一种通过随机采样解决不太适合树搜索解决的弱良定义问题的方法。
2006：Rémi Coulomb 和其他研究者组合了上面两种想法给出了一个新的围棋程序中行动规划的观点——MCTS。Kocsis 和 Szepesvári 将此观点形式化进 UCT 算法。

研究兴趣

从 MCTS 诞生后几年内，就有超过 150 篇与 MCTS 相关的研究论文发布，平均下来是每两周一篇新的文章。这些文章中包含了大概 50 个推荐的变体、强化和优化，这和传统树搜索自其 1928 年诞生开始的加强的数量也差不太多。

这个新的研究领域当前是 AI 中非常热的研究话题，有很多的开放的研究问题有待发掘和解决。

下载1：OpenCV-Contrib扩展模块中文版教程
在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。

下载2：Python视觉实战项目52讲
在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。

下载3：OpenCV实战项目20讲
在「小白学视觉」公众号后台回复：OpenCV实战项目20讲，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。

交流群

欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~