WisKeyのLullaby

這段時間公司開發的游戲上線測試，許多玩家在抽卡時抱怨臉黑，很難抽到所需要的卡牌，而又有一部分玩家反應運氣好能連著抽到紫卡，檢查了下隨機相關邏輯代碼，并沒有找出問題所在，玩家運氣好與壞只是覺得真有可能是概率原因。

測試開服了幾天之后，需要開放某個限時抽卡活動，在內部測試時，我們發現玩家反應的問題在限時抽卡中格外明顯，尤其是其中最主要的一張稀有卡牌，猜測因為限時抽卡庫配置的種類較少，然后就拿該活動來檢查了下我們游戲隨機機制問題。

5%概率？20次出現一次？

大部分游戲策劃使用權值來配置隨機概率，因為權值有個好處就是可以在增加隨機物品時，可以不對之前的配置進行更改，比如：白卡 30，藍卡 10，紫卡 10，轉為概率即是：白卡 60%，藍卡 20%，紫卡 20%。

而上述限時抽卡的例子中，我們的權值配置是5和95，模擬50000次隨機（使用系統隨機函數，如C的rand函數，Python的random庫）得到如下結果：

上圖繪制的是權值為5的卡牌的隨機狀態，紅色的圖是分布圖，X軸是出現的次數，Y軸是相同卡牌再次出現的間隔。綠色的圖是分布概率圖，X軸是間隔數，Y軸是概率。按策劃的想法，5%概率應該等同于20次出現一次，那上圖很明顯并不滿足20次出現一次出現規則，實際間隔從近到遠呈下坡形狀分布，就是說相鄰的概率最大，間隔最大超過160，這與玩家所吐槽的抽卡體驗是一致的。但50000次隨機總共出現了2508次，從統計的意義上來說又是符合5%概率的。所以這個問題，究其原因就是所謂的概率是統計意義上的還是分布意義上的問題。

最原始的實現

我用列表里取元素的方式來模擬20次出現一次，為了方便比較異同，直接隨機的方式我也貼上相關代碼。

pool = [0]*5 + [1]*95 result = [random.choice(a) for i in xrange(N)] 

上面是直接隨機的方式，只保證5%概率。

pool = [] result = [] for i in xrange(N): if not pool: pool = [0]*1 + [1]*19 random.shuffle(pool) result.append(pool[-1]) del pool[-1] 

上面是打亂列表，然后依次取元素的方式，保證20次出現一次，而5%概率則是隱含在內的，生成效果如下圖。

該圖明顯跟第一個實現的圖不一樣，上圖表明了間隔基本上是落在[0, 40]的區間內，并且均勻分布在20那條藍色對稱線附近。這個才是最終想要的隨機的效果。紅色的線是正態分布曲線，是不是很相似？后面我會講到。

眼尖的會發現在第一個實現中我用的pool是[0]*5 + [1]*95，而第二個實現中我用的是[0]*1 + [1]*19。

這里20次出現一次并不等同于100次出現五次，也是從分布的意義上來說的，100次出現五次是存在5次連續出現的可能。

針對策劃的配置，我們需要進行預處理，怎么處理？GCD啊~，5和95的最大公約數是5，所以在第二個實現的代碼中我直接使用了1和19。

但這里有個問題，一般策劃配置的隨機庫中肯定有多個物品。權值如果配置的比較隨意的話，很可能就導致GCD為1，這樣想要實現XX次出現一次就不可行了。比如剛才的權值配置5和95，再加一個權值為11的話，就只能實現111次出現5次。

所以這兩種依賴列表的隨機方式并不適用，一是需要維護的列表內存會比較大，二是對策劃配置方式有過多約束。

更通用更優美的實現

20次出現一次是以20為標準周期，當然不能每次都是間隔20出現，這樣就太假了，根本沒有隨機感受可言，為了模擬隨機并可以控制一定的出現頻率，我選擇正態分布來進行偽隨機分布生成，原因是分布會更自然一些。

關于正態分布這里就不詳細描述了，只需關心分布的兩個參數即可，位置參數為μ、尺度參數為σ。根據正態分布，兩個標準差之內的比率合起來為95%；三個標準差之內的比率合起來為99%。

