游戏的概率计算(2)——期望
游戏的概率计算(2)——期望
先推荐一本书《全景游戏设计》，本文会引用书中的部分例题，展开我对游戏各种场合期望值的计算的一些不同看法，抛砖引玉，与各位探讨。
随机带来偶然性，偶然性有时候就是惊喜，最不济也是挫折，适当的挫折带给人挑战的动力，让人摆脱无聊的体验。
1.1. 从一个赌徒说起
1654年，法国贵族Antoine遇到了一个问题。他是一名狂热的赌徒，他曾经玩过一种赌法，掷4次骰子，赌能够至少有一次掷出6点。他从这种赌博中赚了大钱，但是他的朋友们已经厌倦了失败，并且拒绝再与他玩这个游戏。
为了找到一种新的方法来继续榨取他朋友们的钱财，他发明了一种新的玩法，并相信这种玩法与前一种拥有相同的胜算。在这种新玩法中，他掷24次骰子(每次投掷2个骰子)，赌至少有一次能掷出12点（2个6点）。他的朋友们起初都对这个玩法心存疑虑，但很快就都开始喜欢上这个新游戏——因为Antoine开始飞快的输钱。Antoine感到很迷茫，因为他通过自己的计算，得出两个游戏拥有相同的胜算：
第一种玩法：掷一个骰子4次，如果至少掷出一次6，则Antoine赢。
他的理由是，单独掷一次6点的概率是1/6，因此如果掷4次骰子出6点的概率是：4x(1/6)=66%，这也就说明了他容易赢钱的原因。
第二种玩法：掷一对骰子24次，如果至少掷出一次12点，则Antoine应。
Antoine判定用一对骰子掷出12点的概率是1/36，接着他推论，掷24次骰子的概率应该是24*（1/36）=66%，与之前玩法拥有相同的胜算。
因为输了钱而茫然的Antoine给数学家帕斯卡写了一封信，希望能够得到一些建议。帕斯卡发现这个问题很有趣——当时已有的数学方法还不能回答这些问题。于是帕斯卡给费马写信寻求帮助。两人漫长的书信往来，伴随着越来越多问题的解决和相应的解决方法的不断发现，诞生了数学的新分支——概率论。
故事讲完，长话短说开始计算，顺便介绍一下Excel中容易被忽视的概率统计函数：
1> 第一种玩法：掷一个骰子4次，至少掷出一次6。
这是一个成功率为p=1/6的二项分布，在excel中有2种计算方法：
方法1，使用combin组合函数，利用公式 ans=c(m,n)p^n(1-p)^(m-n)，
先求出4次掷骰中，4次都没有6的几率，然后用1去减。
ans=1- COMBIN(4,4)*(5/6)^4*(1/6)^0= 0.5177
方法2，使用二项分布BINOM.DIST函数，直接求解，
先求出，4次掷骰中，正好0次6的几率，然后用1去减。
Ans= =1-BINOM.DIST(0,4,1/6,1)=0.5177
BINOM.DIST函数的使用说明如下：
Ans=1-0.482=0.52
2> 第二种玩法, 掷一对骰子24次，至少掷出一次12点
使用同样的方法，所求结果ans=1-0.509=0.491，这就是第2种赌法，Antoine会输钱的原因。
那么Antoine究竟在哪里犯了错？掷一个骰子4次，得到6的个数期望值确实是4*(1/6)，但这并不是赢的次数的期望值，因为无论在一把4次的投掷骰子时，无论是1个6还是4个6，都只能算作赢一场。
注：excel还有其它几个常用分布的计算，如泊松分布用函数Poisson, 超几何分布用Hypgeomdist。
1.2. 游戏中的期望值
1.2.1. 技能的期望伤害
同样的，在游戏里，我们也经常有意无意的犯了同样的“错”，比如下表的技能：
技能名称 | 命中率 | 伤害值 |
风 | 100% | 4 |
火球 | 80% | 5 |
闪电球 | 20% | 40 |
我们很容易就把这3个技能的期望值分别算出，风=100%*4=4；火球=80%*5=4；闪电球=20%*40=8。
和1.1赌博的例子类似，当被这些技能攻击的角色，生命值低于技能伤害时，会有伤害的浪费，但这部分伤害，在上一段的计算方法中，被计入了。
以双方均为20生命为例，闪电球在命中成功时，有效的伤害也只有20点而已。似乎，我们应该考虑用20作为闪电球的伤害值，来进行期望伤害的计算，20%*20=4。
期望值的计算调整为，Edam=Min(技能伤害值，目标生命值)*命中率。这也是《全景游戏设计》中介绍的方法。
在游戏的平衡设计中，我们常使用期望值来作为实际的游戏体验的——胜负——情况的参考的利器，但实际上他总与实际情况有着差异。
以技能风，伤害值4，命中率100%和闪电球伤害值20，命中率20%的2个技能比较为例，分别携带这2个技能的生命值均为hp(1<=hp<=100)的2个角色互相PK为例，将风的胜利统计为1，风的失败统计为-1，平局统计为0(注：模拟时，认为双方总是同时出手，胜利条件为，某个回合后自己的生命值大于0，但对方的生命值小于等于0；失败条件则完全相反；平局意味着，某个回合自己和对方生命值一起小于等于0)。
则进行大量实验的结果x(x的取值为-1,0,1)的平均值ave，ave越接近0表示双方的胜负情况越接近。对hp=1,2,…,100分别进行10万次的统计，得到如下的结果：
（每个纵坐标x的值表示的是胜利比失败多出的比例）
可以看到随着生命值hp的提高，x的取值以周期震荡形态逐渐的靠近0。这意味着平衡性随着生命值的提高而变好。
我们如果深入下去，很多值得思索的地方：周期看起来非常像是20，这是偶然吗；各周期的波峰波谷绝对值逐渐减少这是必然吗；每个周期内的均值是多少，能够计算吗？
尽管这几个问题很值得探讨，但本文并不打算深入下去。本文主要的目的，是指出一些“标准流程”中容易过度自信的地方，指出实际情况与计算结果之间产生误差的原因，并尽可能圈出“安全范围”。
对于这个问题，我们看到，只要提高生命值到一定的程度，误差就可以被控制在一定的范围之内。对上述技能风与闪电球的比较中，我们可以粗略的认为，每次的波峰衰减至80%左右。基于此，在10个周期内，偏差会小于0.8的10次方（约为10%），即，200点生命值对于期望值为4的伤害，是足够精确的。
到这里，我们还需要对偏差产生的原因，定性的分析一下，(顺便也解释一下，上文图中呈现试验数据并不是由于代码错误之类的原因造成的，它真的是这样)。我们理一下思路，风(攻击4，命中100%)和闪电球(攻击20，命中20%)比较，第一次交手，双方都能有机会出手，但在第2次交手时，风的技能能否出手，取决于闪电球前面的交手是否命中了他——如果第一次交手就被闪电球命中，第2回合就无法出手。所以，风的5个回合内的平均伤害={4,4*0.8,4*0.8^2,4*0.8^3,4*0.8^4}/5=2.7。
1.2.2. 武器的期望伤害和掷骰子
武器的期望有2种情形，1种是暴击，另1种是武器攻击力的上下限。
我们在计算时，会认为50点攻击的武器——剑，和40点攻击并且25%的几率发生2倍的暴击伤害的武器——匕首，具有同样的期望伤害50点。在实际的属性投放时，基于某些考虑（比如1.2.1中的伤害溢出，或是和其它带暴击效果的比如技能等模块的叠加规则，以及生命值的设置等），暴击的发生概率和暴击的伤害倍率会酌情调整，参考Dota的几个暴击技能(排除了幻影刺客的大招、熊猫和赏金的带闪避暴击复合技能)：
骷髅王，15 % 的几率造成2 .75 倍伤害的致命一击，期望伤害126%
小娜迦，45 % 的几率造成1 .5 倍致命一击,期望伤害122.5%
剑圣，36 % 的几率造成2倍致命一击，期望伤害136%
骷髅王，由于是力量影响，血量和攻击频率与敏捷英雄有差异，也排除掉，观察剑圣和小娜迦，看到dota在这个场合下，对爆率更低的单位给予了更多的期望伤害的补正。
与暴击类似的，是武器的攻击上下限，这和D&D规则中的nDm，以及多次掷骰的期望和相似，也可以将之认为是前面武器或技能的暴击的推广。
以下面的一个赌博玩法为例：
游戏内置了一个赌博玩法，在一个有分支的路线上，散布着玩家可见的宝箱，玩家通过投掷一个范围[1,6]的骰子，来随机距离的进行移动，并获得沿途经过的格子上的宝箱，参考下图：
为简化计算，我们先以一个10格长赌的线性路径为例，平均投掷多少次骰子，才能到达终点（点数和大于等于10）。
如果用期望值，1~6的骰子，每次的期望投掷点数=（1+2+3+4+5+6）/6=3.5，直觉上，平均投掷10/3.5≈2.86次骰子。
到这里大家应该已经能够习惯偏差了，是的，在掷出1次6之后，无论掷出4还是5、6，都能够到达终点，但5和6的出现拉高了掷骰的期望点数，就像拉高我们的平均工资一样。。
解决这个问题，我们先要解决的问题是，n次掷骰，刚好点数和为s的概率，之后就可以通过求n次掷骰子的点数和为10,11,12,…,6n的概率和，来分别计算n次骰子能够到底终点的概率，对这组概率再进行简单的计算，就能够求出掷骰子次数的期望值了。
计算n次掷骰，刚好点数和为s的概率，有不下7种方法，这里列出操作性较高的几种方法：
n 离散多重卷积公式
n 求(1+x+x^2+...+x^5)^n中x^(s-n)的系数
n 函数递归
n 程序模拟
n 马可夫过程
这里用程序模拟的方法，最终分别10万次模拟到达终点，求出10组分别的平均掷骰子的次数如下：{3.32491,3.3225,3.32618,3.32693,3.32595,3.32468,3.32445,3.32322,3.32175,3.32769}
这个结果的精确值是3.32369，与开始的2.86差距还是有些大的。
1.3. 蒙特卡洛模拟
上个月围棋界的李世石VS阿发狗，让很多人听到了“蒙特卡洛”这个名词，其实大多数数值策划都用过这个模拟方法——我们使用vba或是其它的工具，进行若干次数的循环模拟计算结果，就是蒙特卡洛模拟的一种应用方式。
虽然最早认为这种方法的应用，是蒲丰投针试验，但是我个人认为最早的应用可能是在占卜。另外，中学的生物课里学过的孟德尔豌豆实验，也是使用了蒙特卡洛方法。
蒲丰投针试验
孟德尔豌豆实验
现在，随着计算机性能的提高，这种模拟、统计和计算都交给计算机了。
具体模拟的方法，可参考：
《简述如何制作战斗模拟器》http://gad.qq.com/article/detail/7149578
在Mathematica里，这个模拟更加简单:
其中k=10，即所求之和
很多人都说过，战斗的模拟器的制作没什么用，其实这有2种意思：一种说法是，我有更好的办法；另一种说法是，这东西我得不到对我游泳的效果。阿发狗都4比1碾压李世石了，这应该能说明一部分问题了。我希望每个这样说的人，都掌握了更好的方法。
在概率计算(1)中，留了个问题，这里用另一个更一般的问题回答吧：
问题是，一个集字活动期间，玩家每完成一次副本，都有几率获得一个汉字（这个字可能是“八仙过海，各显神通”之一，每个字的概率各不相同，分别为p1,p2,p3,…,p8），收集齐一套汉字，就可以获得活动奖励，活动期间，仅可获得一次奖励，且汉字不可以交易交换。求玩家需要打多少次副本，才能获得奖励？
数学解，答案是：
牛刀小试一番，我们用它计算蛋刀套装的收集次数问题，设蛋刀主手掉率p1=0.1；副手p2=0.05；计算获得一套蛋刀需要计算的boss的平均数量：
ans=
9 / 9