WisKeyのLullaby

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

測試開服了幾天之后，需要開放某個(gè)限時(shí)抽卡活動，在內(nèi)部測試時(shí)，我們發(fā)現(xiàn)玩家反應(yīng)的問題在限時(shí)抽卡中格外明顯，尤其是其中最主要的一張稀有卡牌，猜測因?yàn)橄迺r(shí)抽卡庫配置的種類較少，然后就拿該活動來檢查了下我們游戲隨機(jī)機(jī)制問題。

5%概率？20次出現(xiàn)一次？

大部分游戲策劃使用權(quán)值來配置隨機(jī)概率，因?yàn)闄?quán)值有個(gè)好處就是可以在增加隨機(jī)物品時(shí)，可以不對之前的配置進(jìn)行更改，比如：白卡 30，藍(lán)卡 10，紫卡 10，轉(zhuǎn)為概率即是：白卡 60%，藍(lán)卡 20%，紫卡 20%。

而上述限時(shí)抽卡的例子中，我們的權(quán)值配置是5和95，模擬50000次隨機(jī)（使用系統(tǒng)隨機(jī)函數(shù)，如C的rand函數(shù)，Python的random庫）得到如下結(jié)果：

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

最原始的實(shí)現(xiàn)

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

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

上面是直接隨機(jī)的方式，只保證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次出現(xiàn)一次，而5%概率則是隱含在內(nèi)的，生成效果如下圖。

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

眼尖的會發(fā)現(xiàn)在第一個(gè)實(shí)現(xiàn)中我用的pool是[0]*5 + [1]*95，而第二個(gè)實(shí)現(xiàn)中我用的是[0]*1 + [1]*19。

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

針對策劃的配置，我們需要進(jìn)行預(yù)處理，怎么處理？GCD啊~，5和95的最大公約數(shù)是5，所以在第二個(gè)實(shí)現(xiàn)的代碼中我直接使用了1和19。

但這里有個(gè)問題，一般策劃配置的隨機(jī)庫中肯定有多個(gè)物品。權(quán)值如果配置的比較隨意的話，很可能就導(dǎo)致GCD為1，這樣想要實(shí)現(xiàn)XX次出現(xiàn)一次就不可行了。比如剛才的權(quán)值配置5和95，再加一個(gè)權(quán)值為11的話，就只能實(shí)現(xiàn)111次出現(xiàn)5次。

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

更通用更優(yōu)美的實(shí)現(xiàn)

20次出現(xiàn)一次是以20為標(biāo)準(zhǔn)周期，當(dāng)然不能每次都是間隔20出現(xiàn)，這樣就太假了，根本沒有隨機(jī)感受可言，為了模擬隨機(jī)并可以控制一定的出現(xiàn)頻率，我選擇正態(tài)分布來進(jìn)行偽隨機(jī)分布生成，原因是分布會更自然一些。

關(guān)于正態(tài)分布這里就不詳細(xì)描述了，只需關(guān)心分布的兩個(gè)參數(shù)即可，位置參數(shù)為μ、尺度參數(shù)為σ。根據(jù)正態(tài)分布，兩個(gè)標(biāo)準(zhǔn)差之內(nèi)的比率合起來為95%；三個(gè)標(biāo)準(zhǔn)差之內(nèi)的比率合起來為99%。

用上面的例子來定下參數(shù)，μ=20,σ=20/3，這樣每次按正態(tài)分布隨機(jī)，就能得到一個(gè)理想的隨機(jī)分布和概率區(qū)間。

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

首先，我直接生成權(quán)值為5的卡牌的間隔，檢驗(yàn)下正態(tài)分布的隨機(jī)效果。

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

這圖是不是比第二個(gè)實(shí)現(xiàn)的圖更好看一些，分布也更平滑一些呢。OK，接下來就是替換舊的隨機(jī)算法了。

細(xì)節(jié)和優(yōu)化

剛才說了隨機(jī)庫中會有很多物品，都需要按照各自的權(quán)值隨機(jī)，并各自出現(xiàn)頻率符合正態(tài)分布。下面我們來說說細(xì)節(jié)。

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.) 

這里我使用了統(tǒng)一的隨機(jī)種子，隨機(jī)測試了500萬次后，所得的結(jié)果與多個(gè)隨機(jī)種子差別不大。

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

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

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

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

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

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)) 

測試結(jié)果

問題分析和算法實(shí)現(xiàn)就到這了，替換進(jìn)我的游戲里看看什么效果，我已經(jīng)迫不及待了。

物品測試權(quán)值序列[10, 30, 50, 110, 150, 200, 250, 500]，隨機(jī)測試500萬次。

 
第一個(gè)隨機(jī)實(shí)現(xiàn)

第一個(gè)實(shí)現(xiàn)是只符合統(tǒng)計(jì)要求，不符合分布要求。

 
第二個(gè)隨機(jī)實(shí)現(xiàn)

第二個(gè)實(shí)現(xiàn)中對權(quán)值序列進(jìn)行了GCD，可以看到只有綠色是符合分布要求的，而藍(lán)色和青色退化成第一種實(shí)現(xiàn)。

 
基于正態(tài)分布的隨機(jī)實(shí)現(xiàn)

完美！

玩家體驗(yàn)

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

結(jié)束

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

更多內(nèi)容請移步huangwei.pro