蒙特卡洛，时序差分Temporal-Difference Learning(TD)算法

1.蒙特卡洛

成都创新互联专业提供成都主机托管四川主机托管成都服务器托管四川服务器托管，支持按月付款！我们的承诺：贵族品质、平民价格，机房位于中国电信/网通/移动机房，西部信息服务器租用服务有保障！

Monte-Carlo算法：

1.将agent放入环境的任意状态

2.从这个状态开始选择action, 并进入下一个状态

3.重复第二步直到达到最终状态

4.从最终状态回溯，计算每一个状态的G值

5.重复1-4过程，然后平均每一次的G值，最后得到的就是V值

关于G值：

第一步：根据策略使agent做出动作并进入下一动作，直到到达最终状态，需要记录每一个状态的转移，得到奖励r

第二步：从最终状态回溯，一遍一遍计算G值。 G 等于上一状态的G值（G‘）乘以一定的折扣（gamma）再加上r

G值就是从某个状态到最终状态的奖励总和

G就是V的更新目标，关于MC的更新：

两种方法：

2.时序差分(TD)算法

TD是对MC的改进，即agent走到第N步就可以开始回溯更新。

蒙特卡洛算法是什么？

蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。

与它对应的是确定性算法。蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算）等领域应用广泛。

使用蒙特·卡罗方法步骤：

1．使用随机数发生器产生一个随机的分子构型。

2．对此分子构型的其中粒子坐标做无规则的改变，产生一个新的分子构型。

3．计算新的分子构型的能量。

4．比较新的分子构型于改变前的分子构型的能量变化，判断是否接受该构型。

蒙特卡洛树是什么算法

蒙特卡罗树搜索(MCTS)会逐渐的建立一颗不对称的树。可以分为四步并反复迭代：

(1)选择

从根节点，也就是要做决策的局面R出发向下选择一个最急迫需要被拓展的节点T；局面R是第一个被检查的节点，被检查的节点如果存在一个没有被评价过的招式m，那么被检查的节点在执行m后得到的新局面就是我们所需要展开的T；如果被检查的局面所有可行的招式已经都被评价过了，那么利用ucb公式得到一个拥有最大ucb值的可行招式，并且对这个招式产生的新局面再次进行检查；如果被检查的局面是一个游戏已经结束的游戏局面，那么直接执行步骤4；通过反复的进行检查，最终得到一个在树的最底层的最后一次被检查的局面c和它的一个没有被评价过的招式m，执行步骤2。

(2)拓展

对于此时存在于内存中的局面c，添加一个它的子节点。这个子节点由局面c执行招式m而得到，也就是T。

(3)模拟

从局面T出发，双方开始随机的落子。最终得到一个结果(win/lost)，以此更新T节点的胜利率。

(4)反向传播

在T模拟结束之后，它的父节点c以及其所有的祖先节点依次更新胜利率。一个节点的胜利率为这个节点所有的子节点的平均胜利率。并从T开始，一直反向传播到根节点R，因此路径上所有的节点的胜利率都会被更新。

蒙特卡洛算法和拉斯维加斯算法

一、定义：

特卡罗是一类随机方法的统称。这类方法的特点是，可以在随机采样上计算得到近似结果，随着采样的增多，得到的结果是正确结果的概率逐渐加大，但在（放弃随机采样，而采用类似全采样这样的确定性方法）获得真正的结果之前，无法知道目前得到的结果是不是真正的结果。

拉斯维加斯方法是另一类随机方法的统称。这类方法的特点是，随着采样次数的增多，得到的正确结果的概率逐渐加大，如果随机采样过程中已经找到了正确结果，该方法可以判别并报告，但在但在放弃随机采样，而采用类似全采样这样的确定性方法之前，不保证能找到任何结果（包括近似结果）

二、场景举例

假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。

而拉斯维加斯算法，则是另一种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。

三、结论

•蒙特卡罗算法   

：采样越多，越近似最优解；

