游戏中的伪随机机制

kaleege

平时打游戏的知识，竟然工作中要用这个算法了，保存一下。


游戏中的伪随机机制你知道多少？

在游戏中，存在着大量随机事件，比如常见的暴击和游戏中的抽奖等。对于随机事件的概率，我们通对认为随机事件每一次发生的概率等于设定的概率，从另一个角度来说，随机事件每一次发生的概率都固定且不受事件上一次结果的影响。在大量样本计算的情况下，并不存在什么问题。然而在实际游戏过程中，我们会更关注于相对小的样本数下，也就是有限次操作（攻击/抽奖）过程中，随机事件带来的感受。为了保证有限次操作的概率相对稳定，营造良好的玩家体验，引入了伪随机的机制。本文对游戏中常见的随机过程做简要介绍，对伪随机过程较为详细的分析，并给出了一种简单的由概率求取伪随机过程的方法。

游戏中的随机概率，一般可以分为两类，一类是固定的概率，另一类是根据游戏行为有变化的概率。

比如20%的暴击率，我们通常认为每一次攻击触发暴击都是固定的几率20%，从另一个角度来说，每一次攻击的暴击率是独立且固定的，并不受攻击次数和之前攻击效果的影响。在实际过程中，玩家有了另外一种理解，或者说是期待，5次攻击出现1次暴击，更宽泛的一点说，玩家会认为在3~7（一般4~6为佳）次的过程中发生一次暴击。而对于游戏策划的设计来说，一般并不希望玩家能够在20%的暴击率下，获得较高概率的连续两次暴击，同时也不希望会有连续10次不发生暴击的情况。这些问题在传统固定概率的情况下较难得到解决。

对于固定的概率，定义P（K）为前K-1次未发生暴击，第K次发生暴击的概率，则P（K=N）为:

[url=][/url]

这是一个单调递减函数，随着N的不断扩大，P不断减小，在有限次操作的状态下，玩家对于20%容易缺少一个较为准确的感知。为了增强这种感知，可以让P在K=5附近拥有较大的概率，在其他情况下拥有较小的概率。当然在K=5之外，P趋近于0的速度是我们另外一个可以关注的问题，在此暂不做讨论。

下表为通过固定概率和伪随机过程获得暴击率的对比，P（K）为前K-1次未发生暴击，第K次发生暴击的概率，S（K）为前K项之和。

[url=][/url]

下图更直观的展示了这种差别。

[url=][/url][url=][/url]

从图中，我们可以非常清晰的看到通过伪随机函数能够较好实现预期。对于图表的进一步分析，在K=5附近的概率，3<K<7的概率，以及方差，在此暂不做讨论。

接下来我们对于伪随机过程做介绍，我们继续以暴击率为例。

对于暴击率来说，伪随机机制通过不同攻击次数拥有不同的实际暴击率来实现，具体规则如下：

设定初始的概率为P，定义随机种子C为一个常数。目前对于DOTA中剑圣的暴击率分析较为全面，本文也将以剑圣为例介绍伪随机机制，所以设定P=20%，C=5.57%。

1. 进行第一次攻击，暴击概率为C。如果未暴击，进入流程2；如果暴击，返回流程1进行下次暴击计算。

2. 进行第二次攻击，暴击率为2C。如果未暴击，进入流程3；如果暴击，返回流程1进行下次暴击计算。

3.进行第三次攻击，暴击率为3C。如果未暴击，进入流程4；如果暴击，返回流程1进行下次暴击计算。

。。。。

17. 进行第十七次攻击，暴击率为17C。如果未暴击，进入流程18；如果暴击，返回流程1进行下次暴击计算。

18. 本次攻击必暴击。返回1进行下次暴击计算。

也就是说，如果一个英雄始终不暴击，那么他的暴击概率将会是：C，2C，3C，4C，...，NC。当N足够大时，NC会大于等于1，所以一定会发生暴击。实际上，英雄攻击的暴击概率始终在若干个不同暴率的状态中切换。但是，当这种攻击进行次数很多以后，此英雄的平均暴击概率会趋近于20%

下面的表格是从网上搜索到的WAR3关于显示概率P、随机种子C、暴击前攻击的最大次数 maxN，实际统计概率Pcount的数据表格。

[url=][/url]

接下来对通过C值计算P值的过程做介绍。

在此我们令

[url=][/url]

为第K次攻击的暴击率（之前的K-1次未发生暴击），则

[url=][/url]

令代表第K次成功暴击的概率，即前K-1次未发生暴击，第K次发生暴击。

则

[url=][/url]

综上，成功暴击一次所需要的平均次数为

[url=][/url]

所以暴击的实际概率为：

[url=][/url]

通过以上推导，我们就可以根据C值求出实际概率Pa。

对于我们在实际使用过程中，我们更关注如何通过P值求得C值。P和c的函数关系为单调函数，在此我们介绍一种简单的方法进行实现，最小二分法，在最优化理论中有很多可以减少迭代次数的方法，欢迎大家进行尝试。

最小二分法如下：

首先我们会定义一些参数，C1，C2，C3，eps，初始化C1=0，C2=1，暴击率精度eps=0.01%，预设暴击率为Ps。

1.令C3=（C1+C2）/2

2.计算C3的实际Pa。如果Pa与Ps差值的绝对值小于eps，则结束计算，C3即为所需要的种子；如果Pa与Ps差值大于eps，进入流程3。

3.如果Pa<Ps,则C1=C3;如果Pa>Ps，则C2=C3。返回流程1。

通过有限次的迭代，我们就可以获得随机种子C。

通过以上的伪随机机制，有利于游戏中概率事件的稳定。对于暴击事件来说，伪随机机制降低了连续暴击或者连续不暴击的的概率，使得玩家的体验更为友好。

在现在手机游戏中，广泛采用 了可以保证一定收益的抽奖方法，比如玩家的十连抽，这种过程也是伪随机过程的一种。这种十连抽必中的策略，保证了玩家拥有较为平稳的体验，也有利于游戏体验节奏的把控。对于这些伪随机过程在此不一一分析。对于上文提到的如果使概率更为集中的方法，有兴趣的读者也可以进一步研究。

本文使用了网上的一些资料，对大家表示感谢，希望本文能够为入门同学提供一些帮助。如果大家对于复杂的随机过程感兴趣，欢迎一起讨论。如有版权问题，请联系我。

kaleege

WAR3的那个表太不准了，克扣概率，真黑。这个是自己算的。

P	C
0.05	0.003825
0.1	0.014648
0.15	0.032227
0.2	0.055664
0.25	0.083984
0.3	0.118978
0.35	0.158203
0.4	0.201172
0.45	0.248698
0.5	0.301666
0.55	0.360026
0.6	0.423177
0.65	0.48112
0.7	0.572917
0.75	0.669759
0.8	0.750977
0.85	0.823568
0.9	0.888672
0.95	0.94694
1	1

archers

伪随机似乎好过真随机，真随机的不确定性太大