原文：NGA的一篇隨機(jī)科普，其中包含了對(duì)手游抽卡機(jī)制的探討。本文摘選了我自己感興趣的部分。

真隨機(jī)

先說點(diǎn)題外話，請(qǐng)先看這個(gè)問題

一杯熱水和一杯冷牛奶哪個(gè)熱量更高？

很顯然這個(gè)問題從物理學(xué)和營(yíng)養(yǎng)學(xué)的層面會(huì)得出相反的答案，( 先不考慮物理學(xué)層面說“一杯熱水的熱量”實(shí)際上是錯(cuò)誤的 )，而關(guān)于“隨機(jī)”的問題上的大部分疑惑與爭(zhēng)論都恰如這個(gè)問題一般：

扔硬幣算不算真隨機(jī)？
計(jì)算機(jī)是否只能生成偽隨機(jī)？
偽隨機(jī)是不是就一定能找到規(guī)律？

想要解決這些問題，就必須從兩個(gè)層面去理解“隨機(jī)”，接著看下面兩句話：

1.讓我們丟硬幣/骰子(或其他機(jī)制)來隨機(jī)生成一串?dāng)?shù)字吧

2.這一串?dāng)?shù)字是隨機(jī)的

我們往往認(rèn)為第一句是第二句的必要前提，第二句是第一句的必然結(jié)果，而實(shí)際上它們分別代表了隨機(jī)的兩個(gè)不同層面的特征：

1.不可預(yù)測(cè)

2.不可壓縮

一、不可預(yù)測(cè)——“原理”層面的隨機(jī)

我們?yōu)槭裁匆褂糜矌呕蛘喵蛔尤Q定一件事情？其本質(zhì)在于我們要的是一個(gè)不可預(yù)測(cè)的結(jié)果，自然有人會(huì)說，只要準(zhǔn)確測(cè)量擲出角度速度以及引力空氣阻力等等參數(shù)，硬幣的正反是完全可以預(yù)測(cè)的。然而，這真的是“預(yù)測(cè)”嗎？

試想幾種情況：

硬幣直接平拍在地上——正面
硬幣彈跳了幾下落在地上——正面
硬幣斜著滾了幾圈后倒下——正面
……

這實(shí)際上完全不是同一個(gè)狀態(tài)，這里所謂的“正面”與其說是“預(yù)測(cè)”更接近“歸納”。試想我們做一枚2億面的骰子，一半的面標(biāo)記為正，另一半為反，那么在理想情況下它和硬幣在“擲出去獲取正反兩種結(jié)果”這件事上是完全等價(jià)的(可以互相代替且都不能做得比對(duì)方更多)，現(xiàn)在你就很難再準(zhǔn)確預(yù)測(cè)它的結(jié)果了。你說你可以提升測(cè)量精度，于是我又掏出了20億面骰子、200億面骰子，直到讓你的測(cè)量精度需求撞上一堵嘆息之墻——“普朗克尺度“。

1.注：量子力學(xué)與隨機(jī)

• 有相當(dāng)多的人覺得“量子力學(xué)是玄學(xué)”，誠(chéng)然“不確定性”和“波粒二象性”等等概念實(shí)在不像經(jīng)典物理學(xué)所描繪的圖景那么容易理解，然而非常諷刺的是，經(jīng)典力學(xué)的大廈不是被量子力學(xué)推倒的，而是被鐵一般的實(shí)驗(yàn)事實(shí)摧毀的，而量子力學(xué)恰恰是構(gòu)建在這些實(shí)驗(yàn)事實(shí)上的理論，其基本概念并非是新增的，而是在經(jīng)典力學(xué)里面砍掉諸如“剛體”、“瞬時(shí)作用”、“無窮遠(yuǎn)處”等等我們做題時(shí)候習(xí)以為常但是在理論層面卻極其臃腫丑陋的假設(shè)后提煉出來的。量子力學(xué)中帶有概率的描述反而是當(dāng)代物理學(xué)中對(duì)于客觀現(xiàn)實(shí)最精確的描述，遠(yuǎn)遠(yuǎn)超過經(jīng)典力學(xué)。
• 關(guān)于“量子不確定性原理”最簡(jiǎn)單的理解就是“對(duì)于一個(gè)物體位置和動(dòng)量的測(cè)量(描述并預(yù)測(cè)物體運(yùn)動(dòng)所必須的條件)，兩者的不確定性之積必然大于等于普朗克常數(shù)除以4π”，很多人會(huì)覺得這仿佛是造物主設(shè)下的限制一般，然而正如我前面所講，這一概念也是建立在一個(gè)非常樸素的實(shí)驗(yàn)事實(shí)上：“我們的測(cè)量過程必然存在微觀粒子的相互作用”。舉個(gè)例子：你拿皮尺量腰圍，想要精確測(cè)量就必然要把皮尺收緊，這實(shí)際上就極微小的改變了腰圍，而“恰好搭在腰上不產(chǎn)生壓力”，不管在==(現(xiàn)代物理的)理論上還是在現(xiàn)實(shí)中==都是做不到的，因?yàn)闃?gòu)成人體和皮尺的微觀粒子還存在永不停息的熱運(yùn)動(dòng)，最終造成了不管在理論還是實(shí)驗(yàn)層面都無法避免的不確定性。
• “普朗克尺度”也是一個(gè)經(jīng)常被誤用的概念，很多人把他理解成一個(gè)“bit”性質(zhì)的“最小單位”，而實(shí)際上它只是一個(gè)范圍而非單位，其物理意義也是基于一個(gè)客觀事實(shí)上——“想取得更準(zhǔn)確的測(cè)量結(jié)果就需要使用波長(zhǎng)更短的基本粒子去和被測(cè)量物產(chǎn)生相互作用”(這也是為什么微觀領(lǐng)域可見光顯微鏡不行了需要上電子顯微鏡的原因)，而波長(zhǎng)越短，單個(gè)粒子的能量就越高，根據(jù)相對(duì)論它的質(zhì)量也會(huì)越高，最終會(huì)導(dǎo)致其史瓦西半徑大于康普頓波長(zhǎng)，從而成為一個(gè)黑洞，同時(shí)我們也就失去了該粒子的一切信息——測(cè)量失敗。(這里的概念如果難以理解的話其實(shí)可以不管的，因?yàn)橄胝嬲斫膺@些概念還需要量綱相關(guān)的知識(shí)，非專業(yè)領(lǐng)域?qū)嵲跊]有了解的必要。)

總結(jié)來說，就是預(yù)測(cè)的精度無法無限制地往上提升，最終總是會(huì)以概率的形式呈現(xiàn)（這在前些天和小丁同學(xué)討論完事萬物是不是可以預(yù)測(cè)測(cè)時(shí)候也提到過）

我們可以更簡(jiǎn)單直接一點(diǎn)，直接用微觀粒子來做骰子，這樣“不確定性原理”就可以保證結(jié)果從理論上永遠(yuǎn)無法準(zhǔn)確預(yù)測(cè)。

你或許會(huì)說，技術(shù)上測(cè)量精度應(yīng)該是領(lǐng)先加工精度的，也就是你有做多少面骰子的技術(shù)我就應(yīng)該有那個(gè)精度的測(cè)量能力，所以依然是可以預(yù)測(cè)結(jié)果的，然而，在嘆息之墻前面還有一道名為“混沌(注二)”的冥界之河。

2.注：混沌和隨機(jī)

• 簡(jiǎn)單來說就是：我們實(shí)際上并不需要2億面的骰子，只需要拿3枚硬幣放在一個(gè)盒子里搖上10秒鐘，準(zhǔn)確預(yù)測(cè)結(jié)果所需的測(cè)量精度和計(jì)算量就已經(jīng)爆炸級(jí)的增長(zhǎng)了，只要繼續(xù)增加硬幣數(shù)量和搖晃的時(shí)長(zhǎng)，預(yù)測(cè)所需的計(jì)算能力很快就會(huì)達(dá)到即使把可觀測(cè)宇宙中的所有物質(zhì)都轉(zhuǎn)化成運(yùn)算資源也不夠的程度。

• 小時(shí)候在電視上看到過彩票開獎(jiǎng)，在一個(gè)裝置里搖球。只要搖獎(jiǎng)的時(shí)間足夠長(zhǎng)，不管你把某一次搖獎(jiǎng)的參數(shù)測(cè)量的多么準(zhǔn)確，都無法用這些參數(shù)去準(zhǔn)確重演結(jié)果，甚至一次搖獎(jiǎng)對(duì)獎(jiǎng)球造成的分子尺度的磨損都會(huì)影響下一次的搖獎(jiǎng)結(jié)果，所以進(jìn)行準(zhǔn)確預(yù)測(cè)或控制也是不可能的。

  題外話：彩票舞弊也都是通過視頻作假或者偽造出票時(shí)間(后者基本上就是現(xiàn)實(shí)中所有的彩票舞弊實(shí)例，開獎(jiǎng)后買，后臺(tái)修改出票時(shí)間為開獎(jiǎng)前，尤其是在沒有互聯(lián)網(wǎng)的時(shí)代)。

