« 新的名片 | 返回首页 | 马上启程去北京了 »

随机数有多随机?

作为一个常识,每个程序员在做入门学习时,都会被老师谆谆教导:我们用的编程语言中的随机函数,只能产生出伪随机数。它有它的内在规律,只能作为对显示世界的随机事件的近似模拟。接下来,我们通常会被传授随机种子的概念。以及用物理上更随机的量做种子。比如系统时间、两次敲击键盘的时间间隔、多次移动鼠标的偏移、甚至系统出错的出错信息码等等。

作为游戏数值策划,除了加减乘除,用的最多的数学概念恐怕就是随机数了。有经验的数值策划或许从他的前辈那得知计算机中程序产生的随机数并不太可靠;或者他本身就受过程序方面的训练。如果游戏项目更幸运一点,担当数值策划的他是一个数学爱好者,并读过诸如《计算机程序设计艺术》这样的技术书籍,那么事情会好的多。可惜大多数境遇下,策划们从不深究计算机随机数背后的细节,也不太关心所谓“伪”随机数究竟“伪”到什么程度。

最近几天,有测试人员向我抱怨,我们游戏中某些概率设定总感觉有点怪怪的。似乎跟文档上的不同。

这种抱怨并不少见,许多网络游戏玩家都在抱怨系统生成的随机数不太对劲。善良点的玩家会归咎到自己的 RP 上,阴谋论者则指责系统作弊。运营着的游戏背后,数值策划和程序员们有苦说不出。

有必要科普一些数学常识,也作为我周末读书的一些笔记。

鉴于我所接触过的多数游戏策划大多没有很高的数学素养(这里用于对比的参照物——我自己,在数学方面的修养已经够差了),下面不列公式,只列常识。如果涉及一些数学上的结论,也回避证明过程。

以扔硬币为例来看概率:

如果硬币本身没有问题,那么每次实验的结果,正面和反面的出现概率理应一致,都是 50% 。

btw ,如果碰巧连丢了 10 次都是正面的话,认为第 11 次出现反面的概率更高的读者可以不必看下去了。根据基本的概率理论,作为独立实验,相互间是不会造成概率影响的。无论前面出现多少次正面,下一次正面的概率依旧是 50% ,不会多也不会少。当然,如果是现实中出现这种情况,我会认为是道具本身出了问题,或许这个硬币两面都是正面。这样的话,第 11 次倒是极有可能再次出现正面。

对独立的随机事件的单次预测做不到准确,但却可以从统计上得到一个稳定的数值。我们知道,大量做丢硬币的实验 n 次。随着 n 的增大,出现正面和反面的次数会趋与一致。

OK ,以上都是作为一个游戏数值策划应该具有的常识。只是人们往往忽略了一点:若是正面和反面在多次实验中出现次数严格一致的话,又反过来是一件小概率事件。例如:丢一万次硬币,正好出现 5000 次正面的概率大概不会比你买彩票中个小奖的概率高多少。


补充:

在 10000 次一组的丢硬币的实验中,正好出现 5000 次正面的概率依旧是比所以其它情况概率更大一些的。其它情况可能是 10000 次 …… 5001 次、4999 次、4998 次 …… 甚至零次正面。

正好出现 5000 次正面有最大的可能性,但是绝对概率却不大(也不算太小)。

前段时间写过一篇 blog 谈到了用交换法洗牌 ,那篇文章中提及的一篇论文的结论谈到:

“当 N 大于等于 18 时,用这个方法洗牌后,居然恒等排列(identity permutation)是最有可能出现的。(所谓恒等排列大概是指第 n 张排在第 n 个位置)”

这句话很容易被人误解。概率最大并不等于很容易出现,正如 10000 次丢硬币刚好出现 5000 次正面不易出现一样。


如何看一个均匀分布的随机数发生器产生的数值到底随机不随机,简单的用统计产生出来的数字的分布是否接近均等是远远不够的。接下来介绍一下统计学中最著名的 χ 方检验。

假设我们投一个六面骰。每次 1 ~ 6 的点数出现的概率均为 1/6 。如果用计算机来模拟它,采用函数 random (1,6) 来产生一个 1 到 6 之间的随机整数。怎样判断产生的数字够不够随机呢?

我们可以投 n 次(n 很大,比如 n=10000 ),统计出每个点数出现的次数:Y1,Y2,Y3,Y4,Y5,Y6 。理想的次数则都应该接近于 p=n/6 次。

取 V=(Y1 - p)^2 / n + (Y2 - p)^2 / n + (Y3 - p)^2 / n + (Y4 - p)^2 / n + (Y5 - p)^2 / n + (Y6 - p)^2 / n