•拉斯维加斯算法：采样越多，越有机会找到最优解；

这两类随机算法之间的选择，往往受到问题的局限。如果问题要求在有限采样内，必须给出一个解，但不要求是最优解，那就要用蒙特卡罗算法。反之，如果问题要求必须给出最优解，但对采样没有限制，那就要用拉斯维加斯算法。

你也可以算出圆周率的 - 随机落点算法 - 致即将到来的圆周率日

一年一度的圆周率日就要到了，是的，就是3月14日，因为它与圆周率π的前几位3.14的数字一样。

我们知道，传说中祖冲之计算圆周率用的是“割圆术”的改进方法，可惜我们大多数现代人的脑子已经无法理解这种方法了。使用其他的复杂公式也有，但人的脑子更不容易理解，但有一个异想天开的方法你知道吗？任何人可以简单地去计算出Pi呢（下面我们都用Pi来代替圆周率π吧，好写好认，：p）。

这个方法源自概率论的基础，叫做蒙特卡洛法，形象一点的话我们也可以把它称为随机落点法，我们先说说它的原理：

我们先看看下面这张图

假设有图中的一个正方形和一个刚好套在它中间的圆形，可以很直观地看出：圆形的半径如果是R的话，正方形的边长就是2R。

圆形的面积根据公式是Pi乘以R的平方，也就是 Pi × R × R = PiR²

正方形的面积根据公式是边长的平方，也就是（2R）×（2R）= 4R²

把两个式子相除一下，可以很容易地推算出来，Pi = （圆形的面积 ÷ 正方形的面积）× 4

这样，就巧妙地把计算Pi值的问题转换成计算符合上面图中条件的圆形与正方形的面积之比的计算了。

这时候，概率论可以出场发挥作用了，以及有了计算机之后，我们有的“随机数”这个武器！

假设我们随机在正方形范围内画一个点，那么这个点有可能落在圆形之中，也有可能落在圆形之外；然后我们重复这个动作，从概率论上来说，如果进行无限多次，那么落在圆形中的点的个数与所有已经画的点的个数之比，就应该是圆形的面积和正方形的面积之比。看看下面这张图是不是就好理解了？

想想当里面的点数足够多的时候，就可以覆盖满整个原型和正方形。俗话说：“以点带面”，这时候就可以理解成无数多的点组成了圆形和正方形的面积。

好了，那么下面我们看看用计算机程序来实现这种方法计算圆周率的效果吧！我们这次选用Go语言（Golang）来实现这个算法，因为Go语言相对速度较快（比Python和Java等解释型语言要快得多），编写起来又比C语言更容易看懂。

这段程序的运行结果是：

可以看出来，计算出来的圆周率Pi值越来越接近于我们所熟知的数字：3.1415……

神奇吧，为什么说人也可以算出来呢？假想在地上用粉笔画一个那样的正方形和圆形，然后我们随性地往里扔沙包吧！很童真的画面吧？

蒙特卡洛方法的详细过程

在控制方面，蒙特卡洛方法就是通过大量随机过程，类似于穷举法，验证控制系统的性能，主要是检验系统的鲁棒性，比方说：PID控制器参数已经整定完毕，但是被控对象的参数在某个范围内发生变化，这时，将系统的输出，比方说调整时间和超调亮在坐标图上以点的形式画出，那么如果进行100次试验，就会在图上形成一百个点，如果这些点排列相对集中，那么系统的鲁棒性就相对较好，并且，如果这些点离坐标原点的距离都很近，那么，这个PID控制器的调节时间和超调量性能也就比较好，这是我在控制领域见到的一种蒙特卡洛方法的运用，在经济领域，蒙特卡洛也有运用，可以简化过去的算法，将积分变为直接的随机试验，这样可以降低系统的运行时间，提高效率。

文章标题：go语言蒙特卡洛算法,蒙特卡罗算法是什么算法的一种
路径分享：http://scpingwu.com/article/hciccp.html