于是綜合以上兩點(diǎn)，量子力學(xué)和混沌動(dòng)力學(xué)在原理層面保證了隨機(jī)性的誕生，而在實(shí)驗(yàn)層面上還有一個(gè)影響因素就是“自由意志”，即使你可以預(yù)測(cè)硬幣的結(jié)果，但是你把硬幣交給別人丟，你沒法預(yù)測(cè)他選擇什么時(shí)候用什么力度和角度去丟，而“自由意志”在現(xiàn)代已經(jīng)不是哲學(xué)概念這么簡(jiǎn)單，已經(jīng)把物理學(xué)和數(shù)學(xué)牽扯進(jìn)來，這里就不做過多展開了。

二、不可壓縮——“結(jié)果”層面的隨機(jī)

首先讓我們?cè)囅胍粋€(gè)場(chǎng)景

有三位朋友A、B、C

A在房間里反復(fù)丟一枚硬幣并將結(jié)果報(bào)給房間外面的B

B用1代表正面，0代表反面把結(jié)果記錄下來，再將其轉(zhuǎn)發(fā)給C

下面是B的記錄表格：

次數(shù)	1	2	3	4	5	6	7	8	9	10	11	12	13	……
結(jié)果	1	0	1	0	1	0	0	0	1	1	0	0	1	……

如果B想把A丟硬幣的結(jié)果完整的傳輸給C，顯然他只能把這個(gè)表格整個(gè)傳輸過去，無法進(jìn)行任何壓縮以減少傳輸?shù)臄?shù)據(jù)量。

請(qǐng)務(wù)必仔細(xì)理解這句話，這是本文出現(xiàn)的第一個(gè)需要理解的數(shù)學(xué)概念——“不可壓縮性”——即我們對(duì)某一個(gè)數(shù)列最簡(jiǎn)短的描述就是這個(gè)數(shù)列本身。

那什么情況可以壓縮呢？

顯然如果B從A那里收到的結(jié)果是101010101010……這樣，他就可以告訴C“奇數(shù)次的結(jié)果是正面，偶數(shù)次的結(jié)果是反面”——這一描述顯然要比記錄這些結(jié)果的數(shù)據(jù)串要短得多，這就是一種壓縮。

此時(shí)我們可以給數(shù)列是否“隨機(jī)”定下一個(gè)判斷標(biāo)準(zhǔn)：

我們說一個(gè)數(shù)列是“隨機(jī)的”，當(dāng)且僅當(dāng)該數(shù)列是“不可壓縮的”，反之亦然。

這里一定要分清楚“不可壓縮”和“沒有規(guī)律”的區(qū)別，比如擲理想硬幣生成的數(shù)列，1和0的比值最終應(yīng)該是1：1，這也是一種“規(guī)律”（不可壓縮也滿足這個(gè)規(guī)律），但是和“奇數(shù)位是1偶數(shù)位是0”這樣的規(guī)律不同，無法“基于這一規(guī)律使對(duì)數(shù)列的完整描述變短”，仍然還是“只能用數(shù)列本身來完整描述”，這是這部分最容易混淆的概念，一定要想明白。

就是對(duì)”規(guī)律”這個(gè)詞理解，注意一下就行。

這一判斷方式并不需要參考這一數(shù)列是如何產(chǎn)生的，這一點(diǎn)在本文接下來的部分也很重要。

可以看到圖中出現(xiàn)了兩個(gè)新的英文單詞stochastic和random，此處這兩個(gè)單詞的使用是根據(jù)默里·蓋爾曼的建議，分別描述隨機(jī)過程(stochastic process)和隨機(jī)結(jié)果(random variable)，也就是對(duì)應(yīng)上文的兩個(gè)層面，但需要注意的是這僅僅是為了方便理解的劃分，這兩個(gè)詞在專業(yè)領(lǐng)域往往有更嚴(yán)謹(jǐn)?shù)亩x，不要拿這張圖當(dāng)成嚴(yán)謹(jǐn)定義

總之，這一部分就是講述“真隨機(jī)”的判斷條件——雖然文中我用只用了“隨機(jī)”這個(gè)詞，但實(shí)際上所謂“隨機(jī)”就是指“真隨機(jī)”，而“偽隨機(jī)”是要?dú)w入“不隨機(jī)”中的，具體請(qǐng)看下一部分。

偽隨機(jī)

什么是偽隨機(jī)？

用非stochastic的方式去生成random的嘗試

依然用上面的例子

A、B、C又一次在進(jìn)行擲硬幣的游戲，B正準(zhǔn)備把根據(jù)A告訴他的結(jié)果制作的如下表格逐個(gè)數(shù)字發(fā)給C：

次數(shù)	1	2	3	4	5	6	7	8	9	10	11	12	13	……
結(jié)果	1	0	1	1	1	0	0	1	1	1	0	1	1	……

就在這時(shí)，他們的朋友“大聰明”前來拜訪，他看了一眼B記錄的表格說：“不用記了，接下來13位是1101000000110?！彪S后A報(bào)出來的13次結(jié)果果然是“正正反正反反反反反反正正反”。
B非常驚訝，不知道“大聰明”是怎么猜到的，“大聰明”誒嘿一笑，畫出了如下的表格：

？？	1	4	1	5	9	2	6	5	3	5	8	9	7	……
結(jié)果	1	0	1	1	1	0	0	1	1	1	0	1	1	……

相信大家應(yīng)該看出來“ ？？”代表什么了，原來，A根本沒有投擲硬幣，而是用π小數(shù)點(diǎn)后每一位的奇偶性來生成結(jié)果并報(bào)給B的，那么問題來了：

顯然在“大聰明”眼里A投擲硬幣的表格是可壓縮的（紅色就是壓縮），顯然不是隨機(jī)(random)，但是在Bob眼里卻是不可壓縮的，符合隨機(jī)(random)的定義，那么這到底算不算隨機(jī)(random)呢？

由此我們可以得出偽隨機(jī)(pseudo random)的定義：

用非隨機(jī)過程(non-stochastic process)生成近似于隨機(jī)結(jié)果(random variable)的嘗試稱之為偽隨機(jī)(pseudo random)。

如何實(shí)現(xiàn)偽隨機(jī)

偽隨機(jī)是用隨機(jī)算法(randomized algorithm)生成的，比如上文中的“根據(jù)π小數(shù)點(diǎn)后每一位數(shù)的奇偶性生成1或0”就是一種偽隨機(jī)算法，這并不是一種很好的算法，首先他生成的數(shù)列實(shí)際上是固定的，無法在實(shí)際應(yīng)用中重復(fù)使用，并且還會(huì)被Dave這樣的人破解。而且它無法應(yīng)付巨量的偽隨機(jī)數(shù)需求，比如這一次應(yīng)用取了幾百萬位，下一次再取幾百萬位，很快存儲(chǔ)器中的π值小數(shù)點(diǎn)后的位數(shù)就不夠用了，只能一邊算一邊生成，導(dǎo)致所需的存儲(chǔ)空間越來越大。

一個(gè)優(yōu)秀的、可實(shí)際應(yīng)用的偽隨機(jī)算法通常至少要滿足兩個(gè)條件：

• 可以生成有明顯不同的無數(shù)組數(shù)列；
• 可以用有限的運(yùn)算能力和存儲(chǔ)空間生成任意長(zhǎng)的數(shù)列。我們通常使用一種非常簡(jiǎn)單精妙的方式來解決這個(gè)問題——迭代(iteration)。

例子：

比如今天是11月25日，我們?nèi)?125這個(gè)數(shù)字，將它進(jìn)行平方運(yùn)算，得到1265625，將其前面補(bǔ)一個(gè)0湊成八位數(shù)01265625，取中間四位2656再平方得到7054336，補(bǔ)足八位取中間四位0543再平方……每進(jìn)行一次“平方取中”操作就稱為一次迭代，不斷進(jìn)行下去可以生成如下表格：

迭代次數(shù)	0	1	2	3	4	5	6	7	8	9	10	11	12	……
取值結(jié)果	1125	2656	0543	2948	6907	7066	9283	1740	0276	0761	5791	5356	6867	1556

看起來非常完美是不是，因?yàn)椤捌椒饺≈小辈僮鞯摹叭≈?包括補(bǔ)位)”看起來是一個(gè)帶有主觀性質(zhì)的操作，生成的數(shù)列似乎和真隨機(jī)(random)沒什么兩樣。
然而，50次迭代之后，取到了4100這個(gè)值，接下來的迭代會(huì)出現(xiàn)“4100、8100、6100、2100、4100、8100……”這樣周期僅為4的循環(huán)，這樣的偽隨機(jī)算法顯然也不能滿足實(shí)際需要。

