WisKeyのLullaby

huangwei.pro 『我失去了一只臂膀』「就睁开了一只眼睛」

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  12 Posts :: 0 Stories :: 23 Comments :: 0 Trackbacks

公告

“我该走哪条路?”
“这取决于你要去哪里。”
“我只想能到某个地方。”
“只要你走的够远,你始终能到达那个地方。”

Home: huangwei.pro
E-Mail: sir.huangwei [at] gmail.com
09.6 毕业于杭州电子科技大学
进入网易杭州研究院工作至今

常用链接

留言簿(1)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 45580
  • 排名 - 395

最新评论

阅读排行榜

评论排行榜

http://huangwei.pro/2015-07/game-random/


这段时间公司开发的游戏上线测试,许多玩家在抽卡时抱怨脸黑,很难抽到所需要的卡牌,而又有一部分玩家反应运气好能连着抽到紫卡,检查了下随机相关逻辑代码,并没有找出问题所在,玩家运气好与坏只是觉得真有可能是概率原因。


测试开服了几天之后,需要开放某个限时抽卡活动,在内部测试时,我们发现玩家反应的问题在限时抽卡中格外明显,尤其是其中最主要的一张稀有卡牌,猜测因为限时抽卡库配置的种类较少,然后就拿该活动来检查了下我们游戏随机机制问题。

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

大部分游戏策划使用权值来配置随机概率,因为权值有个好处就是可以在增加随机物品时,可以不对之前的配置进行更改,比如:白卡 30,蓝卡 10,紫卡 10,转为概率即是:白卡 60%,蓝卡 20%,紫卡 20%。

而上述限时抽卡的例子中,我们的权值配置是5和95,模拟50000次随机(使用系统随机函数,如C的rand函数,Python的random库)得到如下结果:

按权值随机50000次

上图绘制的是权值为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%概率

pool = [] 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出现,这样就太假了,根本没有随机感受可言,为了模拟随机并可以控制一定的出现频率,我选择正态分布来进行伪随机分布生成,原因是分布会更自然一些。

正态分布

关于正态分布这里就不详细描述了,只需关心分布的两个参数即可,位置参数为μ、尺度参数为σ。根据正态分布,两个标准差之内的比率合起来为95%;三个标准差之内的比率合起来为99%。

根据正态分布,两个标准差之内的比率合起来为95%;三个标准差之内的比率合起来为99%

用上面的例子来定下参数,μ=20,σ=20/3,这样每次按正态分布随机,就能得到一个理想的随机分布和概率区间。

C语言标准函数库中只有rand,如何生成符合正态分布的随机数可以参见WiKi上的介绍。这里我直接使用Python中random库中的normalvariate函数,当然gauss函数也是一样的,官方文档上说gauss函数会快些,StackOverFlow上说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 minj = -1 for j, pp in enumerate(p): if pp < minp: minp = pp minj = j 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,可以看到只有绿色是符合分布要求的,而蓝色和青色退化成第一种实现。

基于正态分布的随机实现 
基于正态分布的随机实现

完美!

玩家体验

最好每个玩家有各自的随机种子,否则会造成体验上的误差。服从正态分布的全局随机序列,不同玩家任意的取走序列中一段或者一些值,就可能导致对于每个玩家而言,各自取出的随机序列不再服从正态分布。

结束

我只能感叹Python的库太强大了,matplotlib绘制出来的图形也挺漂亮的,感兴趣的童鞋可以查阅用Python做科學計算

更多内容请移步huangwei.pro

posted on 2015-07-27 01:20 威士忌 阅读(2780) 评论(4)  编辑 收藏 引用

Feedback

# re: 游戏中的随机概率 2015-07-27 16:54 GameBoy
C++ 有normal_distribution实现正态分布  回复  更多评论
  

# re: 游戏中的随机概率 2015-07-28 11:55 KaleoVon
在游戏中做强化之类概率的时候,也遇到了这种问题,好文章  回复  更多评论
  

# re: 游戏中的随机概率 2015-08-31 14:18 freeeyes
非常不错,主要是以谁为1的问题。好文章,记录了。  回复  更多评论
  

# re: 游戏中的随机概率 2015-12-01 17:16 mmocake
Python的库确实强大 MARK下  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理