从Dota2的伪随机谈开

起因是在知乎上看到木七七工作室转发的谈随机处理的一个内部视频，视频里面聊到Dota2的技能概率处理方式，比如大鱼人（Sorry好久没玩Dota了已经想不起来这位的真名）的被动技能升满后：

• 每次攻击有25%的几率让敌人眩晕。

一般做法用纯随机 True random distribution的方式，每次攻击时计算概率，独立判断是否触发眩晕。不过可能会出现一些体验问题：

1. 因为每次独立计算概率，极限情况会导致一直触发眩晕和一直不触发，间接造成欧皇和非洲酋长之间的战争。
2. 从玩家体验上来说，感官上25%的几率，超过5，6次不触发，他就会开始怀疑几率是否被策划运营篡改，幕后是否有肮脏的PY交易，而不是回想下初中的数学课。

纯随机在数学上是无罪的，机器底层的随机函数是清白的（其实也不是那么清白，毕竟纯随机是不存在的，不过这个就扯深了，先默认一般的random接口函数就是纯随机），但是有些时候并不是最佳解决方案。

用伪随机分布Pseudo-random distribution处理概率

Dota2的伪随机分布采用概率补偿的方式，每次触发概率从一个值开始递增，第N次的触发概率P(N) = C * N，比如25%的几率，C值大概为8.5%，运算流程如下：

1. 第一次触发眩晕概率为8.5%
2. 第二次为17%，以此类推递增
3. 如果触发眩晕成功，则概率重新从8.5%开始递增计算。

这种方式使得连续触发或连续不触发的几率降低，避免了运气成分过于影响战斗结果（特别是竞技游戏）。

一般几率对应的C值可以参考下面这张图。P(T)代表预期值，就是游戏中显示的几率值。P(A)是用了伪随机后的实际概率。MaxN表示最坏情况下触发概率的次数。

rpic1.png

计算C值的方式和程序实现可以参考这个链接下的回答，有C#的实现代码：

//CfromP是主函数，传入理论概率P就可以求得递增的C值
public decimal CfromP( decimal p )
{
    decimal Cupper = p;
    decimal Clower = 0m;
    decimal Cmid;
    decimal p1;
    decimal p2 = 1m;
    while(true)
    {
        Cmid = ( Cupper + Clower ) / 2m;
        p1 = PfromC( Cmid );
        if ( Math.Abs( p1 - p2 ) <= 0m ) break;

        if ( p1 > p )
        {
            Cupper = Cmid;
        }
        else
        {
            Clower = Cmid;
        }

        p2 = p1;
    }

    return Cmid;
}

private decimal PfromC( decimal C )
{
    decimal pProcOnN = 0m;
    decimal pProcByN = 0m;
    decimal sumNpProcOnN = 0m;

    int maxFails = (int)Math.Ceiling( 1m / C );
    for (int N = 1; N <= maxFails; ++N)
    {
        pProcOnN = Math.Min( 1m, N * C ) * (1m - pProcByN);
        pProcByN += pProcOnN;
        sumNpProcOnN += N * pProcOnN;
    }

    return ( 1m / sumNpProcOnN );
}

上面的伪随机分布算是用概率补偿的方式控制概率来改善玩家的体验，详细的可以参考Dota2的Wiki（打Dota2，向冰蛙学数学）。

当然也有其他方式控制随机数和概率，正好前一阵子看了一个从D&D掷骰角度谈控制随机分布的文章，下面也算一个翻译和整理。

我这把可是1d2有毒的飞刀

D&D里面NdS表示投掷S面的骰子N次，累加结果。比如1d12表示投掷一个12面骰子一次，3d4表示投掷一个4面骰子3次。

假设我们要获取[0,24]之间的随机值，可以先设置一个函数rollDice(N, S)来模拟骰子投掷：

public static int rollDice(int N, int S) {
    int value = 0;
    for (int i = 0; i < N; i++) {
        //每次随机结果为[0, S]
        value += Random.Range(0, S + 1);
    }

    return value;
}

我们可以rollDice(1,24)，也可以拆分成2次，变成rollDice(2,12)，变成两次[0,12]的和，以此类推rollDice(3,8)、rollDice(4,6)，下面这张图可以看到最终结果的分布变化：

rpic5.jpg

