引言如果是第一次听到蒙特卡罗的人，你可能会认为这是人名。 那么，你是个大错误。 蒙特卡洛不是人的名字，而是地方，是赌场的名字！ 但这不是我们的重点。
我们今天的主题是入门搜索蒙特卡罗树。 我个人觉得这个算法非常不可思议和有趣。 因为几年前，阿尔法戈在悲伤的镜树探索和基于深度学习的战略价值网上击败人类冠军，取得了胜利。 今天我们的主角是蒙特卡洛树搜索它到底是怎么实现的？ 其原理是什么？ 举一个例子说明整个算法的工作流程。
一、什么是MCTS？ 蒙特卡罗树搜索为一类树搜索算法的统称，简称mcts(montecarlotreesearch )。 这是一种用于一些决策过程的启发式搜索算法，在搜索空间较大的游戏中非常有效。 那么，搜索空间巨大的是什么？ 例如，20世纪90年代，IBM公司推出了一种叫做深蓝的AI，击败了当时国际象棋的世界冠军。 这个AI也比较简单粗暴，囊括了整个国际象棋搜索空间，列举了整个游戏树，就知道无论对方做了什么，下一步怎么能赢他。 另一方面，在围棋这样的游戏中，围棋盘是19*19的，有361个落子的位置。 那么，如果想列举所有围棋局面的可能性，一般是361。 这个数量比宇宙的原子数还多，即使是世界上最强的超级计算机也无法囊括所有的可能性。 那么就需要像蒙特卡罗树搜索那样稍微聪明一些，用更可行的方法对围棋这个游戏进行国际象棋式的搜索，进行决策，最后战胜人类选手。
总体来看，悲伤镜树搜索的主要目标是给定一个游戏状态来选择最佳的下一步
mts之所以受到关注，主要得益于计算机围棋程序的成功和在许多潜在课题中的应用。 超越游戏游戏本身，MCTS理论上可以用于(状态state，行为动作)中定义和预测模拟并输出结果的所有领域。
一般的APP应用有alpha go、将棋和围棋的AI程序等。
二、算法过程的算法过程一般有四步：
3358www.Sina.com/:可以最大化UCB值的节点3358www.Sina.com/:一个或多个子节点3358www.Sina.com/:在一个节点上以随机策略进行游戏，PLL 使用随机搜索结果更新整个搜索树将继续迭代，直到反向分配完成，返回选择，进行扩展模拟，进行反向分配，返回选择扩展模拟，算法结束，最终
下面通过流程图简要介绍了上面的四个步骤。
当然看上面的流程图可能会有点着迷。 请不要慌张。 用中文流程图给出了整个算法的流程。
算法的整个过程就是这样的。 首先，找到表示当前游戏状态的根节点S0，然后确定它是否是叶节点。 如果是中间节点而不是叶节点，则计算该节点下所有子节点的UCB值，找到UCB值最大的子节点，将UCB值最大的子节点作为当前节点重复下一步，继续确定当前节点是否是叶节点如果还不是叶节点，则在该节点下计算所有子节点的UCB值，找到最大节点并继续作为当前节点重复，直到找到一个节点是叶节点，然后确定该节点的n (搜索次数)是否为0 这相当于Node Expansion，将第一个新节点ROLLOUT为当前节点。
详细说明算法的四个步骤。
1 .选择对选择中的UCB公式的各项进行说明。
Vi :该节点上的平均值的大小。 例如，好的一步值更大，坏的一步值相对小于c :常数，通常可以取2。 正两边式的一个权重n :总搜索次数，对于所有节点总共相当于ni :当前节点的搜索次数2 .扩展(nodeExpplore )
例如，从根节点出发，然后计算这两个子节点的UCB值，而不是叶节点。 例如，节点3上的UCB值更大，但它以前已被访问。 根据以前的流程图，该节点不直接执行ROLLOUT，而是枚举当前节点的所有可能操作并将其添加到树中。 因为节点3可能有两个操作，所以图(
3 .模拟(Rollout )继上述步骤之后，根据我们的流程图，将第一个新节点(节点4 )作为当前节点，对其进行滚转。
那么这个ro
llout 怎么做呢？它会进行一个随机检测，下面我用一段伪代码来表示 rollout 过程： def Rollout(S_i): # S_i：当前状态loop forever: # 无限循环if S_i a terimal state: # 如果当前状态是个终止状态，比如说你赢了或者他赢了return value(S_i) # 返回对 S_i 这个状态的价值，比如说你赢了，这个价值可能就会相对比较高# 假设还没到终止状态A_i = random(available_action(S_i)) # 随机选取当前状态下能够采取的一个动作S_i = simulate(A_i, S_i) # 通过当前状态 S_i 与随机选取的动作 A_i 来计算出下一步的状态并赋值给 S_i下面我再用图示进行说明。
来看下面这张图，假设我们从黄色节点 1 进行 Rollout，它随机决策到结点 2，然后再随即决策到结点 3，然后在随机决策一直到最后红色结点 7，该节点的状态是 terminal state，然后得到一个 value，然后再将 value 返回给黄色节点 1。
这一步其实也是蒙克卡罗树搜索的非常重要的一关，因为这一步很像是在用随机的方法去逼近整体的一个分布，你想，如果黄色节点 1 代表的是更好的一个动作的话，那么赢的概率就会更大一点。经过很多次的仿真，都会得到一个比较大的概率值，如果它是一个不好的策略，那么经过很多次的仿真，大概率是不会得到一个很好的概率。
在完成了 Selection，Expansion 和 Rollout 之后，我们再进行 Backpropagation。它是做什么的呢？
在 Rollout 中我们计算出了 value 之后，我们需要返回这个 value，那么对于它所有的父节点（下图黑线上的所有的结点），它们的探索次数全部 +1，它们的 value 也会进行一个累加，然后我们整个算法会 repeate 很多次，直到蒙特卡洛树能够给出当前状态下最好的一个解答，就是我到底应该怎么走。
那么四个步骤到此就结束了，但是之前提到过这个算法会一直进行迭代，那么这个算法到底什么时候结束？
算法何时终结？一般的方法比如说游戏内棋手的限制时间，比如说，像围棋，国际象棋，在比赛当中每个棋手的时间都是有限制的，但是如果你用电脑肯定就有无限的时间，你可以将其全部穷举出来，但是这样是没有意义的。所以我觉得一个 AI 能够在规定时间内，尤其是时间越少越好，能够在更少的时间内做出更好的决策说明这个机器才更加的智能。如果给你无限的时间来做出一个决策，你可以暴力穷举出所有的可能性，其实就说明这个 AI 没有那么智能。所以一般来说我们会在规定时间范围内终结算法的迭代，然后给出最优的一个解答，下一步应该怎么走，然后再让对面去下棋，对面下完之后，你再进行一个搜索在规定时间内给出一个最优的。
还有一种就是固定迭代的次数。比如说，第一个 AI 迭代了 5000 次得到了一个比较好的结果，另一个 AI 用了 50 次就迭代出了一个比较好的结果，那么就基本认定第二个 AI 相对来说是比较智能的。所以我们也可以给出一个固定的迭代次数，比如说你算到 5000 次迭代就让蒙特卡洛树搜索停下来给出一个决策。
至于怎么给出一个决策呢？很简单，在迭代完成后，选择 value 更大的结点即可完成决策。
举例说明下面举出一个例子来详细说明蒙特卡洛树搜索的过程。
首先我们有一个根节点，S_0，它有两个属性值 T_0（价值），N_0（迭代的次数）。
那么我们首先先判断 S_0 是否是叶节点，它确实是一个叶节点，我们需要对它进行一个 Node Expansion，我们发现有两种策略可以采取分别为 S_1 和 S_2。
在这里，我们可以直接选择 S_1 作为当前节点，也可以通过 UCB 公式计算一下 S_1 和 S_2 的 UCB 值，并选取其中 UCB 值较大的节点作为当前节点。下面我们在列出 UCB 的公式：
可以发现 S_1 和 S_2 的 ni 都是 0，那么对于 S_1 和 S_2 来说，它们的 UCB 值都是无穷大，所以选择谁都是一样的，那么我就根据我上面画的流程图，选择第一个新结点作为当前节点，即 S_1。
然后我们发现 S_1 的 n_1（探索次数）为 0，即它没有被探索过，根据之前的流程图就应该进行 Rollout。
结果我们发现 value = 20，在 Rollout 完成之后，我们对 S_1 进行 Backpropagation，将 S_1 的 T_1 更新为 20，n_1 更新为 1，然后再反向传播到它的父节点 S_0，并更新S_0 的 T_0 为 20，N_0 为 1。那么就完成了第一轮迭代。
每一次迭代，都需要从根节点开始。所以到了第二轮迭代，我们同样首先判断 S_0 是否是叶节点，S_0 不是叶节点，然后我们使用 UCB 对它进行一个 Selection，选择下一个节点，S_1 的迭代次数为 1，而 S_2 的迭代次数还是 0，所以 S_2 的 UCB 还是无穷大，所以下一个节点选择 S_2，然后判断 S_2 是否是叶节点，它是叶节点，并且还未被探索过，那么直接对 S_2 进行 Rollout，然后我们得到 value = 10，然后进行 Backprppagation，更新 S_2 的 T_2 为 10， n_2 为 1，然后更新 S_2 的父节点 S_0，将 S_0 的 T_0 更新为 30（20+10），N_0 为 2（1+1），那么就完成了第二次迭代。
接下来，我们继续迭代，我们还是从 S_0 开始，它不是叶节点，然后计算 S_1 和 S_2 的 UCB 值。
因为 S_1 的 UCB 大于 S_2，所以我们选择 S_1，S_1 是一个叶节点，并且它的探测次数不为 0，那么我们就枚举出当前节点所有可能的动作，并添加到树中，即 Node Expansion。那么假设 S_1 也有两个动作 S_3 和 S_4。
因为 S_3 和 S_4 它们的探索次数都为 0，所以 UCB 都为无穷大，所以我们还是选择第一个新结点 S_3 作为当前节点，然后对 S_3 进行 Rollout，最终我们得到的 value = 0，然后对它进行一个反向传播，更新 S_3 的 T_3 为 0，n_3 为 1，更新 S_1 的 n_1 为 2，T_1 不变，更新 S_0 的 N_0 为 3，T_0 不变。这就是我们的第三次迭代。
然后我们进入第四次迭代，还是从 S_0 开始，它不是叶节点，然后根据 UCB 公式计算我们选择 S_1 还是 S_2，此时我们需要注意的是，在 UCB 公式中，Vi 是 value 的平均值，所以在 S_1 中，S_1 已经被探索了 2 次，所以 S_1 的平均 value 为 10（20/2=10），那么 S_1 和 S_2 的 UCB 计算如下：
所以我们下一个节点选取 S_2，S_2 为叶节点，而且已经被探索过了，所以需要枚举出所有的动作并添加到树中，还是假设 S_2 有 2 个动作 S_5 和 S_6，然后我们选择 S_5 对其进行 Rollout，得到 value = 15，然后依次更新 S_5，S_2, S_6 相应的 T 和 n，然后又完成了一次迭代。
假如我们现在就停止迭代，那么我们看一下我们究竟应该选 S_1 还是 S_2，很明显，S_2 的 T_2 （value）会更大一些，所以说我们通常会选择 S_2，也就是做第二个动作，是目前这个树当中最优的解。
那么，关于 UCB 公式还有几个需要注意的点。如果说 Vi 越大，那么 UCB 相应的也是越大的，而 UCB 越大代表越有可能选择这条路径，Vi 越大代表这个节点平均的价值会更高，我们就更愿意去搜索它。但是如果说只有 Vi 可不可以呢？比如将 UCB 公式变成这样：
当然不行，如果这样的话那些没有被探索过的节点就永远不会被探索，这就是为什么会有右边这一项，特别是当 ni 等于 0 的时候，UCB 会等于无穷大，那么就一定会去探索这个没有被探索过的节点，那么随着 N 的一些变化，相应的 UCB 也会跟着变化。总之，这个 UCB 公式既保证了探索了的分支可以再次被探索，又保证了我们尽量去探索那些价值更大的那些路径然后让我们能够更好的完成整个游戏。
以上就是我对蒙特卡洛树搜索的初步理解，如有错误，还请指正~~