算法 | 有哪些算法惊艳到了你？

算法数学之美

日期：2019年1月30日

正文共：1670字6图

预计阅读时间：5分钟

来源：算法与数学之美

来个最常接触的算法，我相信有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机制控制的物品有

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

下面就是非常繁琐的PRD机制了，不敢兴趣的掠过就是

概率公式

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

PRD 常数C

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

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

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

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

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

1.常数C的有效位数。我们可以从上面的表格中看到，在实际运算中我们没有采用无线有效位而是取了一个近似的5位小数点，造成了之后的误差。如果是采取动态实时运算的C的话，这会在每一次攻击动作的判定都会耗费非常多的CPU资源，因此选取了一种静态的look up table。

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

- End - -

更多精彩：