不亂的「亂數」

開場先上兩個遊戲相關的新聞。

其一應該比較多人知道：最近新出的《魔物獵人 崛起》當中，用來抽選鍊金石的〈鍊金術・幽玄〉被爆出在很少量的抽選之後竟然就開始循環，造成根據玩家不同，有的人只會得到某幾種結果不斷循環，無法獲得其他種類。這件事國內外有不少網站有報告過，大家自己搜尋一下都找得到。

其二大概就比較少人知道了：老牌沙盒遊戲《Minecraft》當中，被人發現有一些亂數生成的特徵具有不可思議的關連性，包含一些實際距離很遠的特性 (例如地表的黏土堆和地底的鑽石團，它們的水平座標竟然可以非常接近)。我這裡連結兩篇文，一篇是其他人轉貼到 PTT 的 Minecraft 版的文章在這裡，一篇則是我簡單地解說背後的原因在這裡。

這兩個新聞所提的現象雖然看起來不太一樣，但都有一個特性：這個「亂數」怎麼看起來並不亂？

LCG (線性同餘產生器)

首先，我不確定這個觀念是不是很多人都有了所以在此重提一次：

電腦程式並沒有「真」隨機，只有根據演算法產生的「偽」隨機亂數。

程式無法無中生有生出隨機值，只能根據固定的輸入產生固定的輸出；因此我們需要的是一個演算法，給定一些輸入（稱做「種子」），能夠產生出「統計上」看起來是隨機的輸出。這個「統計上的隨機」，意思是在產生足夠長的序列之後，其某些統計量具有跟理論上的隨機序列類似的結果。這在數學上可以表示為一個統計檢定問題：這些產生出來的序列是否符合「這是由理論隨機產生器產生的序列」這樣的統計假設？不過這方面不是我們今天的主題，就在此表過不提。有興趣的人可以從英文維基百科條目 Statistical randomness 及 Randomness test 開始研究。

在遊戲方面使用的亂數絕大部份都是使用各個程式語言內建的「線性同餘產生器」(Linear Congruential Generator, LCG)。這麼稱呼的原因是，這個決定下一個亂數的演算法可以表示為這樣的數學公式：

$$X_{k+1}=a\cdot X_k+c\mod m$$

其中 \(a, c, m\) 是固定的常數，\(X_k\) 是前一個亂數，\(X_{k+1}\) 則是所產生的下一個亂數。這條公式是線性公式（輸入值的一次式），算完後除以一個除數 \(m\) 求餘數，因此才稱做「線性同餘」。¹

會提出這個式子的原因其實和乘法群裡的原根有關。原根具有的性質是：

對正整數 \((a,m)=1\)，如果 \(a\) 是模 \(m\) 的原根，那麼 \(a\) 是整數模 \(m\) 乘法群 […] \(\mathbb{Z}_m^\times\) 的一個生成元。

中文維基百科 原根 條目

「生成元」白話地說就是：如果一直進行乘以 \(a\) 之後除以 \(m\) 求餘數的話，它可以取遍 \(1\) 到 \(m-1\) 中和 \(m\) 互質的所有數，因此每 \(\varphi(m)\) 個數就會循環。那麼，當取 \(m\) 是一個質數時，就能獲得一個 \(1\) 到 \(m-1\) 的排列，這就提供了一個直覺上的「亂數排列」。\(+c\) 的作用則是將這樣產生的序列進行某個程度的平移，讓即使單獨乘以 \(a\) 無法產生全排列的狀況也有機會加上平移產生全排列，甚至連原先只靠乘時無法產生的 \(0\) 也有機會產生了。

一個簡單的例子：若我們取 \(a=41, c=17, m=100\)，則從 \(X_0=0\) 開始可以依序得到這個序列：
0, 17, 14, 91, 48, 85, 2, 99, 76, 33, 70, 87, 84, 61, 18, 55, 72, 69, 46, 3, 40, 57, 54, 31, 88, 25, 42, 39, 16, 73, 10, 27, 24, 1, 58, 95, 12, 9, 86, 43, 80, 97, 94, 71, 28, 65, 82, 79, 56, 13, 50, 67, 64, 41, 98, 35, 52, 49, 26, 83, 20, 37, 34, 11, 68, 5, 22, 19, 96, 53, 90, 7, 4, 81, 38, 75, 92, 89, 66, 23, 60, 77, 74, 51, 8, 45, 62, 59, 36, 93, 30, 47, 44, 21, 78, 15, 32, 29, 6, 63
63 的下一個回到 0，就開始循環了。可以看到這裡 0~99 每個數字都出現恰好一次。

