[同挖坑]DOTA中对有限血量的目标进行攻击的研究

三 18

[同挖坑]DOTA中对有限血量的目标进行攻击的研究

其实我标题党了哈~这个和真正的DOTA还是略有差距的。主要是昨天看到SQYBI牛在blog里面提出了这样的一个问题：

如果我们有两个英雄X和Y，他们每次攻击造成伤害的数学期望是一样的。那么如果他们的攻击目标Z的血量无限，在经过足够长的时间之后，他们造成的总伤害期望也应该是一样的。
但是实际上，DotA的英雄血量并不是无限的。这时就会有一个问题了，让X和Y对打的话，谁赢的几率大一些？

于是我对这个问题进行了一下自己的思考，同时也挖了一个坑。

先简单叙述一下SQYBI牛的问题：假设英雄Y的攻击力稳定为一个值，英雄X的攻击力在上下限中浮动，同时具有暴击——就是一定概率打出k倍于平时的攻击力，其中假设这两个英雄的攻击力期望值相等。然后让这两个英雄分别攻击具有同样血量的目标（护甲什么的其他因素一概忽略），那么他们的攻击次数的期望谁更少？

将这个问题抽象出来便是：在数轴上有两个动点X和Y位于0点，Y每次向右移动的距离是固定的，X向右移动的距离是不定的，但是两个动点移动距离的期望是相等的，现在问要到达或者超过点L，X和Y哪个点移动的次数最少？希望这样叙述一遍之后不会再造成一些不必要的误解了。下文依旧按照原题背景进行分析讨论。

我开始在原背景基础上尝试建立一个简单的模型。假设目标的血量是L，英雄X的普通攻击力是A——此处先不考虑攻击力在上下限中浮动的问题，即只有普通攻击和暴击两种情况。打出暴击的概率是p，暴击能打出k倍于普攻的攻击力。那么X的攻击力期望值就是 $E[X]=(1-p)A+pkA=E[Y]$ ，这个也是英雄Y每次都稳定的攻击力。显然得到Y的攻击次数便是 $\lceil \frac{L}{(1-p)A+pkA} \rceil$ （取天花板数）。主要问题便是分析X的攻击力。假设X在整个攻击过程中打出了t次普攻，s次暴击，那么可以得到一个不等式 $tA+skA\geq L$ 。显然，对于每一组(t,s)，这都是一个贝努利实验，于是每一组(t,s)对应的情况出现的概率便是

$C_{s+t}^{t}(1-p)^{t}p^s$

接下来便是确定t和s的取值情况。对不等式进行变换，便可以得到 $s\geq \frac{L-tA}{kA}$ ，由于s是满足此式的最小整数，那么便能得到 $s=\lceil \frac{L-tA}{kA}\rceil$ 。所以我们能够通过t来确定s。显然的，t的取值范围是 $[0,\lceil \frac{L}{A}\rceil]$ ，那么与概率式相结合，我们就得到了英雄X的攻击次数期望：

$\sum\limits_{t=0}^{\lceil \frac{L}{A}\rceil}[C_{s+t}^{t}(1-p)^{t}p^s(t+s)]$

其中 $s=\lceil \frac{L-tA}{kA}\rceil$

下面便是真正困难的地方了：我们求出了两个英雄的攻击次数期望值，但是难以对它们进行比较。于是我便考虑通过mathematica对这两个情况进行分析，情况如下：

以上是我的代码，即将概率p视作连续因变量进行作图分析，在下面的几幅结果图中，靠右的一条线是英雄X的，分段的线是英雄Y的结果

A=20,k=4,L=200的情况

A=30,k=4,L=200的情况

A=20,k=4,L=350的情况

A=20,k=8,L=200的情况

通过上述mathematica对一些参数的具体值进行的分析结果，我们可以得出，英雄Y的期望攻击次数确实是小于英雄X的，也就是说对于同样血量的目标，拥有稳定的攻击力能够用更少的次数击杀掉它。

下面的坑便来了：我试图进行更一般的分析。假设英雄X的攻击力为 $A_i$ ，对应的击出概率为 $p_i$ 。那么便有攻击力期望 $E[X]=\sum p_i A_i =E[Y]$ 。此时易得Y的攻击次数。假设在整个攻击过程中，英雄X进行了 $t_i$ 次攻击力为 $A_i$ 的攻击，那么我们也能同样地列出一个不等式： $\sum t_i p_i A_i \geq L$ 。对于每一组 $(t_1,t_2,\cdots ,t_n)$ ，都能通过多项分布的公式计算得到此组数出现的概率是

