微信号:MathAndAlgorithm

介绍:从生活中挖掘数学之美,在实践中体验算法之奇,魅力旅程,从此开始!

学会这个算法 《Dota》轻松虐菜

2015-05-11 00:00 算法与数学之美

看到知乎上有人在讨论算法,来个最常接触的,我相信有80%的人都接触过这个,DOTA里对各种概率型(比如暴击)攻击内置的算法——伪随机算法(Pseudo Random Distribution,简称PRD,不是需求文档!)

暴击真的看脸吗?当然不是,当你深刻理解伪随机算法,我想你还是可以对暴击进行一些人为干预的。这就是你dota水平迈向另一个境界的时候了。

伪随机跟真随机有什么区别?来举个例子吧,假如剑圣的暴击几率为20%,那么真随机的情况下,系统随机在1~100里面生产一个整数,如果生成的整数小于等于20,那这次攻击就判定为暴击。这个时候就有可能出现连续5次攻击全是跳劈,脸黑得选手可能连续10次攻击也没有一次暴击。

而极限的情况就是,你的BM或者PA可能一整场都在暴击(卧槽,你丫开挂呢),或者你打完一整场都没暴击过一次(艹,简直猪队友啊)。而伪随机呢,就是用来解决“减少连续性暴击,减少连续性没暴击”这个问题。

还是拿剑圣20%暴击概率举例,这时候剑圣第一次攻击暴击的概率是5.57%,而下次的攻击就会是11.14%,如果第二次还没暴击,那么接下来的第三次攻击的暴击概率就提升到了16.71%,每次都加5.57%,直到第17次攻击就会是100.26%的保证性暴击((⊙o⊙)…,好像还真有脸黑的情况存在)。暴击之后回到之前的5.57%,这样在多次的攻击后会形成平均20%暴击的几率。

使用PRD机制的事件

•进攻类,暴击、重击、双刀、漩涡

•防御类,山岭的皮肤,所有盾类

不受PRD机制控制的物品有

•碎骨锤,深渊之刀的晕,蝴蝶/天堂之戟的闪。

概率公式

p(N)=C*N

P(N)表示在第N次攻击时该动作发生的概率(下面还是以暴击举例吧),N表示第N次修正概率后的攻击次数(最小值为1),C表示暴击发生的初始概率以及每次攻击之后概率的增量,是个简单地线性关系。当N足够多得时候,P(N)总会趋向于1。在以下的文章里,技能描述上的概率会以P(E)来代替,表示期望值。

下面有两个表来描述常数C。P(E)表示期望值,C是常数。MAXN表示理论上叠加到100%暴击之前的最后一次攻击计数,举个例子,如下表,比如的暴击几率是45%,C是0.24931,那么N就是4,因为之前的连续4次攻击都可以是普通攻击(第4次攻击的),但第五次的时候,必定暴击。

当然以上得理论值不是暴雪实际中应用的数值,实际应用是如下表

在上面表中可以发现,当暴击几率到一定值得时候,实际暴击几率P(actual)就低于P(E),这后面就会涉及到暴击收益递减的问题,这里就不深入讨论了,dota里面的暴击也不是那么好堆,如果WOW的话倒是可以讨论一下。

再把两个图放一起对比,好好感受一下。常数C在在30%的时候实际值跟理论值还是很接近的,但是超过这个值以后,误差就开始大了。

那么引起这个概率偏差的原因是什么呢?简单归纳是由以下两点因素造成

1、常数C的有效位数。我们可以从上面的表格中看到,在实际运算中我们没有采用无限小数位而是取了一个近似的5位有效数字,造成了之后的误差。如果是采取动态实时算法来获取C的话,这会使每一次攻击动作的判定都会耗费非常多的CPU资源,因此选取了一种静态的lookuptable,以节省游戏资源。

2、所有的数值都是为天梯地图准备的,而不是普通用户自己编辑的地图。我们可以发现天梯地图里面技能概率值最大的特殊攻击是牛头人的粉碎,触发几率为25%,再回头看看,在30%以下,实际技能触发概率和期望概率是基本一致的,30%以后的C值都是在用之前的数据拟合的。所以大几率触发的事件目前来看并不重要,而且暴雪粑粑也不关心这些情况。

那么知道以上算法后,对我们DOTA有什么指导意义呢?来个下面的场景,上路二塔附近团战马上开打,你操控剑圣先去打普通怪物,连续两次(如果贪心的话你可以凑3次或者更多,看你感觉...)攻击不暴击的话,你就可以上去开战了,这样第一刀上去必然暴击,这肯定会提高你这次团战的DPS。

一些注意事项

虽然知道暴雪引擎内置了PRD算法,但很多机制还是得通过游戏观察推理得到,因为并不知道暴雪到底是如何运用PRD算法。比如你在攻击建筑物的时候攻击计数不会增加(一段时间拆塔之后,回头给一刀敌方英雄,不会100%暴击)。你的攻击计数也不会因为对方英雄的闪避(比如蝴蝶、PA自带的闪避技能)、高地造成的丢失而增加,但其中有一个例外,那就是虚空的“回到过去”,这个技能的机制是一种魔法效果,因此你的攻击被虚空“回到过去”时,你的攻击计数是会叠加的。

对于发球效果,在内置冷却期间攻击计数不会停止。对于一个英雄同时拥有多项PRD机制的技能,攻击计数是独立的。而一旦其中某个技能事件触发,所有的攻击计数都会归0,重新开始计数。当然每个幻想都有自己独立的攻击计数。


据说好多人都不知道长按图片也能关注,你知道吗?



 
算法与数学之美 更多文章 数学常数e的含义 数学最重要,一个经济博士(常春藤)Ph.D.的总结 线性代数的核心问题分析 最富创造性的数学家—黎曼 行列式的几何意义
猜您喜欢 InnoDB doublewrite与重做日志的关系 三天搞定Python基础功,Day 1基础篇 OpenStack进阶: 数据库开发基础篇 Elasticsearch特点介绍 昨晚面向对象直播太HI了,今晚8点继续...