蒙特卡洛树是什么,蒙特卡洛搜索树python

　　什么是MCTS？

　　Monte zydyf树搜索的全称是人工智能问题中做出最佳决策的方法，一般是组合博弈中的一种走法规划形式。它结合了随机模拟的一般性和树搜索的精确性。

　　MCTS的迅速受到关注主要是由于计算机围棋程序的成功及其在许多难题中的潜在应用。在游戏本身之外，MCTS理论上可以用在任何由{状态，动作}定义，并通过模拟预测和输出结果的领域。

　　基本算法

　　基本的MCTS算法很简单：根据仿真结果，按照节点构造搜索树。该过程可分为以下步骤：

　　搜索树的构建过程

　　选择：从根节点R开始，递归地选择最优的子节点(稍后解释),直到到达叶节点L。扩展：如果L不是终止节点(即不会导致游戏终止)，那么创建一个或多个word子节点，选择c中的一个。

　　模拟：从C运行一个模拟输出，直到游戏结束。

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

　　有关此过程的更多信息，请参见教程。

　　每个节点需要包含两条重要的信息：一条是基于模拟结果的估计值和节点被访问的次数。

　　根据最简单和最节省内存的实现，MCTS将在每次迭代中添加一个子节点。但是，需要注意的是，根据不同的应用，在每次迭代中可以添加多个子节点。

　　节点选择

　　强盗和UCB

　　当树向下遍历时，通过选择最大化某个量来实现节点选择，这实际上类似于多臂土匪问题，参与者必须选择一个老虎机(土匪)来最大化每一轮的估计收益。我们可以使用常用的置信上限(UCB)公式进行计算：

　　其中v_i是节点的估计值，n_i是节点被访问的次数，n是其父节点被访问的总次数。c是可调参数。

　　开采和勘探

　　UCB公式平衡了对已知利益的利用和鼓励与未访问过的节点联系的探索。收益估计是基于随机模拟的，因此必须对节点进行多次访问，以使丢包估计更加可靠。MCTS估计在搜索开始时并不可靠，但在给定的足够时间后最终会收敛到更可靠的估计，并且可以在无限时间内达到最优估计。

　　MCTS和UCT

　　2006年，Kocsis和Szepervari首先构造了完整的MCTS算法，通过将UCB扩展到极大极小树搜索，该算法被命名为树的置信上限(UCT)。实际上，这是许多MCTS实现中使用的算法版本。

　　UCT可以说是MCTS的一个特例：UCT=MCTSUCB。

　　优势

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

　　冒险的

　　MCTS不需要任何关于特定领域策略或特定实践的知识来做出合理的决策。除了基本规则之外，不需要任何关于游戏的知识，这种算法就能有效地工作；这意味着一个简单的MCTS实现只需稍加调整就可以在许多游戏中重用，因此它也使MCTS成为通用游戏的一个好方法。

　　不对称的

　　MCTS执行非对称树以适应搜索空间拓扑的增长。该算法将更频繁地访问更感兴趣的节点，并将其搜索时间集中在树的更相关的部分。

　　不对称增长

　　这使得MCTS更适合分支因子较大的游戏，比如19X19 Go。如此大的组合空间会给基于深度或宽度的标准搜索方法带来问题，因此MCTS的适应性表明，它可以(最终)找到那些更优化的动作，并将搜索工作集中在这些部分。

　　随时

　　该算法可以在任何时候终止，并返回最新的估计。当前构建的搜索树可以被丢弃或以后重用。

　　简洁的

　　该算法实现起来非常方便(参见代码)。

　　劣势

　　MCTS的缺点很少，但这些缺点可能也是关键因素。

　　行动能力

　　按照它的基本形式，ts算法在一些甚至不是很大的游戏中，无法在可承受的时间内找到最佳的行动方式。这基本上是由于组合步长空间的总大小，关键节点不能访问足够的次数来给出合理的估计。

　　速度

　　MCTS搜索可能需要足够的迭代来收敛到一个好的解，这也是一个在难以优化的应用中更普遍的问题。例如，最好的围棋程序可能需要数百万次参与和领域优化和强化才能获得专家行动计划，而最GGP的实现可能只需要每秒几十次参与(与领域无关)就可以进行更复杂的游戏。对于可承受的行动时间，这样的GGP可能没有什么时间去拜访每一个合理的行动，所以在这样的情况下不太可能有很好的搜索。

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

　　促进

　　出现了各种各样的MCTS增强技术。这些基本上可以分为两类：领域知识或领域独立性。

　　领域知识

　　可以在树中使用特定游戏游戏的领域知识，过滤掉不合理的动作，或者在模拟过程中产生重要的游戏(更接近人类对手的表现)。这意味着参与度结果将比随机模拟更真实，因此节点只需要几次迭代就可以给出真实的收入值。

　　领域知识可以产生很大的性能改进，但是在速度和通用性方面也会有一些损失。

　　领域独立性

　　领域独立性强化可以应用于所有问题领域。这些通常用于树种(如AMAF)，有些用于模拟(如倾向于在战斗中获胜的行动)。领域独立强化并不局限于某个特定的领域，而是通用的，这也是目前研究的重点。

　　背景和历史

　　1928年：约翰冯诺依曼的极大极小定理给出了搜索对手树的方法，从诞生到现在形成了计算机科学和人工智能的决策基础。

　　20世纪40年代：Monte zydyf方法作为一种通过随机抽样解决不适合树搜索的弱良定义问题的方法而形成。

　　2006年：R mi Coulomb等研究人员将上述两种思想结合起来，给出了围棋程序——MCTS中动作规划的新观点。Kocsis和Szepesvri将这一思想形式化为UCT算法。

　　研究兴趣

　　在MCTS出生后的几年内，已有150多篇与MCTS相关的研究论文发表，平均每两周就有一篇新文章发表。这些文章包含了大约50个推荐的变体、增强和优化，这与传统树搜索自1928年诞生以来的增强数量相差不大。

　　这一新的研究领域是目前人工智能领域非常热门的研究课题，有许多开放的研究问题有待探索和解决。

　　MCTS:最新成就

　　伦敦帝国理工学院于2010年8月举办了第一次国际MCTS研讨会，主题是MCTS:最先进的技术。发言者包括：

　　O.泰陶德，“艺术的状态：什么是MCTS，它现在在哪里，它将走向何方？“2010年[在线]。可查阅：http://www . aigames network . org/_ media/main:events:London 2010 . pdf

　　米（meter的缩写））穆勒，“蒙特卡罗zydyf树搜索中的挑战”，2010年[在线]。可用：http://www . aigames network . org/_ media/main:events:London 2010-mcts-challenges . pdf

　　R.Hayward，“MoHex:计算机Hex世界冠军”，2010年[在线]。可用：http://www . aigames network . org/_ media/main:events:mohex talk . pdf

　　H.Finnsson和y . bjrnsson，“CadiaPlayer:一般游戏中的MCTS”，2010年[在线]。可用：http://www . aigames network . org/_ media/main:events:cadia player _ lic _ slides _ print . pdf

　　A.里梅尔，“Havannah，Monte zydyf增强和线性变换”，2010年[在线]。可用：http://www . aigames network . org/_ media/main:events:presmctsworkshop _ rimmel . pdf

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。