實(shí)際上，上面那個(gè)最終看起來似乎很愚蠢的算法是馮·諾依曼發(fā)明的，可見構(gòu)造一個(gè)優(yōu)秀的偽隨機(jī)算法是多么困難的事情。之后的線性同余發(fā)生器(LCG, Linear Congruential random number Generator)雖然速度極快且周期夠大(2^31-1)，但是存在很大的缺陷，甚至可以說一直到1997年基于梅森旋轉(zhuǎn)算法(Mersenne twister)的MT19937出現(xiàn)，才有了在實(shí)際應(yīng)用中可以當(dāng)成真隨機(jī)(random)來用的偽隨機(jī)算法。

隨機(jī)數(shù)發(fā)生器和隨機(jī)數(shù)表

其實(shí)上文中已經(jīng)多次提到了隨機(jī)數(shù)發(fā)生器(RNG,Random Number Generator)，硬幣、骰子等等包括后來提到的LCG等隨機(jī)算法都是隨機(jī)數(shù)發(fā)生器，顯然他們可以分成兩類：真隨機(jī)數(shù)發(fā)生器(True Random Number Generator)和偽隨機(jī)數(shù)發(fā)生器(Pseudo Random Number Generator)，而我們使用RNG的根本目的是為了獲取隨機(jī)數(shù)表(RNT,Random Number Table)，也就是上文中所說的隨機(jī)數(shù)列，在游戲領(lǐng)域的話我們通常稱為亂數(shù)表，通常我們用這樣的表格來呈現(xiàn)：

經(jīng)過上文的介紹，大家應(yīng)該明白用偽隨機(jī)數(shù)發(fā)生器生成這樣的表格是很容易的，而真隨機(jī)數(shù)發(fā)生器又是怎么生成這樣的表格的呢？

1.第一種最簡(jiǎn)單的方法就是直接生成，比如擲骰子生成的正面反面用1和0來記錄的話就可以視為二進(jìn)制數(shù)，選擇適當(dāng)?shù)臄?shù)字串長(zhǎng)度劃分就可以生成任意范圍的隨機(jī)數(shù)。在科研領(lǐng)域我們一般使用基于“量子骰子”的量子隨機(jī)數(shù)發(fā)生器(QRNG,Quantum Random Number Generator)，另外值得驕傲的是在這一領(lǐng)域，我國(guó)處于世界領(lǐng)先地位。

2.另一種是“觀測(cè)”性質(zhì)的生成，比方說觀測(cè)某一限定空間內(nèi)的微觀運(yùn)動(dòng)或宏觀混沌系統(tǒng)(如大氣溫度)，然后將結(jié)果閾值化，舉例來說就是這樣：

把50只老鼠放進(jìn)一個(gè)面積約能容納100只老鼠的扁平且溫暖的方盒中，然后不定期進(jìn)行拍照，在照片上劃分10*10的方格，每一格內(nèi)超過1/2老鼠身體則涂黑，不足1/2則涂白，那么這張照片就可以當(dāng)成二維碼來掃，這樣就能生成隨機(jī)數(shù)表了。

隨機(jī)數(shù)表的應(yīng)用

隨機(jī)數(shù)表在應(yīng)用層面主要有兩大方式：

• 提供判斷：

  最簡(jiǎn)單的模式就是比如做一個(gè)擲硬幣的模擬游戲：

  1.依次在隨機(jī)數(shù)表中取數(shù)字。 
  2.當(dāng)取值在1~50之間時(shí)輸出“正面”。 
  3.當(dāng)取值在51~100之間時(shí)輸出“反面”。
  

  于是根據(jù)隨機(jī)數(shù)表中的“71、81、20、65、14……”該程序就生成了“反面、反面、正面、反面、正面……”這樣的結(jié)果。
  實(shí)際應(yīng)用中的取值要更復(fù)雜一些，比如很多游戲中的“武器強(qiáng)化系統(tǒng)”：+1的成功率是70%、+2降低到60%、+3是50%這樣很常見的設(shè)定是如何實(shí)現(xiàn)的呢？我們可以寫這樣的程序：

  1.在隨機(jī)數(shù)表中依次取值。 
  2.判斷武器的狀態(tài)。 
  3.當(dāng)武器為+0的時(shí)候，取值在1~30之間判定為“失敗”，在31~100之間判定為“成功”。 
  3.當(dāng)武器為+1的時(shí)候，取值在1~40之間判定為“失敗”，在41~100之間判定為“成功”。 
  3.當(dāng)武器為+2的時(shí)候，取值在1~50之間判定為“失敗”，在51~100之間判定為“成功”。
  

• 隨機(jī)排序：

  我們?cè)趯?shí)際應(yīng)用中經(jīng)常會(huì)遇到把若干個(gè)元素隨機(jī)排序的需求，如果使用數(shù)學(xué)方式(隨機(jī)數(shù)表屬于數(shù)學(xué)范疇)實(shí)現(xiàn)的話也被稱為洗牌算法(shuffle algorithm)。
  假設(shè)我們要將100個(gè)數(shù)的順序打亂，顯然直接用上面的隨機(jī)數(shù)表當(dāng)序號(hào)是不行的，因?yàn)橛兄貜?fù)的數(shù)字，而在隨機(jī)數(shù)發(fā)生器中加入剔除相同數(shù)值的機(jī)制的話又會(huì)嚴(yán)重影響效率(因?yàn)槊可梢粋€(gè)數(shù)都要和之前所有數(shù)進(jìn)行“逐一比對(duì)”，在數(shù)據(jù)量很大的時(shí)候運(yùn)算量過高)，我們可以用這樣的程序去實(shí)現(xiàn)“洗牌”：

  1.將需要排序的N個(gè)數(shù)按輸入的順序排列好。 
  2.選擇第N個(gè)數(shù)字，并在數(shù)值總量大于N的隨機(jī)數(shù)表中取值，設(shè)所取值為M，則將第N個(gè)數(shù)字和第M個(gè)數(shù)字位置對(duì)調(diào)，若M大于N，則用M除以N并“取余數(shù)再加1”作為M再進(jìn)行操作。 
  3.選擇第N-1個(gè)數(shù)字，在隨機(jī)數(shù)表中取下一個(gè)數(shù)作為M進(jìn)行同“步驟2”的操作。 
  4.持續(xù)操作直到對(duì)第1個(gè)數(shù)字進(jìn)行操作，排序完畢。
  

  比如我們對(duì)“10、20、30、40”四個(gè)數(shù)字進(jìn)行隨機(jī)排序：
  首先操作第4個(gè)數(shù)字“40”，隨機(jī)數(shù)表第一個(gè)值是“71”>數(shù)列長(zhǎng)度4，我們用71除以4得到17余3，再+1=4，那么最終得到的M值就是“4”，因?yàn)槲覀冞x擇的已經(jīng)是第4個(gè)數(shù)字了，所以不用進(jìn)行對(duì)調(diào)。此時(shí)數(shù)列仍然為“10、20、30、40”
  接下來操作第3個(gè)數(shù)字“30”，隨機(jī)數(shù)表中取值“81”，81除以4得到20余1，再+1=2，M=“2”，于是我們就把第3個(gè)數(shù)字“30”和第2個(gè)數(shù)字“20”進(jìn)行對(duì)調(diào)。此時(shí)數(shù)列變成了“10、30、20、40”
  接下來選擇此時(shí)的第2個(gè)數(shù)字“30”(別忘了我們剛剛在上一步把2換過來了)，在隨機(jī)數(shù)表中取值“20”，20除以4得到5余0，再+1=1，M值=“1”，于是我們就把第2個(gè)數(shù)字“30”和第1個(gè)數(shù)字“10”進(jìn)行對(duì)調(diào)。此時(shí)數(shù)列變成了“30、10、20、40”
  最后選擇第1個(gè)數(shù)字“30”，在隨機(jī)數(shù)表中取值“65”>數(shù)列長(zhǎng)度4，于是用65除以4得到16余1，再+1=2，M值=“2”，于是我們就把第1個(gè)數(shù)字“30”和第2個(gè)數(shù)字“10”進(jìn)行對(duì)調(diào)。此時(shí)數(shù)列變成了“10、30、20、40”，這也就是我們最終的排序結(jié)果。

當(dāng)我們利用計(jì)算機(jī)生成的隨機(jī)數(shù)表來進(jìn)行上面的操作的時(shí)候，常常會(huì)有人這樣評(píng)價(jià)“因?yàn)?strong>計(jì)算機(jī)只能生成偽隨機(jī)”，所以你這個(gè)洗牌算法(或者別的機(jī)制)不夠隨機(jī)?！边@種評(píng)價(jià)的邏輯是對(duì)的么？

計(jì)算機(jī)只能生成偽隨機(jī)

