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算法，具体来说就是采用能使如下表达式达到最大值的节点：