划简后 V=6/n * ( Y1 到 Y6 的平方和) - n

这个 V 即量化表示了这 n 次实验反应出来的数字随机性。当 V 过大时,骰子可能偏向某几个特定点数更多一些。而 V 过小的话,则可能是随机数发生器有一些明显的规律(事实上,所有伪随机数产生算法都是一定有规律的)。

我们现在需要知道的是,对于一个随机数列,什么样的 V 是比较合理的。对于用随机数做骰子的实验,V 的值也是随机的,当然不是均匀分布。实际上它符合 χ 方分布。如果我们投骰子用的随机数是真正的均匀分布的话,V 值出现特别小或特别大的概率都很小。

实际上,在这个六面骰的例子中,V 有 1% 的可能小于 0.5543 ,有 5% 的可能小于 1.1455 ,有 25% 的可能小于 2.675 ,有 50% 的可能小于 4.351 ,有 75% 的可能小于 6.626 ,有 95% 的可能小于 11.07 ,有 99% 的可能小于 15.09 。

我实验了 gcc 3.4.2 的 libc 中带的随机函数去模拟六面骰。做了五组实验,每组分别为 2000, 4000, 6000, 8000, 10000 次。得到的 V 的值分别为:

9.088 3.371 6.432 15.805 1.7204

注:我使用了系统时间做种子,每次做此实验都会得到不同结果,本质上这些值也是随机的。

每组次数不同是因为:伪随机数列往往具有一定的周期性,当不知道它的周期特性时,n 选的不合适可能导致多段非随机带有某中倾向性的区间相互抵消其影响。

我们再次分析上面得到的五个数据,若随机数真的随机,他们出现的概率大约落在这样五个区间75%~95%) ,(25%~50%) ,(50%~75%),(99%~100%),(5%~25%)

表现不太坏,但也不算好。尤其是第四组实验数据,V=15.805 ,这是个很大的值。因为 V 值本应有 99% 的概率小于 15.09 ,所以出现这个值的概率应该只有不到 1% 。当然这也可能是个巧合(1% 的事件发生并不算太奇怪)。我后来又反复取不同的 n 测算了几次,有一次 V 又小于了 0.55 ,这也不太正常(也只有不到 1% 的可能性)。

最后,我的结论是:我用的 gcc 这个版本的 rand 函数不算很好。至少不能应用于极端要求随机性的场合。它对大量模拟六面骰这件事情上做的不太成功。

ps. 关于 χ 方分布的选定的百分值,可以参考《计算机程序设计艺术 第二卷 半数值算法》的 P39 页。上面我摘取的第五行。因为这里六面骰的点数分布有五个自由度(第六种点数的出现次数可以用其它五种出现次数推算出来)。


前几天写过一篇 blog ,里面随手举了个例子:游戏设计人员设计了一个 10 万分之一的凋落率 。一个做策划的朋友在 gtalk 上问我,这并不是个复杂的问题呀。难道有什么玄机?

按这个朋友的思路,产生两次随机数就够了,一次 random(1,1000) 一次 random(1,100) ,只有两个数值都为 1 时,这个十万分之一个小概率事件才发生。

不错,理论上是这样,实际我们大多也这样的。而且很高兴看到,作为一个数值策划,他回避了直接用 random(1,100000) 。有编程常识的兄弟们都知道,大多数语言提供的标准数学函数库中不提供十万分之一级别精度的随机函数。

但是精度问题依然存在。我反过来问如果产生一个十万分之七的随机数时,他出现了一点小失误:random(1,100) * random(1,1000) <=7 是不对的。当然这个小错误很容易被修正。

实际应用中,更为正确的做法是回避直接使用高分辨率的随机数列。因为通常所用的线形同余序列产生的伪随机数列都不适用(道理很简单,每个随机数的精度要求提高意味着伪随机数列的周期变短,过短的周期性必然带来随机性的丧失)。如果真的有这类需求,我们应该让程序员去专门写一个了。

不光是这种超高精度随机数的需求应该尽量被回避。单次随机量的自由度也最好被限制。计算机模拟丢硬币总比模拟投六面骰看起来要真实一些。而模拟六面骰又好过二十面。用固定面数的骰子模拟出来,也比数值设定时八卦一个百分比概率要强。

原因并非完全源于它们需要的精度不同。更重要的是自由度小一些的随机量,更容易被统计方法检验是否合理。一旦程序产生的伪随机数随机性被检验出来不太好,我们总有机会去尝试一个更好的,不是吗?

最后推荐一个随机数发生器:http://www.agner.org/random/

Comments

暴雪的工程师们很喜欢伪随机数

V = [(Y1^2 + Y2^2 + ... + Y6^2) / n] - P

