計算機產(chǎn)生的大多數(shù)隨機數(shù)都是偽隨機數(shù)拢蛋。是按照分布概率產(chǎn)生隨機數(shù)字的過程桦他，數(shù)字在概率分布上滿足隨機要求，但實際上是計算機通過隨機函數(shù)模擬產(chǎn)生的谆棱。生成的方法包括直接法快压、逆轉(zhuǎn)法、接受拒絕法等垃瞧。本篇要介紹的是prd偽隨機算法和基于rsa的偽隨機算法蔫劣。
Pseudo Random Distribution
這種偽隨機算法在游戲中的應(yīng)用非常廣泛。游戲希望角色間應(yīng)互相制衡个从，同時為增加游戲的不確定性脉幢，故引入了隨機概念，如暴擊率嗦锐、回避率等都是一個隨機概率的表現(xiàn)嫌松。prd偽隨機算法能夠盡量使觸發(fā)事件的情況均勻地分布在多次事件中，從而避免了連續(xù)多次的暴擊或回避奕污，也可以減少長時間不暴擊情況的發(fā)生萎羔。
實際上Pseudo Random Distribution是來自Warcraft3引擎，同時在dota2中得到了發(fā)揚碳默。prd偽隨機算法是計算觸發(fā)角色特殊能力的概率的算法贾陷。對于普通的偽隨機算法，我們能夠發(fā)現(xiàn)嘱根，每次觸發(fā)事件的概率都相同昵宇。但對于prd偽隨機算法而言，每次觸發(fā)事件的概率卻不相同儿子，它會隨著暴擊事件或非暴擊事件的觸發(fā)而改變瓦哎。但在均攤概率上來說，卻是滿足角色能力要求的，也是滿足隨機概率要求的蒋譬。
一定程度上prd算法改善了暴擊的發(fā)生的頻次和分布割岛，使其更為均勻，從而保證了游戲的公平性和趣味性犯助。
具體實現(xiàn)
- prd的工作機制大致如下：觸發(fā)事件的概率會隨著未觸發(fā)事件發(fā)生的次數(shù)增加而增加癣漆，直到100%。另一方面剂买，當(dāng)觸發(fā)一次事件后（如暴擊事件）惠爽，緊接著下一次動作觸發(fā)事件的概率會明顯地低于平均概率p，這也是為了防止多次觸發(fā)事件瞬哼。
- 實驗發(fā)現(xiàn)婚肆，采用prd偽隨機算法和普通的偽隨機算法，后者多次連續(xù)觸發(fā)事件的概率高于前者坐慰，也就是說较性，prd算法試驗中“極為幸運”或“極為不幸”的事件很少發(fā)生。但對于總體而言结胀，二者的均攤概率是相同的赞咙。
- 如未觸發(fā)事件，每次的增量概率應(yīng)該是游戲中預(yù)先計算好的糟港，保存在一張表中攀操。之所以不在游戲中計算，是因為prd算法獲得增量概率的計算量和所需時間要多余普通的隨機算法秸抚。在Warcraft3中增量概率步長為
5%速和，但這對觸發(fā)概率大于15%的事件而言是不正確的。 - 對于有些動作是不能出發(fā)概率增加的耸别，如對防御塔的攻擊健芭。
wiki中給出了prd的計算結(jié)果表县钥。
| P(T) | P(A) | C | Max N | Most Probable N | Average N | SD | SDt |
|---|---|---|---|---|---|---|---|
| 5% | 5% | 0.00380 | 264 | 16 | 20.00 | 10.30 | 19.53 |
| 10% | 10% | 0.01475 | 68 | 8 | 10.00 | 5.06 | 9.50 |
| ... | ... | ... | ... | ... | ... | ... | ... |
| 75% | 63.2% | 0.46134 | 3 | 2 | 1.58 | 0.57 | 0.96 |
| 80% | 66.7% | 0.50276 | 2 | 1 | 1.50 | 0.5 | 0.87 |
正如上表給出的結(jié)果秀姐。PT為理論概率，PA為實際均攤概率若贮，C時prd常數(shù)（增量概率）省有，Max N是達到100%所需次數(shù)，Most Probable N為觸發(fā)事件最有可能的次數(shù)谴麦，Average N是觸發(fā)事件平均次數(shù)蠢沿，SD為N的理論標(biāo)準(zhǔn)差，SDt為普通隨機算法的標(biāo)準(zhǔn)差匾效。由此可見舷蟀，該偽隨機算法一定程度上降低了離散程度，使得游戲更為公平。
偽隨機與加密算法
網(wǎng)上看到可以用rsa生成偽隨機數(shù)野宜。命題如下：如何生成1億個不重復(fù)的偽隨機數(shù)扫步。顯然用普通的隨機算法效率太低。但仔細想來匈子，生成偽隨機數(shù)如果不重復(fù)的話河胎，就是一個打亂的過程。這就可以用到rsa這種目前被廣泛應(yīng)用的加密算法虎敦。
具體的操作步驟如下：
a = (b ^ c) mod (m * n);(c * d) mod ((m - 1) * (n - 1)) = 1b = (a ^ d) mod (m * n)
上式中游岳，m、n其徙、c為素數(shù)胚迫。由第一條和第三條等式可以得出，a和b是一一對應(yīng)的映射擂橘。由此可以由有序的序列A={a1,a2,a3,...,an}派生出隨機序列B={b1,b2,b3,...,bn}晌区。其中，m通贞、n朗若、c都是事先確定的常數(shù)，它們滿足第二條等式昌罩，如m=3哭懈，n=5，c=3茎用，滿足等式(3 * 3) mod (2 * 4) = 1遣总。
不妨對2到9之間的數(shù)字生成偽隨機數(shù)。
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|
| 8 | 12 | 4 | 5 | 6 | 13 | 2 | 9 |
對于這種生成不重復(fù)偽隨機數(shù)的方法有幾個前提要求轨功。上面的m和n不能夠相同旭斥，也就是說它們必須是不同的素數(shù)。同時古涧，d和(m-1)*(n-1)的最大公因數(shù)為1垂券。
