mcts算法知乎 (mcts算法原理)

Monte Carlo Tree Search（MCTS）算法是一种用于求解各种问题的启发式搜索算法，最初在计算机博弈领域中被广泛应用。它的核心思想是通过随机模拟来不断扩展搜索树，以找到最优解。MCTS算法的流程可以分为四个主要步骤：选择、扩展、模拟和回溯。

首先是选择阶段，MCTS算法从根节点开始，根据一定的策略选择子节点进行探索。这个策略通常是UCB（Upper Confidence Bound）算法，该算法结合了节点的平均收益和探索次数，以有效平衡探索与利用的问题。选择阶段会一直进行到达到叶子节点为止。

接下来是扩展阶段，在选择阶段结束后，如果叶子节点是一个未访问过的节点，MCTS算法会对该节点进行扩展，生成一个或多个子节点。这些子节点代表了当前状态可以转移到的不同可能状态。

然后是模拟阶段，对每个新生成的子节点，MCTS会使用随机模拟的方法来进行一次模拟对局，直到达到游戏结束或者设定的深度。这个模拟过程通常是根据一定的策略或者规则来进行，在棋类游戏中可能是随机走子，而在其他问题中可能是其他形式的模拟。

最后是回溯阶段，模拟结束后，MCTS会根据模拟结果对每一个探索过的节点进行收益更新。回溯过程会更新节点的访问次数和收益值，以反映模拟的结果。通过不断的模拟和回溯，MCTS算法可以逐渐收敛到最优解。

总体来说，MCTS算法具有以下优点：

1. 适用性广泛：MCTS算法可以用于求解各种问题，不仅限于博弈领域，还可以应用于路径规划、决策优化等领域。

2. 对领域知识要求低：相比于传统启发式搜索算法，MCTS算法对领域知识的要求相对较低，更加适用于各种复杂问题。

3. 鲁棒性强：由于MCTS算法的随机模拟方式，它具有一定的鲁棒性，能够在不同问题领域和情况下表现出色。

不过，MCTS算法也存在一些挑战和局限性：

1. 搜索空间过大：在某些问题中，搜索空间巨大，MCTS算法需要大量的计算资源和时间才能达到较好的效果。

2. 参数调整困难：MCTS算法中的参数设置对算法性能影响较大，需要进行仔细调整和优化。

3. 探索与利用平衡：在选择阶段中，MCTS算法需要平衡探索新节点和利用已知信息的问题，这个过程需要合理的策略。

MCTS算法是一种强大的启发式搜索算法，能够广泛应用于各种领域的问题求解。通过不断的优化和改进，MCTS算法有望在未来发挥更加重要的作用。

蒙特卡洛树是什么算法

蒙特卡罗树搜索(MCTS)会逐渐的建立一颗不对称的树。 可以分为四步并反复迭代：(1)选择从根节点，也就是要做决策的局面R出发向下选择一个最急迫需要被拓展的节点T；局面R是第一个被检查的节点，被检查的节点如果存在一个没有被评价过的招式m，那么被检查的节点在执行m后得到的新局面就是我们所需要展开的T；如果被检查的局面所有可行的招式已经都被评价过了，那么利用ucb公式得到一个拥有最大ucb值的可行招式，并且对这个招式产生的新局面再次进行检查；如果被检查的局面是一个游戏已经结束的游戏局面，那么直接执行步骤4；通过反复的进行检查，最终得到一个在树的最底层的最后一次被检查的局面c和它的一个没有被评价过的招式m，执行步骤2。 (2)拓展对于此时存在于内存中的局面c，添加一个它的子节点。 这个子节点由局面c执行招式m而得到，也就是T。 (3)模拟从局面T出发，双方开始随机的落子。 最终得到一个结果(win/lost)，以此更新T节点的胜利率。 (4)反向传播在T模拟结束之后，它的父节点c以及其所有的祖先节点依次更新胜利率。 一个节点的胜利率为这个节点所有的子节点的平均胜利率。 并从T开始，一直反向传播到根节点R，因此路径上所有的节点的胜利率都会被更新。

