蒙特卡罗方法入门、蒙特卡洛树简介（转载） - 玄牝之门

蒙特卡罗方法入门、蒙特卡洛树简介（转载）

本文通过五个例子，介绍蒙特卡罗方法（Monte Carlo Method）。

一、概述

蒙特卡罗方法是一种计算方法。原理是通过大量随机样本，去了解一个系统，进而得到所要计算的值。

它非常强大和灵活，又相当简单易懂，很容易实现。对于许多问题来说，它往往是最简单的计算方法，有时甚至是唯一可行的方法。

它诞生于上个世纪40年代美国的"曼哈顿计划"，名字来源于赌城蒙特卡罗，象征概率。

二、π的计算

第一个例子是，如何用蒙特卡罗方法计算圆周率π。

正方形内部有一个相切的圆，它们的面积之比是π/4。

现在，在这个正方形内部，随机产生10000个点（即10000个坐标对 (x, y)），计算它们与中心点的距离，从而判断是否落在圆的内部。

如果这些点均匀分布，那么圆内的点应该占到所有点的 π/4，因此将这个比值乘以4，就是π的值。通过R语言脚本随机模拟30000个点，π的估算值与真实值相差0.07%。

三、积分的计算

上面的方法加以推广，就可以计算任意一个积分的值。

比如，计算函数 y = x² 在 [0, 1] 区间的积分，就是求出下图红色部分的面积。

这个函数在 (1,1) 点的取值为1，所以整个红色区域在一个面积为1的正方形里面。在该正方形内部，产生大量随机点，可以计算出有多少点落在红色区域（判断条件 y < x²）。这个比重就是所要求的积分值。

用Matlab模拟100万个随机点，结果为0.3328。

四、交通堵塞

蒙特卡罗方法不仅可以用于计算，还可以用于模拟系统内部的随机运动。下面的例子模拟单车道的交通堵塞。

根据 Nagel-Schreckenberg 模型，车辆的运动满足以下规则。

• 当前速度是 v 。
• 如果前面没车，它在下一秒的速度会提高到 v + 1 ，直到达到规定的最高限速。
• 如果前面有车，距离为d，且 d < v，那么它在下一秒的速度会降低到 d - 1 。
• 此外，司机还会以概率 p 随机减速， 将下一秒的速度降低到 v - 1 。

在一条直线上，随机产生100个点，代表道路上的100辆车，另取概率 p 为 0.3 。

上图中，横轴代表距离（从左到右），纵轴代表时间（从上到下），因此每一行就表示下一秒的道路情况。

可以看到，该模型会随机产生交通拥堵（图形上黑色聚集的部分）。这就证明了，单车道即使没有任何原因，也会产生交通堵塞。

五、产品厚度

某产品由八个零件堆叠组成。也就是说，这八个零件的厚度总和，等于该产品的厚度。

已知该产品的厚度，必须控制在27mm以内，但是每个零件有一定的概率，厚度会超出误差。请问有多大的概率，产品的厚度会超出27mm？

取100000个随机样本，每个样本有8个值，对应8个零件各自的厚度。计算发现，产品的合格率为99.9979%，即百万分之21的概率，厚度会超出27mm。

六、证券市场

证券市场有时交易活跃，有时交易冷清。下面是你对市场的预测。

• 如果交易冷清，你会以平均价11元，卖出5万股。
• 如果交易活跃，你会以平均价8元，卖出10万股。
• 如果交易温和，你会以平均价10元，卖出7.5万股。

已知你的成本在每股5.5元到7.5元之间，平均是6.5元。请问接下来的交易，你的净利润会是多少？

取1000个随机样本，每个样本有两个数值：一个是证券的成本（5.5元到7.5元之间的均匀分布），另一个是当前市场状态（冷清、活跃、温和，各有三分之一可能）。

模拟计算得到，平均净利润为92, 427美元。

七，参考链接

• Introduction To Monte Carlo Methods，by Alex Woods
• Monte Carlo Simulation Tutorial
• 蒙特卡罗（Monte Carlo）方法简介，by 王晓勇
• 蒙特卡罗（Monte Carlo）模拟的一个应用实例

（完）

 

转载自阮一峰 http://www.ruanyifeng.com/blog/2015/07/monte-carlo-method.html

 

 

八，蒙特卡洛树搜索

首先，蒙特卡洛方法大家都知道，利用随机采样的样本值来估计真实值，理论基础是中心极限定理。先不考虑树搜索的事，就单纯的用蒙特卡洛方法来下棋[1, 2]（最早在1993年被提出，后在2001被再次提出）。我们可以简单的用随机比赛的方式来评价某一步落子。从需要评价的那一步开始，双方随机落子，直到一局比赛结束。为了保证结果的准确性，这样的随机对局通常需要进行上万盘，记录下每一盘的结果（比如接下来的落子是黑子，那就根据中国规则记录黑子胜了或输了多少子），最后取这些结果的平均，就能得到某一步棋的评价。最后要做的就是取评价最高的一步落子作为接下来的落子。也就是说为了决定一步落子就需要程序自己进行上万局的随机对局，这对随机对局的速度也提出了一定的要求。和使用了大量围棋知识的传统方法相比，这种方法的好处显而易见，就是几乎不需要围棋的专业知识，只需通过大量的随机对局就能估计出一步棋的价值。再加上诸如All-Moves-As-First等优化方法，基于纯蒙特卡洛方法的围棋程序已经能够匹敌最强的传统围棋程序。

 

