以赌城命名蒙特卡洛算法到底有多神奇?

   “人机大战”虽已落幕,但热度依然不减,有专家表示,AlphaGo的胜利只能说是算法的胜利。据悉,AlphaGo主要使用了深度学习+强化学习+蒙特卡洛树搜索,而“蒙特卡洛”算法成为隐藏的“撒手锏”之一。在AlphaGo问世之前,计算机与人类的棋类比赛中,蒙特卡洛这一算法同样发挥着重要作用。那么,这一算法到底有何神奇之处?

以赌城命名的概率算法

  据了解,蒙特卡洛算法问世由来已久,很早就被人们发现和利用。东南大学物理系教师白羽告诉记者,20世纪40年代美国在第二次世界大战中参与研制原子弹的“曼哈顿计划”的成员乌拉姆和冯·诺伊曼首先提出蒙特卡洛方法。数学家冯·诺伊曼更是用摩纳哥的赌城Monte Carlo来命名这种方法,为它蒙上了一层神秘色彩。

  不过在此之前,蒙特卡洛算法就已经存在,1777年,法国布冯提出用投针实验的方法求圆周率,这被认为是蒙特卡洛算法的起源。

  白羽表示,蒙特卡洛算法是一种“随机化”的方法,名字来源于赌城,是因为赌博中体现了许多随机算法,所以借以命名。“比如,可用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见,而是通过对选民进行小规模的抽样调查来确定可能的优胜者,其基本思想是一样的。”

  “其实,一把黄豆就可以完成蒙特卡洛算法。”白羽告诉记者,比如在广场上画一个边长一米的正方形,在正方形内部随意用粉笔画一个不规则的形状,现在要计算这个不规则图形的面积,怎么计算呢?蒙特卡洛算法告诉我们,均匀地向该正方形内撒N个黄豆(N是一个很大的自然数),随后数数有多少个黄豆在这个不规则几何形状内部,比如说有M个,那么,这个奇怪形状的面积便近似于M/N,N越大,算出来的值便越精确。在这里我们假定黄豆都在一个平面上,相互之间没有重叠,而且是均匀撒出。

“抢红包”就用到了蒙特卡洛算法

  说了这么多,这种算法到底有何魔力?白羽告诉记者,就蒙特卡洛算法本质而言,是用类似于物理实验的近似方法求解问题,它的魔力在于模拟,“模拟真实的实验场景,然后可以研究进行中的实验到底会发生什么。蒙特卡洛需要巨量的计算资源,不仅仅因为处理问题有多复杂,另一方面它需要很大的统计量,统计量越大结果则越精确。”

  不过,现实生活中的问题要比实验室中复杂得多。比如金融衍生产品(期权、期货、掉期等)的定价及交易风险估算,问题的维数(即变量的个数)可能高达数百甚至数千。对这类问题,传统的数值方法难以对付(即使使用速度最快的计算机)。蒙特卡洛算法则能很好地用来对付维数,因为该方法的计算复杂性不再依赖于维数,可以基于随机仿真的过程给出近似的结果。以前那些本来是无法计算的问题现在也能够计算出。

  目前,蒙特卡洛算法在金融工程学、宏观经济学、生物医学、计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。

  那么,日常生活中人们是否接触到这么“高大上”的算法?“有没有发现微信抢红包时,你抢到的金额都是随机发放的,这些随机金额怎么生成的,这其中就运用到了蒙特卡洛算法。”白羽告诉记者,生活中一些生成随机数领域,多运用到蒙特卡洛算法。

计算机对弈的“撒手锏”

  蒙特卡洛算法和计算机棋类游戏颇有渊源。可以说,计算机在棋类游戏中“精进”得益于蒙特卡洛算法的不断发展。

  不像五子棋等简单棋类游戏,国际象棋和围棋这样的复杂棋类,从初始盘面出发穷尽所有变化的复杂度(也称穷举复杂度)更是大得难以想象。信息论创始人克劳德·香农在1950年曾第一个估计出国际象棋的穷举复杂度大概在10120种变化左右,具体数字被后人称为“香农数”。而围棋的穷举复杂度又远远超出国际象棋,达到了惊人的10360。

  有人会问,有没有可能存在一个高效的算法,可以在棋面呈指数级增长状况的同时,仍然对当前盘面做出准确评估呢?

  于是,蒙特卡洛算法开始被应用于围棋盘面评估。专家表示,每个围棋盘面都有一个“最优值”,对于围棋已经证明,计算这个最优值的时间至少随该盘面到终盘之间的步数呈指数级数增长(平均200步,每步平均增长200倍数量的可能盘面),从理论上是无法得到最优值。那么,可不可以根据蒙特卡洛思想对整个可能性空间进行某种采样,然后通过统计估值的方法逼近这个最优值呢?人们对这个问题的思考在2006年终于取得了突破性进展,提出了一种称为蒙特卡洛树搜索的动态评估方法。在围棋弈棋系统的实践中,蒙特卡洛树搜索在比赛时间受限的情况下确实表现出远远超过传统方法的棋力。

  不过,虽然“蒙特卡洛树搜索”方法在此前一些弈棋程序中有采用,在相对较小的棋盘中能够很好地发挥作用,但在正规的全尺寸棋盘上,这种方法的缺陷也体现出来了,因为涉及的搜索树实在太大了。最近几年人们开始在空间选择策略中加入更多和围棋相关的专家知识,使得基于蒙特卡洛树搜索的围棋弈棋系统水平不断提高。

  此次AlphaGo则采用了更聪明的策略,即利用深度学习的方法降低搜索树的复杂性。因此“深度学习”和“蒙特卡洛树搜索”就成为它的两个关键因素,在每个模拟游戏中,AlphaGo都有两个大脑指引它进行搜索:价值网络和政策网络。“政策网络”观察棋盘布局企图找到较好的下法,“价值网络”则预测这样下的话对方棋手赢棋的可能。结合这两个建议,AlphaGo最终决定了怎样落子才是胜算最大的。

20世纪十大算法

  本世纪初,美国物理学会和IEEE计算机社团的一本联合刊物《科学与工程中的计算》发表了由田纳西大学和橡树岭国家实验室两位专家联名撰写的“世纪十大算法”一文,该文“试图整理出在20世纪对科学和工程领域的发展产生最大影响力的十大算法”。两位作者苦于“任何选择都将是充满争议的,因为实在是没有最好的算法”,他们只好用编年顺序依次列出了这十项算法领域人类智慧的巅峰之作——给出了一份算法排行榜。有趣的是,该期杂志还专门邀请了这些算法相关领域的“大拿”为这十大算法撰写十篇综述文章,这十大算法依次为:

1.1946年,计算蒙特卡洛过程度伦敦算法;

2.1947年,单纯形法;

3.1950年,Krylov子空间迭代法;

4.1951年,矩阵计算的分解方法;

5.1957年,优化的Fortran编译器;

6.1959-1961年,计算矩阵特征值的QR算法;

7.1962年,快速排序算法;

8.1965年,快速傅立叶变换;

9.1977年,整数关系探测算法;

10.1987年,快速多极算法。