白话蒙特卡罗算法

1997年，机器人“深蓝”首次在人机对抗中击败等级分排名世界第一的国际象棋大师——卡斯帕罗夫，赛后IBM宣布“深蓝”退役。当时很多人都说电脑下围棋是不行的，毕竟机器下棋的本质都是搜索树，围棋的搜索树树宽有几百，而国际象棋只有几十。

机器下棋主要依靠两方面：一是人工智能，二是海量计算。但是在有限的时间内想要遍历这么宽的树，只能牺牲深度，往后少看几步。深蓝重达1270公斤，有32个微处理器，1997年的深蓝可搜索及估计随后的12步棋（人类象棋好手大约可以往后估算10步），即便是今天计算机的运行速度仍然不可能遍历围棋搜索树。

围棋是一种依赖于远见的游戏，不同于往后看“几步”的象棋。所以，要想保证搜索深度，就只能放弃遍历，改为随机采样——这就是为什么在没有MCTS（蒙特卡罗搜树）类的方法之前，机器围棋的水平几乎是个笑话。

蒙特卡罗算法最早在人工智能领域崭露头角是2012年DeepZenGo与武宫正树的四子局中，我们先来看一看这样一步。

白53大飞，威胁黑棋右边一块。DeepZenGo竟然非常大方地弃掉了右下角。白棋吃掉右下虽然大有所得，但黑棋通过弃子把中腹走厚，还是有不小的优势。白61扳的时候，DeepZenGo非常机警，黑棋直接抱吃中央一子，白棋还是没有机会把局面引向混乱。DeepZenGo敢于舍弃眼前这么大的利益，我们可以认为其搜索深度已经达到人类专业棋手的水平。

当然随着人工智能的发展，2017年5月柯洁0:3负于阿尔法狗，陈耀烨、时越、芈昱廷、唐韦星、周睿羊5名棋手组团“群殴”阿尔法狗，结果还是输了。

今天我们就一起走进让DeepZenGo击败武宫正树的蒙特卡罗算法。蒙特卡洛算法的理论基础是大数定律，大数定律是描述相当多次数重复试验的结果的定律，根据这个定律可知，样本数量越多，其平均就越趋近于真实值。蒙特卡洛的基本原理可以简单描述为先大量模拟，然后计算一个事件发生的次数，再通过这个发生次数除以总模拟次数，估计计算结果。

01

计算圆周率

接下来我们通过一个计算圆周率的例子来说明蒙特卡罗的使用过程。

Step1：取四分之一单位圆和单位正方形；

Step2：生成(0,1)之间均匀随机分布实数对，向正方形投点；

Step3：建立投点n次，投入圆内m次，则有

从这张动图我们可以看出，随着迭代次数增加，投点次数n由10次增加至1000次，绝对误差不断减小，但是因为投点次数较少，误差减小趋势并不明显，接下来我们继续增加投点次数来观察绝对误差的变化趋势。

通过上面这个例子，我们可以将蒙特卡罗算法的步骤归纳为：

Step1：描述或构造概率过程：对于确定性问题，构造概率过程；对于随机问题，描述概率过程；

Step2：利用概率分布抽样：通过计算机产生已知概率分布的随机变量；

Step3：建立估计量：确定一个随机变量，作为所要求问题的解，一般是把多次随机抽样结果的算术平均值作为解的近似值；

计算定积分

02

接下来，我们按照上述步骤，看一个蒙特卡罗在计算定积分中的例子，计算

Step1：构造概率过程：阴影部分与长方形面积比为I/5；

Step2：概率分布抽样：按均匀分布随机投点到长方形；

Step3：建立估计量：I 约为投点落到阴影部分频率乘以5。

今天这篇推文通过两个小例子对蒙特卡罗方法做了一个入门介绍，蒙特卡罗方法在深度学习领域应用很广，值得大家进一步深入学习。

看完文章有收获？请转发分享给更多人