取 V=(Y1 - p)^2 / n + (Y2 - p)^2 / n + (Y3 - p)^2 / n + (Y4 - p)^2 / n + (Y5 - p)^2 / n + (Y6 - p)^2 / n

划简后 V=6/n * ( Y1 到 Y6 的平方和) - n
"划简"是错别字,应该是"化简",另外结果是不对的,化简结果应该为:
V = [(Y1^2 + Y2^2 + ... + Y6^2) + 6P^2 -2P(Y1 + Y2 + ... + Y6)] / n
V = (Y1^2 + Y2^2 + ... + Y6^2) + nP - 2nP] / n
V = [(Y1^2 + Y2^2 + ... + Y6^2) / n] - P

随机数确实是个相当深的话题!

留言和文章一样精彩

我研究宇宙的,很荣幸能来到你的空间。留个脚印!

解决了我的疑问,谢谢!
对于判断随机数质量的好坏,我的疑问正好可以用得上:
反复掷硬币,记录连续出现正面的次数(2~n), 并记录下一次是否出现反面。检查随着连续出现同一面次数的增大,下一次出现反面的概率是否稳定在 50%。

另外,小概率掉落我觉得可以用多次连乘来解决,逻辑跟Diablo稀有物品的掉落相似。例如万分之一的掉落可以是(1/50)*(1/200),先检测物品类型再检测稀有度,分两步甚至多步来实现掉落

'VBA随便写了个,基本能计算出“掷硬币100次出现45次正面的几律是多少”这种问题。

'排列组合公式
Function FP(m, n)
FP = m
For j = 1 To n - 1
FP = FP * (m - j)
Next j
End Function
Function FC(m, n)
FC = FP(m, n) / FP(n, n)
End Function

Private Sub 计算_Click()

p = Sheet4.Cells(2, 2)
k = Sheet4.Cells(4, 2)

'清空区域单元格
Range("A8:B158") = ""


'输出结果
Sheet4.Cells(8, 1) = "成功0次几率"
Sheet4.Cells(8, 2) = (1 - p) ^ k

For i = 1 To k
Sheet4.Cells(8 + i, 1) = "成功" & i & "次几率"
Sheet4.Cells(8 + i, 2) = (1 - p) ^ (k - i) * p ^ i * FC(k, i)

If Sheet4.Cells(8 + i, 2) < Sheet4.Cells(8 + i - 1, 2) And Sheet4.Cells(8 + i, 2) < 0.00005 Then
Sheet4.Cells(8 + i + 1, 1) = "下面几率皆约为0.00%"
Exit For
End If

Next i

End Sub

“例如:丢一万次硬币,正好出现 5000 次正面的概率大概不会比你买彩票中大奖的概率高多少。”

你买的是什么彩票啊,大奖的中奖概率这么高......
------------------------------------------
看来这位仁兄也没看懂的样子

所谓随机,随成什么样子呢....最近的活动不是出问题了么,好象是用winhex读到了内存,一个人连续搞了好多蛋蛋.怎么样随机都比不过select and update来的快吧,人的问题比程序的问题难解决的多吧.

当年我在做游戏的时候也花过几天时间研究这个问题,也买了那卷半数值算法看过,记得有十几二十个检验的方法,本想写程序试验一下,发现有个segma函数的定义是引用第一卷的,而当时我没买第一卷。。。到现在都没买。。。现在也不做游戏了-_-|||

我老板之前做的测试,看看你是否用的上。

http://www.csis.hku.hk/cisc/projects/va/main.html

数学上来说,概率(值)实际上是经过大量的随机实验获得的一个数值。譬如说中奖几率是1/2。当有人告诉你中奖的几率是1/2,虽然有具体的数值,可是这个数值是无法令人完全相信的。不像“我给你0.5元”,0.5元就是一个很明确的数或者东西。因此,概率实际上是一个量化了的经验。它可以帮助别人去预测,但是误差的大小,就与统计方法有关。
然而概率却为什么与随机数搅和在一起?这实际上与计算机模拟有关。高等数学概率论只是对(现实世界)已经发生的随机现象做研究并拓展建立起来的学科,它并没有告诉我们怎么用数值方法来模拟这些已经发生了的随机现象——这是一门新的学科《随机过程》。其实可以这样说,现实世界就是由不断发生的随机事件组合而成的。
譬如“掷骰子”,计算机里面怎么模拟这件普通得不能再普通的生活现象?(这个曾经是网易招聘数值策划的一道考题,用来帮助策划们理解概率和随机数)于是随机数应运而生。在《程序设计与艺术》第二卷《半数值算法》的第一章中,我们知道产生随机数的算法是一个数集到这个数集本身的映射,并且有周期,且周期就是这个数集的维度;其实我们可以有理由认为,在这个维度范围内,某种方法产生的随机数就是符合要求的真随机。譬如游戏的活动中,要设计一个物品的掉率是1/10000,如果活动下来,参与的人次有10000次,这时最精确的方法应该是从[1,10000]中选1,而不是[1,100]中选两次并且两次都是1。
当然,如果更复杂的理论可以参考概率论和随机过程等相关书籍。这远比我们随便说说来得严谨。