經(jīng)常會(huì)聽到一句話：計(jì)算機(jī)只能生成偽隨機(jī)

然而，相當(dāng)諷刺的是，如果你帶著這句話回到1951年，也就是第一臺(tái)商用電子計(jì)算機(jī)Ferranti Mark 1問世的那一年，幾乎所有對(duì)計(jì)算機(jī)有所了解的人的反應(yīng)都會(huì)是：

什么？計(jì)算機(jī)還能生成偽隨機(jī)的？你別騙人了，計(jì)算機(jī)只能生成真隨機(jī)！

在Ferranti Mark 1中，阿蘭·圖靈設(shè)計(jì)了一個(gè)真隨機(jī)數(shù)發(fā)生器(TRNG)，原理是采集系統(tǒng)內(nèi)的電氣噪聲生成一個(gè)20比特的隨機(jī)數(shù)字串，然而這一實(shí)打?qū)嵉恼骐S機(jī)卻讓開發(fā)人員非常不滿，因?yàn)槠渫耆豢煽?，?shí)際編程應(yīng)用中對(duì)隨機(jī)數(shù)的要求包括可重復(fù)性(用于編程調(diào)試)和可以在一定范圍內(nèi)進(jìn)行調(diào)整(比如前文提到的LCG就可以通過更改參數(shù)來調(diào)整周期等)的能力。平方取中過于弱雞，LCG因?yàn)橥噙\(yùn)算需要進(jìn)行大量除法運(yùn)算，在當(dāng)時(shí)計(jì)算機(jī)的能力下效率堪憂。于是在那個(gè)時(shí)代的科研與生產(chǎn)中，最常見的場(chǎng)面就是大家手捧一本巨大的《A Million Random Digits with 100,000 Normal Deviates(百萬亂數(shù)表)》利用里面的隨機(jī)數(shù)來進(jìn)行工作，該書是蘭德(RAND)公司在1955年利用電脈沖發(fā)生器產(chǎn)生的隨機(jī)數(shù)編寫的，當(dāng)年技術(shù)人員幾乎人手一本，可見對(duì)于高質(zhì)量隨機(jī)數(shù)的需求有多大。

一直到1960年第一個(gè)比較可靠的商用偽隨機(jī)數(shù)發(fā)生器——IBM公司的RANDU子程序才誕生，但是其依然存在著很大的缺陷(見前文“注八”中的“奧妮醬，卒”，另外學(xué)計(jì)算機(jī)的應(yīng)該都有印象，好多教材關(guān)于偽隨機(jī)生成器的章節(jié)都要把RANDU拉出來當(dāng)反面教材鞭尸。)，并沒有完全取代《百萬亂數(shù)表》。一直到90年代計(jì)算機(jī)性能的提升和日漸普及的計(jì)算機(jī)網(wǎng)絡(luò)對(duì)于安全性的極高需求，偽隨機(jī)數(shù)發(fā)生器才真正進(jìn)入了黃金時(shí)代。

然而一直到現(xiàn)代，我們的計(jì)算機(jī)包括智能手機(jī)里面，都還有真隨機(jī)數(shù)發(fā)生器的存在，主要用于一些對(duì)生成速度要求不高但是對(duì)于安全性要求極高的場(chǎng)合，比如現(xiàn)代藍(lán)牙芯片中基本都有TRNG，用于配對(duì)過程中的通信安全，這一類TRNG又被稱為硬件隨機(jī)數(shù)發(fā)生器(HRNG,Hardware Random Number Generator)。除了直接生成數(shù)據(jù)，也有基于“觀測(cè)”的HRNG，比如1997年的LavaRand，使用攝像頭對(duì)一個(gè)熔巖燈持續(xù)拍攝并將圖像數(shù)字化生成隨機(jī)數(shù)。

綜上，這句話應(yīng)該改成“計(jì)算機(jī)程序只能生成偽隨機(jī)”，而廣義的“計(jì)算機(jī)”概念生成真隨機(jī)是非常自然的事情，且普遍應(yīng)用于科研和生產(chǎn)的歷史幾乎和計(jì)算機(jī)本身的歷史一樣長(zhǎng)。

然而即使是“計(jì)算機(jī)程序生成的偽隨機(jī)”，我們?cè)趯?shí)際應(yīng)用中利用其獲取真隨機(jī)數(shù)也很容易，還是讓A和她的朋友們給大家示范一下：

A寫了一個(gè)小程序：

1.在后臺(tái)存儲(chǔ)中生成一個(gè)“1”，0.1秒后切換成“0”，之后每0.1秒持續(xù)如此在“1”和“0”之間切換。 
2.每當(dāng)用鼠標(biāo)點(diǎn)擊屏幕的時(shí)候，顯示此刻后臺(tái)存儲(chǔ)中的結(jié)果。

之后Alice隨意的點(diǎn)擊屏幕，生成了一串“1、1、0、1、0、1、0、0……”這樣的數(shù)字。

這個(gè)程序是偽隨機(jī)(pseudo random)，然而Alice通過真隨機(jī)(stochastic)選擇輸出結(jié)果，得到的就是真隨機(jī)(random)的結(jié)果，這一方式最常見的應(yīng)用就是滾動(dòng)抽獎(jiǎng)，就是那種屏幕上持續(xù)滾動(dòng)手機(jī)號(hào)之類的，然后嘉賓選擇何時(shí)停止，這些手機(jī)號(hào)的排序和滾動(dòng)模式通常都是由偽隨機(jī)數(shù)控制，但是最終抽選則是基于嘉賓的自由意志，當(dāng)然這種抽獎(jiǎng)模式相對(duì)于搖獎(jiǎng)機(jī)來說想要作假還是很容易的，比如每次嘉賓按停止鍵時(shí)顯示事先定好的數(shù)字(這種方式下通常要把滾動(dòng)做的極快讓人看不清)，但這和隨機(jī)機(jī)制本身無關(guān)。

B也寫了一個(gè)小程序：

1.當(dāng)輸入奇數(shù)的時(shí)候，輸出“1”。 
2.當(dāng)輸入偶數(shù)的時(shí)候，輸出“0”。

然后Bob持續(xù)投擲一枚骰子，將生成的點(diǎn)數(shù)如“6、4、1、2、2、4、3、1……”輸入程序生成了一串“0、0、1、0、0、0、1、1……”這樣的數(shù)字。

這個(gè)程序顯然也是偽隨機(jī)(pseudo random)，然而Bob直接把真隨機(jī)(stochastic)當(dāng)作輸入值(這一過程中偽隨機(jī)程序?qū)嶋H上起的作用和“把硬幣的正反記為1和0”性質(zhì)相同的作用，只是一種“轉(zhuǎn)換模式”)，得到了真隨機(jī)(random)的結(jié)果。

綜上，計(jì)算機(jī)實(shí)現(xiàn)真隨機(jī)有兩種方式：

1.直接使用硬件隨機(jī)數(shù)發(fā)生器(HRNG,Hardware Random Number Generator)生成真隨機(jī)(random)。
2.通過在偽隨機(jī)數(shù)發(fā)生器(Pseudo Random Number Generator)中增加真隨機(jī)(stochastic)因素將其改造成真隨機(jī)數(shù)發(fā)生器(True Random Number Generator)。

如何設(shè)計(jì)一整套隨機(jī)機(jī)制

1.設(shè)計(jì)或選擇一個(gè)隨機(jī)數(shù)發(fā)生器(RNG,Random Number Generator)——根據(jù)實(shí)際需要選擇真隨機(jī)數(shù)發(fā)生器或偽隨機(jī)數(shù)發(fā)生器(以及發(fā)生器的具體形式)。
2.將==初始值(此處的的“初始值”在編程領(lǐng)域我們通常稱之為種子(seed)，之后我們要經(jīng)常用到這個(gè)概念)==輸入隨機(jī)數(shù)發(fā)生器，生成隨機(jī)數(shù)表?！梢允褂昧硗獾臋C(jī)制(包括另一個(gè)隨機(jī)數(shù)發(fā)生器)生成種子，也可以使用另外的機(jī)制(包括另一個(gè)隨機(jī)數(shù)生成器)對(duì)生成的隨機(jī)數(shù)表進(jìn)行操作(如篩選或排序)。
3.設(shè)計(jì)隨機(jī)數(shù)表實(shí)現(xiàn)應(yīng)用要求的模式并應(yīng)用這些模式進(jìn)行操作得出結(jié)果。——如上文中提到的“提供判斷”和“隨機(jī)排序”

例子：

