算法快速模拟一卷加载骰子

随机数的快速高效生成一直是一个重要的挑战。几个世纪以来，碰运气的游戏都是靠掷骰子、抛硬币或洗牌来增加游戏的随机性。在20世纪下半叶，计算机开始接管这个角色，用于密码学、统计学和人工智能，以及各种模拟——气候、流行病学、金融等等。

麻省理工学院的研究人员现在已经开发出一种计算机算法，这种算法至少可以在某些任务中，以目前可用的速度、精度和低内存要求的最佳组合大量输出随机数。该算法被称为快速加载骰子滚轮(FLDR)，由麻省理工学院的研究生Feras Saad、研究科学家Cameron Freer、Martin Rinard教授和首席研究科学家Vikash Mansinghka发明，并将在下周的第23届人工智能和统计国际会议上展示。

简单地说，FLDR是一个模拟掷骰子产生随机整数的计算机程序。骰子可以有任意数量的边，它们被“加载”或加权，以使某些边比其他边更可能出现。一个加载的骰子仍然可以产生随机数——因为人们无法提前预测哪边会出现——但随机性受到约束，必须满足预先设定的概率分布。例如，可以使用加载的骰子来模拟棒球比赛的结果;尽管胜券在握的一方更有可能获胜，但在某一天，任何一方都有可能最终取得胜利。

使用FLDR，骰子被“完美地”加载，这意味着它们准确地实现了指定的概率。例如，对于一个四面的骰子，我们可以安排数字1、2、3和4的出现正确率分别为23%、34%、17%和26%。

为了模拟有大量边的已加载骰子的滚动，麻省理工学院的团队首先必须利用一种更简单的随机性来源——这是一种计算机化的(二进制)掷硬币的版本，结果要么是0，要么是1，每一个都有50%的概率。他们的方法是一个关键的设计标准，其效率取决于他们必须利用这个随机源的次数——换句话说，“掷硬币”的次数——来模拟每个骰子的滚动。

在1976年发表的一篇具有里程碑意义的论文中，计算机科学家唐纳德·克努斯(Donald Knuth)和安德鲁·姚(Andrew Yao)设计了一种算法，可以以理论上可以达到的最大效率来模拟已加载骰子的滚动。“虽然他们的算法在时间方面是最高效的，”Saad解释说，这意味着没有什么东西可以比它更快，“但在存储信息所需的空间或计算机内存方面是低效的。”事实上，所需的内存数量呈指数级增长，这取决于骰子的边数和其他因素。他说，这使得Knuth-Yao方法变得不切实际，除非在特殊情况下，尽管它在理论上很重要。

FLDR是为更大的实用性而设计的。萨阿德说:“我们的时间效率几乎是一样的，但就记忆效率而言，要好几个数量级。”FLDR可以比Knuth-Yao方法节省10,000倍的内存存储空间，而每次操作所花费的时间不会超过1.5倍。

目前，FLDR的主要竞争对手是别名方法，别名方法几十年来一直是该领域的主导技术。Freer认为，从理论上分析，FLDR与Alias相比有一个明显的优势:它比Alias更有效地利用随机源(“抛硬币”)。此外，在某些情况下，FLDR生成加载骰子卷的速度也比Alias快。

当然，FLDR仍然是一种全新的技术，还没有得到广泛的应用。但它的开发人员已经在考虑通过软件和硬件工程来提高它的效率。除了普遍存在的随机数需求之外，它们还有特定的应用。Mansinghka认为，FLDR的最大帮助是提高所谓的蒙特卡罗模拟和蒙特卡罗推断技术的效率。正如FLDR使用抛硬币来模拟更复杂的多面加权骰子一样，蒙特卡罗模拟使用骰子来生成更复杂的随机数模式。

例如，联合国对地震活动进行模拟，显示全球何时何地发生地震、震动或核试验。联合国还进行蒙特卡罗推断:运行随机模拟，为实际地震数据产生可能的解释。这是通过进行第二组蒙特卡罗模拟来实现的，这些模拟随机测试了底层地震模拟的备选参数，以找到最可能重现观测数据的参数值。这些参数包含关于地震和核试验可能实际发生的时间和地点的信息。

Mansinghka说:“蒙特卡罗推理需要的随机数比蒙特卡罗模拟多出几十万倍。”这是FLDR可以真正帮助解决的一个大瓶颈。蒙特卡罗模拟和推断算法也是概率编程的核心，概率编程是人工智能的一个新兴领域，有着广泛的应用。”

谷歌的研究主任Ryan Rifkin看到了FLDR在这方面的巨大潜力。“蒙特卡罗推理算法是现代人工智能工程的核心……也是大规模统计建模的核心，”里夫金说，他没有参与这项研究。“FLDR是一个非常有前途的开发，它可能会导致加速随机数生成的基本构建块的方法，并可能帮助谷歌使蒙特卡罗推断显著更快和更节能。”

尽管FLDR的未来看起来很光明，但它几乎没有被发现。麻省理工学院的四名研究人员在1月份的一次研讨会上发表了一篇论文，介绍了一种单独的算法。在工作中,作者表明,如果一个预先确定的数量的内存被分配给一个计算机程序模拟卷的骰子,他们的算法可以确定最少的“错误”可能——也就是说,距离就向会议指定为每个骰子的概率。

如果不提前限制内存，错误可以减少到零，但是Saad注意到一个零错误的变体使用了更少的内存，速度也几乎一样快。起初，他认为这个结果可能太微不足道了。但他向弗里尔提到了这一点，后者向萨阿德保证，这条路值得走下去。在同样的方面，FLDR是没有错误的，它起源于那些卑微的起源，现在有机会成为随机数生成领域的领先技术。考虑到我们生活在一个很大程度上由随机过程控制的世界，这不是一件小事——这一原则适用于宇宙中星系的分布，也适用于激烈的骰子游戏的结果。