|
|
文/破戒僧
游戏的设计过程中经常涉及到概率的计算，这些实际问题有的简单有的复杂，有些看似简单的问题实际上需要复杂的计算，反过来，有些看似复杂的问题却又有简单的计算方法。而概率的计算，往往又因为思考角度不同，会有截然不同的解答方式，整个过程一个思考或计算偏差将导致这些计算结果的天差地别（如各种强化期望次数的计算，不同计算结果可以差出数百上千倍）。
这种情况下，如果有一种普适性的(可应对尽可能多的实际问题)、稳定的(计算步骤尽量少，计算不易出错)计算方法，就好了。在对这个问题的长久思考下，发现有2种方法，在游戏的概率计算时，可以通用：
1、循环模拟；
2、函数递归。
这两种方法都借助计算机进行计算，所以能尽量的减少计算中的步骤和人工计算，降低了出错机会。这2个方法也几乎不需要数学公式，公式越多越容易出错。理论上早期教材的高中数学(貌似现在初中就开始教了)的排列组合知识就足够掌握着两种方法了。
先以一个相对简单的计算作为实例：《魔兽世界》的副本Boss伊利丹掉落埃辛诺斯战刃(蛋刀)的主／副手，主副手的掉落概率分别为pa和pb，求集齐一套蛋刀平均需要击杀多少次伊利丹？若无特殊说明，本文蛋刀主副手的掉落互斥，即ab不会同时掉落。
1、循环模拟法
这个方法最为简单和粗暴，略有vba或其它语言基础的同学们都可以使用。但也因此这个方法往往被人诟病——技术含量低、结果不精确、计算效率低。原理很简单，以上述蛋刀套装的计算为例，使用2层循环，内循环使用一个Do while循环语句，在循环主体中使用一个变量对Boss击杀次数累加，并使用一个随机数模拟Boss的掉落结果。
在上述例题中，当蛋刀主／副手的掉落都为真时，则退出内循环，在外循环的For ..to..语句中，进行指定套数的蛋刀套装收集的模拟，用内循环的计数总和／指定的套装套数，得到平均一套蛋刀需要击杀的Boss次数。
基本逻辑伪代码主体部分如下：
pa=0.1
pb=0.5
raids=0
For set=1 to 1000000
seta=False
setb=False
Do while seta!=True and set!=True
‘循环体
‘模拟一次掉落
‘生成一个随机数
rd=Randbetween(1,100)
‘根据这个随机数，判断a／b本次的掉落情况
seta=Or(seta,rd>pa*100)
setb=Or(setb,rd>pa*100&&rd<(pa*100+pb*100))
raids=raids+1
…
loop
…
raids/1000000
…
vba很好学，24小时真的可以通关(满足工作需求绝无问题)，多练习就可以。上述的方法无法使得每个人都满意，比如，当条件改变时——收集3把蛋刀主手和4个蛋刀副手，就需要修改循环主体，所以可以考虑将需要凑齐的部件作为函数的参数传入。
function raids(pa,pb,seta,setb)
…
end function
前面有说过，这个方法无法得到精确结果，但当模拟次数足够多时(如上文百万次)，结果和精确结果非常近似。排除代码因素造成的人为Bug，这个方法非常可靠。所以有相当一部分数值策划直接用这个方法计算；或是用这个方法对概率公式的计算结果进行一次验算。 假如我们坚持要求出精确的期望次数，并且仍然希望解答方法足够简单，我们可以尝试函数递归。
2、函数递归法
递归，指的是函数在运行的过程中，会调用自身。使用递归解决问题有2个经典的案例，1个是斐波那契数列，1个是汉诺塔。递归的思想能极大的简化计算思路。
（1）爬楼梯问题
我分享了这样一道题：已知一个楼梯有n级，问有多少种爬法？
很多人说这个题意不明，考虑到契合主题，我们省略中间的分类例举和解释步骤，直接补全题意——人正常步伐下，一次迈步，可以跨越1～4级的楼梯(不考虑安全因素的话，每次都用跳的应该可以有5～6级，但是题目求的是比较正常的“爬”楼梯的情况)。
先考虑最简单的情况，一次只能爬一级楼梯，那么无论n=?，都只有一步一格的这样一种爬法。如果一步要么爬一级，要么两级，那么一个n级楼梯又有多少种爬法？貌似很难计算，但是如果用递归思想，爬到第n级楼梯，无非是从第n-1级楼梯一步一级的跨上来，或从第n-2级一步两级的跨上来。那么f(n)=f(n-1)+f(n-2)。这个算式其实就是斐波那契数列。后面还有一步能最多能跨3级和4级的情况，思路相同，不再赘述(面试中这题是考验应变和思路)。
可以看到，递归其实就是把一个复杂问题，分解为近似的若干子问题，这些子问题再行分解，直至达到一个可经过简单计算的子子..子问题，就可以得到最终答案。上述爬楼梯的可简单计算的子问题就是f(1)=1,f(2)=2，即一级的楼梯只有一种方法二级楼梯有{1,1}和{2}这样2种爬法。
（2）汉诺塔问题
同样的，汉诺塔问题也可以用递归方法很简单的解答。汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智 玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
为尽快进行实际计算，这里只截图对比一下递归和非递归计算的代码（VBA也可以轻松的写出这样的函数来）：
递归：
非递归，屏幕不够长，只截取最后一段：
相比起来，递归是个更有内涵的计算方法(严格说它不是个算法，只是一种思想)，初次接触的人会有少许的不适应感。蛋刀的计算问题，在上文提供的面试题集锦里，也有正确的算法。这里我给出另一种解法：
1 + pa (1/pb) + pb (1/pa)+ (1 - pa - pb)*x == x (方程1)
解这个方程得到，期望值x=
带入pa=0.1和pb=0.05，得到x=23.3333
因为主／副手互斥，所以，第一次掉落有3种情况，掉a(主手)／掉b(副手)／都不掉，这3种情况的概率是pa/pb/(1-pa-pb)。
如果第一次掉a，则还需要打出一件b，需要1/pb次，同理，掉b打a需要1/pa，都不掉则还需要x次(x是从无到有到打出一套蛋刀的期望次数)。
所以方程1代表的意义很明确：
1(有3种可能性的第一次掉落事件占用的次数)+ pa (1/pb)(掉a掉话，还要1/pb次凑齐套装)+ pb (1/pa)(掉b的话，还要1/pa次凑齐套装) + (1 - pa - pb)*x(什么都不掉还需要x次)，这些次数乘以各自发生的概率，得到的加权平均值就是要求的期望次数x——这是由期望值的定义得到的，期望值的这个性质是后面递归算法的核心。
如果暂时对这个方程理解还不够透彻，我们可以先看一个更简单的问题来强化这个认知：一个硬币有正反2面，正面朝上的概率为0.5，反面朝上的概率也为0.5，问：抛多少次硬币，才能至少看到一次正面和一次反面？
情形1，第一次为正面时，还需要投掷的次数=1 + 1/P正=1+1/0.5=3
情形2，第一次为反面时，还需要投掷的次数=1 + 1/P反=1+1/0.5=3
最终，期望次数=p正*期望次数1+p反*期望次数2=0.5*3+0.5*3=3
注：以前碰到一些同学，认为这里平均只需要2次就可以看到一次硬币正面和一次反面。有个很简单的方法可以证伪：只看到1次正面或1次反面的机会就需要平均2次了，条件更苛刻之后，需要同时也看到一次反面或正面，次数一定更多，所以一定大于2。
3、实战演练
前面说了这么多，我们再来一题实战：还是魔兽世界，还是打副本，这次是70级的职业套装副本，魔兽世界的某个10人副本，一次cd只能进入一次，副本内只有1个Boss，击杀Boss一定掉落一个兑换装备用的道具。这个道具可能是A,也可能是B，也可能是C，分别用于兑换战士/猎人/萨满，骑士/术士/牧师，以及盗贼/法师/德鲁伊/死亡骑士的装备兑换。
问：10个人进入副本，需要经过多少个副本CD才能每个人都拿到至少一件自己用的装备。
先化简题意：
我们所求其实是：1个Boss，有3个道具的掉落，掉率事件互斥，问期望击杀它多少次，能够拿到3个A,3个B和4个C。我们编写一个函数，期望次数 =n[A,B,C]，其中A,B,C是输入的参数，表示题目所要求的道具A/B/C的数量。
显然，当第一次副本掉了A时，我们还需要n[A-1,B,C]次。同样，当第一次掉B时，需要n[A,B-1,C]，掉C则为n[A,B,C-1]。
设第一次副本掉落A/B/C这3种情况的发生概率分别为,Pa,Pb和Pc，则：
n[A,B,C]=1+Pa*n[A-1,B,C]+Pb*n[A,B-1,C],Pc*n[A,B,C-1]
和爬楼梯相似，递归算法，需要一些简单可计算的子过程：
当B,C凑齐后，还缺少nA个A，则还需要的次数
n[nA,0,0]= nA/Pa;
同样，打nB个B或nC个C需要：
n[0,nB,0]=nB/Pb;n[0,0,nC]=nC/Pc;
当C凑齐后，需要nA个A和nB个B时，还需要的次数：
n[nA,nB,0]= (1 +Pa*n[nA - 1, nB, 0] + Pb*n[nA, nB - 1, 0])/(1 -Pc);
同样：
n[0, nB, nC]:= (1 + Pb*n[0, nB - 1, nC] + Pc*n[0, nB, nC -1])/(1 - Pa);
n[nA, 0, nC]:= (1 + Pa*n[nA - 1, 0, nC] + Pc*n[nA, 0, nC - 1])/(1 - Pb);
代入，Pa=1/3；b=1/3；c=1/3，就能得到结果：
VBA也可以写函数递归，只是没有mma方便(vba写一个递归函数，需要对参数的输入值大量的条件判断)，思路相同，语法有差别。
最后，留下2个思考：
1、文中例举的是掉落互斥的情形，如果相容(掉落互为独立的事件，不相互干扰)，应当怎样计算呢？
2、除循环模拟和递归这2个借助机器的解答方法外，纯正的数学解法是怎样的呢？
相关阅读：解构游戏设计中的随机性与概率问题
via：GAD
|
|
[复制链接]
发表于 2016-3-3 10:55:08
