MCTS (Monte Carlo Tree Search)[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

以下文章摘录自：

《机器学习观止——核心原理与实践》

京东： https://item.jd.com/13166960.html

当当：http://product.dangdang.com/29218274.html

(由于博客系统问题，部分公式、图片和格式有可能存在显示问题，请参阅原书了解详情)

MCTS (Monte Carlo Tree Search)

1.1        MCTS概述

在前面的学习中，我们分析了蒙特卡洛方法，本章节将为大家解开蒙特卡洛树搜索的“面纱”。虽然它们的名字很接近，但大家需要注意的是这两者却有着本质区别。

我们先简单回顾一下Monte Carlo Method，它起源于二战时期的“曼哈顿计划”。一方面是出于保密性考虑，另一方面蒙特卡洛方法本身就和随机事件相关联，所以冯诺依曼等科学家就以世界闻名的摩纳哥赌城为其命名，即Monte Carlo。

MC Method是一系列方法的统称，其核心思想简单来说就是通过有规律的“试验”来获取随机事件出现的概率，并通过这些数据特征来尝试得到所求问题的答案的近似解。这样子描述可能有点抽象，下面我们举一个利用蒙特卡洛方法来求圆周率的经典例子。

大家都知道圆周率是数学及物理学中的一个数学常数，它等于圆形面积S和半径(r)平方的比值，即：

S1 = r2

另外，正方形的面积计算公式是边长(假设为2r)的平方：

S2 = (2r)2

那么如果把圆放在正方形里面，就形成了如下所示的图形：

图 ‑ 利用蒙特卡洛方法求解圆周率(1)

紧接着我们在这个图形里随机产生N(通常在10000以上)个随机数，如下图所示：

图 ‑2 利用蒙特卡洛方法求解圆周率(2)

那么理论上落在圆内的点的数量，应该和落在正方形内的点的数量，形成如下关系：

 = 

         =  =  

所以我们求解圆周率的问题，通过MC Method最终就能从随机实验中找到答案的近似解了(理论上实验次数越多，结果值越接近于真实值)。

蒙特卡洛树搜索和蒙特卡洛方法不同，它可以说是帮助机器学习做出最优决策的一种辅助手段。

1.2        MCTS算法核心处理过程

MCTS算法不算太复杂，通常由如下几个核心阶段组成：

l  Selection (选择)

从根节点Root开始，按照一定的策略(参见后续的分析)来选择子节点，直到算法抵达叶子节点Leaf (即之前没有经历过的节点)

l  Expansion (扩展)

如果上一步中的叶子节点并不是终止状态(例如游戏到此结束)，那么我们就可以创建一个或者多个新的子节点，并从中选择下一步的节点S

l  Simulation (模拟)

从上一步中选择的S开始执行模拟输出，直到终止状态(注意，这并不是绝对的。譬如AlphaGo就采用了Value Network来提前预判出结果，这样一来就不需要走到游戏结束，从而大幅降低了搜索次数)

l  Backpropagation (反向传播)

利用上一步模拟得到的结果，反向更新当前行动序列中的所有元素。然后再重复以上的几个步骤，直至达到终止条件

蒙特卡洛树搜索算法的简单示意图可以参照下面的阐述：

图 ‑ MCTS算法的核心处理过程

可见MCTS算法本身并不复杂，它结合了对未知事件的探索及优化过程。其中的关键点之一是“如何选择下一步节点”，我们在下一小节做进一步分析。

1.3        UCB和UCT

在选择下一步的节点时，有两个因素是我们需要重点考虑的：

l  exploitation

如果是为了取得较好的效果，那么采用当前已经探索到的最佳值做为下一步选择无疑是不错的选择

l  exploration

但是我们面对的是一个未知世界里的问题——这意味着总是选择当前状态下看起来的最佳值做为下一步节点，有可能犯“一叶障目”的错误。或者更直白地说，就是在某些情况下很可能无法得到全局的最优解

因而对于下一步节点的选择，我们通常更青睐于上述两者的结合。

UCT(Upper Confidence Bound1 applied to trees)算法是将它们二者结合的尝试之一，并且在当时很长一段时间都得到了广泛的应用。从名称中不难看出，它是对UCB (Upper Confidence Bound)的扩展。或者更确切地说，是UCB与树搜索的“强强联合”。

UCB1算法是为了解决“Multi-armed bandit”等类似问题而提出来的，后者又被称为“多臂赌博机”问题，是一个经典的优化问题。下面摘录wikipedia对其的描述：

“In probability theory, the multi-armed bandit problem (sometimes called the K- or N-armed bandit problem) is a problem in which a gambler at a row of slot machines (sometimes known as “one-armed bandits”) has to decide which machines to play, how many times to play each machine and in which order to play them”

简单而言就是如何优化“gambler”的选择，以期达到老虎机奖励的最大化。

UCT针对下一节点的选择借鉴了UCB算法，具体来说就是采用能使如下表达式达到最大值的节点：

其中：

l  wi 代表的是在i次操作后候选节点赢的次数

l  ni 代表的是候选节点参与模拟的次数

l  Ni 代表的是父节点模拟次数的总和

l  c是一个探索参数，我们可以根据需要来调整它的具体值

既然说是exploitation和exploration的结合体，那么我们当然有必要分析一下它是如何做到二者兼顾的。

l  UCT中的exploitation设计

上述表达式中的第一部分，即wi/ni代表了对已经探索过的经验数据的利用——只要赢的次数在总次数中的比率越大，那么最终值也越大

l  UCT中的exploration设计

上述表达式的剩余部分则体现了exploration的考虑。换句话说，ni次数与它被选中的机会成反比;同时我们还可以通过调整c参数来反应出探索的“力度”。这样一来就有效降低了未知的更佳状态被雪藏的风险了

基于本小节的分析，我们不难发现MCTS的优点在于：

l  具备一定的通用性

MCTS对于特定问题的信息没有很强的依赖性，这就意味着它可以在较小的修改范围内就适应其它问题领域

l  非对称性的树增长

MCTS总是带着“某种策略”来搜寻下一步状态，因而理论上它的树形会朝着更为有利的方向发展，这同时也让它与一些传统算法相比在性能和最终结果上都有更好的表现

图 ‑ MCTS的非对称性树示例

1.4        MCTS实例解析

本章的最后，我们通过一个范例来让大家更好地理解蒙特卡洛树搜索，同时也为前述内容做下小结。

图 ‑ MCTS范例

这个范例如上图所示，每个节点代表一种状态;圆圈中的数字A/B，表示在B次的访问中该节点赢了A次。现在我们要通过MCTS来进行搜索——根据前面小节学习到的知识，总共需要经历四个步骤。

(1)   Selection

从根节点开始，每次选择UCT值最大的节点往下走。例如根节点下有4种选择，它们的UCT计算过程分别是(取C为理论值):

l  7/10

= 7/10 + C = 0.7 + 0.567C = 1.5

l  2/5

= 2/5 + C = 0.4 + 0.802C = 1.534

l  5/9

= 5/9 + C = 0.556 + 0.598C = 1.402

l  0/3

= 0/3 + C = 0 + 1.04C = 1.47

由此可见当前的最佳选择是2/5节点。

(2)   Expansion

我们需要重复前一步骤直到抵达叶子节点，在本例子中就是2/5节点本身。然后开始执行扩展操作，意即为其新增一个(或多个)子节点0/0 (下图中用虚线区分出来了)：

图 ‑ Expansion环节

(3)   Simulation

Simulation是MCTS中非常重要的一个环节，它沿着扩展节点开始进行模拟，直至可以得出最终结果。

值得一提的是，并不是所有问题场景都可以直接进行类似“围棋预测”这样的模拟，此时需要我们根据具体场景来做些改进工作。

(4)   Backpropagation

将模拟的结果反向传播到父结点中。我们假设前一步骤中得到的结果是输，即扩展节点更新为0/1，那么其链路上的各节点数值更新如下：

图 ‑ Backpropagation环节

当然，如果是类似围棋这样的博弈场景，那么我们还需要综合考虑黑棋和白棋两种情况，具体问题具体分析。