用上面的例子來定下參數，μ=20,σ=20/3，這樣每次按正態分布隨機，就能得到一個理想的隨機分布和概率區間。

C語言標準函數庫中只有rand，如何生成符合正態分布的隨機數可以參見WiKi上的介紹。這里我直接使用Python中random庫中的normalvariate函數，當然gauss函數也是一樣的，官方文檔上說gauss函數會快些，StackOverFlow上說gauss是非線程安全函數，所以會快。我自己簡單測試了下，在單線程情況下，gauss是會快些，但只是快了一點點而已。

首先，我直接生成權值為5的卡牌的間隔，檢驗下正態分布的隨機效果。

NN = int(N*0.05) mu, sigma = 20, 20/3. delta = [int(random.normalvariate(mu, sigma)) for i in xrange(NN)] 

這圖是不是比第二個實現的圖更好看一些，分布也更平滑一些呢。OK，接下來就是替換舊的隨機算法了。

細節和優化

剛才說了隨機庫中會有很多物品，都需要按照各自的權值隨機，并各自出現頻率符合正態分布。下面我們來說說細節。

wtp = [1.*x/sum(wt) for x in wt] result = [] p = [random.normalvariate(1./x, 1./x/3.) for x in wtp] for i in xrange(N): minp = 1.e9 minj = -1 for j, pp in enumerate(p): if pp < minp: minp = pp minj = j result.append(minj) for j, pp in enumerate(p): p[j] -= minp p[minj] = random.normalvariate(1./wtp[minj], 1./wtp[minj]/3.) 

這里我使用了統一的隨機種子，隨機測試了500萬次后，所得的結果與多個隨機種子差別不大。

簡單解釋下代碼：初始化對所有物品按權值進行正態分布隨機，每次取位置最小值的物品（也就是最先出現的），然后其它物品均減去該值，被取出的物品再單獨進行一次正態分布隨機，再次循環判斷位置最小值。

這里，每次都需要對所有物品進行求最小值和減法，都是需要遍歷的運算，我們可以有如下優化。

例如：(1,3,4) -> 取1減1, (0,2,3) -> 隨機1, (1,2,3)，其實我們只是為了保持各物品之間位置的相對順序即可，將對其它物品的減法變成對自己的加法，操作量級立馬從O(N)縮為O(1) 。

如上面的例子：(1,3,4) -> 取1, (0,3,4) -> 隨機1加1, (2,3,4)，這樣的操作不會改變物品序列的正確性。

熟悉最小堆的朋友，將查找最小值優化到O(1)應該也沒啥問題吧。

wtp = [1.*x/sum(wt) for x in wt] result = [] p = [(random[i].normalvariate(1./x, 1./x/3.), i) for x in wtp] heapq.heapify(p) for i in xrange(N): minp, minj = heapq.heappop(p) result.append(minj) heapq.heappush(p, (random[minj].normalvariate(1./wtp[minj], 1./wtp[minj]/3.)+minp, minj)) 

測試結果

問題分析和算法實現就到這了，替換進我的游戲里看看什么效果，我已經迫不及待了。

物品測試權值序列[10, 30, 50, 110, 150, 200, 250, 500]，隨機測試500萬次。

 
第一個隨機實現

第一個實現是只符合統計要求，不符合分布要求。

 
第二個隨機實現

第二個實現中對權值序列進行了GCD，可以看到只有綠色是符合分布要求的，而藍色和青色退化成第一種實現。

 
基于正態分布的隨機實現

完美！

玩家體驗

最好每個玩家有各自的隨機種子，否則會造成體驗上的誤差。服從正態分布的全局隨機序列，不同玩家任意的取走序列中一段或者一些值，就可能導致對于每個玩家而言，各自取出的隨機序列不再服從正態分布。

結束

我只能感嘆Python的庫太強大了，matplotlib繪制出來的圖形也挺漂亮的，感興趣的童鞋可以查閱用Python做科學計算。

更多內容請移步huangwei.pro