泊松分布的推导看我原来写的一篇吧,我觉得不算复杂的 :)

http://blog.codingnow.com/2007/09/poisson_distribution.html

学而时习之 不亦说乎

学了一些概率,到现在为止,自己也说不出那些指数分布,泊松分布...是怎么来的,后来问了专门研统计的同学,他说也不知道,只知道怎么用;至于<计算机程序设计艺术>中作者的那些概率分析的妙用,心里着实痒痒的,可是自己用来分析一个也分析不出,呵呵,我还没有入门

云风的数学素养至少比我强……但是看了又很有感悟。那么只好说说计算机技术了。

gcc和libc是两回事~libc一般都是系统带的。gnu也有libc,叫glibc。所以随机数算法出问题,是一类系统出问题,而不是一类编译器编译的程序出问题。

/dev/random和/dev/urandom,各个系统实现不一样。
BSD系列,包括Mac OS X,都是伪的
Linux下则有/dev/random是真的——不过它不是什么时候都出随机数的,可能读挂起。这个的信息学原理是有个熵池……呃,不懂……

"Unix 里面有一个系统的随机数发生器 /dev/random ,是收集设备噪声来产生的,是真随机数。"

应该是伪随机数序列,只要达到一定要求就可以称为随机了。楼主不是说了吗,参考《计算机程序设计艺术 第二卷 半数值算法》。

生成一个任意长随机数,完全凭借物理现象是很难的,现有的伪随机生成器(PRNG)试图解决的就是这个问题,即从一个短的真随机0/1序列扩展到一个任意长的伪随机0/1序列。这个起始的真随机序列一般是通过物理方法得到,在普通计算机中可以由OS采集设备噪声来得到,一般可以认为是真随机。假设one-way function的存在(这一假设是密码学的基石),PRNG在理论上已经被构造出来,而在实际中也有很多足够好的算法被提出。当然,算法或者实现都可能出现这样那样的问题,近几年有一些paper就是分析windows、linux、freebsd、openbsd的实现的,最近的一篇分析windows漏洞的paper发表在Crypto 07,是一群以色列人做的工作。PRNG是非常重要的东西,因为密码学中几乎所有算法都依赖于随机数的生成,并且会影响到我们的实际生活,比如windows的漏洞就导致黑客可以比较容易的算出你之前所有SSL加密过的通讯内容,进而得知你的银行账号等。游戏中的随机数要求也许不这么高,但做的大了难保别人不会研究出破绽。

我们用确定的算法产生不确定的伪随机数,本身这种做法就可能有问题。貌似有个什么量子密码学,从理论上可以产生完整的随机数,好像是获取原子能量跳变是产生能量的大小来获取的,不过距离应用还有很长的时间啊。现在应该有利用系统高斯噪声产生随机数的办法。。。

Andrew Yao的结果只是理论吧,难道真的有那样的随机数发生器?

改过来了。 我本来是想说中个 10 块钱就算大奖了 :) 没买过彩票,随手写的。

以前记得学习遗传的时候,说孟德尔的那个数据太好了,从概率上不太可能是真的,呵呵,和楼主的数据一个意思

“例如:丢一万次硬币,正好出现 5000 次正面的概率大概不会比你买彩票中大奖的概率高多少。”

你买的是什么彩票啊,大奖的中奖概率这么高......

事实上,现在基本上所有的操作系统都直接提供了支持伪随机数的API。统计意义上安全的随机数在密码学意义上并不一定安全,你可以查阅wiki上关于Cryptographically secure pseudorandom number generator的介绍。Knuth归纳的方法基本上还是早期的方法,后来随着密码学的发展,随机数生成已经不是使用那些方法了,这其中贡献最大的包括华人科学家Andrew Yao。简单的说,Cryptographically secure PRNG要保证的是任何一个多项式图灵机(严格说来是Non-uniform PPT)都无法将PRNG生成的bit sequence与一个真正的uniform bit sequence区分开来。你所列出的 χ 方检验只是一种方法。

Unix 里面有一个系统的随机数发生器 /dev/random ,是收集设备噪声来产生的,是真随机数。

Post a comment

非这个主题相关的留言请到:留言本