眾妙之門玄之又玄，遊戲系統中的偽隨機(Pseudo-Randomization)和真隨機(True-Randomization)算法實現Python3

我正在參加掘金社區遊戲創意投稿大賽個人賽，詳情請看：遊戲創意投稿大賽

有人説，如果一個人相信運氣，那麼他一定參透了人生。想象一下，如果你在某款moba遊戲中，在裝備平平，隊友天坑的情況下，卻刀刀暴擊，在一小波gank中輕鬆拿下五殺，也許你會感歎自己的神操作和好運氣，但其實，還有另外一種神祕的力量在支配着這一切，那就是：隨機算法。

偽隨機（Pseudo-Randomization）

其實，競技遊戲通常是拒絕隨機性干預的，因為它干擾了玩家實際操作水平的考量。但是，應對突發情況也應該是玩家應變能力的一種表現。因此，在moba遊戲中，有很多隨機事件，這些隨機事件降低了遊戲的可預測性，增加了變數。為了限制這種隨機性的影響，偽隨機算法應運而生。

偽隨機分佈(pseudo-random distribution，簡稱PRD)在遊戲中用來表示關於一些有一定機率的裝備和技能的統計機制。在這種實現中，事件的機率會在每一次沒有發生時增加，但作為補償，第一次的機率較低。這使得效果的觸發結果更加一致。

以Dota2為例，在大量的英雄技能中，比如説斯拉達的重擊、酒仙的醉拳、主宰的劍舞之類的技能，都利用了偽隨機機制：

具體的實現邏輯是這樣的，每次釋放技能，都使用一個不斷增加的概率來進行計算，如果這個事件一直觸發不成功，那麼概率就不斷上升，直到事件發生為止。

要完成這個偽隨機算法，要解決的問題就是，對於一個發生概率為p的事件，在我們第n次釋放技能的時候，發生的機率在第N次成功觸發的機率為P(N) = C × N，對於每一個沒有成功觸發的實例來説，偽隨機分佈PRD會通過一個常數C來增加下一次效果觸發的機率。這個常數會作為初始機率，比效果説明中的機率要低，一旦效果觸發，計數器會重置，機率重新恢復到初始機率。

舉個例子，斯拉達的重擊有25%機率對目標造成眩暈，那麼第一次攻擊，他實際上只有大約8.5%機率觸發重擊，隨後每一次沒有成功的觸發實例都會增加大約8.5%觸發機率，於是到了第二次攻擊，機率就變成大約17%，第三次大約25.5%……以此類推，直到重擊的概率達到100%。在一次重擊觸發後，下一次攻擊的觸發機率又會重置到大約8.5%，那麼經過一段時間之後，這些重擊機率的平均值就會接近25%。

基於偽隨機的效果使得多次觸發或多次不觸發的極端情況都變得罕見，這使得遊戲的運氣成分相對降低了一些。然而雖然理論上可行，但是在遊戲中玩家很難運用這個機制來“刻意”增加下一次觸發的機率。值得一提的是，Dota2對偽隨機技能算法也有限制，如果被釋放技能的對象根本就不可能觸發效果，那麼觸發機率不會增加，也就是説，一個英雄反補或攻擊建築不會增加他下一次攻擊觸發的致命一擊機率，因為致命一擊對反補和建築無效。

馬爾可夫鏈（Markov chain）

那麼，Dota2底層到底怎麼實現的呢？這涉及到一個算法公式：馬爾可夫鏈（Markov chain）

馬爾可夫鏈因俄國數學家Andrey Andreyevich Markov得名，為狀態空間中經過從一個狀態到另一個狀態的轉換的隨機過程。該過程要求具備“無記憶”的性質：下一狀態的概率分佈只能由當前狀態決定，在時間序列中它前面的事件均與之無關。