這種型式的產生器有個很明顯的缺點：固定常數 \(a, c, m\) 不能隨便亂選。不是所有的\(a, c, m\) 的組合都會產生全排列 (有一些數學上的必要條件存在)，而就算是全排列也不一定夠亂。舉個例：如果選 \(a=c=1\)，那麼雖然我們得到了一個 \(0\) 到 \(m-1\) 的排列，但卻是按照 \(0, 1, 2, \cdots, m-1\) 的順序產生，這顯然不能稱做「亂」數。好一點的乘數能夠稍微打散一點這樣的「順序性」，但其更深層的關連性卻是到了近二三十年才被詳細的研究分析的。

取高位 vs 取低位

在還找不到更好的演算法之前，其實是有一個簡單的用在 LCG 上的補救法的：把內部狀態的範圍取大一點，然後只取更新後的高位位元做為輸出。理由很簡單：如果亂數每次都是 \(m\) 個一組每個數字各一次，那顯然也不很「亂」；那如果丟棄掉循環比較明顯的低位的話，高位表現出來的「亂度」會稍微好一點。

繼續上面的例子：如果把上面序列的個位丟掉，以十位作為產生的亂數，則 100 個數循環的序列會是這樣子的：
0, 1, 1, 9, 4, 8, 0, 9, 7, 3, 7, 8, 8, 6, 1, 5, 7, 6, 4, 0, 4, 5, 5, 3, 8, 2, 4, 3, 1, 7, 1, 2, 2, 0, 5, 9, 1, 0, 8, 4, 8, 9, 9, 7, 2, 6, 8, 7, 5, 1, 5, 6, 6, 4, 9, 3, 5, 4, 2, 8, 2, 3, 3, 1, 6, 0, 2, 1, 9, 5, 9, 0, 0, 8, 3, 7, 9, 8, 6, 2, 6, 7, 7, 5, 0, 4, 6, 5, 3, 9, 3, 4, 4, 2, 7, 1, 3, 2, 0, 6
這個序列雖然出值只有 0 到 9，但至少看起來是有亂一點了；而個位則是 0, 7, 4, 1, 8, 5, 2, 9, 6, 3 的循環，顯然並不能當做好的亂數來用。

這個「取高位」和「取低位」的差別，其實正是一些使用 LCG 的亂數演算法表現不佳的原因。或許有人聽說過：取某個小範圍的亂數時不要把系統給的亂數除以範圍取餘，而是先除以出值範圍變成 \([0,1)\) 再乘以所要的小範圍，其理由就是這個：除以範圍取餘等同於取了亂數出值的「低位」(例如上面的例子中除以 10 取餘即是取個位)，而先除以出值範圍則相當於取亂數出值的「高位」(例如上面例子中除以 100 後乘以 10 再取整即是取十位)。

不過如果用的是比較近代一點的系統，那這個高低位的差別其實已經不大了。這是因為，現在還留存的使用 LCG 的實作，幾乎都會有比較大一點的內部種子長度，出值時再把低位給丟掉；也就是其實函式庫已經先幫你「取高位」了。例如《Minecraft》所使用的 java.util.Random 的實作，其參數為 \(a=25214903917, c=11, m=2^{48}\)，內部種子是 48 位元的數字，但輸出時至少捨棄低 16 位元；這樣規定的理由就在這裡。

「推算」亂數

既然提到了《Minecraft》，就來提一下最開頭提到的那個發現好了。這也是 LCG 有的另外一個弱點的展現：對於相近的種子數，其後數個出值之間有很強的關連性。這一點從 LCG 的公式裡就可以看得出來了：差 1 的種子數得到的下一個亂數只差 \(a\)，而這是個已知值。

對於已知差距的兩個種子，只要我們有辦法得到兩者之一的出值、或是由這個出值導出的小範圍值 (不論它取了高位或低位)，那就能大致上推算另一個亂數值或以同樣方法導出的小範圍值。繼續上面的範例，若以 9 為種子，下一個亂數是 86，取個位的話得取值是 6；差 1 的種子亂數出值會差 41，所以可以簡單推算出若以 10 為種子，下一個亂數取個位會是 7：實際上的出值是 27，個位確實是 7。

這個關連性甚至不限於下一個出值，而是後續的所有出值都有一樣的關連：下兩個出值會差 \(a^2\)，下三個會差 \(a^3\)，等等。《Minecraft》的狀況是，為了生成兩項特性所使用的導出種子碼數值很接近 (是某個和世界種子及 chunk 座標有關的函數加上兩個很接近的常數)，因此我們可以藉由其中一個亂數決定的一項特性的水平位置座標 (頭兩個亂數出值)，推算出另一個亂數決定的另一項特性的水平座標。

由於 java.util.Random 在取值時會幫你取高位，出值很接近代表取高位得到的數值也會接近到幾乎相同，因此這代表下一個出值幾乎相同，再下一個出值只會有少量差別。也就是，兩個方向的座標其一會幾乎相同，另一會有個可以推算的差值；這就是那則影片所介紹的關係的背後原理所在。²第三個亂數出值在兩項特性上的用途不同 (一邊是型態種類，另一邊是垂直座標)，但因為也有這種推算關係，數值上的偏移值可以轉化為兩者之間的 (半) 對照表，一邊是這種型態則另一邊的垂直座標會在哪個範圍這個樣子。

這還只是一個比較簡單的推算方式，如果要深究的話有很多數學關係可以一拉拉一串出來的。一個稍微進階一點的例子是 Spectral Test，它將連續數個出值當做一組，觀察它在出值空間中形成的超平面來評估強度；能夠這樣找的原因正是 LCG 亂數連續出值之間也有很強的關連性。因此在一些這種推算會造成弱點的應用上 (例如密碼學)，所要使用的亂數都不會是這種簡單的演算法，而是會經過更多複雜運算讓輸出的位元組之間的關係幾乎被打散開來的偽亂數演算法。不過這裡在談的是遊戲上的應用，是沒有必要動到這把牛刀的，就在這裡簡單帶過。

2021/10/14 補充：Minecraft 1.18 將會使用新的亂數生成演算法 xoroshiro128++，是不屬於 LCG 形式的亂數產生器，因此這些推算方式無法適用到新的演算法上；不過 xoroshiro128++ 有它自己的弱點在，但是否能有類似的推算方式就需要進一步研究了。

2023/5/20 補充：Minecraft 1.20 將掉落物也綁定種子，而有人利用了 xoroshiro128++ 數學形式上的弱點進行了一系列的掉落物預測「攻擊」。意外的是，這次顯示出來的弱點和上面我所解說的使用 java.util.Random 時的弱點，其核心原因竟然是很接近的：都是兩個有相關性的種子產生的亂數序列之間的關聯性；這次因為 xoroshiro128++ 的數學形式關係，還可以進行掉落物關連性統計，某種程度上可以類比前面提到的兩團生成性質的關連性性質。詳情就請看這則影片吧。

平方「亂數」

說到不同的演算法，上面提的都是 LCG 這種類型的演算法，因為實作簡單，又很容易有好的性質，加上很多程式語言及函式庫都直接內建了，因此對於遊戲這種類型的應用來說已經足夠了。

但如果就是有人覺得「這太簡單了，我有個好點子來把它搞複雜一點」的話呢？在偽隨機亂數這個領域上，隨便搞複雜一點可是很容易弄巧成拙的。

這裡就來提一個很有名的「爛」偽隨機亂數：平方取中法。它的公式很簡單：取一個 \(n\) 位數的種子 (\(n\) 要是偶數)，平方之後補到 \(2n\) 位，然後只截取正中間的 \(n\) 位下來做為下一個亂數出值。以數學公式表示的話就是：
$$X_k=\left\lfloor\frac{X_{k-1}^2}{10^{n/2}}\right\rfloor \mod 10^n$$
例如若取 \(n=6\) 則可能會這麼進行：
$$\begin{array}{lll}
675,248&\to675,248^2=455,959,861,504&\Rightarrow959,861\\
&\to959,861^2=921,333,139,321&\Rightarrow333,139\\
&\to\cdots\end{array}$$

看起來很不錯嗎？如果寫支程式把這串亂數繼續取下去會發現：675248 這個起始值會在 210 次亂數之後到達 625000，然後就卡在這個數了。更可怕的是，如果你對全部一百萬個種子都丟下去跑，會發現所有數在足夠多次亂數之後都會掉進以下 17 個迴圈之一當中：

一百萬個數都會掉進這 475 個數當中，其中有超過三十萬個數會掉進 1834 開始的這個長達 210 個數的迴圈，而在迴圈外待最久的是 229339，卻也只用了 923 步就進入 16000 迴圈二十個數當中的 736000。這顯然是個連普通都算不上的偽隨機亂數－－而造成這個現象的理由僅僅是公式裡用了一個平方而已。

為什麼？因為平方這個操作是個多對一的操作，會有多個種子得到的下一個亂數是相等的，這就使得數值範圍逐漸收窄，收到最後就變成很有限的迴圈了。之所以取中不是原因是因為，取中其實只是把上面討論過能夠有一點推算依據的低位和高位給丟掉了而已；要說這樣的操作就能使數值推移變成這樣其實不太符合直覺，因為都把有一點規則的東西丟了嘛。

說到這裡，有些人可能會有一些既視感出現了：最一開始提到的《魔物獵人 崛起》當中出現的 bug，看起來很像是上面這種跑一跑最後掉進一個短迴圈裡的現象；而就在這篇文章發表前不久，又有進一步的研究指出事實上有的時候是會掉進一個很大的迴圈當中的 (其中一個比較有名的迴圈甚至長達 2647 個護石)，又跟上面那個 210 個數的迴圈可以相類比。我手上沒有 Switch，所以我連實際遊戲都沒有碰過，更不可能知道實際程式碼，但這樣的現象和平方取中亂數有這麼類似的性質，很難不懷疑這遊戲使用的偽隨機亂數是不是因為公式不知為何出現了種子數的平方或高次方才會有這種狀況出現。³

好在我們現在有了除了 LCG 之外不錯的選擇了：近代常見的偽隨機亂數演算法有不少是基於線性反饋移位暫存器 (LFSR) 定義的，例如 Mersenne Twister、XorShift⁴、WELL 等，實作不會比 LCG 複雜太多，又能有比 LCG 更好的性質 (例如極長週期、多維均等分布等性質)，因此在不少地方都慢慢出現更多這些演算法的使用了。

亂數的使用

上面我提到有個說法說取小範圍的亂數時不要拿出值直接除以那個範圍取餘，有些人可能聽過另一個理由是：這樣取出來的範圍會不平均，有些值會比其他值多一次。這個理由是真的：以上面的 0~99 的亂數為例，如果除以 3 取餘數的話，在這 100 次當中 0 會出現 34 次，1 和 2 則只會出現 33 次，這樣並不是均勻亂數。但是，如果持這個理由說要先變成 \([0,1)\) 再乘才是對的的話，那就不對了。不管是怎麼取，只要單取這一次並進行任何數學轉換，你就是在把這 100 個出值塞進 3 個箱子裡，不管你怎麼分一定不會平均。

那要怎麼辦？這其實並不需要到電腦世界才有答案。在「亂數」這回事仍然需要一張很大的亂數表來查的時候，就已經有了應對這種轉換的指示：「取出所需要的位數之後，如果得到的值超過所要的範圍，就丟掉這個亂數重取一個。」這其實才是我們該做的：把不平均的比例給丟掉重新取一個新的。現在我們有電腦程式運算，這個指示我們其實能做得更好：我們把所要的範圍重覆到出值範圍，在這之外零散的才丟掉。在亂數表上要取 0 到 2，我們會丟掉 3 到 9；但其實我們能只丟掉 9，把 3~5 和 6~8 也對應到 0~2，這樣得到的亂數也是均勻的。

這其實是個更大一部份的亂數應用最常出現的問題：在不同的離散分布之間進行轉換時，使用了錯誤的方式進行轉換，使得轉換成的分布和所想要的分布出現差距。最常見的例子是很多人學程式學到亂數時會做的習題：將一副 52 張的撲克牌洗亂。初學的人很容易就會寫出像下面這樣的程式碼：

for(int i = 0; i < 1000000; i++)
{
    int x = randomInt(52);
    int y = randomInt(52);
    int temp = card[x];
    card[x] = card[y];
    card[y] = temp;
}

簡而言之，每次都隨機找兩張牌對調，這樣做夠多次之後就洗亂了。⁵數學上來說，如果你的交換能做無限多次，那在極限狀況下確實是能夠均勻地把所有牌洗亂沒錯－－但是，程式不能執行無限多次，而單單有限次數這件事就會和極限狀況之間有個小差距存在，交換次數越少這個差距就越明顯。

正確的洗牌方式是使用 Knuth Shuffle (又稱 Fisher-Yates Shuffle)⁶：

for(int i = 0; i < 52; i++)
{
    int r = randomInt(52 - i) + i;
    int temp = card[i];
    card[i] = card[r];
    card[r] = temp;
}

