mcts算法原理 (mcts算法 加快)

Monte Carlo Tree Search（MCTS）算法是一种用于树搜索的启发式算法，通过不断模拟随机游戏进行搜索，以找到最有可能导致胜利的路径。MCTS算法在近年来在人工智能领域被广泛运用，尤其在棋类游戏中取得了很好的效果。

MCTS算法原理的核心是利用蒙特卡洛方法进行搜索。这种方法通过大量的模拟实验来估计目标函数的值。在MCTS中，搜索树是通过不断模拟游戏的方式进行构建和优化。整个算法可以分为四个主要阶段：选择（Selection）、扩展（Expansion）、模拟（Simulation）和回溯（Backpropagation）。下面我们将详细介绍这四个阶段：

1. 选择（Selection）：在选择阶段，算法从根节点（初始游戏状态）开始，通过一定策略选择一个子节点作为下一步的搜索方向。通常采用UCB1算法来确定子节点的优先级，该算法综合了子节点的平均奖励和探索次数，以平衡探索和开发的需求。

2. 扩展（Expansion）：在扩展阶段，选择的子节点会被扩展成新的节点，表示对应的游戏状态。如果子节点还未被访问过，则会将其加入搜索树中，否则继续选择合适的子节点进行扩展。

3. 模拟（Simulation）：在模拟阶段，算法会随机模拟游戏的进行，直到达到游戏结束的条件。通过这些模拟来评估当前选择的子节点的价值，并更新搜索路径上的信息。

4. 回溯（Backpropagation）：一旦模拟完毕，算法会根据模拟结果回溯更新搜索路径上各节点的信息，例如累计获胜次数和访问次数。这样可以不断优化搜索树，使得更有可能找到最优的决策路径。

总体来说，MCTS算法通过不断迭代以上四个阶段，可以逐步深入搜索空间，找到最有可能导致胜利的路径。相比于传统的启发式搜索算法，MCTS算法更加灵活和适用于各种多人游戏。当然，MCTS算法也有一些缺点，比如搜索树的增长可能会导致计算量过大，以及在局部搜索中可能无法达到全局最优。

MCTS算法在决策树搜索领域有着重要的应用意义，通过不断优化搜索树，可以在复杂的游戏中找到较好的解决方案。随着人工智能技术的发展，相信MCTS算法会继续发挥重要作用，并在更多领域得到应用。

【转载】AlphaGo原理解析

这些天都在没日没夜地关注一个话题，谷歌人工智能程序AlphaGo（国内网友亲切地称为“阿尔法狗”）以5:0击败欧洲职业围棋冠军樊麾二段，并在和世界冠军的比赛中2:0领先。 什么！！ 19年前计算机击败国际象棋冠军卡斯帕罗夫的情景还历历在目，现在计算机又要来攻克围棋了吗！？ 虚竹在天龙八部里自填一子，无意中以“自杀”破解“珍笼”棋局，逍遥子方才亲传掌门之位。难道以后“阿尔法狗”要出任逍遥派掌门了？ 1933年，东渡日本19岁的吴清源迎战当时的日本棋坛霸主、已经60岁的本因坊秀哉，开局三招即是日本人从未见过的三三、星、天元布阵，快速进击逼得对方连连暂停“打卦”和弟子商量应对之策。随后以“新布局”开创棋坛新纪元。难道阿尔法狗会再造一个“新新布局”？ 作为一个关心人工智能和人类命运的理科生，近些天刷了好些报道，记者们说“阿尔法狗是个‘价值神经网络’和‘策略神经网’络综合蒙特卡洛搜索树的程序”，但我觉得光知道这些概念是不够的。我想看看“阿尔法狗”的庐山真面目。

准备好棋盘和脑容量，一起来探索吧？

围棋棋盘是19x19路，所以一共是361个交叉点，每个交叉点有三种状态，可以用1表示黑子，-1表示白字，0表示无子，考虑到每个位置还可能有落子的时间、这个位置的气等其他信息，我们可以用一个361 * n维的向量来表示一个棋盘的状态。我们把一个棋盘状态向量记为s。 当状态s下，我们暂时不考虑无法落子的地方，可供下一步落子的空间也是361个。我们把下一步的落子的行动也用361维的向量来表示，记为a。 这样，设计一个围棋人工智能的程序，就转换成为了，任意给定一个s状态，寻找最好的应对策略a，让你的程序按照这个策略走，最后获得棋盘上最大的地盘。 如果你想要设计一个特别牛逼惊世骇俗的围棋程序，你会从哪里开始呢？对于在谷歌DeepMind工作的黄士杰和他的小伙伴而言，第一招是：