蒙特卡洛树搜索 - 以蛮力对抗智慧

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

比如围棋，棋手需要针对盘面的情况，选择下一步走哪个位置。这个决策过程可以认为是一个决策函数a = f(s) ，即面对 可能的状态s ， 决策函数f会提供一个 行动a （落子位置）。当然，我们希望 f 尽可能优秀，其决策a能够尽可能赢棋。

我们也可以将f构造为一颗决策树。从盘面初始状态开始（没有棋子），令初始状态为根节点，第一手棋有19*19=361个位置，因此根节点下面有361个子节点，第二手棋有360个可能的位置，即361个节点下，每个节点又有360个子节点......随着双方的落子，树的分枝越来越多，每个分支最终会进入叶子状态（对局结束，黑胜或白胜）。理论上可以列举所有可能的情况，做一棵完整的决策树，但实际上这个数据量大到不可能实现。因此，我们必须在有限的时间和空间之内，高效的构建一个子树，这是一个不完整但 尽量好的决策树 。

即便只是尽量好的决策，也是很困难的。因为一步棋的好坏通常不能立即判断出来，最终的评判要到下完的时候才能决定谁赢，况且即便赢了棋，也不代表其中每一步都是好的。

但是，无论怎样，必须提供某种方法让AI知道一步棋好不好，也就是要提供一些 启发 ，于是我们可以采用蒙特卡洛树搜索方法。

刚才我们说到下一盘棋不能判定其中走法的好坏，但如果下很多次呢？比如在某个特定盘面s1情况下，进行n次对局（接着s1盘面往后走），如果统计下来黑棋赢得多，说明s1情况对黑棋比较有利。这就是蒙特卡洛方法的思想，用大量随机事件逼近真实情况。

虽然通过蒙特卡罗方法可以近似估计一个状态的好坏，但我们依然无法对太多状态进行估算。因此，我们需要有选择的集中力量对决策树中的可能更有价值的那些节点进行估算。这就需要使用蒙特卡洛树搜索，它提供了一种选择机制，使我们能够尽量选择决策树中比较有潜力的节点进行蒙特卡洛模拟，从而使得树可以尽量集中在“较好”的策略上进行“生长”。

蒙特卡洛树搜索有四个主要步骤：

从根节点R开始，选择连续的子节点向下至叶子节点L。让决策树向最优的方向扩展，这是蒙特卡洛树搜索的精要所在。也就是要选择一个尽量”有潜力“的树节点，那么怎样的节点是有潜力呢？ 一个是胜率高，另一个是被考察的次数少 。 胜率高的节点（状态）意味着最后赢棋的概率较大，当然应该多花些精力分析其后续走法。被考察次数少的节点意味着该节点（状态）尚未经过充分研究，有成为黑马的可能。

具体来说，通常用UCB1（Upper Confidence Bound，上置信区间）公式来计算一个节点的”潜力“：

wi：第 i 次移动后取胜的次数 ni：第 i 次移动后仿真的次数 c：探索参数/权衡参数，理论上等于 根号2，在实际中通常可凭经验选择 t：仿真总次数，等于所有 ni 的和

看一个例子（参考28 天自制你的 AlphaGo（五） ）

上图中每个节点代表一个局面。而 A/B 代表这个节点被访问 B 次，黑棋胜利了 A 次。例如一开始的根节点是 12/21，代表总共模拟了 21 次，黑棋胜利了 12 次。

图中展示了蒙特卡洛树搜索的四个步骤，我们先看左边第一个树（Selection）。假设根节点是轮到黑棋走。那么我们首先需要在 7/10、5/8、0/3 之间选择，采用上面的UCB1公式：

假设 C 比较小（比如C=1），上述3个分数为 1.25 1.245 1，于是我们选择 7/10 节点（它得分1.25是最高的）。然后接下来 7/10 下面的 2/4 和 5/6 之间选择。注意，由于现在是白棋走，需要把胜率估计倒过来。即图上黑棋胜率是 2/4 和 5/6，则白棋胜率是 (1 - 2/4) 和 (1 - 5/6)：

那么白棋应该选 2/4 节点。（图中扩展的是 5/6 节点，这不是很合理）。

