游戏中的随机概率_python_动态网站制作指南
游戏中的随机概率
来源：人气：440
o/2015-07/game-random/
这段时间公司开发的上线测试，许多玩家在抽卡时抱怨脸黑，很难抽到所需要的卡牌，而又有一部分玩家反应运气好能连着抽到紫卡，检查了下随机相关逻辑代码，并没有找出问题所在，玩家运气好与坏只是觉得真有可能是概率原因。
测试开服了几天之后，需要开放某个限时抽卡活动，在内部测试时，我们发现玩家反应的问题在限时抽卡中格外明显，尤其是其中最主要的一张稀有卡牌，猜测因为限时抽卡库配置的种类较少，然后就拿该活动来检查了下我们游戏随机机制问题。
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%概率。
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出现，这样就太假了，根本没有随机感受可言，为了模拟随机并可以控制一定的出现频率，我选择正态分布来进行伪随机分布生成，原因是分布会更自然一些。
关于正态分布这里就不详细描述了，只需关心分布的两个参数即可，位置参数为$\mu$、尺度参数为$\sigma$。根据正态分布，两个标准差之内的比率合起来为95%；三个标准差之内的比率合起来为99%。
用上面的例子来定下参数，$\mu=20, \sigma=20/3$，这样每次按正态分布随机，就能得到一个理想的随机分布和概率区间。
C语言标准函数库中只有rand，如何生成符合正态分布的随机数可以参见。这里我直接使用Python中random库中的normalvariate函数，当然gauss函数也是一样的，上说gauss函数会快些，上说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
for j, pp in enumerate(p):
if pp & minp:
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，可以看到只有绿色是符合分布要求的，而蓝色和青色退化成第一种实现。
当然，实现20次出现一次这样的分布伪随机还有其它方法，比如保存一个，每随机一次就加到计数器上，当计数器的值大于或等于1，即必然出现。但这种实现需要计数器，每个玩家每个随机库每个物品都需要这么一个计数器字段，空间上实在太大了。
关于随机种子，除非是全服竞争类资源，不然最好每个玩家有各自的随机种子，否则会造成体验上的误差，比如抽卡、关卡掉落等这些只针对玩家自身的系统随机。服从正态分布的全局随机序列，不同玩家任意取走序列中一段或者一些值，就可能导致对于每个玩家而言，各自取出的随机序列不再服从正态分布。
我只能感叹Python的库太强大了，matplotlib绘制出来的图形也挺漂亮的，感兴趣的童鞋可以查阅。
更多内容请移步
优质网站模板如何在Python中实现这五类强大的概率分布 - 推酷
如何在Python中实现这五类强大的概率分布
R编程语言已经成为统计分析中的事实标准。但在这篇文章中，我将告诉你在Python中实现统计学概念会是如此容易。我要使用Python实现一些离散和连续的概率分布。虽然我不会讨论这些分布的数学细节，但我会以链接的方式给你一些学习这些统计学概念的好资料。在讨论这些概率分布之前，我想简单说说什么是
。随机变量是对一次试验结果的量化。
举个例子，一个表示抛硬币结果的随机变量可以表示成
X = {1 如果正面朝上,
2 如果反面朝上}
随机变量是一个变量，它取值于一组可能的值（ 离散 或 连续 的），并服从某种 随机性 。随机变量的每个可能取值的都与一个概率相关联。随机变量的所有可能取值和与之相关联的概率就被称为
我鼓励大家仔细研究一下
概率分布有两种类型：离散（discrete）概率分布和连续（continuous）概率分布。
离散概率分布也称为
。离散概率分布的例子有伯努利分布（Bernoulli distribution）、二项分布（binomial distribution）、泊松分布（Poisson distribution）和几何分布（geometric distribution）等。
连续概率分布也称为
，它们是具有连续取值（例如一条实线上的值）的函数。正态分布（normal distribution）、指数分布（exponential distribution）和β分布（beta distribution）等都属于连续概率分布。
若想了解更多关于离散和连续随机变量的知识，你可以观看可汗学院关于概率分布的
二项分布（Binomial Distribution）
服从二项分布的随机变量X表示在n个独立的是/非试验中成功的次数，其中每次试验的成功概率为p。
E(X) =&np, Var(X) =&np(1-p)
如果你想知道每个函数的原理，你可以在IPython笔记本中使用 help file 命令。&E(X)表示分布的期望或平均值。
键入 stats.binom? 了解二项分布函数 binom 的更多信息。
二项分布的例子：抛掷10次硬币，恰好两次正面朝上的概率是多少？
假设在该试验中正面朝上的概率为0.3，这意味着平均来说，我们可以期待有3次是硬币正面朝上的。我定义掷硬币的所有可能结果为
：你可能观测到0次正面朝上、1次正面朝上，一直到10次正面朝上。我使用
计算每次观测的概率质量函数。它返回一个含有11个元素的列表（list），这些元素表示与每个观测相关联的概率值。
您可以使用 .rvs 函数模拟一个二项随机变量，其中参数 size 指定你要进行模拟的次数。我让Python返回10000个参数为n和p的二项式随机变量。我将输出这些随机变量的平均值和标准差，然后画出所有的随机变量的直方图。
泊松分布（Poisson Distribution）
的随机变量X，表示在具有比率参数（rate parameter）λ的一段固定时间间隔内，事件发生的次数。参数λ告诉你该事件发生的比率。随机变量X的平均值和方差都是λ。
E(X) =&λ, Var(X) =&λ
泊松分布的例子：已知某路口发生事故的比率是每天2次，那么在此处一天内发生4次事故的概率是多少？
让我们考虑这个平均每天发生2起事故的例子。泊松分布的实现和二项分布有些类似，在泊松分布中我们需要指定比率参数。泊松分布的输出是一个数列，包含了发生0次、1次、2次，直到10次事故的概率。我用结果生成了以下图片。
你可以看到，事故次数的峰值在均值附近。平均来说，你可以预计事件发生的次数为λ。尝试不同的λ和n的值，然后看看分布的形状是怎么变化的。
现在我来模拟1000个服从泊松分布的随机变量。
正态分布（Normal Distribution）
是一种连续分布，其函数可以在实线上的任何地方取值。正态分布由两个参数描述：分布的平均值μ和方差σ2&。
E(X) =&μ, Var(X) =&σ2
正态分布的取值可以从负无穷到正无穷。你可以注意到，我用 stats.norm.pdf 得到正态分布的概率密度函数。
β分布（Beta Distribution）
β分布是一个取值在&[0, 1]&之间的连续分布，它由两个形态参数α和β的取值所刻画。
β分布的形状取决于α和β的值。贝叶斯分析中大量使用了β分布。
当你将参数α和β都设置为1时，该分布又被称为均匀分布（uniform distribution）。尝试不同的α和β取值，看看分布的形状是如何变化的。
指数分布（Exponential Distribution）
指数分布是一种连续概率分布，用于表示独立随机事件发生的时间间隔。比如旅客进入机场的时间间隔、打进客服中心电话的时间间隔、中文维基百科新条目出现的时间间隔等等。
我将参数λ设置为0.5，并将x的取值范围设置为 $[0, 15]$ 。
接着，我在指数分布下模拟1000个随机变量。 scale 参数表示λ的倒数。函数 np.std 中，参数 ddof 等于标准偏差除以 $n-1$ 的值。
结语（Conclusion）
概率分布就像盖房子的蓝图，而随机变量是对试验事件的总结。我建议你去看看
的讲座，Joe Blitzstein教授给了一份摘要，包含了你所需要了解的关于统计模型和分布的全部。
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致酷勤网 C 程序员的那点事！
当前位置： >
浏览次数：次
生成随机数是程序设计里常见的需求。一般的编程语言都会自带一个随机数生成函数，用于生成服从均匀分布的随机数。不过有时需要生成服从其它分布的随机数，例如高斯分布或指数分布等。有些编程语言已经有比较完善的实现，例如Python的NumPy。这篇文章介绍如何通过均匀分布随机数生成函数生成符合特定概率分布的随机数，主要介绍Inverse Ttransform和Acceptance-Rejection两种基础算法以及一些相关的衍生方法。下文我们均假设已经拥有一个可以生成0到1之间均匀分布的随机数生成函数，关于如何生成均匀分布等更底层的随机数生成理论，请参考其它资料，本文不做讨论。
Inverse Transform Method
最简单的生成算法是Inverse Transform Method（下文简称ITM）。如果我们可以给出概率分布的累积分布函数（下文简称CDF）及其逆函数的解析表达式，则可以非常简单便捷的生成指定分布随机数。
生成一个服从均匀分布的随机数U&Uni(0,1)
设F(X)为指定分布的CDF，F&1(Y)是其逆函数。返回X=F&1(U)作为结果
这是一个非常简洁高效的算法，下面说明其原理及正确性。
我们通过图示可以更直观的明白算法的原理。下图是某概率分布的CDF：
我们从横轴上标注两点xa和xb，其CDF值分别为F(xa)和F(xb)。
由于U服从0到1之间的均匀分布，因此对于一次U的取样，U落入F(xa)和F(xb)之间的概率为:
P(U&(F(xa),F(xb)))=F(xb)&F(xa)
而由于CDF都是单调非减函数，因此这个概率同时等于X落入xa和xb之间的概率，即：
P(U&(F(xa),F(xb)))=P(F&1(U)&(F&1(F(xa)),F&1(F(xb))))=P(X&(xa,xb))=F(xb)&F(xa)
而根据CDF的定义，这刚好说明X服从以F(x)为CDF的分布，因此我们的生成算法是正确的。
下面以为例说明如何应用ITM。
首先我们需要求解CDF的逆函数。我们知道指数分布的CDF为
F(X)=1&e&&X
通过简单的代数运算，可以得到其逆函数为
F&1(Y)=&1&ln(1&Y)
由于U服从从0到1的均匀分布蕴含着1&U服从同样的分布，因此在实际实现时可以用Y代替1&Y，得到：
F&1(Y)=&1&ln(Y)
下面给出一个Python的实现示例程序。
import randomimport mathdef exponential_rand(lam):if lam &= 0:return -1U = random.uniform(0.0, 1.0)return (-1.0 / lam) * math.log(U)
Acceptance-Rejection Method
一般来说ITM是一种很好的算法，简单且高效，如果可以使用的话，是第一选择。但是ITM有自身的局限性，就是要求必须能给出CDF逆函数的解析表达式，有些时候要做到这点比较困难，这限制了ITM的适用范围。
当无法给出CDF逆函数的解析表达式时，Acceptance-Rejection Method（下文简称ARM）是另外的选择。ARM的适用范围比ITM要大，只要给出概率密度函数（下文简称PDF）的解析表达式即可，而大多数常用分布的PDF是可以查到的。
设PDF为f(x)。首先生成一个均匀分布随机数X&Uni(xmin,xmax)
独立的生成另一个均匀分布随机数Y&Uni(ymin,ymax)
如果Y&f(X)，则返回X，否则回到第1步
通过一幅图可以清楚的看到ARM的工作原理。
ARM本质上是一种模拟方法，而非直接数学方法。它每次生成新的随机数后，通过另一个随机数来保证其被接受概率服从指定的PDF。
显然ARM从效率上不如ITM，但是其适应性更广，在无法得到CDF的逆函数时，ARM是不错的选择。
下面使用ARM实现一个能产生的随机数生成函数。
首先我们要得到标准正态分布的PDF，其数学表示为：
f(x)=12&&&&e&x22
为了方便，这里我会直接使用来计算其PDF。
程序如下。
import randomimport scipy.stats as ss&def standard_normal_rand():while True:X = random.uniform(-3.0,3.0)Y = random.uniform(0.0, 0.5)if Y & ss.norm.pdf(X):return X
注意：标准正态分布的x取值范围从理论上说是(&&,&)，但是当离开均值点很远后，其概率密度可忽略不计。这里只取(&3.0,3.0)，实际使用时可以根据具体需要扩大这个取值范围。
当目标分布可以用其它分布经过四则运算表示时，可以使用组合算法生成对应随机数。
最常见的就是某分布可以表示成多个独立同分布（下文简称IID）随机变量之和。例如二项分布可以表示成多个0-1分布之和，可以由多个IID的指数分布得出。
以Erlang分布为例说明如何生成这类随机数。
设X1,X2,&,Xk为服从0到1均匀分布的IID随机数，则&1&lnX1,&1&lnX2,&,&1&lnXk为服从指数分布的IID随机数，因此
X=&1&lnX1&1&lnX2&&&1&lnXk=&1&ln&i=1kXi&Erl(k,&)
所以生成Erlang分布随机数的算法如下：
生成X1,X2,&,Xk&Uni(0,1)
返回&1&ln&ki=1Xi
这类分布的随机数生成算法很直观，就是先生成相关的n个IID随机数，然后带入简单求和公式或其它四则公式得出最终随机数。其数学理论基础是，稍微有些复杂，这里不再讨论，有兴趣的同学可以查阅相关资料。
生成具有相关性的随机数
现在考虑生成多维随机数，以最简单的二维随机数为例。
如果两个维度的随机数是相互独立的，那么只要分别生成两个列就可以了。但是如果要求两列具有一定的相关系数，则需要做一些特殊处理。
下列算法可以生成两列具有相关系数&的随机数。
生成IID随机变量X和Y
计算X&=&X+1&&2&&&&&&Y
返回(X,X&)
可以这样验证其正确性：
corr(X,X&)=&corr(X,X)+1&&2&&&&&&corr(X,Y)=&
注意：corr(X,X)=1，corr(X,Y)=0。
因此X和X&确实具有相关系数&。
这篇文章讨论了生成指定分布随机数的基本方法。这篇文章只打算讨论基础方法，所以还有很多有趣的内容，本文没有深入的探讨。这里给出一些扩展阅读资料，供有兴趣的朋友深入学习。首先是一篇，这篇文章来自美国陆军实验室，对计算机生成指定分布随机数的方方面面进行了全面深入描述，是不可多得的好资料。
在实现方面，可以参考以及我开发的。另外我做过一个，可以帮助你直观理解不同分布及PDF参数对分布的影响。
& 相关主题：