蒙特卡洛树入门（下）

4. 蒙特卡洛树搜索（MCTS）

简介

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

引用自：https://zh.wikipedia.org/zh-hans/蒙特卡洛树搜索

搜索步骤

解释一

选举(selection)是根据当前获得所有子步骤的统计结果，选择一个最优的子步骤。

扩展(expansion)在当前获得的统计结果不足以计算出下一个步骤时，随机选择一个子步骤。

模拟(simulation)模拟游戏，进入下一步。

反向传播(Back-Propagation)根据游戏结束的结果，计算对应路径上统计记录的值。

引用自：https://www.cnblogs.com/steven-yang/p/5993205.html

解释二

选择（Selection）：从根结点R开始，选择连续的子结点向下至叶子结点L。后面给出了一种选择子结点的方法，让游戏树向最优的方向扩展，这是蒙特卡洛树搜索的精要所在。

扩展（Expansion）：除非任意一方的输赢使得游戏在L结束，否则创建一个或多个子结点并选取其中一个结点C。

仿真（Simulation）：在从结点C开始，用随机策略进行游戏，又称为playout或者rollout。

反向传播（Backpropagation）：使用随机游戏的结果，更新从C到R的路径上的结点信息。

引用自：https://zh.wikipedia.org/zh-hans/蒙特卡洛树搜索

图解

引用自：https://www.cnblogs.com/steven-yang/p/5993205.html

详细算法

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

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

1. 选择(Selection)

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

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

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

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

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

对于这三种可能：

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

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

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

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

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

2. 拓展(Expansion)

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

3. 模拟(Simulation)

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

4. 反向传播(Backpropagation)

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

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

引用自：https://www.zhihu.com/question/39916945/answer/83799720

另可参考：https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/

算法伪代码

5.上限置信区间算法（UCT）

UCB1

在该式中：

引用自：https://zh.wikipedia.org/zh-hans/蒙特卡洛树搜索

其中，C越大，就会越照顾访问次数相对较少的子节点。

引用自：https://zhuanlan.zhihu.com/p/25345778

UCT介绍

UCT算法（Upper Confidence Bound Apply to Tree）即上限置信区间算法，是一种博弈树搜索算法，该算法将蒙特卡洛树搜索方法与UCB公式结合，在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。

即：MCTS + UCB1 = UCT

引用自：https://baike.baidu.com/item/UCT算法

算法中的UCB公式可替换为：UCB1-tuned 等

优点

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

1.Aheuristic 启发式

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

2.Asymmetric 非对称

MCTS 执行一种非对称的树的适应搜索空间拓扑结构的增长。这个算法会更频繁地访问更加有趣的节点，并聚焦其搜索时间在更加相关的树的部分。这使得 MCTS 更加适合那些有着更大的分支因子的博弈游戏，比如说 19X19 的围棋。这么大的组合空间会给标准的基于深度或者宽度的搜索方法带来问题，所以MCTS 的适应性说明它（最终）可以找到那些更加优化的行动，并将搜索的工作聚焦在这些部分。

3.任何时间

算法可以在任何时间终止，并返回当前最有的估计。当前构造出来的搜索树可以被丢弃或者供后续重用。（对比dfs暴力搜索）

4.简洁

算法实现非常方便（http://mcts.ai/code/python.html）

引用自：https://www.jianshu.com/p/d011baff6b64

缺点

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

1.行为能力

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

2.速度

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

引用自：https://www.jianshu.com/p/d011baff6b64

6.详细示例代码

http://mcts.ai/code/python.html

图文：Tao

编辑：囧星人

首发于微信公众号：SUMSTC

苏州大学微软俱乐部