説白了就是，如果對於一個觸發概率為5%暴擊的技能，那麼我砍第一刀出現暴擊的概率是c，第二刀是2c，如果一直沒有暴擊，直到第N刀，出現了（c*N）大於1了，那麼這次暴擊就必然發生了，而在中間的每一次，如果暴擊發生了，那麼我們就把隨機概率重置為c。

P = 1*c + 2*c(1-c) + 3*c(1-c)(1-2c)+4*c(1-c)(1-2c)(1-3c)

其中 P = 1/p，N=1/c（第N刀，即累加概率的最後一刀必然暴擊）

那麼我們就可以用折半查找在(0,1)之間不斷估算c，直到這個公式成立就行了。

首先，模擬N次觸發，計算是否會在N次觸發之後必然發生：

``` import math

def p_from_c(c):

po, pb = 0, 0  
sumN = 0  
maxTries = math.ceil(1/c)

for n in range(maxTries):  
    po = min(1, c*n) * (1-pb)  
    pb = pb + po  
    sumN = sumN + n * po


return (1 / sumN)

```

隨後，在遍歷中，不斷地取中值判斷，如果觸發的概率足夠小，那麼認為已經找到了對應的c係數：

``` def c_from_p(p):
cu = p
cl = 0.0
p1, p2 = 0, 1
while True:
cm = (cu + cl) / 2
p1 = p_from_c(cm)
if abs(p1 - p2) <= 0.000000001:
break

    if p1>p:  
        cu = cm   
    else:   
        cl = cm  
    p2 = p1

return cm

```

具體使用上，我們需要單獨存儲一個閾值變量，那就是釋放次數 fail，如果 fail 一直處於未暴擊的狀態，那就累加對應的釋放概率：

``` fail = 1

print(c_from_p(0.20)100fail)

fail = 2

print(c_from_p(0.20)100fail)

fail = 3

print(c_from_p(0.20)100fail) ```

輸出返回值：

5.570398829877376 11.140797659754751 16.711196489632126

對於一個20%暴擊的技能，第一刀實際上只有5%，第二刀11%，等到砍到第三刀就有16%。

那麼知道了底層算法和實現，有什麼用呢？我們就可以在遊戲中超神了嗎？事實上，底層算法對玩家在遊戲實際操作技巧是有一定指導意義的，比如，如果玩家能夠記住釋放技能以後的攻擊次數，對應的，玩家腦子裏就會有一個概率，事實上，第一刀5%觸發的概率還是非常低的，而反補和打建築物又不能增加fail閾值的次數，所以如果是在團戰中，面對半血或者殘血英雄，第一刀完全可以不砍他，因為概率太小，完全可以前兩刀砍對方別的英雄，留出後面幾刀再砍，這樣就會在無形中增加暴擊或者眩暈技能，是的，如果半血被暈，基本上人頭就交出去了，電光石火之間，算法可以幫我們增大超神的概率，要知道，職業玩家的反應能力不是業餘玩家可以想象的。

這就好比，在牌局中，真正的高手會靠記憶力將手牌中間段的數量記住，如9/10/J，來保證自己的順子能夠在最後時刻打通或者逼出對手炸彈。

真隨機(True-Randomization)

什麼叫真隨機？有人會説，拋硬幣、擲骰子，這些都是真隨機事件。

是的，一枚銀色的硬幣在半空中快速地翻轉着，一閃一閃地泛着光輝，你看不清楚哪面向上、哪面向下，甚至連硬幣的主人自己也不清楚。

但其實，拋硬幣的角度、力量、周圍風速等等因素都會影響最終結果，所以，嚴格意義上來説，拋硬幣當然不是真隨機事件，因為這個宏觀運動過程和結果嚴格遵守物理定律，而每次的輸入變量也是有限且確定的。

所以，我們所定義的真隨機是有條件的，即如果偽隨機是靠次數做關聯繫遞增，那麼真隨機就跟它相反，多次實施過程中沒有關聯的事件，我們稱之為真隨機。