在所选的叶子节点L，如果已经能判定输赢，则该轮游戏结束，否则创建一个或多个子节点并选取其中一个节点C。

看上图第2个树（Expansion），假设黑棋选择了（当前的）叶子节点 3/3，然后创建了一个子节点，初始状态 0/0。

从节点C开始，用随机策略进行游戏，直到分出输赢（获得一次准确的回报）。这一步骤又称为playout或者rollout。

虽然原则上蒙特卡洛方法是采用随机策略，不过实际中也可以采用一些“有经验”的策略，或者两者的结合。所谓有经验的策略就像一个有一定水平的棋手，ta 可以下出一些比较好的走法。我们可以在仿真的某个阶段采用棋手的走法，另外一些阶段采用随机走法。 不过总的来说，仿真需要很快速的完成，这样才能得到尽量多的仿真结果，使统计结果逼近真实的胜率。

看上图第3个树（Simulation），黑棋从 0/0 节点开始进行模拟游戏直到终局，假设黑棋输，所以得分是 0/1。

使用随机游戏的结果，更新从C到R的路径上的节点信息。

看上图第4个树（Backpropagation），从 0/0 节点开始遍历父节点，直到根节点R，这条路径上的每个节点都添加一个 0/1。

当构建了一棵蒙特卡洛树以后，需要用它来做决策时，应该选择访问量最大的节点，而不是胜率最高的节点，也不是UCB分数最高的节点。

访问量不够大的节点，即使胜率高，也不够可靠（因为模拟次数不够多）。而访问量最大的节点，通常也有一定的胜率，想想UCB公式，如果胜率不高是不会经常被选中的（访问量不会大）。所以采用访问量最大的节点，AI的表现会更加稳定。

对于围棋AI，仅使用蒙特卡洛树搜索是不够的，尤其是 AlphaGO 这样的顶级AI，更多分析请参考：左右互搏，青出于蓝而胜于蓝？阿尔法狗原理解析

28 天自制你的 AlphaGo（五） AlphaGo背后的力量：蒙特卡洛树搜索入门指南 蒙特卡洛树搜索（MCTS）算法 维基百科——蒙特卡洛树搜索 维基百科——蒙特卡罗方法

阿尔法狗核心算法是什么

阿尔法狗的核心算法主要是基于深度学习的神经网络，包括卷积神经网络（CNN）和循环神经网络（RNN）的变种。这些神经网络被训练来模拟人类棋手的策略，以在围棋游戏中进行预测和决策。

具体来说，阿尔法狗使用了一种称为“蒙特卡罗树搜索”（MCTS）的算法，该算法结合了深度学习和人工智能技术，以在复杂游戏中进行搜索和决策。MCTS通过模拟人类棋手的思考过程，逐步构建出一种近似最优解的策略。

在神经网络方面，阿尔法狗使用了多个卷积神经网络（CNN）和循环神经网络（RNN）的变种，这些网络能够从大量数据中学习并模拟人类棋手的决策过程。通过深度学习技术，阿尔法狗可以理解围棋游戏的规则和复杂度，从而更好地进行决策和预测。

在算法上，阿尔法狗使用了“策略网络”（Policy Net）和“值网络”（Value Net）两种神经网络。策略网络负责预测下一步棋子移动后的对局结果和对手的下一步行动，而值网络则负责评估当前局势下的最优棋步。这两者相互协作，共同完成了阿尔法狗的核心算法。

此外，阿尔法狗还采用了“深度残差学习”（Deep Residual Learning）的技术，通过这种方法，神经网络可以更快地学习和优化，从而提高决策速度和准确性。

总的来说，阿尔法狗通过模拟人类棋手的决策过程，利用深度学习的神经网络和蒙特卡罗树搜索算法的结合，实现了在围棋游戏中的卓越表现。

若对本页面资源感兴趣，请点击下方或右方图片，注册登录后

搜索本页相关的【资源名】【软件名】【功能词】或有关的关键词，即可找到您想要的资源

如有其他疑问，请咨询右下角【在线客服】，谢谢支持！