深度分析游戏中的随机概率

这段时间公司开发的游戏上线测试，不少玩家在抽卡时抱怨运气不佳，很难抽到所需卡牌；但也有部分玩家反馈运气好，能连着抽到紫卡。检查随机相关逻辑代码后，并未发现问题，玩家运气好坏似乎真的是概率原因所致。

测试开服几天后，需开放某个限时抽卡活动。内部测试时发现，玩家反应的问题在限时抽卡中尤为明显，特别是其中最主要的一张稀有卡牌。推测是因为限时抽卡库配置的种类较少，于是我们利用该活动来检查游戏的随机机制问题。

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

大部分游戏策划采用权值来配置随机概率，权值的优势在于增加随机物品时，无需更改之前的配置。例如，白卡权值为 30，蓝卡权值为 10，紫卡权值为 10，转换为概率后，白卡为 60%，蓝卡为 20%，紫卡为 20%。

在上述限时抽卡的例子中，我们的权值配置是 5 和 95。使用系统随机函数（如 C 的 rand 函数、Python 的 random 库）模拟 50000 次随机，得到如下结果：

绘制的图展示了权值为 5 的卡牌的随机状态。红色图为分布图，X 轴是出现的次数，Y 轴是相同卡牌再次出现的间隔；绿色图是分布概率图，X 轴是间隔数，Y 轴是概率。按策划的想法，5%概率应等同于 20 次出现一次，但从图中明显可以看出，并不满足这一出现规则。实际间隔从近到远呈下坡形状分布，即相邻的概率最大，间隔最大超过 160，这与玩家吐槽的抽卡体验一致。不过，50000 次随机中该卡牌总共出现了 2508 次，从统计意义上来说，是符合 5%概率的。所以，这个问题的关键在于，所谓的概率是统计意义上的还是分布意义上的。

最原始的实现

我采用从列表里取元素的方式来模拟“20 次出现一次”，为方便比较异同，也贴上直接随机方式的相关代码。

直接随机方式

import random
N = 50000  # 假设 N 为模拟次数
pool = [0]*5 + [1]*95
result = [random.choice(pool) for i in range(N)]

上述直接随机的方式，仅保证 5%概率。

打乱列表依次取元素方式

import random
N = 50000  # 假设 N 为模拟次数
pool = []
result = []
for i in range(N):
if not pool:
pool = [0]*1 + [1]*19
random.shuffle(pool)
result.append(pool[-1])
del pool[-1]

这种打乱列表然后依次取元素的方式，保证“20 次出现一次”，而 5%概率则隐含在内，生成效果如下图所示。

该图明显与第一个实现的图不同，图中表明间隔基本上落在 [0, 40] 的区间内，并且均匀分布在 20 那条蓝色对称线附近，这才是我们最终想要的随机效果。红色的线是正态分布曲线，是不是很相似？后面会详细讲解。

需要注意的是，“20 次出现一次”并不等同于“100 次出现五次”，从分布意义上来说，“100 次出现五次”存在 5 次连续出现的可能。

针对策划的配置，我们需要进行预处理，这里可以使用最大公约数（GCD）。5 和 95 的最大公约数是 5，所以在第二个实现的代码中，我们直接使用了 1 和 19。

但存在一个问题，一般策划配置的随机库中会有多个物品。如果权值配置比较随意，很可能导致最大公约数为 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 确实会快一点。

生成符合正态分布的随机间隔

import random
N = 50000  # 假设 N 为模拟次数
NN = int(N * 0.05)
mu, sigma = 20, 20 / 3
delta = [int(random.normalvariate(mu, sigma)) for i in range(NN)]

这个图是不是比第二个实现的图更好看，分布也更平滑呢？接下来，我们要替换旧的随机算法。

细节和优化

前面提到随机库中有很多物品，需要按照各自的权值进行随机，并且各自的出现频率要符合正态分布。下面详细说明具体细节。

import random
import heapq

wt = [5, 95]  # 假设权值序列
N = 50000  # 假设模拟次数
wtp = [1. * x / sum(wt) for x in wt]
result = []
p = [(random.normalvariate(1. / x, 1. / x / 3.), i) for i, x in enumerate(wtp)]
heapq.heapify(p)
for i in range(N):
minp, minj = heapq.heappop(p)
result.append(minj)
p_new = random.normalvariate(1. / wtp[minj], 1. / wtp[minj] / 3.) + minp
heapq.heappush(p, (p_new, minj))

这里使用了统一的随机种子，随机测试 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) 应该不难。

测试结果

问题分析和算法实现就到这里，我迫不及待地将新算法替换到游戏中，看看效果如何。

物品测试权值序列为 [10, 30, 50, 110, 150, 200, 250, 500]，随机测试 500 万次。

第一个随机实现

第一个实现仅符合统计要求，不符合分布要求。

第二个随机实现

第二个实现对权值序列进行了最大公约数（GCD）处理，可以看到只有绿色符合分布要求，而蓝色和青色退化为第一种实现。

基于正态分布的随机实现

完美！

其它

当然，实现“20 次出现一次”这样的分布伪随机还有其他方法，例如保存一个计数器，每随机一次就加到计数器上，当计数器的值大于或等于 1 时，物品必然出现。但这种实现方式需要为每个玩家、每个随机库、每个物品都设置一个计数器字段，空间开销太大。

关于随机种子，除非是全服竞争类资源，否则最好每个玩家有各自的随机种子，否则会造成体验上的误差，比如抽卡、关卡掉落等针对玩家自身的系统随机。对于服从正态分布的全局随机序列，不同玩家任意取走序列中的一段或一些值，可能导致每个玩家取出的随机序列不再服从正态分布。

结束语

我不得不感叹 Python 的库太强大了，matplotlib 绘制的图形也很漂亮。感兴趣的同学可以查阅 用 Python 做科学计算。