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。
今天这篇推文通过两个小例子对蒙特卡罗方法做了一个入门介绍,蒙特卡罗方法在深度学习领域应用很广,值得大家进一步深入学习。
看完文章有收获?请转发分享给更多人
领取专属 10元无门槛券
私享最新 技术干货