$\frac{(\sum t_i)!}{\prod (t_i !)}\prod p_i^{t_i}$

然后仿照前述方法便可求出期望，但是式子异常繁琐。通过mathematica对一些参数的具体值进行分析可得到，基本上Y的攻击次数还是大于X的攻击次数的。

现在的坑就是：怎么样通过分析上面的期望表达式进行一些定性分析。例如我可以猜想打出暴击的概率越大，暴击的倍数越小，则攻击次数期望越接近。或者是分析当两个英雄都不是稳定攻击力时，在攻击力期望相等的前提下怎么比较攻击次数的期望大小。我认为只有讨论了这些，才是对这个问题的彻底解决。

恩，暂时就能想到这么多，不知道SQYBI牛和读者有什么想法~~

本文由严酷的魔王创作，转载或引用前请联系我们。

标签：DOTA, Mathematica, 建模, 期望, 游戏

2011年3月18日星期五

14条评论

2011年3月18日星期五 16:17:12

sqybi 说：

哇，对这个问题进行的描述相当清晰！我的确有点觉得自己的描述比较蛋疼，导致了楼下各种误解……
分析应该很清楚了，已经达到了我想做出的结果……当初概率论没学好，惭愧……
不过比较攻击次数两个期望的大小的确是个难题，我感觉自己是无能为力了，只能期待数学牛的出现……

回复

严酷的魔王
2011年3月18日星期五 17:39:21

回复：
同期待……
不过根据mathematica的模拟，当p很大的时候，其实有可能出现有暴击者的攻击次数期望小于攻击力恒定者的情况，不过好像都到p>0.9的情况了，所以我之前想走的变形出一个可以进行比较的不等式的路应该不行……

回复

sqybi
2011年3月18日星期五 23:45:48

回复：
除了p=100%以外，不可能有这种情况。。直觉上是这样的

回复

sqybi
2011年3月18日星期五 23:48:26

回复：
而且我似乎测试过0.99，还没有出现这种情况。。。

回复

严酷的魔王
2011年3月19日星期六 0:02:39

回复：
诶呀好像我找不到这个情况了。。。嘛。。说不定是我当时的code出问题了当时我的code和现在这个不一样

回复

darkraven
2011年3月20日星期日 0:32:01

回复：
总觉得有问题，p=0的时候，两者的攻击次数不应该是一样的么

回复

严酷的魔王
2011年3月24日星期四 11:25:16

回复：
我也在苦恼这个问题 = =|||
当p=0的时候取极限，发现暴击的式子的值正好是稳定攻击力的值的Ceiling[L/A]倍。。

回复

异生
2011年4月5日星期二 11:20:12

回复：
“对于每一组(t,s)，这都是一个贝努利实验”，比如L=8,A=1,k=3,由t=1算出s=3,显然对于(1,3)，没对应一个贝努利实验，因为先出现暴击3次时，已不需要普通攻击了，所以算X攻击次数期望时多算了很多情况。（还没完全想清楚，不确定是否说出了本质）
{OT}这个博客真不错，景仰一下……

回复

异生
2011年4月5日星期二 11:30:15

回复：
sorry漏了两字，“对于每一组(t,s)，这都是一个贝努利实验”有误

回复
2011年3月18日星期五 22:43:45

FlowerShin 说：

哎哟我擦……您这简直是……

回复

严酷的魔王
2011年3月18日星期五 23:28:04

回复：
简直是让你不得不好好写概率论50题作业去~ XD

回复
2011年3月20日星期日 0:24:35

darkraven 说：

再一般化一点吧：
对于随机数列{An}，Ai取k的概率为Pa(k),
对于随机数列{Bn}，Bi取k的概率为Pb(k),
Ta=min(i | sum(1~i,Ai)>=L)
Tb=min(i | sum(1~i,Bi)>=L)
比较Ta和Tb的数学期望

回复

darkraven
2011年3月20日星期日 0:25:07

回复：
唔，其中函数Pa,Pb给定

回复
2011年3月23日星期三 17:26:51

Malloc 说：

设置参数有点多啊，可以简单的把L设为1，然后A=0.xxxL这样可能容易看得到一些东西。

回复

f(Program,Poet)=Programet

[同挖坑]DOTA中对有限血量的目标进行攻击的研究

14条评论

留下您的足迹

雁过留声

看一看，瞧一瞧~

随机阅读

最新评论

索引