**用戶需求：**設(shè)計(jì)某網(wǎng)絡(luò)游戲中的抽獎(jiǎng)機(jī)制，獎(jiǎng)品總價(jià)值比較低，要求程序?qū)用姹M量簡(jiǎn)單，但又不容易被找出規(guī)律，需要能支持較大量用戶同時(shí)抽獎(jiǎng)并獲得有差異的結(jié)果，并且對(duì)于不同價(jià)值獎(jiǎng)品可以提供方便調(diào)整的中獎(jiǎng)概率設(shè)定，最后就是機(jī)制層面的用戶體驗(yàn)越高越好。
需求分析：
獎(jiǎng)品總價(jià)值比較低——不需要太貴的商用隨機(jī)數(shù)發(fā)生器了。
程序?qū)用婧?jiǎn)單——不能用太復(fù)雜的算法。
不容易被找出規(guī)律——盡量接近真隨機(jī)(random)。
能支持較大量用戶同時(shí)抽獎(jiǎng)——隨機(jī)數(shù)生成要盡量高速。
獲得有差異的結(jié)果——同時(shí)抽獎(jiǎng)的用戶結(jié)果要盡量不同。
對(duì)于不同價(jià)值獎(jiǎng)品可以提供方便調(diào)整的中獎(jiǎng)概率設(shè)定——在隨機(jī)數(shù)表的應(yīng)用方式上要提供調(diào)整的余地。
機(jī)制層面的用戶體驗(yàn)越高越好——盡量讓用戶覺得抽獎(jiǎng)結(jié)果更取決于自己。

程序設(shè)計(jì)

隨機(jī)發(fā)生器：

1.使用“平方取中”方式，每次輸入一個(gè)四位數(shù)種子，進(jìn)行平方運(yùn)算，結(jié)果如不足八位數(shù)則在最前面補(bǔ)充0直到形成八位數(shù)，將最終生成的八位數(shù)的中間四位繼續(xù)進(jìn)行前述的“平方取中”方式，此為1次迭代。 
2.共進(jìn)行10次迭代，并輸出這10次的結(jié)果作為一個(gè)隨機(jī)數(shù)表。 
3.等待下一次種子的輸入，并重復(fù)以上步驟。

種子獲?。?/p>

當(dāng)用戶點(diǎn)擊抽獎(jiǎng)時(shí)，抓取當(dāng)時(shí)的服務(wù)器時(shí)間，取“AB分CD秒”的“ABCD”作為四位數(shù)種子輸入隨機(jī)發(fā)生器。

隨機(jī)數(shù)表使用方式：

1.用戶點(diǎn)擊抽獎(jiǎng)后，用戶界面出現(xiàn)10個(gè)寶箱，將隨機(jī)數(shù)表中的10次迭代結(jié)果依次填入10個(gè)寶箱之中。
2.讓用戶自己點(diǎn)擊選擇一個(gè)寶箱開啟。
3.根據(jù)寶箱中的的四位隨機(jī)數(shù)值判定中獎(jiǎng)結(jié)果。
中獎(jiǎng)率設(shè)定方式

1.0000、0100、2100、4100、6100、8100這5個(gè)會(huì)形成短周期的迭代結(jié)果設(shè)置為價(jià)值最低的獎(jiǎng)品或“謝謝惠顧”等。 
2.確定最稀有獎(jiǎng)品的編號(hào)，如只有10個(gè)的最高獎(jiǎng)，可以設(shè)置成“X999”，如“999、3999、9999”才可中獎(jiǎng)等。 
3.其他獎(jiǎng)品可以用區(qū)間或倍數(shù)的形式再剔除掉大獎(jiǎng)編號(hào)的方式定義，如“0~5000之間除X999外為末等獎(jiǎng)”，“每逢11的倍數(shù)為四等獎(jiǎng)”等等。

案例點(diǎn)評(píng)：

優(yōu)點(diǎn)：
1.用戶最終自己選擇寶箱的方式極大程度提高了隨機(jī)性和用戶體驗(yàn)。
2.因?yàn)檫x擇寶箱的方式極大的提高了隨機(jī)性，對(duì)隨機(jī)數(shù)發(fā)生器的要求就大大降低了，此時(shí)即可選擇“平方取中”這樣的極簡(jiǎn)方式大大提升效率。
3.隨機(jī)數(shù)表和中獎(jiǎng)率的設(shè)置簡(jiǎn)單合理，調(diào)整非常容易。
缺點(diǎn)：
1.以“XX分XX秒”作為種子在“平方取中”方式中有很大的弊端，因?yàn)橛胁糠钟脩粲性凇?0分00秒”進(jìn)行抽獎(jiǎng)的個(gè)人癖好，此時(shí)迭代結(jié)果必然全是0，影響用戶體驗(yàn)。
2.取服務(wù)器時(shí)間為種子，大大增加了服務(wù)器同時(shí)接受的請(qǐng)求量，容易造成服務(wù)器壓力過大導(dǎo)致宕機(jī)。
改進(jìn)方案：
1.在服務(wù)器端設(shè)置若干計(jì)數(shù)器程序，內(nèi)部以0000~9999循環(huán)滾動(dòng)數(shù)字，滾動(dòng)速度可以對(duì)應(yīng)任何時(shí)間間隔如CPU時(shí)鐘周期等，不必和現(xiàn)實(shí)時(shí)間周期掛鉤。
2.用戶發(fā)出抽獎(jiǎng)?wù)埱髸r(shí)，根據(jù)用戶本地時(shí)間、ip地址或網(wǎng)卡mac地址等信息通過一個(gè)極簡(jiǎn)算法(如隨便除以一個(gè)小質(zhì)數(shù)取余數(shù))分配某一個(gè)計(jì)數(shù)程序?yàn)槠淙‘?dāng)時(shí)的數(shù)值作為種子。
3.不定期分批重置這些計(jì)數(shù)程序。

經(jīng)常被誤當(dāng)成“偽隨機(jī)”的“隨機(jī)修正機(jī)制”

當(dāng)你在搜索引擎里面搜索“偽隨機(jī)”這三個(gè)字的時(shí)候，通常在前幾個(gè)結(jié)果里面就能看到“war3的偽隨機(jī)機(jī)制”，它的完整描述通常是這樣的：

war3(warcraft3,魔獸爭(zhēng)霸3)里面的劍圣(blademaster)這個(gè)英雄有一個(gè)“致命一擊(critical strike)”技能，在滿級(jí)的時(shí)候有20%的概率觸發(fā)并造成4倍于普通攻擊的傷害(實(shí)際機(jī)制要更復(fù)雜一點(diǎn))。

假設(shè)劍圣一刀可以造成100點(diǎn)傷害，那么可以計(jì)算出每7刀造成的傷害期望就是1120點(diǎn)，也就是敵方英雄血量不足1120，且劍圣可以安全的進(jìn)行7次攻擊的情況下就可以嘗試擊殺對(duì)方英雄了。

然而我們同樣可以計(jì)算出，連續(xù)7次攻擊均不發(fā)生致命一擊的概率高達(dá)21%，也就是這種嘗試有超過五分之一的概率會(huì)失敗。與此同時(shí)還有另一種情境，比如我方英雄尚有1000點(diǎn)血量，按期望計(jì)算敵方劍圣平均需要7次攻擊才能擊殺，

而當(dāng)時(shí)游戲中的狀態(tài)是敵方劍圣只能在自身安全的前提下進(jìn)行4次攻擊，此時(shí)按理來說可以認(rèn)為我方英雄是安全的，然而敵方劍圣魯莽的沖了上來砍了4刀，打出了2次致命一擊造成100x2+400x2=1000點(diǎn)傷害將我方英雄直接擊殺！

這種情況發(fā)生的概率實(shí)際上高達(dá)18%?；蛟S這樣的場(chǎng)面很有觀賞性，但是對(duì)于一項(xiàng)嚴(yán)謹(jǐn)?shù)碾娮痈?jìng)技項(xiàng)目來說，這種情況嚴(yán)重的影響了職業(yè)選手的策略判斷，可能會(huì)使選手的策略偏向保守，從而在深層次上影響比賽的觀賞性。

為了在不改動(dòng)“致命一擊發(fā)動(dòng)的概率為20%”的前提下改善這種情況，設(shè)計(jì)師設(shè)計(jì)了這樣的機(jī)制：

設(shè)致命一擊技能要求的發(fā)動(dòng)概率為P(P=20%)。 
在實(shí)際進(jìn)行第1次攻擊時(shí)給劍圣賦予一個(gè)初始概率C以發(fā)動(dòng)致命一擊，C<P。 
如果第1次攻擊沒有產(chǎn)生致命一擊，第二次攻擊產(chǎn)生致命一擊的概率調(diào)整為2C。 
以此類推，如果第n次攻擊沒有產(chǎn)生致命一擊，第n+1次攻擊產(chǎn)生致命一擊的概率調(diào)整為(n+1)C。 
當(dāng)nC>100%時(shí)直接產(chǎn)生一次致命一擊。 
當(dāng)任意一次攻擊產(chǎn)生致命一擊時(shí)，下一次攻擊產(chǎn)生致命一擊的概率重置為C。 
根據(jù)設(shè)定的C值計(jì)算出當(dāng)攻擊次數(shù)趨近于無限時(shí)，實(shí)際致命一擊發(fā)動(dòng)的概率P'，當(dāng)P'=P或與P的差在設(shè)計(jì)允許的范圍內(nèi)時(shí)，采用此時(shí)的C值作為最終的設(shè)定。 
最終計(jì)算得到的C值為5.57%

