蒙特卡罗方法、蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）初探

1. 蒙特卡罗方法（Monte Carlo method） 0x1：从布丰投针实验说起 - 只要实验次数够多，我就能直到上帝的意图 18世纪，布丰提出以下问题：设我们有一个以平行且等距木纹铺成的地板（如图）， 现在随意抛一支长度比木纹之间距离小的针，求针和其中一条木纹相交的概率。并以此概率，布丰提出的一种计算圆周率的方法——随机投针法。这就是蒲丰投针问题（又译“布丰投针问题”）。  我们来看一下投针算法的步骤： 1. 类比实验证明法 4个交点 3个交点 2个交点 1个交点 都不相交 将此结论推广到 l=a/2，那么最多也只有一个交点，m与n的比值是针与直线相交的概率，即， 2. 概率密度证明法 0x2：蒙特卡罗方法(Monte Carlo Simulation) - 一种随机模拟（统计模拟）方法 1. 蒙特卡洛方法的一些历史  随机模拟 (或者统计模拟) 方法有一个很酷的别名是蒙特卡罗方法(Monte Carlo Simulation)。这个方法的发展始于 20 世纪 40 年代，和原子弹制造的曼哈顿计划密切相关，当时的几个顶级科学家，包括乌拉姆、冯. 诺依曼、费米、费曼、Nicholas Metropolis， 在美国洛斯阿拉莫斯国家实验室研究裂变物质的中子连锁反应的时候，开始使用统计模拟的方法, 并在最早的计算机上进行编程实现。 现代的统计模拟方法最早由数学家乌拉姆提出，被 Metropolis 命名为蒙特卡罗方法，蒙特卡罗是著名的赌场，赌博总是和统计密切关联的，所以这个命名风趣而贴切，很快被大家广泛接受。 2. 蒙特卡洛方法思想 在上一节中，我们举了一个蒲丰投针的例子。投针的过程就是进行大量的随机试验，通过对投针结果（表象）的观测和记录，反过来推测一个未知随机量（里像）。所以本质上说，布丰投针实验就是一种蒙特卡洛方法。 像投针实验一样，用通过概率实验所求的概率估计来估计一个未知量，这样的方法统称为蒙特卡罗方法（Monte Carlo method）。 在现实世界中，大量存在一些复杂性过程，由于这类模型含有不确定的随机因素，我们很难直接用一个确定性模型来分析和描述。面对这种情况．数据科学家难以作定量分析，得不到解析的结果，或者是虽有解析结果，但计算代价太大以至不能使用。在这种情况下，可以考虑采用 Monte Carlo 方法。 一个典型的例子如下，如果我们需要计算任意曲边梯形面积的近似计水塘的面积．想象应该怎样做呢？ 很显然，我们不可能写出一个精确的数学公式，来模拟任意形状池塘的面积，我们应该放弃精确性的思想，转而寻求随机性，世界本来就是复杂的，也许随机性才是世界的真相。 一种可行的测量方法如下： 假定水塘位于一块面积已知的矩形农田之中 随机地向这块农田扔石头使得它们都落在农田内 被扔到农田中的石头可能溅上了水，也可能没有溅上水 估计被“溅上水的”石头量占总的石头量的百分比 利用这估计的百分比去近似计算该水塘面积？ Relevant Link:     2. 蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）算法 0x1：算法主要思想提炼 蒙特卡洛树搜索是一种基于树结构的蒙特卡洛方法，所谓的蒙特卡洛树搜索就是基于蒙特卡洛方法在整个2N（N等于决策次数，即树深度）空间中进行启发式搜索，基于一定的反馈寻找出最优的树结构路径（可行解）。概括来说就是，MCTS是一种确定规则驱动的启发式随机搜索算法。 上面这句话其实阐述了MCTS的5个主要核心部分： 树结构：树结构定义了一个可行解的解空间，每一个叶子节点到根节点的路径都对应了一个解（solution），解空间的大小为2N（N等于决策次数，即树深度） 蒙特卡洛方法：MSTC不需要事先给定打标样本，随机统计方法充当了驱动力的作用，通过随机统计实验获取观测结果。 损失评估函数：有一个根据一个确定的规则设计的可量化的损失函数（目标驱动的损失函数），它提供一个可量化的确定性反馈，用于评估解的优劣。从某种角度来说，MCTS是通过随机模拟寻找损失函数代表的背后”真实函数“。 反向传播线性优化：每次获得一条路径的损失结果后，采用反向传播（Backpropagation）对整条路径上的所有节点进行整体优化，优化过程连续可微 启发式搜索策略：算法遵循损失最小化的原则在整个搜索空间上进行启发式搜索，直到找到一组最优解或者提前终止 算法的优化核心思想总结一句话就是：在确定方向的渐进收敛（树搜索的准确性）和随机性（随机模拟的一般性）之间寻求一个最佳平衡。体现了纳什均衡的思想精髓。 0x2：算法主要步骤 我们知道，MCTS搜索就是建立一棵树的过程。蒙特卡罗树搜索大概可以被分成四步。选择(Selection)，拓展(Expansion)，模拟(Simulation)，反向传播(Backpropagation)。下面我们逐个来分析。 1. 初始化 在开始阶段，搜索树只有一个节点，即根节点。搜索树中的每一个节点包含了三个基本信息： 当前需要决策的局面R：即下一步可选的action list，action list是构成解空间的基本要素 该节点被访问的次数：用于提供一个确定性的收敛方向判据 累计评分：用于提供一个确定性的收敛方向判据  2. 选择阶段 下图是一张描述整个算法步骤的简要图， 0x3：节点选择策略 1. Upper Confidence Bounds（UCB）- 节点评估函数  ，其中 vi 是节点估计值，ni 是节点被访问的次数，而 N 则是其父节点已经被访问的总次数。C 是可调整参数。  UCB 公式对已知收益节点加强收敛，同时鼓励接触那些相对未曾访问的节点的尝试性探索。这是一个动态均衡公式。 每个节点的收益估计基于随机模拟不断更新，所以节点必须被访问若干次来确保估计变得更加可信，事实上，这也是随机统计的要求（大数情况下频率近似估计概率）。 理论上说，MCTS 估计会在搜索的开始不大可靠，而最终会在给定充分的时间后收敛到更加可靠的估计上，在无限时间下能够达到最优估计。 TreeNode 类里初始化了一些数值，主要是 父节点，子节点，访问节点的次数，Q值和u值，还有先验概率。同时还定义了选择评估函数（决定下一个子节点的生长方向）， 选择函数根据每个动作（就是子节点）的UCB损失函数值，选择最优的动作作为下一个子节点生长方向。 2. 节点扩展 expend()的输入参数 action_priors 是一个包括的所有合法动作的列表（list），表示在当前局面我可以在哪些地方落子。此函数为当前节点扩展了子节点。 3. 模拟 这里实现了一个基本的对弈游戏类， MCTS类的初始输入参数： policy_value_fn：当前采用的策略函数，输入是当前棋盘的状态，输出 (action, prob)元祖和score[-1,1]。 c_puct：控制探索和回报的比例，值越大表示越依赖之前的先验概率。 n_playout：MCTS的执行次数，值越大，消耗的时间越多，效果也越好。 _playout(self, state)： 此函数有一个输入参数：state, 它表示当前的状态。这个函数的功能就是 模拟。它根据当前的状态进行游戏，用贪心算法一条路走到黑，直到叶子节点，再判断游戏结束与否。如果游戏没有结束，则 扩展 节点，否则 回溯 更新叶子节点和所有祖先的值。 get_move_probs(self, state, temp)： 它的功能是从当前状态开始获得所有可行行动以及它们的概率。也就是说它能根据棋盘的状态，结合之前介绍的代码，告诉你它计算的结果，在棋盘的各个位置落子的胜率是多少。有了它，我们就能让计算机学会下棋。 update_with_move(self, last_move)： 自我对弈时，每走一步之后更新MCTS的子树。与玩家对弈时，每一个回合都要重置子树。 4. 反向传播更新 将子节点的评估值反向传播更新父节点，每传播一次，来自初始子节点的评估值影响力就逐渐减弱。 update_recursive() 的功能是回溯，从该节点开始，自上而下地更新所有的父节点。 5. 构建一个MCTS的玩家 MCTSPlayer类的主要功能在函数get_action(self, board, temp=1e-3, return_prob=0)里实现。自我对弈的时候会有一定的探索几率，用来训练。与人类下棋是总是选择最优策略。 6. 完整代码 Relevant Link:      3. 围棋AI AlphaGo中蒙特卡洛树搜索的应用 我们知道，下棋其实就是一个马尔科夫决策过程（MDP），根据当前棋面状态，确定下一步动作。问题在于，该下哪步才能保证后续赢棋的概率比较大呢？ 对于这个问题，人类世界演化出了很多围棋流派，例如， 这些流派充满了领域先验主义的味道，完全是个别的领域专家通过自己长期的实战实践中通过归纳总结得到的一种指导性方法论。 现在转换视角，我们尝试用现代计算机思维来解决下围棋问题，最容易想到的就是枚举之后的每一种下法，然后计算每步赢棋的概率，选择概率最高的就好了： 但是，对于围棋而言，状态空间实在是太大了，没有办法完全枚举。   这个时候就需要蒙特卡洛树搜索进行启发式地搜索，这里所谓的启发式搜索，就是一种小范围尝试性探索的优化思路，随机朝一个方向前进，如果效果好就继续，如果效果不好就退回来。 用通俗的话说就是，「没病走两步」 在当前状态（每一步棋）的基础上，选择一个备选动作/状态（下一步棋），即一次采样； 从备选动作/状态开始，「走两步」，不需要枚举后续所有状态，只要以一定的策略（如随机策略和 AlphaGo 中的快速走棋网络）一直模拟到游戏结束为止； 计算这次采样的回报； 重复几次，将几次回报求平均，获得该备选动作/状态的价值。 Relevant Link: