從《羊了個羊》看隨機數的生成原理

語言: CN / TW / HK

theme: channing-cyan

“我報名參加金石計劃1期挑戰——瓜分10萬獎池,這是我的第1篇文章,點選檢視活動詳情


你的《羊了個羊》第二關通關了嗎?

作為一款三消類的休閒小遊戲,《羊了個羊》雖然在玩法上並沒有多大創新,但卻以其相鄰關卡間巨大的遊戲難度落差成功出圈。討論度提高的同時,也招致了一些批評的聲音,主要是指責《羊了個羊》毫無遊戲性可言,罪狀無一例外都提到同一個詞——隨機性

簡單講就是,三消類的遊戲雖然看起來是一堆混亂無序的元素,但大體遵循一些預設的遊戲規則,比如每種元素的數量以及所有元素的總數量一定數字3的倍數,以保證所有的元素最終都能配對消除並獲勝,只是每種元素出現的時機是隨機的而已。

但《羊了個羊》偏偏“不講武德”,它讓每種元素出現的概率都是隨機的,也就是批評者口中的“真隨機性”,這樣導致的結果就是,你分配到的牌局可能從一開始就是個死局,等你玩到最後才發現根本無法完全消除。

最後的無解情況.png

今天我們不討論《羊了個羊》“武德”問題,但既然提到了遊戲中的隨機性問題,那我們就想站在程式的角度來好好說道說道了~


大家好,我是玩羊玩到晚上要數羊睡覺的椎鋒陷陳,今天我們要分享的主題是隨機數的生成原理

可能有讀者要產生疑惑了,我們討論的不是遊戲中的隨機性問題嗎,怎麼變成了隨機數的生成原理了?這是因為,隨機數本身就是隨機性所產生的結果,又是反過來指導遊戲行為的依據,比如《羊了個羊》中每回合出現的元素種類,所以引申出來討論隨機數的生成原理並不生硬。

這裡我們首先要探究的一個問題就是,遊戲中產生的隨機數,是真的隨機數嗎?很遺憾,並不是,這裡面大部分產生的都是偽隨機數

偽隨機數是什麼?

計算機是確定性的,這意味著其產生的所有行為,都是由其預先編寫的所有指令所決定的,僅依賴一個確定性的事物,是無法產生一個隨機性的結果的。

隨機數.png

我們拿到的所謂隨機數,只是看起來隨機而已,也就是說,只是符合統計學上對於隨機性認定的要求,但隨機數的產生過程卻是確定的

什麼意思呢?

首先,偽隨機數生成器內部制定了一個演算法,本質上就是一個數學公式。公式所得到的隨機數集是一個序列,序列中的每一個隨機數,都是由前一個隨機數代入相同的公式計算得出的

而序列的起始值,我們稱之為種子數,決定了整個隨機數序列的所有數值。

所以,理論上,我們只要知道偽隨機數生成器的種子數和內部演算法,就可以推演出整個隨機數序列。因此,偽隨機數生成器是不安全的,不能用於安全係數要求高的場合,比如登入時預設的隨機密碼生成,但對於《羊了個羊》這一類的休閒小遊戲來講還是沒啥問題的。

那麼,偽隨機數生成器都有哪些演算法呢?

偽隨機數生成器演算法

平方取中法

平方取中法是由馮·諾伊曼提出的一種產生均勻偽隨機數的演算法,演算法的原理很簡單,首先選定一個種子數,假設是一個四位數字,比如4321。

接著,正如演算法的名字所表述,先對種子數進行平方4321^2=18671041,再取中間四位數字18[6710]41,從而得到序列下一項6710。

如果平方後不足八位,則在數字的前面填充0直至滿八位,如241^2=58081=00[0580]81=0580。

隨後重複這個過程,就能持續生成多個位於0到9999之間的隨機數。

線性同餘生成器

不過,這顯然不能滿足我們需要生成偽隨機數的多數場景。目前生成偽隨機數的最佳演算法,是一種叫做馬特賽特旋轉演演算法的現代演算法,其基於更簡單的線性同餘生成器,一種常見的偽隨機數生成器。

線性同餘生成器要求有4個輸入,除了固定要求的種子數之外,還有模數m、乘數a以及增量c

計算方式是種子數乘以a再加上c,然後把計算結果對m進行求模,也即除以m並取餘數。

線性同餘生成器.png

隨後重複這個過程,就可以得到餘下的隨機數序列,得到的隨機數將位於0到m-1之間。

演算法過程我們瞭解了,但線性同餘生成器又是憑藉什麼優勢,在偽隨機數生成這方面更受青睞的呢?

線性同餘生成器的優勢

其實,無論是哪一種偽隨機數生成器演算法,除了前面所提到的安全性問題之外,還有一個相同的天然缺陷,那就是其生成的隨機數序列,無論長短,最終都會重複出現,即形成一個迴圈。

因此就有了週期的說法,所謂週期,指的就是在兩次迴圈之間出現的不同隨機數項的數目

原因我們前面已經講了:恆定的計算公式,以及依賴於前一個隨機數。

我貼一部知名恐怖電影的海報你們就懂了:

恐怖遊輪.png

而線性同餘生成器的優勢在於,其週期的長度是m-1,即取決於模數m,只要保證m的取值儘量大,比如2的32次方,就能極大地延長隨機數重複的週期,但也只是延長,本質上仍無法避免。

那麼,真的就無解了嗎?既然有偽隨機數的說法,那有沒有真隨機數呢?

還是有的。

真隨機數怎麼得到?

既然從內部無法自我解決,那就尋求外部的幫助吧,也即接受一個我們認為是隨機性的外部事物的輸入作為種子數,從而使得經過計算機處理之後的結果也是隨機的,這個外部事物就是——自然界的噪聲。

這個噪聲是物理學上的含義,指的是一切不規則的訊號,而不一定是聲音。

比如RANDOM.ORG這個網站,就是以大氣噪聲,也即自然界雷暴活動所產生的電磁輻射作為隨機性的外部事物的輸入,藉此提供各項服務以滿足各種各樣需要生成真隨機數的場景。

閃電擊中廣州塔.png

既然需要外部事物的輸入,那也就意味著需要額外的硬體裝置支援,以收集和測量隨機的物理現象或普通事件。但也不用把它想象的過於高大上,諸如滑鼠、鍵盤的點選都可以作為隨機事件的種子數。

另一方面,由於蒐集外部的資料需要時間,也導致了真隨機數生成器的另外一個缺點——不夠快。以及,由於隨機性的外部事物的輸入很難重現,也將導致我們無法復現隨機數生成過程,測試流程常常無法正常進行。

不過,己之缺點即是彼之優點,對於偽隨機數生成器來說,不需要外部裝置支援、計算效率高、可復現則是其明顯的優勢

好了,這個就是今天要分享的內容。

總結一下,《羊了個羊》每種元素的隨機生成使用的仍然是偽隨機數生成器,因此說它“真隨機性”其實並不太準確。

而其宣傳所謂的通關率不到0.1%,與遊戲難度本身關係不大,你無法通過大概率是你剛好被分配到的牌局沒有達到三消類遊戲通關的基本要求。

最後,祝你是那0.1%的幸運兒,遊戲如是,生活也如是。

通關截圖.png

少俠,請留步!若本文對你有所幫助或啟發,還請:

  1. 點贊👍🏻,讓更多的人能看到!
  2. 收藏⭐️,好文值得反覆品味!
  3. 關注➕,不錯過每一次更文!

===> 公眾號:「椎(chui)鋒陷陳」💪

你的支援是我繼續創作的動力,感謝!🙏

參考

How to Generate Pseudorandom Numbers | Infinite Series https://www.youtube.com/watch?v=C82JyCmtKWg