我們把這個(gè)新機(jī)制代入以上的情境進(jìn)行計(jì)算，會(huì)發(fā)現(xiàn)連續(xù)7次攻擊不觸發(fā)致命一擊的概率從21%降低到了16%，而4次攻擊中至少有2次致命一擊的概率從18%下降到了4%(特別要補(bǔ)充的是連續(xù)4次全觸發(fā)致命一擊的概率從0.16%下降到了0.001%！)

這一機(jī)制被稱為PRD:Pseudo Random Distribution，翻譯過來就是“偽隨機(jī)分布”，又常被簡(jiǎn)稱為“偽隨機(jī)”。

于是，每次在網(wǎng)絡(luò)上進(jìn)行隨機(jī)相關(guān)的討論中，總會(huì)出現(xiàn)這樣的場(chǎng)景：

場(chǎng)景A：
1.“某游戲的抽卡一定是偽隨機(jī)，因?yàn)橛?jì)算機(jī)只能生成偽隨機(jī)?！?br> 2.“如果是偽隨機(jī)”的話，如果咱們一直抽不到五星卡，概率會(huì)越來越高。”
場(chǎng)景B：
1.“我從來沒連續(xù)抽出過兩張五星卡，說明這游戲用的一定是偽隨機(jī)”
2.“那肯定的啊，計(jì)算機(jī)只能生成偽隨機(jī)嘛?！?/p>

為什么會(huì)出現(xiàn)這種誤解呢？問題實(shí)際上不出在“簡(jiǎn)稱”上，而是在“斷句”上，所謂“偽隨機(jī)分布”不是指“==偽隨機(jī)==分布”，而是指“**偽**隨機(jī)分布”，下面我簡(jiǎn)單的說明一下什么叫“隨機(jī)分布”：

假設(shè)我寫如下4個(gè)生成只含有“1和0的數(shù)字串”的程序：

A:使用TRNG“機(jī)械裝置持續(xù)投擲一枚理想硬幣”并記錄正反面結(jié)果，用1代表正面，0代表反面輸出。
B:采集“程序A”輸出的結(jié)果，然后在其中挑出所有“連續(xù)超過五個(gè)1”或者“連續(xù)超過五個(gè)0”的數(shù)字串并將其縮短至5位。
C:使用PRNG“梅森旋轉(zhuǎn)算法”持續(xù)生成偽隨機(jī)數(shù)，將生成的奇數(shù)記為1，偶數(shù)記為0輸出。
D:采集“程序C”輸出的結(jié)果，然后在其中挑出所有“連續(xù)超過五個(gè)1”或者“連續(xù)超過五個(gè)0”的數(shù)字串并將其縮短至5位。

之后我們把每個(gè)程序輸出的結(jié)果列出來，并進(jìn)行分析，這就是所謂的“分布”：
程序A輸出的結(jié)果是真隨機(jī) 分布：不存在周期性，每一位都不可預(yù)測(cè)，可以存在任意長(zhǎng)的連續(xù)1或者0數(shù)字串。
程序B輸出的結(jié)果是偽隨機(jī)分布：不存在周期性，每當(dāng)連續(xù)出現(xiàn)五個(gè)1之后的下一位必然是0，每當(dāng)連續(xù)出現(xiàn)五個(gè)0之后的下一位必然是1，其他位不可預(yù)測(cè)，只能存在最多連續(xù)5位1或者0數(shù)字串。
程序C輸出的結(jié)果是偽隨機(jī)分布：存在周期性，在不了解所用PRNG算法的情況下在第一個(gè)周期內(nèi)每一位都不可預(yù)測(cè)，第二個(gè)周期開始每一位都可預(yù)測(cè)，在周期長(zhǎng)度限制內(nèi)可以存在充分長(zhǎng)的連續(xù)1或者0數(shù)字串。
程序D輸出的結(jié)果是偽隨機(jī)分布：存在周期性，每當(dāng)連續(xù)出現(xiàn)五個(gè)1之后的下一位必然是0，每當(dāng)連續(xù)出現(xiàn)五個(gè)0之后的下一位必然是1，其他位在不了解所用PRNG算法的情況下在第一個(gè)周期內(nèi)都不可預(yù)測(cè)，第二個(gè)周期開始每一位都可預(yù)測(cè)，在周期長(zhǎng)度限制內(nèi)可以存在最多5位連續(xù)1或者0數(shù)字串。

要理解這一段只要先明確真隨機(jī)分布的特點(diǎn)即可，其不管稱為真隨機(jī)分布或者真隨機(jī)分布都是一樣的，甚至可以直接用隨機(jī)分布來稱呼，它的特點(diǎn)就是不可預(yù)測(cè)和不可壓縮(還記得第一部分關(guān)于這兩點(diǎn)的介紹嗎？)，“不存在周期性”和“可以存在任意長(zhǎng)的連續(xù)1或者0數(shù)字串”都是這兩點(diǎn)的自然推論。

之后偽隨機(jī)分布也很好理解，它就相當(dāng)于在一個(gè)周期內(nèi)(因?yàn)镻RNG的特點(diǎn)導(dǎo)致必然存在周期)盡量去模仿真隨機(jī)分布，一個(gè)優(yōu)秀的PRNG生成的偽隨機(jī)分布幾乎沒有什么辦法在周期內(nèi)和真隨機(jī)分布進(jìn)行區(qū)分，并且還都有很長(zhǎng)的周期(梅森旋轉(zhuǎn)算法周期可以達(dá)到2^19937-1)。
理解這兩者之后就很容易把偽隨機(jī)分布和它們區(qū)分開，實(shí)際上它就是用某種機(jī)制把某一隨機(jī)分布**(既可以是真隨機(jī)分布也可以是偽隨機(jī)分布)進(jìn)行“修正”從而使其更符合應(yīng)用需求。
在下文中為了避免混淆，我們將直接用PRD這一英文縮寫來指代(war3中的這種“概率修正”性質(zhì)的)偽隨機(jī)分布。

抽卡游戲的三種“保底”機(jī)制

不知道有沒有讀者看到這個(gè)章節(jié)題目的時(shí)候會(huì)說“你可算說到有用的東西了”，某種程度上來說確實(shí)如此，“抽卡類游戲”的崛起對(duì)游戲討論環(huán)境的改變是巨大的，過往其他類型游戲的討論中，技術(shù)向的討論通常只有(對(duì)游戲機(jī)制有一定了解)的小部分玩家參與，而抽卡游戲關(guān)于概率與隨機(jī)的討論則幾乎所有玩家都參與進(jìn)來，畢竟涉及到現(xiàn)實(shí)利益嘛。于是這類討論的平均理論水平就被稀釋的很低，各種錯(cuò)誤概念錯(cuò)誤理解甚至于種種玄學(xué)甚至成為主流，這也是促使我寫這篇文章最核心的原因。
既然大家都等了很久了，我們直接進(jìn)入正題，先說兩個(gè)前提性質(zhì)的結(jié)論：

1.幾乎所有抽卡游戲都是使用PRNG(偽隨機(jī)數(shù)發(fā)生器Pseudo Random Number Generator)。
2.幾乎所有抽卡游戲都不會(huì)使用PRD(war3中的**“概率修正”**性質(zhì)的)偽隨機(jī)分布Pseudo Random Distribution

第一點(diǎn)應(yīng)該很好理解，因?yàn)榇祟愑螒蛲枰诙虝r(shí)間內(nèi)處理極大量的抽卡請(qǐng)求，能滿足這樣需求的==TRNG==(真隨機(jī)數(shù)發(fā)生器True Random Number Generator)成本太高，調(diào)試和維護(hù)也比較麻煩，而現(xiàn)有的高端商用PRNG加上高質(zhì)量的種子生成模式足以應(yīng)付需求。
第二點(diǎn)只要回憶一下上面我們講PRD時(shí)候舉的例子就明白了，PRD在減少“一直抽不出五星卡”的情況的同時(shí)更大幅度的減少了“連續(xù)抽到五星卡”的情況(此處“更大幅度”的前提是“抽到五星卡”的初始概率比較低，聯(lián)系一下上面關(guān)于暴擊的概率計(jì)算就明白了)，而這種“歐洲人”的情況對(duì)于游戲體驗(yàn)的提升是巨大的，很多玩家持續(xù)玩下去的動(dòng)力都是獲得了這種體驗(yàn)后的喜悅或者對(duì)于獲得這種體驗(yàn)的期待，更重要的是在“出五星卡概率恒定”和“有足夠多的玩家數(shù)量”兩個(gè)條件下，極少數(shù)“連續(xù)抽到五星卡”的情況是不影響運(yùn)營(yíng)利益的(總期望不變且更加接近理論期望)。
但是，“連續(xù)不出五星卡”的“非洲人”體驗(yàn)帶來的危害也是不能忽略的，絕大多數(shù)玩家放棄一款抽卡游戲的理由都是“沉船棄坑”，于是絕大多數(shù)抽卡游戲運(yùn)營(yíng)商(注意：不是“所有”)都會(huì)設(shè)置一個(gè)“保底機(jī)制”來給玩家一點(diǎn)安慰，在實(shí)際中才用的“保底機(jī)制”主要有以下三種：

