蒙特卡洛树搜索入门---强化学习 - 知乎蒙特卡洛树搜索（Monte Carlo tree search）简称MCTS，和一般的蒙特卡洛方法不是一个概念。通俗的理解，蒙特卡洛方法是随机现象中用频率来近似概率，模拟次数越多，结果越准确。而蒙特卡洛树搜索，是减少某些决策…https://zhuanlan.zhihu.com/p/657911872蒙特卡洛树搜索Alphago火了，深蓝也已经家喻户晓，它们同时都运用了一项关键的搜索技术——蒙特卡洛树搜索，本文旨在对蒙特卡洛树搜索作简要介绍。https://mp.weixin.qq.com/s?__biz=MzA4OTYwNzk0NA==&mid=402083679&idx=1&sn=2d3c4d05595ba50824857cf7dd711d78&chksm=021bb538356c3c2e51d809f2cd3ac27c39c7f2d29c459f48c74841dfb12a42016b35cf147b4f&scene=27【详细原理】蒙特卡洛树搜索入门教程！_考虑如下所示的零和博弈树。指向上的三角形,如顶部节点(根),代表最大化玩家的选择-CSDN博客文章浏览阅读4.1k次，点赞4次，收藏34次。我的微信公众号名称：AI研究订阅号微信公众号ID：MultiAgent1024公众号介绍：主要研究强化学习、计算机视觉、深度学习、机器学习等相关内容，分享学习过程中的学习笔记和心得！期待您的关注，欢迎一起学习交流进步！  本文是对Monte Carlo Tree Search – beginners guide这篇文章的文章翻译，以及对其代码的解释：1 引言  蒙特卡洛树搜索在200..._考虑如下所示的零和博弈树。指向上的三角形,如顶部节点(根),代表最大化玩家的选择https://blog.csdn.net/weixin_39059031/article/details/103985855       搜索树是一种计算机领域的常用的数据结构。这里面的搜索树表示的是博弈树，树的每个节点表示在当前状态下博弈方可能执行的的一种动作，每次执行一个动作后己方状态会更新，环境也会更新，状态会更新。树的根节点代表博弈方的起始状态。博弈树表示了博弈方所有可选的路径。博弈算法的目标就是找到一条最容易获得胜利的路径。

        蒙特卡洛是一个城市名，该城市是个有名的赌城，这种博弈方法脱胎于赌博技术。该方法就是在不断去采样，看看选择哪种动作，最后获得胜利的成功的次数更多。就是一种用频率估计概率的方法。

       蒙特卡洛树搜索就是在博弈树上进行大量模拟，然后选择最有利路径的方法。

        蒙特卡洛树算法包含几个步骤，选择、扩展、模拟、反向传播。

        选择就是在当前局面下选择下一步要走的动作。这个选择不能随机选择，要确保有一定的广度，防止陷入局部最优的境地。同时要有目标，尽量选择目前效益较好的动作，提高搜索效率。利用节点在前面搜索过程中的效益评估结果，淘汰掉一些效益很低的无效的动作，相当于剪枝了，避免和minmax搜索一样陷入完全搜索。可以按照UCB公式来计算。

        其中vi是节点估计的预期收益，ni是此节点被访问的次数，而 N 则是其父节点已经被访问的总次数。C 是可调整参数。

        扩展就是选择到一个叶子节点的时候，下一步无法选择了，就在叶子节点上增加一个子节点。当选择到叶子节点是未完全展开叶子节点时，有限扩展，每次扩展添加一个子节点，优先选择扩展的子节点。

        当选择的节点确定后，在该节点上进行rollout模拟，rollout模拟目的是为了评估当前选择的节点的价值。最简单的方法是rollout到游戏结束，得到游戏结果。这个过程只为了评估当前节点的赢面，所以模拟过程的策略可以简单一点，关键是要快，所以可以采用随机策略来快速模拟。

        反向传播，就是将rollout的结果，反馈到rollout路径上的所有的节点。每个节点的访问次数需要加1，如果博弈成功，成功次数也加一。或者其他方法更新该节点的价值信息。

        蒙特卡洛树搜索的优点，不需要像minmax算法那样完全遍历，速度可控。缺点是也需要足够多的模拟才能得到较为准确的估计。