這樣就能夠在有限步驟當中均勻地把一副 52 張牌給洗混了。詳細演算法的解釋可以參照上面連結的維基百科，這裡就不多提了。

也就是說，有的時候亂數不亂是因為應用時的演算法不正確造成結果的機率不平均的關係。這一點差別在普通的遊戲裡可能還不是那麼重要，但如果是博奕類的遊戲，一點點的機率不平均長期下來都會造成偏誤，這就會使得這些遊戲的公正性遭受質疑了。一個這方面比較有名的好例子是，知名的網路日本麻將對局網站天鳳，把他們所使用的牌山生成演算法及所使用的亂數種子給公開，讓所有人可以依照所公開的演算法程式碼 (正是 Fisher-Yates 演算法) 及亂數種子求得實際對局時洗亂的牌山，再和公開的牌譜資料進行互相對照驗證；當然也就有許多人依照他們所提供的資料進行驗證和研究，所以我們可以有很高的信心說，在這個網站上面打牌並不會發生系統故意把特定型式的牌發給某些人之類的問題。

小結

這篇的長度已經是之前寫編碼文章的快兩倍長了，所以也寫了好一陣子。給一個相對時間線的話，開頭提到的這兩件新聞就是讓我起心想寫這一篇的動機，這還是在《魔物獵人 崛起》的 bug 還剛發現八顆短循環的時候；而在整理這些東西的時候又被我聽說了「會掉進一個大循環」的發現，所以原本只單純想談 LCG 和其後的演算法使用的硬是加了一段簡單談了不好的亂數公式。

對這方面有研究的人也會發現，我這裡其實省略了很多非常細的細節 (例如被我一筆帶過的統計檢定、和比較新一點的 LFSR 式產生器)，主要焦點其實是 LCG 類型亂數應用在遊戲上的狀況；也因為文章真的已經寫太長了，雖然帶到了博奕類遊戲，但卻刻意沒提例如轉蛋系統等題材 (況且這方面我還真的沒資格談，這方面的實作有很多遊戲設計上的需求要考量，並不是直接拿亂數隨便丟就可以的)。

在這個人人都會寫程式都想寫遊戲的時代，是否正確地使用亂數可以很大程度地影響遊戲體驗 (對，我到結語了還是在鞭《魔物獵人 崛起》XD)；不過坦白說這其實是個不容易做對的題材，因為做對了玩家大多不會注意，只有做錯了才會被挖出來談，所以常常時不時就有同樣的問題在各種遊戲當中出現。希望這篇能夠給大家一個簡單的起步。

(說起來，這 blog 的副標上有遊戲兩個字，結果卻是到了現在才有第一篇有遊戲分類的文章……(汗)

註腳

1. 英文維基百科上在這裡有條註解：通常在數學上會稱有 (+c) 的變換叫做「仿射變換」，「線性變換」單純只稱乘上固定值的變換；但在電腦科學界已經把這個式子叫做線性叫習慣了所以就這樣用了。 ↩︎
2. 這裡我略去了 java.util.Random 在設定種子時會先做一次 XOR 的操作，因為只要其結果仍然只有小差距那這些推論就都仍然成立。那則影片的最後解釋了這個 XOR 操作有時會造成預測失準，這裡就表過不提。 ↩︎
3. 題外話，平方也不是做不出好亂數喔：有個名為 Blum Blum Shub 的隨機亂數產生器即是以平方做為基本演算法，但對參數做了嚴格限制使其擁有更好的性質，甚至有著密碼學上的強度在。 ↩︎
4. 2021/10/14 補充：上面補充裡提到的 xoroshiro128++ 就是 xorshift 的改進版 xoshiro 系列演算法之一，加入了位元旋轉的操作，但基底仍然是類似 LFSR 的結構。 ↩︎
5. 提一件小趣事：二十年前的我初學 C/C++ 的時候，學到亂數這裡時就做過類似的題目，而我當時正是寫出了這個「做法」XD 在學了更多東西之後才知道這個做法是錯的。 ↩︎
6. 會叫 Knuth Shuffle 的原因是因為，Knuth 這位大神在他的鉅作《The Art of Computer Programming》當中推廣了這個演算法適用於電腦程式的修正版的關係。最初由 Fisher 和 Yates 兩個數學家提出時，還是使用紙本亂數表的年代，所以他們描述的步驟寫成程式是有點不那麼方便的。 ↩︎