洗牌式：
假設(shè)一個(gè)抽卡游戲的概率是這樣設(shè)定的：
五星卡：1%
四星卡：9%
三星卡：20%
二星卡：30%
一星卡：40%
那么我們可以直接用1_{100的數(shù)字來代表這些卡，1號(hào)是五星卡，2號(hào)}10號(hào)是四星卡，11號(hào)_{30號(hào)是三星卡，31號(hào)}60號(hào)是二星卡，61號(hào)~100號(hào)是一星卡。然后使用如下抽卡程序：

1.用PRNG生成的隨機(jī)數(shù)表對(duì)1號(hào)~100號(hào)數(shù)字進(jìn)行排序。 
2.每次玩家發(fā)出抽卡請(qǐng)求，依次反饋排序后的序號(hào)。 
3.根據(jù)序號(hào)生成抽卡結(jié)果。 
4.每當(dāng)1號(hào)~100號(hào)均被抽取過后，重新用PRNG生成的隨機(jī)數(shù)表對(duì)其進(jìn)行排序，等待玩家繼續(xù)抽取。

在實(shí)際應(yīng)用的時(shí)候，可以把序號(hào)增加若干倍，比如使用10000個(gè)序號(hào)，這樣可以容納更多的卡牌，并且最關(guān)鍵的是可以對(duì)同稀有度的不同卡牌進(jìn)行概率控制，具體操作是這樣：
首先我們把序號(hào)擴(kuò)大至10000，那么代表五星卡的序號(hào)就是10000x1%=100即1號(hào)~100號(hào)，之后比如此時(shí)卡池中有五張五星卡，分別分配20個(gè)序號(hào)即可，之后如果想讓某一張卡概率翻倍，只要給它分配40個(gè)序號(hào)，其他卡平分剩下的60個(gè)序號(hào)每人15個(gè)即可，非常方便。

洗牌式與其說是抽卡游戲中的保底機(jī)制，更應(yīng)該被稱為所有抽卡游戲的始祖，首先現(xiàn)實(shí)中的(小規(guī)模)抽獎(jiǎng)自古以來幾乎都是用這種“抓鬮”的方式，之后在電子游戲的雛形期，幾乎所有的程序內(nèi)抽卡機(jī)制都是使用的這種方式，因?yàn)樗诔绦蛏蠘O其簡(jiǎn)單，設(shè)定和調(diào)整也非常方便，但是其缺點(diǎn)也非常明顯：首先這種模式非常容易被玩家發(fā)現(xiàn)，之后如果玩家發(fā)現(xiàn)自己在“一個(gè)序號(hào)循環(huán)周期”的最初幾次抽卡就抽出了五星，那么他就明白接下來的幾乎整個(gè)周期將不會(huì)再出現(xiàn)五星卡，這極大的降低了游戲體驗(yàn)，所以這種機(jī)制目前多用于單機(jī)游戲，或者網(wǎng)絡(luò)游戲中一些和現(xiàn)實(shí)貨幣不掛鉤的抽獎(jiǎng)系統(tǒng)中，還可以通過提供“卡池重置”操作來提高用戶體驗(yàn)。

天井式：
這是最簡(jiǎn)單粗暴的一種方式，直接設(shè)定一個(gè)抽卡次數(shù)，達(dá)到該次數(shù)后，無論抽卡結(jié)果為何(即使已經(jīng)出了高于理論期望值的五星卡)，也直接給予玩家一張五星卡。
該次數(shù)一般設(shè)定為比實(shí)際抽出五星卡的平均期望次數(shù)高很多比如翻倍，以免對(duì)實(shí)際五星獲取率提升過大，造成五星卡貶值。

天井制是最省心的方式，并且因?yàn)樘菀妆话l(fā)現(xiàn)，一般采用這種方式的運(yùn)營(yíng)商都直接將其公之于眾，促使重度消費(fèi)玩家直接以天井為目標(biāo)投入金錢抽卡，當(dāng)然其弊端也是顯而易見的，很容易打擊低消費(fèi)玩家，尤其是其中那些運(yùn)氣不好的，投入達(dá)不到天井又沒有出卡，“打水漂”的感受要比沒有天井機(jī)制的游戲更加強(qiáng)烈，最終容易導(dǎo)致玩家群體分布出現(xiàn)割裂，即只剩下高消費(fèi)玩家和幾乎零消費(fèi)的玩家，這樣沙漏型的玩家結(jié)構(gòu)是不如紡錘形穩(wěn)定的。

水位式：
這種模式有點(diǎn)像war3的PRD了，只不過不需要調(diào)整概率本身，而是給每個(gè)抽卡用戶一個(gè)后臺(tái)“計(jì)數(shù)器”，每當(dāng)玩家進(jìn)行一次抽卡，計(jì)數(shù)器就+1，只要玩家抽出五星卡，計(jì)數(shù)器就歸零，否則就一直增加下去，直到預(yù)先設(shè)定好的一個(gè)“水位值”的時(shí)候，直接讓玩家該次必然獲得一張五星卡。該數(shù)值一般設(shè)定為比抽出五星卡的平均期望次數(shù)稍高一點(diǎn)，讓玩家總體的最低出卡體驗(yàn)比較接近。

這可以說是現(xiàn)在最流行的一種方式了，相當(dāng)于在幾乎不增加“連續(xù)抽到五星卡”情況的前提下大大減少了“一直抽不出五星卡”的情況。并且還相當(dāng)隱蔽，沒有大量的數(shù)據(jù)收集很難被發(fā)現(xiàn)，同時(shí)又有很大的調(diào)整空間，然而恰恰因?yàn)楹髢蓚€(gè)優(yōu)點(diǎn)，大部分運(yùn)營(yíng)商都將其作為后臺(tái)參數(shù)進(jìn)行保密，于是一旦被發(fā)現(xiàn)，也會(huì)影響運(yùn)營(yíng)方的信譽(yù)，因?yàn)楫吘股婕暗浆F(xiàn)實(shí)利益，很多玩家會(huì)覺得既然有“后臺(tái)參數(shù)調(diào)整”的機(jī)制，那么即使現(xiàn)在運(yùn)營(yíng)做的是“利于玩家的調(diào)整”，但是難保以后運(yùn)營(yíng)方不會(huì)利用這些機(jī)制做“不利于玩家的調(diào)整”，所以說消費(fèi)者的心還真的很難掌握呢。

原理層面：

應(yīng)用層面

隨機(jī)在科研和生產(chǎn)中的應(yīng)用

這里先簡(jiǎn)單說兩點(diǎn)：
1.實(shí)際科研生產(chǎn)中偽隨機(jī)往往優(yōu)于真隨機(jī)。
如今的我們很難想象，在那個(gè)“計(jì)算機(jī)只能生成真隨機(jī)數(shù)的時(shí)代”，當(dāng)科研人員需要使用隨機(jī)數(shù)的時(shí)候，往往是捧起一本巨大的《隨機(jī)數(shù)表》，隨便翻一頁(yè)直接用里面的隨機(jī)數(shù)，甚至在我國(guó)2008年發(fā)布的關(guān)于質(zhì)檢的國(guó)家標(biāo)準(zhǔn)《GB/T 10111-2008》的附錄中還有隨機(jī)數(shù)表

真隨機(jī)一定公平嗎

當(dāng)然不是了，首先理想的硬幣就不存在，其次即使是理想的條件下，我們也可以很容易構(gòu)造出一個(gè)不公平的真隨機(jī)數(shù)發(fā)生器：

取一枚理想的骰子，把1、2兩個(gè)面寫上“正”字，把3、4、5、6四個(gè)面寫上“反”字，然后把它視為一個(gè)硬幣去投擲并用1和0分別代表正面和反面來記錄結(jié)果。

顯然它生成的由1和0組成的數(shù)列中出現(xiàn)0的概率是1的兩倍，然而我們無法用這一規(guī)律進(jìn)行預(yù)測(cè)和壓縮，所以它仍然是真隨機(jī)的。
有一個(gè)方法可以在保持真隨機(jī)的前提下提高公平性：