既然蒙特卡洛的路似乎充满着光明，我们就应该沿着这条路继续前行。MCTS也就是将以上想法融入到树搜索中，利用树结构来更加高效的进行节点值的更新和选择。一般来说，MCTS操作分为4个部分[3]， 

1. Selection 
   从root node开始，根据Tree Policy依次选择最佳的child node，直到到达leaf node。Tree Policy就是选择节点（落子）的策略，它的好坏直接影响搜索的好坏，所以是MCTS的一个研究重点。比如上面说的选择平均赢子数最多的走法就是一种Tree Policy。而目前广泛采用的策略有UCT，后面会详说。
2. Expansion 
   扩展leaf node，将一个或多个可行的落子添加为该leaf node的child node。具体如何暂开，各个程序各有不同。
3. Simulation 
   根据Default Policy从扩展的位置下棋到终局。完全随机落子就是一种最简单的Default Policy。当然完全随机自然是比较弱的，通过加上一些先验知识等方法改进这一部分能够更加准确的估计落子的价值，增加程序的棋力。
4. Backpropagation 
   将Simulation的结果沿着传递路径反向传递回root node。

UCT & UCB

那么目前广泛采用的UCT的又是个什么呢。UCT的全称是UCB for Trees [4]，UCB指的是Upper Confidence Bounds [5]，不过光看名字果然还是不明所以。 
其实这个算法是有很深刻的背景的，老h机大家都玩过吧，假设有一排总共K台老h机，每台机子的期望收益是不一样的并且是固定的，但是我们并不知道各台机子的设置（不知道收益的分布），假设每次投入的本金都是一样的，那么如何规划每次玩哪台机子来使自己获得最大收益呢，这就是K-armed bandit problem了。 
容易想到，如果我们每次都能够将本金投入到期望收益最高的那台机子上，自然可以获得理论上最大的收益。但是可惜我们并不知道哪台机子是最好的，所以一方面我们需要分出成本去了解各个机子的收益情况，但是在收益不高的机子上投入太多成本自然是亏损的，所以也需要在当前发现的收益最高的老h机上投入成本。这是一个exploitation-exploration（收获-探索）困局。我们需要一个好的策略来掌握好探索和收获之间平衡。而UCB是一个（准确说是一类）能有效解决这个问题的方法。虽然要说清楚这个方法并不容易，不过还是让我们再深入一点， 
首先，将由于没有选中最佳机器所造成的累积亏损记为regret(t)，t为玩老h机的总次数。这个问题有一个理论极限，在t足够大的时候，一定有办法将regret(t)抑制在ln(t)数量级上，但是不可能比ln(t)数量级还要小。当然，要达到理论值是非常麻烦的，UCB能够用一个相对简单的方法让维持在ln(t)数量级上（虽然常数项要大一些）。UCB的基本想法是不选取平均收益最高，而是选取置信上限最高的机器。为什么要这么做呢，举一个极端的例子，假如有两台老h机，一台有0.8概率中奖的机子和一台只有0.2概率中奖的机子，我们可以简单的把每台机子各玩两次，但是很不幸的是概率0.8的那台机子两次都没能中奖，而0.2概率的机子两次都中奖了，如果我们采用取最高均值的策略，那么0.2概率的那台机子将会被选中，并且因为这台机子的平均值不会变为0，胜率较高的那台机器就没有机会被选中了。这个方法的问题在于没有进行足够的探索,而是将成本都投入到了收获中。实际上，平均收益只是对实际收益期望的一个估计，特别是采样数较少的时候 ，均值很可能会与期望产生较大的偏离，我们不应该直接把样本的均值当成实际的期望，而是要对期望给出一个置信区间和置信水平(概率)。至于要如何计算这个置信区间，就要运用Chernoff-Hoeffding bound了（推导可以参见[6]）， 
P(1n∑ni=1Xi≤μ−a)≤e−2a2n 
其中n代表样本数（放在老h机问题里面就是该台机子被选中的次数），μ代表期望，稍微变形一下， 
P(μ≥1n∑ni=1Xi+a)≤e−2a2n 
这个式子可以用来确定期望的置信上界，UCB方法中的UCB1使用置信水平1t4，根据等式1t4=e−2a2n，就可以解出a=2lntn−−−√， 
加上目前的平均收益，就得到了收益期望的置信上限，同时也是UCB1的定义， 
xj¯+2lntnj−−−√ 
其中j是老h机的编号。