可以看到投掷的次数越多，最终结果分布就越集中在[0,24]的平均值附近，所以4d6的武器比3d8的武器输出更平稳，但3d8的武器造成高伤害的几率也更高。

除了控制随机取值的集中区域，我们还可以用简单的方式控制随机取值是大部分分散在平均值以下还是大部分分散在平均值以上。

两次随机取较大/较小值

还是以取[0,24]之间随机值为例，每次rollDice(2,12)两次，取较大值：

int roll1 = rollDice(2, 12);
int roll2 = rollDice(2, 12);
int result = Math.Max(roll1,  roll2);

分布图如下：

rpic2.png

反过来，取较小值，可以获得集中在平均值以下的分布：

int roll1 = rollDice(2, 12)
int roll2 = rollDice(2, 12)
int result = Math.Min(roll1, roll2);

rpic4.png

取较小值在计算伤害值比较常见，比如一个角色的攻击力在20到40之间，利用这种方法可以使得最后结果集中在较低的范围，高伤害出现的几率较低。

三次随机取较大的两个值

rollDice(1,12)三次，取较大的两个值：

int roll1 = rollDice(1, 12);
int roll2 = rollDice(1, 12);
int roll3 = rollDice(1, 12);

int result = roll1 + roll2 + roll3;
result = result - Math.Min(roll1, roll2, roll3);

分布图如下：

rpic3.png

可以看出比两次取较大/较小值分布更为平滑。

总结一下，可以看到在控制某个范围内随机数时，可以从下面几个角度进行自定义以满足需求：

1. 范围。确定随机范围的最大值和最小值，如果需要可以做一些偏移，比如[20, 30]可以分解为20 + rollDice(1, 10)。
2. 方差。将一次随机分解为多次随机，可以使结果更靠近中间值。相反，次数越少，结果分布范围越广。
3. 不对称性。可以通过上面介绍的两种方法，使随机结果更多分布在平均值之前或者之后。

自定义概率分布

很多情况下，策划过来找你的时候，情景有可能是：我这里有10种掉落物品，每种的掉率我都想单独配置，比如A掉率10%，B掉率20%等等和一个Excel文件。

最终的配置文件可能是像这样一个数组，前面是掉率（以100算100%），后面跟着物品ID。

local dropRate = {
    {10, 100001},
    {20, 100002},
    {30, 100003},
    {40, 100004},
}

掉率的总和不一定正好是100，毕竟要考虑些对配置文件的容错性，所以先算出概率和sumRate，取random(sumRate)的值value，依次遍历dropDate表，累加概率和weight，如果value小于等于weight，则算是落在当前区间，返回对应的物品ID。我用lua写了一段测试代码，毕竟lua的table实在是太方便了。

local dropRate = {
    {10, 100001},
    {20, 100002},
    {30, 100003},
    {40, 100004},
}

local distribute = {
    [100001] = 0,
    [100002] = 0,
    [100003] = 0,
    [100004] = 0,
}

local checkRate = function(t, value)
    local weight = 0
    for i=1,#t do
        weight = weight + t[i][1]
        if value <= weight then
            return t[i][2]
        end
    end

    return nil
end

local getDropItem = function(t)
    local weightTotal = 0
    for k,v in pairs(t) do
        weightTotal = weightTotal + v[1]
    end

    local value = math.random(weightTotal)

    return checkRate(t, value)
end

local main = function()
    --用倒序时间设置random的seed，确保seed随时间显著变化
    math.randomseed(tostring(os.time()):reverse():sub(1, 6))

    for i=1,10000 do
        local id = getDropItem(dropRate)
        if id and distribute[id] then
            distribute[id] = distribute[id] + 1
        end
    end

    for index,dis in pairs(distribute) do
        print("index:",index)
        print("dis:",dis)
        print("percent:",dis / 10000)
        print("=================")
    end
end

main()

测试结果和配置概率很接近，这样就可以让策划尽情发挥他的奇怪掉率了。

总结

上面的部分只是最近看到的一些有意思的随机数讨论整理，真正在实际项目中，随机数的处理是跟随不同的需求做变化的，随机可以增加游戏过程的乐趣，可以给游戏增加卖点，也可以变成各种“坑”，对于开发来说，只要这个坑是可控制的，不要坑到自己就行了~