蒙特卡洛树搜索

蒙特卡洛树搜索（Monte Carlo Tree Search），简记为MCTS，乍一看还挺陌生的，但它确是战胜人类围棋冠军的阿尔法狗（Alpha GO）的核心算法之一。Alpha GO有两大支撑，深度学习加蒙特卡洛树搜索。今天我们就来了解一下这个MCTS，主要包括如下内容：

一、随机搜索

蒙特卡洛树搜索首先它是一个搜索算法，而前面带有蒙特卡洛，从某中意义讲带有蒙特卡洛就是随机搜索的意思，所以蒙特卡洛树搜索就是一种随机搜索算法。注意，随机算法大致可以分为两类，一类是Las Vegas算法，另一类是Monte Carlo算法。Las Vegas算法总是精确的返回一个答案，而Monte Carlo算法是一种带有随机大小错误的近似算法。

搜索算法，顾名思义就是从一个搜索空间中找到一个最优解或是近似的最优解，当这个搜索空间不大的时候，我们可以遍历每个可能的解，即暴力搜索，然后比较出最优解。但当搜索空间巨大的时候这种做法就不再合适了。1997年的深蓝在国际象棋比赛中赢得胜利，主要就是采用的暴力搜索。但对于围棋这种棋类，总共有19*19共381个落子点，若采用暴力搜索是绝对不可能的。

那么随机搜索的原理是什么呢？从统计学的角度来讲，假设我们不知到某个目标的分布，我们可以通过随机采样产生一堆样本，然后利用样本的均值和方差来近似推断出目标的分布。进一步，假设我们面前有K台机器，我们可以向里面投币，每台机器都有一定的概率返回双倍的钱，但我们不知道每台的具体概率是多少，为了让我们的收益最大化，我们肯定选取概率最大的那台机器，所以我们就得先投一定数量的硬币去测试哪台的概率最大，然后选取测试概率最大的那台，这就是随机搜索背后的理论。

二、蒙特卡洛树的结构

蒙特卡洛树它是一个树形结构，每个节点对应一种状态，边代表的是从一个状态转到另一个状态的转换，其中根节点表示的是当前的状态，每个节点内部存储便于搜索的相关信息，譬如节点的遍历次数，选择这个节点的收益等等，这就是蒙特卡洛树。以井字棋为例如下图：

当前状态为空，然后总共有9种行动可以采取，即9个空格都可以放棋子，每采取相应的行动就产生一个新的状态，上图只是为从空状态采取相应的行动构建的蒙特卡洛树的一部分。注意在下棋比赛中，状态就是指棋盘的状态，每次落子后棋盘状态都会改变。

蒙特卡洛树是通过迭代构建的，每次迭代产生一个节点，所以上图是三次迭代的结果，迭代的次数越多，相应的结果也就越精确，具体迭代多少次要根据计算机的计算能力和对时间的要求。迭代完成后就可以选取能产生最优状态的那个行动就好了，然后进入下一个状态，若游戏未结束，则重新以当前状态为根节点构建蒙特卡洛树。

三、MCTS四步法

上面提到构建蒙特卡洛树，如何构建蒙特卡洛树其实就是蒙特卡洛树搜索，总共分为四步：

1、Selection

从根节点开始（初始的时候也只有根节点），检查当前状态下所有可行的动作，按照某种策略选择一种动作[见三]，进入下一个状态。若这个动作从来没有做过，即做一次expansion，具体怎么做expansion见2。若这个动作已被expansion，则转入改动作执行后对应的状态继续做selection。假设下图中选中红色箭头所指的节点，节点中的信息为胜利次数/总的访问次数。

2、Expansion

Expansion即从找到未被expansion的动作的那个节点处创建一个新的孩子节点表示执行该动作后的状态。注意每次只会在expansion阶段创建出新的节点，创建新节点的那个节点可以是叶子节点也可以是非叶子节点，但创建出来的新节点一定是叶子节点。

3、Simulation

Simulation就是做推演模拟，即转入到新创建的状态节点，按照某种策略选择动作，如随机选择可行的动作或按照某种指导原则选择可行动作，直到状态结束，即胜利或失败。然后update新节点中的相关状态，若此次simulation的结果为胜利则设胜利次数为1，若为失败则设为，设该节点的访问次数为1。

4、Backpropagation

最后把新的simulation的结果反向传播回根节点，即从改叶节点原路返回至根节点，在返回路径上的每个节点访问次数和胜利次数加上新的叶节点的访问次数和胜利次数。

由此可见，迭代的次数越多，最后胜利的估计概率越趋向于真实的概率。

四、上限置信区间

上面selection中提到用一种策略选择一种动作，那么这个策略的到底是什么呢？最简单的比如随机选择一个动作或是每次选择当前已知情况下估计获胜概率最大的那个，若一样时再随机。前者没有用到已经获得的信息不是很好的策略，后者则过多的相信已有的信息没有探索是否有更高获胜概率的动作的机会，这就是典型的exploration-exploitation权衡。这里介绍常用的上限置信区间策略（Upper Confidence Bound），即：

ai表示第i个动作，wi表示执行ai时统计的的获胜概率，即胜利次数/总访问次数，Ti表示第i个动作对应的状态节点被访问的次数，若第i个节点未拓展则为，此时特殊处理成无穷的，c为收到设置的常数用于平衡exploration和exploitation。UCB分为2项，前面是用于exploitation，即给估计获胜概率大的动作给予大的值，后面是用于exploration，即越是访问少的节点，其值越大。然后选取UCB值最大的动作作为我们的selection策略。

山猫，一个专注于高级计算机技术分享的团队。

如果大家有什么问题或技术需求，可以后台留言或加山猫小墨的微信（二维码在页面底部）。

小墨简介：资深白帽，国内某互联网公司研发负责人，现从事机器学习、神经网络相关算法研究。