如果我们乐观一些，认为期望能够达到置信上限，那么选择具有最高UCB1的老h机就成为了一个更好的策略。同时，我们可以注意观察一下UCB1的定义，前半部分是当前的平均收益，这代表着收益，后半部分则是相对于平均收益的偏移，被选中次数越少则偏移会变得越大，有更大的可能被选中，这就保证了当前收益不是那么高的机器也能够被探索到。这就很好的达成了收获和探索之间的平衡。当然，UCB的思想并不仅限运用于老h机，在围棋中，从多种可能落子中选择一步最好的同样是类似的问题，也需要掌握好收获与探索的平衡（但是也并不完全相同 1.老h机问题的目的是要尽量小的累积regret，而围棋只要能找到最好的那一步就够了，并不在乎探索途中的regret。2. 期望是会变动的。所以UCT对UCB1进行了一定的变动，实际使用的是xj¯+2Cplntnj−−−√，也就是给偏移部分加上了一个正常数项）。而UCT就是将上述的UCB的思想运用到了树搜索中，在Selection的阶段， 总是选择UCB值最大的node，直至leaf node。 
弄明白了MCTS和UCT的原理，这里我们直接用wiki上面的例子来走一遍MCTS的操作，Tree Policy用的就是UCT， 

首先，已经有一定量的节点被加入到树中，从root node开始逐层往下选择UCB值最高的node（图中的11/21, 7/10, 5/6, 3/3），直到遇到leaf node（图中的3/3），为该节点添加子节点（图中的0/0），随后从此节点开始进行simulation，得到结果并按照搜索下来的路径将结果返回（注意这里的结果和纯蒙特卡洛方法并不一样，只记录胜负结果而不是子数，胜返回1，负则返回0），更新在路径上的每一个节点，在到达结束条件之前，这些操作会一直循环进行下去。可以注意到MCTS是逐步构建搜索树的，并且树是非平衡发展的，更优的node有可能被搜索的更深。 
确实MCTS的出现让围棋AI的棋力得到了进步，最强的围棋程序们也都统统采用了MCTS，但是它们的棋力离顶尖棋手依然有很远的距离。

AlphaGo

就在MCTS的发展似乎也要山穷水尽的时候，深度学习的发展让AlphaGo横空出世。但是仔细想想又不算是横空出世，一作Huang正是十年前最强的围棋程序CrazyStone的作者，为MCTS发展做出了贡献的Coulom的学生，David Silver也是早在10年前就开始将强化学习运用在MoGo等程序中。可谓十年磨一剑了。人机大战的结果我们也都看见了，相比之前的Zen，CrazyStone等程序，阿法狗的棋力有了飞跃性的提升（从nature的那篇论文[7]中可以看到，阿法狗对这些之前最强的程序的胜率几乎达到100%，应该可以说这是深度学习的威力）。 
我对深度学习并不了解，而且已经有一篇田博士的讲解文章了[8]。这里我只想说说对MCTS部分的认识， 
1. 在AlphaGo中，使用的Tree Policy可以算是变形的UCT， 
at=argmaxa(Q(st,a)+u(st,a)) 
这里的s指的是一个state，代表一个盘面。a是指action，指下一步棋。从一个state做一个action，就会迁移到另一个state，当然本质上和我们之前用大白话做的分析没啥区别。Q是累积平均胜率，u则是对于Q的偏移，也就是选择让Q+u最大的一步棋。Q在论文中的定义如下， 
N(s,a)=∑ni=11(s,a,i) 
Q(s,a)=1N(s,a)∑ni=11(s,a,i)V(siL) 
V(sL)=(1−λ)vθ(sL)+λzL 
1(s,a,i)函数代表第i次simulation中边(s,a)所通向的节点有没有被访问到（论文中用的是边(s,a)，也没有本质区别。因为之前的分析用的都是节点，这里为了方便也说是节点），N(s,a)自然是所有的simulation中(s,a)所指向节点的访问次数。 
而V(sL)则是一次simulation后，那个leaf node的胜率（也就是反向传递回去的结果），但是这里的胜率并不简单是simulation的结果(zL)，而是综合了估值网络所给出的胜率(vθ(sL))，λ是权重系数。 
而u(st,a)的定义如下， 
u(s,a)∝P(s,a)1+N(s,a) 
P(s,a)是策略网络输出的当前局面s下落子a的概率。正如[8]中所说，说明探索刚开始时，策略网络的影响比较大，而随着探索的进行，策略网络的影响慢慢降低，偏移慢慢变小，而真正在simulation中取得更好胜率的落子会更容易被选中。 
2. [8]中提到的访问leaf node累积访问到40次才进行expansion，这是一个implementation上的细节，不过却是很重要的。

References

[1] Monte Carlo Go, Bernd Brugmann, 1993 
[2] Computer Go: An AI oriented survey, Bruno Bouzy et al., 2001 
[3] A Survey of Monte Carlo Tree Search Methods, Cameron Browne et al., 2012 
[4] Bandit based Monte-Carlo Planning, Levente Kocsis et al., 2006 
[5] Finite-time Analysis of the Multiarmed Bandit Problem, PETER AUER et al., 2002 
[6] https://www.zybuluo.com/qqiseeu/note/109942 
[7] Mastering the game of Go with deep neural networks and tree search, David Silver et al., 2016 
[8] http://zhuanlan.zhihu.com/yuandong/20607684 

 

转自http://blog.csdn.net/natsu1211/article/details/50986810