终于到了大名鼎鼎的蒙特卡洛树搜索了。
蒙特卡洛树搜索是一种在决策过程中做出尽可能做出最优决策的启发式算法，可以用于实现人工智能。
蒙特卡罗方法
蒙特卡洛树搜索是基于蒙特卡洛方法的算法，所以在此之前先简要了解一下蒙特卡罗方法。
蒙特卡洛方法是一种基于随机抽样和概率统计的数值计算方法，用于近似求解复杂或解析困难的问题。
蒙特卡洛方法的理论基于大数定律和中心极限定理。
听不懂？但是你一定听过下面这个方法：
一种测算
的方法：画一个圆圈和包围圆圈的方块，然后不断随机往方块内丢石头，当石头丢得足够多的时候，便可以通过石头总数和圈内石头总数算出 的值。
这种就是蒙特卡洛方法的应用。
换句话说，蒙特卡洛方法主要在做的就是随机模拟，然后根据大量模拟得到问题的近似解。
树搜索
同样需要了解的是树搜索。遍历树的方法经常为人所知有DFS和BFS。不过这里重点不是介绍树搜索，而是树搜索的用法。
将游戏的状态（最常见的例如下棋的棋盘）看作节点，不同状态间根据时间先后顺序可以构成一棵树。
通过遍历树的每一个节点，我们可以找到最优的状态，以及从当前节点到达该状态的路径，从而得到决策结果。
但是对于绝大部分情况来说，游戏的状态数量都是爆炸性地多，用BFS和DFS遍历得到猴年马月，而且节点还会占用存储空间。
蒙特卡洛树搜索
树的结构
蒙特卡洛树搜索运行在一棵特别的搜索树上。
这棵树的根节点是当前正在决策的游戏状态，叶节点是搜索树当前的边界，而父节点和子节点之间的关系是「父节点可以通过一个具体动作到达子节点的状态」。
另外，这棵搜索树的所有节点还记载了当前节点搜索时被经过的次数，以及从该节点开始往下所有模拟结果所获得的奖励。
运行流程
蒙特卡洛树搜索是一个不断迭代的过程，每次迭代由四个步骤组成：选择（Selection）、扩展（Expansion）、模拟（Simulation）、反向传播（Backpropagation）。
大致流程框架如下：
- 选择：算法从根节点开始，根据特定的策略（如 UCT / UCB1 等）向下遍历现有的搜索树，直到到达一个可以被扩展的叶节点。
- 扩展：如果叶节点不是游戏终止状态，并且还有没尝试的动作，就可以进行扩展，通过动作创建一个新的子节点。
- 模拟：在创建的新节点上使用一个默认策略（通常是随机策略）进行完整的游戏模拟，直到得到游戏结果。
- 反向传播：根据得到的游戏结果，更新当前搜索路径上的节点的信息（例如访问次数和累计奖励）
好处
蒙特卡洛树搜索相对于树搜索，能够适应数量爆炸的游戏状态。
之所以能有这种效果，是因为在建树的时候并不是给每一个可能的游戏状态建节点，而是根据搜索的需求动态进行构建，而搜索的需求则取决于节点模拟结果（可以看成胜率的指标），因此在搜索时通常只会对胜率高的几条路径进行扩展和搜索，从而无需计算所有可能的节点。
MCTS 在下棋的时候和人类其实是相似的，就像我们通常不会在那些下完以后变成劣势局面的预演上继续耗费精力，而是尽可能在优势局面上进行后续第二步、第三步的推演。
节点的选择策略
以 UCB1 策略为例，UCB1 的公式如下：
其中：
是第 个节点的平均奖励 是一个超参数，用于控制探索和利用的平衡。探索指的是搜索很少经过的路径，利用则是搜索经常经过的路径。 是当前总模拟的次数。 是第 个节点的访问次数。
通过公式对当前节点的子节点进行计算，选择值高的节点优先遍历，从而提高遍历到潜力路径的效率。
评价
MCTS 实际上是久经考验的算法框架，其背景蒙特卡洛方法甚至背景的背景大数定理和中心极限定理都是相当好用的。
MCTS 有个举世闻名的应用例子，那就是每次提到 AI 就会拿出来说的、知名围棋人机大战中打败李世石的 AlphaGo 阿尔法狗。阿尔法狗就是 MCTS 和 DRL 深度强化学习结合实现的 AI。
其他常见的 MCTS 的案例则是应用在象棋、国际象棋、斗地主、麻将等棋牌游戏中，主要是因为棋牌游戏的游戏环境和 MCTS 的契合度较高。