蒙特卡洛搜索树（Monte-Carlo Tree Search）是一种“大智若愚”的方法。面对一个空白棋盘S0，黄士杰的老师Coulum最初对围棋一无所知，便假设所有落子方法分值都相等，设为1。然后扔了一个骰子，从361种落子方法中随机选择一个走法a0。Coulum想象自己落子之后，棋盘状态变成S1，然后继续假设对手也和自己一样二逼，对方也扔了一个筛子，随便瞎走了一步，这时棋盘状态变成S2，于是这两个二逼青年一直扔骰子下棋，一路走到Sn，最后肯定也能分出一个胜负r，赢了就r记为1，输了则为0，假设这第一次r=1。这样Coulum便算是在心中模拟了完整的一盘围棋。 Coulum心想，这样随机扔骰子也能赢？运气不错啊，那把刚才那个落子方法（S0,a0）记下来，分值提高一些：

我刚才从（S0, a0）开始模拟赢了一次，r=1，那么新分数=2，除了第一步，后面几步运气也不错，那我把这些随机出的局面所对应落子方法(Si,ai)的分数都设为2吧。然后Coulum开始做第二次模拟，这次扔骰子的时候Coulum对围棋已经不是一无所知了，但也知道的不是太多，所以这次除（S0, a0）的分值是2之外，其他落子方法的分数还是1。再次选择a0的概率要比其他方法高一点点。 那位假想中的二逼对手也用同样的方法更新了自己的新分数，他会选择一个a1作为应对。如法炮制，Coulum又和想象中的对手又下了一盘稍微不那么二逼的棋，结果他又赢了，Coulum于是继续调整他的模拟路径上相应的分数，把它们都+1。随着想象中的棋局下得越来越多，那些看起来不错的落子方案的分数就会越来越高，而这些落子方案越是有前途，就会被更多的选中进行推演，于是最有“前途”的落子方法就会“涌现”出来。 最后，Coulum在想象中下完10万盘棋之后，选择他推演过次数最多的那个方案落子，而这时，Coulum才真正下了第一步棋。

蒙特卡洛搜索树华丽转身为相当深刻的方法，可以看到它有两个很有意思的特点： 1）没有任何人工的feature，完全依靠规则本身，通过不断想象自对弈来提高能力。这和深蓝战胜卡斯帕罗夫完全不同，深蓝包含了很多人工设计的规则。MCTS靠的是一种类似遗传算法的自我进化，让靠谱的方法自我涌现出来。让我想起了卡尔文在《大脑如何思维》中说的思维的达尔文主义[6]。 2）MCTS可以连续运行，在对手思考对策的同时自己也可以思考对策。Coulum下完第一步之后，完全不必要停下，可以继续进行想象中的对弈，直到对手落子。Coulum随后从对手落子之后的状态开始计算，但是之前的想象中的对弈完全可以保留，因为对手的落子完全可能出现在之前想象中的对弈中，所以之前的计算是有用的。这就像人在进行对弈的时候，可以不断思考，不会因为等待对手行动而中断。这一点Coulum的程序非常像人，酷毙了。 但黄士杰很快意识到他老师的程序仍然有局限：初始策略太简单。我们需要更高效地扔骰子。 如何更高效的扔骰子呢？ 用P_human()来扔。

如果某一步被随机到很多次，就应该主要依据模拟得到的概率而非P_human。 所以P_human的初始分会被打个折扣：

这样就既可以用P_human快速定位比较好的落子方案，又给了其他位置一定的概率。看起来很美，然后实际操作中却发现：“然并卵”。因为，P_human()计算太慢了。 一次P_human()计算需要3ms，相对于原来随机扔骰子不到1us，慢了3000倍。如果不能快速模拟对局，就找不到妙招，棋力就不能提高。所以，黄士杰训练了一个简化版的P_human_fast()，把神经网络层数、输入特征都减少，耗时下降到了2us，基本满足了要求。先以P_human()来开局，走前面大概20多步，后面再使用P_human_fast()快速走到最后。兼顾了准确度和效率。 这样便综合了深度神经网络和MCTS两种方案，此时黄士杰的围棋程序已经可以战胜所有其他电脑，虽然距离人类职业选手仍有不小的差距，但他在2015年那篇论文的最后部分信心满满的表示：“我们围棋软件所使用的神经网络和蒙特卡洛方法都可以随着训练集的增长和计算力的加强（比如增加CPU数）而同步增强，我们正前进在正确的道路上。” 看样子，下一步的突破很快就将到来。同年2月，黄士杰在Deepmind的同事在顶级学术期刊nature上发表了“用神经网络打游戏”的文章[2]。这篇神作，为进一步提高MCTS的棋力，指明了前进的新方向：