那麼，在Python中，能否用邏輯實現這種“真隨機”？

假設我從1-100個數裏，“真隨機”挑數字，計數器進行隨機挑選後的記錄，挑一萬次，理論上，它會存在正態分佈嗎：

import random from collections import Counter c = Counter() for _ in range(10000): c[random.randint(1, 100)] += 1 print(c) print(c.values()) print(max(c.values()))

返回輸出：

Counter({90: 123, 51: 122, 84: 121, 77: 119, 74: 118, 2: 117, 86: 116, 33: 116, 72: 113, 81: 112, 56: 112, 42: 112, 9: 111, 11: 110, 97: 110, 16: 109, 27: 109, 8: 109, 6: 109, 62: 109, 15: 108, 29: 108, 12: 107, 22: 106, 28: 106, 82: 106, 7: 105, 94: 105, 89: 105, 71: 105, 5: 105, 24: 105, 80: 105, 65: 104, 20: 104, 48: 104, 93: 104, 1: 104, 79: 103, 57: 103, 40: 103, 26: 103, 63: 103, 30: 102, 68: 102, 75: 101, 18: 101, 23: 101, 39: 100, 44: 100, 54: 99, 85: 99, 91: 99, 59: 99, 76: 99, 43: 98, 31: 98, 66: 98, 25: 98, 60: 97, 58: 97, 35: 97, 64: 97, 70: 97, 19: 97, 34: 97, 96: 96, 13: 96, 52: 96, 61: 95, 100: 95, 21: 95, 98: 95, 49: 94, 69: 94, 99: 93, 87: 93, 88: 93, 78: 92, 73: 91, 17: 91, 67: 91, 4: 91, 46: 90, 92: 90, 36: 90, 3: 89, 14: 89, 41: 89, 55: 87, 53: 85, 32: 85, 38: 84, 37: 84, 50: 83, 83: 83, 10: 83, 45: 82, 47: 80, 95: 75}) dict_values([121, 99, 112, 99, 94, 110, 89, 93, 93, 98, 95, 91, 109, 100, 109, 116, 104, 105, 91, 84, 106, 104, 105, 92, 106, 83, 104, 105, 110, 103, 82, 102, 112, 85, 105, 103, 85, 89, 103, 99, 117, 83, 87, 96, 100, 96, 90, 105, 123, 99, 91, 104, 101, 118, 99, 103, 91, 83, 98, 95, 98, 107, 111, 97, 104, 101, 113, 116, 97, 98, 97, 122, 90, 101, 108, 94, 96, 106, 112, 97, 102, 103, 108, 75, 97, 109, 80, 93, 109, 109, 95, 95, 90, 97, 89, 84, 105, 119, 97, 105]) 123

最高的一次出現了123次，接着我們來換個方式，不用random：

import random from collections import Counter c = Counter() for _ in range(10000): c[100] += 1 print(c) print(c.values()) print(max(c.values()))

返回輸出：

Counter({100: 10000}) dict_values([10000]) 10000

對比之下，我們可以這麼理解，出現次數的最大值約大，我們的隨機性就越小。

所以，雖然每一次獲取沒有表面上關聯性，但這並不是“真隨機”，所以説，計算機到底能不能實現“真隨機”？並不能，因為Python的random模塊本身就是基於PRD偽隨機算法，可以理解為Python中的隨機是“使用隨機算法”計算出的隨機，而使用恰當的隨機算法可以讓這個隨機很逼近“真正”的隨機。

結語：

偽隨機指的是“從邏輯層面對隨機算法的結果進行干擾”，真隨機指的是“現有技術或可支出成本無法修正的系統誤差”，兩套邏輯均被大量應用在遊戲領域，但不能否認的是，運氣這東西也確實存在，所以古代玩家難免也會發出“時來天地皆同力,運去英雄不自由。”的感慨。

原文轉載自「劉悦的技術博客」 http://v3u.cn/a_id_212