让飞镖飞——蒙特卡罗算法入门

前几天Nature最新的论文介绍了Google的DeepMind团队的最新成果AlphaGo Zero, 抛开人类棋谱，不依赖人类监督，通过强化学习算法，从零开始学习如何下围棋。结果非常惊人，仅用四百九十万自我对局就在3天内赶超了去年3月份AlphaGo Master的水平，最终经过一个多月的训练，上千万的自我对局，完全碾压了AlphaGo Master.

然而，如此强力的AlphaGo Zero，和其前代AlphaGo Master以及Alphago Lee一样，仍然基于机器学习领域的经典算法——蒙特卡罗搜索树。

蒙特卡罗和拉斯维加斯

机器学习中的蒙特卡罗算法，实际上是某一类算法的统称。也就是说，蒙特卡罗不是一个特定的算法的名称，而是某类算法共有的一个特征的名称。

围棋的规则很简单，理论上计算机下围棋也很简单，只要把各种可能的下法及其后续变化都搜索一遍，然后选取一个最优的下法就可以。但实际上呢，AlphaGo以前的计算机围棋水平是很糟糕的。问题在哪里？围棋的棋盘太大了，搜索的空间和时间太恐怖了。

用数学的语言来说（放心，并不会有公式冒出来），围棋的下法是一个完全采样不可能问题。因此只能使用针对不完全采样的随机算法。既然采样不完全，那就不能保证找到的解是最优解，只能尽力去找最优解。

那么，如何尽力去找最优解呢？有很多很多的策略和算法。总的来说，这些策略和算法可以分成两类：

采样越多，找到的解越接近最优解。

采样越多，找到最优解的概率越大。

前者称为蒙特卡罗算法，后者称为拉斯维加斯算法。这两个名字来源于两个著名的赌城，因为不完全采样的随机算法，就是在赌自己能在有限的采样次数内命中最优解或者足够接近最优解的解。

赌城夜景

为了帮助理解，下面我们讨论下如何用随机算法找对象的问题。

童话故事里，公主最后总是能和世界上最优秀的王子一起过上幸福快乐的生活。但是，童话故事里的公主，很少积极地去找王子，她只是在那里静静地等待剧情的发展。但是，正如光良的歌唱的那样“童话里都是骗人的”。如果没有剧情推动，公主真的想找世界上最优秀的王子共度余生的话，那她就得将所有王子全部搜索一遍，也就是完全采样取最优解。实际上，如果是在童话故事里，这个采样还不一定完全，因为有的王子可能被变成青蛙之类的生物了，说不定那个青蛙才是最优解。

如果用随机策略找王子的话，那公主就可以先和第一个碰到的王子谈恋爱，然后每碰到一个王子，就和正在恋爱的王子比较一下，如果比现有的对象优秀，就换一个王子，否则就保留现有的王子。这个算法，就具有蒙特卡罗特征，是一种蒙特卡罗算法。其实现实中有些人相亲就使用这个策略，只不过他们不知道这个名称而已。

现实中大概极少有人用拉斯维加斯算法找对象。小说里倒可以找到这样的例子。《天龙八部》中天山童姥为了躲避死对头李秋水的追杀，和虚竹躲藏在西夏皇宫的冰窖里。期间天山童姥为了让虚竹破戒，找来一名一丝不挂的妙龄女子放在虚竹身旁，虚竹终于破了淫戒。女子睡梦中被掳来，开始还以为自己在做梦，后来与虚竹互称梦姑梦郎。虚竹对梦姑的身份和外貌（冰窖里很黑）一无所知，后来要找这个梦姑，用蒙特卡罗算法就完全没用，因为虚竹要找的是梦姑本人，而不是一个和梦姑足够接近的女子。这种情况下，虚竹就得用拉斯维加斯算法——每碰到一个年龄相仿的女子，就搂在怀里感受一下。搂抱的女子越多，就越有可能找到梦姑。

AlphaGo下围棋使用蒙特卡罗算法，而不是拉斯维加斯算法，读者可以想一想这是为什么。

蒙特卡罗飞镖

看起来蒙特卡罗算法好像很简单，甚至有点无脑。但是，计算机本身就是一个无脑的设备。计算机不缺“蛮力”。所以，蒙特卡罗算法对于解决某些问题非常好用。

最经典的例子就是用蒙特卡罗算法计算圆周率π.

如何计算π？

我们知道π可以定义为圆周长和半径的比值，也可以定义为圆面积和半径的比值。半径可以直接测量，那么，我们只需要设法求出圆周长或者圆面积，就可以知道π的值了。

圆周长怎么算？最容易想到的办法就是用正多边形去逼近，也就是祖冲之用的“割圆术”。

圆面积怎么算？当然也可以参照“割圆术”的思路，用正多边形的面积去逼近。但是，我们也可以换一条思路，用蒙特卡罗算法来算。

我们以圆心为中心，以圆直径（2r, r为圆半径）为边长，作一个与圆相切的正方形。这个正方形的面积很好算

那么，如果我们能求出圆面积和正方形面积的比值，我们就能知道圆面积。

如何求出圆面积和正方形面积的比值呢？答案很简单：扔飞镖。蒙上眼睛乱扔（随机），扔啊扔，一天接一天地扔，或者找很多人来扔，扔够n个飞镖（n是一个比较大的数字，比如10000），数数看有多少飞镖命中了正方形内部的圆。假定有m个飞镖命中，那面积之比就是m/n.

由此，我们得到圆面积：

代入圆周率的定义，我们得到π的值为：

如果是用计算机来“扔飞镖”，那就可以直接生成一对随机数来表示一个正方形内的一个点，然后计算一下这个点与圆心的距离判断是否命中。同时，计算机“扔”起来可比人快多了。

大家可以运行一下上面的代码，看看和π的标准值偏差多少。也可以修改一下numDarts的值，看看估算的结果会有什么差别。

将这个方法推广一下，我们可以计算任意不规则图形的面积。微积分公式忘了？没关系，让飞镖飞一会！

大刘的《三体》里有一段，就是书中的角色魏成介绍蒙特卡罗算法：

那是一种计算不规则图形面积的计算机程序算法，

具体做法是在软件中用大量的小球随机击打那块不规则图形 （中略）

这种方法虽然简单，却展示了数学中的一种用随机的蛮力对抗精确逻辑的思想方法，

一种用数量得到质量的计算思想。

这就是我解决三体问题的策略。

结语

春秋时期《论语·阳货》云：“不有博弈者乎？”这里的“弈”为围棋，已和赌博联系在一起。其实围棋在古代一直是常用的赌博工具。宋洪迈《夷坚志》就记载了范端智与杨太傅的姬妾赌资高达三千缗金币的棋局。《红楼梦》里也记载了宝钗、香菱、莺儿之间下围棋赌博的事。近代以来，围棋渐渐脱离了赌博工具的色彩，而围棋的人工智能，却基于受赌博启发的蒙特卡罗算法，也算是一个有趣的巧合。