红白机很多人小时候都玩过，你能都打通吗？黄士杰的同事通过“强化学习”方法训练的程序在类似红白机的游戏机上打通了200多个游戏，大多数得分都比人类还好。

“强化学习”是一类机器学习方法，Agent通过和环境s的交互，选择下一步的动作a，这个动作会影响环境s，给Agent一个reward，Agent然后继续和环境交互。游戏结束的时候，Agent得到一个最后总分r。这时我们把之前的环境状态s、动作a匹配起来就得到了一系列<s,a>，设定目标为最后的总得分r，我们可以训练一个神经网络去拟合在状态s下，做动作a的总得分。下一次玩游戏的时候，我们就可以根据当前状态s，去选择最后总得分最大的动作a。通过不断玩游戏，我们对<s,a>下总得分的估计就会越来越准确，游戏也玩儿得越来越好。 打砖块游戏有一个秘诀：把球打到墙的后面去，球就会自己反弹得分。强化学习的程序在玩了600盘以后，学到这个秘诀：球快要把墙打穿的时候评价函数v的分值就会急剧上升。

机器学习的开山鼻祖Samuel早在1967年就用自对弈的方法来学习国际跳棋[7]，而之前的蒙特卡洛搜索树也是一个自对弈的过程。但是现在黄士杰不仅有一个从人类对弈中学习出的P_human这样一个高起点，而且有一个神经网络可以从对弈样本中学习，有理由相信这次会有更好的结果。

黄士杰准备在MCTS框架之上融合局面评估函数v()。这次还是用P_human作为初始分开局，每局选择分数最高的方案落子，下到第L步之后，改用P_human_fast把剩下的棋局走完，同时调用v(SL)，评估局面的获胜概率。然后按照如下规则更新整个树的分数：

前两项和原来一样，如果待更新的节点就是叶子节点，那局面评估分就是v(SL)。如果是待更新的节点是上级节点，局面评估分是该节点所有叶子节点v()的平均值。 如果v()表示大局观，“P_human_fast模拟对局”表示快速验算，那么上面的方法就是大局观和快速模拟验算并重。如果你不服，非要做一个0.5: 0.5之外的权重，黄士杰团队已经实验了目前的程序对阵其他权重有95%的胜率。 以上，便是阿尔法狗的庐山真面目。

上图演示了阿尔法狗和樊麾对弈时的计算过程，阿尔法狗执黑，红圈是阿尔法狗实际落子的地方。1、2、3和后面的数字表示他想象中的之后双方下一步落子的地方。白色方框是樊麾的实际落子。在复盘时，樊麾觉得位置1的走法更好。 深度学习、蒙特卡洛搜索树，自我进化三招齐出，所有其他围棋ai都毫无还手之力。99%的胜率不说，“阿尔法狗”还可以在让四子的情况下以77%的胜率击败crazystone。“阿尔法狗”利用超过170个GPU，粗略估算超过800万核并行计算，不仅有前期训练过程中模仿人类，自我对弈不断进化，还有实战时的模拟对局可以实时进化，已经把现有方法发挥到了极限，是目前人工智能领域绝对的巅峰之作。

围棋是NP-hard问题，如果用一个原子来存储围棋可能的状态，把全宇宙的原子加起来都不够储存所有的状态。于是我们把这样的问题转换为寻找一个函数P，当状态为S时，计算最优的落子方案a = P(s)。我们看到，无论是“狂拽酷炫”的深度学习，还是“大智若愚”的MCTS，都是对P(s)的越来越精确的估计，但即使引入了“左右互搏”来强化学习，黄士杰和团队仍然做了大量的细节工作。所以只有一步一个脚印，面对挑战不断拆解，用耐心与细心，还有辛勤的汗水，才能取得一点又一点的进步，而这些进步积累在一起，终于让计算机达到并超过了人类职业选手的水平。

蒙特卡洛树是什么算法

蒙特卡罗树搜索(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）算法 维基百科——蒙特卡洛树搜索 维基百科——蒙特卡罗方法

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

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

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