我們現(xiàn)實(shí)中的硬幣因?yàn)檎磧擅鎴D案不同，所以出現(xiàn)的概率必然也有微小的差別，如果需要用硬幣進(jìn)行嚴(yán)肅的決定(所以說為什么嚴(yán)肅的決定要用硬幣??！)
可以用這樣的機(jī)制：

1.將該硬幣連續(xù)投擲兩次。 
2.將“正、反”的結(jié)果視為“正面”，將“反、正”的結(jié)果視為“反面”。 
3.如果出現(xiàn)“正、正”或者“反、反”的結(jié)果就將其忽略，重新進(jìn)行兩次投擲直到出現(xiàn)步驟2中的情況。

于是即使我們使用了一枚極其不公平的硬幣，比如說正面的概率是反面的兩倍，那么“正、反”的概率為2/3乘以1/3等于2/9，“反、正”的概率為1/3乘以2/3還是2/9。始終是公平的。

當(dāng)然這種公平性實(shí)際上也是相對(duì)的，畢竟第一次投擲造成硬幣在微觀層面上的變形或磨損也可能會(huì)影響第二次投擲的結(jié)果，但是對(duì)于能用一枚硬幣來決定的事情來說這種公平性應(yīng)該是足夠了，但是我們由此也會(huì)發(fā)現(xiàn)一個(gè)事實(shí)：

彩票用的搖獎(jiǎng)機(jī)是完美的真隨機(jī)發(fā)生器，但實(shí)際上對(duì)于單次搖獎(jiǎng)結(jié)果來說并不公平，雖然這種不公平性在極微觀的層面導(dǎo)致無法人為控制。
目前彩票中心是通過每次搖獎(jiǎng)更換新球的方式來使這種不公平被平均化大體上消除，然而如果所有彩民都是理性的且追求公平性的話，彩票中心用一個(gè)足夠優(yōu)質(zhì)的偽隨機(jī)發(fā)生器反而更公平……

偽隨機(jī)是否代表一定有“玄學(xué)時(shí)段”或者“窗口期”

先和我一起念下面這句話：

程序員第一定律：程序員永遠(yuǎn)會(huì)用最low的代碼去實(shí)現(xiàn)用戶需求。

然后回顧一下前面關(guān)于PRNG的概念，再看看那個(gè)完整的隨機(jī)機(jī)制設(shè)計(jì)案例，然后請(qǐng)問大家，如何在偽隨機(jī)發(fā)生器的層面實(shí)現(xiàn)可供利用(最起碼長(zhǎng)度達(dá)到數(shù)分鐘)的“玄學(xué)時(shí)段”？
之后如果你真的理解了前文，你只會(huì)有一種反應(yīng)：

這不是有病嗎?。?/mark>

首先，想要在偽隨機(jī)發(fā)生器層面實(shí)現(xiàn)“玄學(xué)時(shí)間”本身倒不難，只要縮短周期就行了，然而別忘了，PRNG首先要保證高速生成大量高質(zhì)量隨機(jī)數(shù)這一要求，這就太難了，需要在隨機(jī)數(shù)表的應(yīng)用模式上附加大量的機(jī)制，總的來說，兩個(gè)字，有病。
如果真的想要在某個(gè)時(shí)段讓玩家出卡率提高，直接在概率設(shè)定上改不就好了嗎？這和真隨機(jī)偽隨機(jī)有什么關(guān)系呢？所以總結(jié)一下就是以下幾句話：

1.存不存在“玄學(xué)時(shí)段”和游戲是否采用偽隨機(jī)發(fā)生器沒有任何關(guān)系。
2.同理如果存在“玄學(xué)時(shí)段”也不能說明游戲采用了偽隨機(jī)發(fā)生器。
3.運(yùn)營(yíng)方的任何概率調(diào)整唯一的原因就是利益層面，而“(非公開的)玄學(xué)時(shí)段”帶不來什么利益，程序員不寫沒用的代碼。
4.如同我前面那個(gè)案例所說，抽卡游戲幾乎都是在服務(wù)器上設(shè)置單獨(dú)的、不和現(xiàn)實(shí)時(shí)間周期有對(duì)應(yīng)的、定期重置的計(jì)數(shù)器，即使運(yùn)營(yíng)方人為設(shè)置了“玄學(xué)時(shí)間”也和現(xiàn)實(shí)時(shí)間不一定存在對(duì)應(yīng)關(guān)系。

可是為什么我抽卡的時(shí)候感覺有很明顯的“玄學(xué)時(shí)段”或者“窗口期”呢

說明運(yùn)營(yíng)方使用了高質(zhì)量的偽隨機(jī)發(fā)生器。

如果抽卡時(shí)候讓你感覺有很明顯的“玄學(xué)時(shí)段”或者“窗口期”，是因?yàn)檫\(yùn)營(yíng)方使用了高質(zhì)量的偽隨機(jī)發(fā)生器，抽卡結(jié)果非常近似于真隨機(jī)。

隨機(jī)分布產(chǎn)生的疏密是在已經(jīng)產(chǎn)生了結(jié)果后對(duì)結(jié)果的“歸納”，在生成層面是無法加以利用的。
舉例說明就是觀察一個(gè)大城市生男孩和女孩的比例，最終的結(jié)果可能是各約50%，比如女孩495811人：男孩501933人，但是如果分別觀察每一棟居民樓生男孩和生女孩的比例，非常容易出現(xiàn)比如女孩1人：男孩3人這樣“女孩25%，男孩75%”這樣看似懸殊的比例，也就是所謂的疏密。
這是隨機(jī)分布本身的特點(diǎn)，而并非有一種機(jī)制強(qiáng)行去制造這種疏密，同樣也不存在一種機(jī)制在宏觀上去平均這種疏密，如果不理解這一點(diǎn)，就容易陷入一種悖論之中：
假設(shè)你所在的居民樓目前有4個(gè)女孩，1個(gè)男孩，你妻子剛懷孕，你覺得生男孩的概率高還是生女孩的概率高？
**A思路：**男孩的概率高，我們這個(gè)城市的女孩和男孩比例是1：1，這棟樓現(xiàn)在是4：1，肯定要平衡成1：1的。
**B思路：**女孩的概率高，我們樓的女孩和男孩比例是4：1，說明我們樓更容易生女孩。
這兩種思路顯然都是荒謬的，然而非常不幸的是，在網(wǎng)絡(luò)上關(guān)于概率的討論，就我觀察而言，90%以上都是按這兩種思路在討論。

偽隨機(jī)是否一定可以“墊刀”

所謂“墊刀”就是“利用保底機(jī)制獲利”的意思，比如war3劍圣砍雜兵好幾刀沒出致命一擊就趕緊去砍對(duì)方英雄，因?yàn)槌鲋旅粨舻母怕时籔RD疊高了很多，“墊刀”的稱呼源自某上古網(wǎng)游中的武器強(qiáng)化機(jī)制，一旦強(qiáng)化失敗武器會(huì)破碎消失，于是很多人先用垃圾武器去強(qiáng)化，連續(xù)破碎幾把之后才強(qiáng)化高級(jí)武器。
對(duì)于這個(gè)問題，能看到這里的朋友好像不需要我再做詳細(xì)解釋了，直接給結(jié)論：

1.能不能“墊刀”跟是不是偽隨機(jī)沒有任何關(guān)系。
2.如果存在“墊刀”機(jī)制也是運(yùn)營(yíng)方在隨機(jī)數(shù)發(fā)生器之外單獨(dú)設(shè)置的，和真隨機(jī)偽隨機(jī)也沒有任何關(guān)系。
3.對(duì)于“洗牌”或者“天井”機(jī)制來“保底”的抽卡游戲來說“墊刀”沒有意義，前者墊不墊你都得輪到那個(gè)號(hào)才出五星，后者明晃晃的天井在那給你數(shù)著呢你還墊什么。
4.對(duì)于“水位”機(jī)制，看似“墊刀”很有意義，畢竟計(jì)數(shù)器一直漲上去肯定會(huì)出，然而仔細(xì)思考一下就會(huì)發(fā)現(xiàn)實(shí)際上根本沒法墊，因?yàn)槊恳淮纬榭ǖ某晒Ω怕试谀菙[著呢啊，你想墊的過程中抽出五星了那計(jì)數(shù)器不就歸零了，所謂的“墊刀操作”在這類游戲中實(shí)際不就是“普通的抽卡操作”么。
5.至于“在游戲內(nèi)代幣池抽若干次不出好東西再去氪金池抽”這種操作就太掩耳盜鈴了，基本只有八九十年代的單機(jī)游戲才會(huì)整個(gè)游戲使用一張隨機(jī)數(shù)表，抽卡游戲里不同的卡池都是使用單獨(dú)的偽隨機(jī)發(fā)生器的。文章來源地址http://www.zghlxwxcb.cn/news/detail-439242.html

到了這里，關(guān)于【雜談】概率與隨機(jī)以及手游抽卡機(jī)制的科普的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！