不怎么正规的前言：

　　《伤害输出》是我已经动笔写了接近一年的一部作品。但是很遗憾，整部作品计划有五章，我目前只完成了第二章。第一章因写作水平有限，怎么改都不满意，所以只能先放下。后面三章尚未开始。

　　如果按照这个进度，整部作品完成可能需要太久的时间，所以我打算先放出第二章的内容。第二章的内容是“解析评估方法”，讲的是如何用数学解析的方式来评估一个角色的DPS。

　　作品中带有[M]标志的内容表示里面用到了高等数学；带有[HM]标志的内容表示里面用到了专业性较强的数学。无论如何，作品中大量使用的数学符号是为了精确描述，我建议读者去尝试阅读这些符号，但如果读者感到厌烦，略过所有数学符号应当不会影响你理解文章内容。

　　如果有生之年能完成全部五章内容，我会重新把它们整理成一篇作品。

解析评估方法

　　从这一章开始，我们要开始介绍实际的方法了。我们首先从评估开始。评估要做的事情是在实际进行游戏之前估计(或者说计算)DPS，有了评估的能力，我们才能做到在战前调整好状态，做好最佳准备，意义不言自明。评估可以直接解决“N选1”的决策问题——你有两件装备不知道哪个好？分别评估一下就知道了。评估同样也是后面我们要探讨的优化问题的基础，所以也在解决“

　　我们这里将评估方法分成了两大类：解析评估方法和统计评估方法。大家其实更熟悉统计评估方法，因为SimC属于统计评估，而且SimC的开发者们在哲学上是将解析评估和统计评估对立起来的，他们将这两类方法称为“Formulation”和“Simulation”[Ref]。如果听他们的说法，你会感觉“Simulation”是强大的而“Formulation”几乎没有意义。他们的说法其实大多都是对的，但一面之词春秋笔法，催使人产生主观情绪。这些开发者都是做实事的人而非理论家，统计方法更实用，所以当然更受到他们的青睐。

　　这里我将解析评估方法放在最一开始的位置，是因为我认为理解这类方法对于理解整个伤害输出问题的帮助是最大的，掌握这里的几个方法后读者会对整个问题有一个彻底颠覆的认识，所有人(只要你想认真玩)都应当了解这些方法。而之后还有对统计评估方法的介绍，则是因为统计方法确实在实际运用上更具有可行性，是供真正付诸研究实践的Theorycrafter准备的。

　　阅读这一章节读者要牢记，这些方法虽然能够解决问题，但我们大多数时候不会直接运用这些方法。讨论它们是为了分析和解剖我们的问题，所以读者应当着重理解每一个方法当中蕴含的思想。这里的每一个方法都是在经历相当精妙的思考后才能得到的，个个都让人拍案惊奇。

　　我想用实例的方式来叙述方法，我们需要构造一个例题，然后用各种方法求解它，并且在求解的过程中向读者展示这些方法的精妙之处。为了让大家不用花太多时间在理解例子上，对于评估和优化两类问题我都仅举一例。当然，例题是比较简单的，但它会包含实际问题当中碰到的那些难以处理的因素，所以实际问题无非就是将这些例题的规模扩大了而已，而求解方法几乎是完全相同的。

　　对于评估，我们将始终探讨这样一个问题：

笨牧师问题

　　笨牧师到目前为止暂时只会一个技能“痛”。

图 谁都会有搞砸的时候啦[Ref]

　　因为不熟练，笨牧师的痛只有30%概率会命中。

　　没命中的话，就什么都不会发生。如果命中，则挂一个DoT，每GCD造成1伤害，持续3GCD。如果重复挂DoT，会刷新。

　　在这里，为了方便起见，我们把时间的单位统一，无论GCD还是秒我们都认为是原子时间，而且干脆假设一个GCD就是1秒，以避免在时间单位上反复折腾。

　　笨牧师连续不停地对假人释放痛，求DPS期望。

　　这个问题非常经典，而且也相当实用，这个问题实际上来自于研究实践，而且在各个职业的模型当中都经常遇到它。举两例：

　　激怒覆盖率问题

　　狂暴战有一个技能叫嗜血。释放嗜血占用1GCD，如果嗜血暴击(几率为c%)，战士会激怒，持续5GCD。战士每3GCD释放一次嗜血，求激怒覆盖率。

　　狩猎刺激问题

　　猎人不停地释放奥术射击。每次奥术射击有30%的概率触发狩猎刺激，使下三次奥术射击的集中值消耗降低10点(重复触发则回到3层)。求奥术射击平均每发节约了多少集中值。

　　战士用这个模型来估计精通的收益，猎人则用这个模型估计狩猎刺激天赋的价值，所有“触发效果覆盖率”相关的问题大多都是这种模型，可以说是WoW当中的常见问题了。会计算它应当说很关键。

　　这个问题说难也并不难，但大多数人独自解此问题都不容易想出来，需要经其他人点拨一下才能找到解法(否则当时就不会为此讨论那么多层楼了)。

笨牧师问题——古典解法

　　我们求覆盖率。因为DoT的伤害是固定的，有了覆盖率我们很容易求DPS。

　　所谓覆盖率，有两种解释。一种是概率解释：假设笨牧师已经连续练习很久了，整个过程进入稳态，然后任取一个时刻看此时有DoT挂在木桩上的概率。一种是频率解释：让笨牧师打很长时间的木桩，然后统计DoT总共持续的时间，除以笨牧师打木桩的总时间。这两种解释最终得到的值是相同的(联系大数定律，它们相当于一个期望和均值的关系)。在实际游戏中，我们常用第二种，但分析问题时我们用第一种，因为分析问题的时候我们没有统计数据，而实际游戏中我们又懒得算。

　　问题的难点在于，当前时刻是否有DoT，与过往的事件有关。很难直接写出某一时刻有DoT覆盖的概率(假设为p)，因为之前(3秒内)任何一个时刻触发DoT都会延续到当前时刻，然后重复触发又会掩盖先前的触发，所以你几乎无法从“当前时刻DoT覆盖”反推出关于历史的任何有用的信息。

　　一点点逆向思维可以极大地简化这个问题。我们求“当前时刻DoT未覆盖”的概率。从“当前时刻DoT未覆盖”我们可以反推出有用的历史信息，因为当且仅当“前3次痛全部Miss”时，当前时刻才会“DoT未覆盖”。

　　命题“当前时刻DoT未覆盖”是“前3次痛全部Miss”的充分必要条件

　　充分性：命题“前3次痛至少有1次命中”→“当前时刻DoT覆盖”为真(显然)，所以逆否命题“当前时刻DoT未覆盖”→“前3次痛全部Miss”也为真

　　必要性：“前3次痛全部Miss”→“当前时刻DoT未覆盖”(显然)

　　“当前时刻DoT未覆盖”的概率1-p，就是“3连Miss”的概率，就是“Miss”的概率的三次方。喔哦，这么想来好像很简单。

　　求DPS更简单，我们具体看某一个GCD。如果DoT覆盖了，则会造成1伤害；如果没覆盖就没有伤害。

　　DPS是期望伤害除以时间。对这一个GCD求DPS就可以了，因为整个过程是由无数个像这样的GCD组成的，各个GCD之间都是对称的。(这种说法是通俗的直观解释，从马尔科夫链的角度来看，是因为这个链具有“非周期性”。)

　　2012年3月，华中科技大学的黄志超第一个向我展示了此类问题的古典解法。

[M]笨牧师问题——马尔科夫链

　　上一种解法虽然妙但并不美。隐约之中我们能够感觉到问题的全貌没有展示出来，而是被我们用小技巧回避了。我们找到了这个问题的一个弱点，然后从这一点突破，解决了这个问题，然而并不是所有问题都会有这样的弱点供我们突破。我们需要更加有力的工具来解决更广泛的问题，所以这一回，我们迎难而上，全面解剖问题，而不是寻求捷径。

　　在任意时刻，笨牧师可能处于以下四种状态之一(断痛，1/3痛，2/3痛，满痛)，我们分别标记为

图 状态划分

　　每次施法，都会导致状态发生转移：

　　处在

　　处在

　　处在

　　处在

　　这是很容易列写的。导致状态转移的因素有两个，一个是痛的命中与否，一个是时间的流逝，不要忘记后面这个因素，时间推移导致你在

　　我们把状态转移画到图上。

图 马尔科夫链

　　图中绿色箭头表示命中的结果，红色箭头表示未命中的结果。它们的转移概率分别写在了连线上。至此，我们构建了一个每条边都带有概率的有向图，这就是一个完整的马尔科夫链。

　　人们关于马尔科夫链的研究已经进行了上百年，所以我们将问题转化成了一个马尔科夫链之后，我们就有丰富的理论工具来对付这个问题了。在上一个解法中，我们求的是“痛的覆盖率”，这里我们也可以很容易地求覆盖率，我们运用马尔科夫链当中的“平稳分布”这个工具来求。

　　平稳分布指的是，当马尔科夫链平稳后(平稳指已经进行了很多步转移，记不清最开始是从哪里出发的了)，任意时刻我们处在各个状态上的概率。我们假设平稳分布为

　　我们知道我们一定处于这四个状态中的一个，所以有

　　因为整个过程已经平稳，当前我们的分布是

　　每一个方程的含义都是“此状态的分布=转入此状态的概率之和”。

　　将以上方程联立求解，可以得到

这个结果的含义是：任意时刻没有痛的概率是0.343，痛持续时间剩余1秒的概率是0.147，持续时间剩余2秒的概率是0.21，持续时间剩余3秒的概率是0.3。覆盖率是“有痛的概率”即

　　我们能不能不通过覆盖率计算DPS，而是直接从马尔科夫链的工具出发求出DPS呢？毕竟并不是每一个伤害输出问题都是无限挂DoT这样简单的，遇到复杂的问题没有通用的解决办法而只会取巧就会很麻烦。上面我们在建模时一直忽略了一个重要的因素：伤害。伤害作为一种价值取向，我们应当以“回报”的形式加入到模型中来，也就是说，造成伤害是对我们角色的一种奖励。将回报值写在每一条边上，就形成了我们完整的马尔科夫模型。

图 添加了回报的马尔科夫链

　　在笨牧师问题里，只要处于有痛的状态，就会造成1点伤害，所以我们把从

　　马尔科夫链清晰地描述了问题模型，并且也很容易求解，接下来有许多方法将基于马尔科夫链构建，所以理解此方法中的状态划分和状态转移的思想非常重要。

　　2013年8月，在探讨一个类似的问题(狩猎刺激)时，llxibo给出了一份基于马尔科夫链的解法[Ref]+得到了与古典解法相同的结果，并扩充了可解的问题范围。

　　在NGA能够找到一些年代非常古老的运用马尔科夫链的帖子，说明这个工具很早就已经有人在使用了。我在每个方法后面附注的来源，都是我自己得到这些方法的来源，而不是这些方法的创始。

[M]笨牧师问题——动态规划

　　上一个方法已经可以求解所有满足平稳假设的伤害输出问题了。但是实际游戏中我们并不是总能达到平稳状态的，短时间的战斗比比皆是，特别是每个版本末期，各个Boss的击杀速度快到超乎想象。如果能够放松甚至取消平稳假设，我们分析的问题就会更加贴近实际(几乎可以做到与实际游戏完美切合)，也会带给我们更多的启发。

　　现在我们对笨牧师问题添加一个条件：

　　假设笨牧师开始打木桩时，木桩上没有痛。n秒后，她一共连续释放了n次痛，求此时此刻她的DPS。

　　这样一个平稳的伤害输出过程(无始无终)就变成了一个非平稳的伤害输出过程(有始有终)。我们现在来尝试求解这个更加复杂的问题。

　　第一眼看上去，这个问题非常棘手。但仔细分析后我们能够找到解决问题的思路。

　　回想我第一次冲击进度的时候，H死亡之翼的脊背是我的团队遇到的最大的挑战，通过它就可以轻松通过整个H巨龙之魂。

　　作为战士，在死亡之翼的脊背上有一项重要的任务——爆发肌腱。

　　肌腱从出现到消失一共20秒。战士的GCD固定为1.5秒，所以在每次爆发肌腱时，我确定地能够释放13个技能，不会多也不会少。

　　而这13个技能的顺序，是固定的，是可以背下来的：撕裂-致死-巨人-压制-致死-压制-猛击-致死-压制-猛击-致死-猛击-压制。

　　你发现了吗？爆发肌腱的过程和我们这里的问题非常相似。确定的战斗时长，对我们分析问题其实是有帮助的。

　　而且，这个确定的时长越短，问题变得越简单。

　　在无从下手的时候，我们总是从最简单的那个地方入手。既然时长越短越简单，我们就从最短的时长开始入手。

　　假设n=0。

　　没有时间，当然是没有任何伤害的。

　　假设n=1。

　　如果我们当前没有痛，只有1个GCD我们是造成不了伤害的，我们挂上痛就要跳伤害的瞬间战斗结束了。

　　考虑更广的情况，分别假设我们现在处于

，给我们1个GCD的时间，我们造成的伤害都是多少？

　　这是很容易算的，对转出边的权值求个期望而已，

的转出边权值都是0，其他状态转出边的权值都是1。也就是说，从

开始我们造成不了任何伤害，从其他状态开始我们都一定能造成1点伤害(已经有痛了，战斗刚开始就会跳1点伤害出来，和我们释放的新痛没关系)。

　　所以我们很轻松地求解n=1的情况。我们把结果填写在一个表格里。

出发状态	S0	S1	S2	S3
n=0	0	0	0	0
n=1	0	1	1	1

　　假设n=2。

　　每当n增大一点，问题就复杂一点。n=1时，问题简单到不需要考虑时序因果关系，而只要看当前状态就能解决；n=2以后，因果关系就掺和了进来，问题难度陡然增加了。

　　如果当前没有痛，我们处于

。我们第一个GCD一定造成不了伤害，但我们有两种后续的可能：如果这次痛命中了(30%概率)，我们下一个GCD状态转移到

，于是下一个GCD就能够造成1点伤害；如果这次痛没能命中(70%概率)，我们下一个GCD状态依然处于

，于是也无法造成任何伤害。

　　但我们希望分析问题的时候仍然和n=1时一样简单，只看当前的情况而不用瞻前顾后，这样在n更大的时候我们分析问题才有可行性。如何拆掉这层因果关系呢？

30%命中->造成0伤害->转移到S₃->命中/未命中->造成1伤害

70%未命中->造成0伤害->转移到S₀->命中/未命中->造成0伤害

　　绿色表示这一时刻发生的事情，红色表示后续时刻发生的事情。我们不愿意瞻前顾后，也就是说我们希望避免考虑红色的部分，而只去考虑绿色的部分。

　　我们把红色部分单独拿出来作为一个子问题来看，在转移到

之后，时间还剩1GCD，我们发现问题形成了一个我们见过的格局：n=1，从

出发。这是我们在前面n=1的情况里刚刚讨论过的，我们已经知道n=1从

出发造成的伤害是1。同样地，我们知道转移到

之后的事情，n=1从

出发造成的伤害是0，这些我们在表格里能够查到。

　　所以我们可以把因果链条写得更简单一些：

30%命中->造成0伤害->造成1伤害(查表n=1,S₃)

70%未命中->造成0伤害->造成0伤害(查表n=1,S₀)

　　将这两种情况求个期望，我们就在表格里填上了一个新的数。粉色数字是从(n=1,

)的位置查到的，绿色数字是从(n=1,

)的位置查到的。

出发状态	S0	S1	S2	S3
n=0	0	0	0	0
n=1	0.0	1.0	1.0	1.0
n=2	70%(0+0.0)+30%(0+1.0)

出发状态	S0	S1	S2	S3
n=0	0	0	0	0
n=1	0.0	1.0	1.0	1.0
n=2	0.3	70%(1+0.0)+30%(1+1.0)	70%(1+1.0)+30%(1+1.0)	70%(1+1.0)+30%(1+1.0)

　　于是n=2的结果就全部可以计算出来了。

　　我们用数学语言来精确地描述这个问题的解决方法。定义符号

　　

——从状态s出发经过k步得到的期望伤害总量(即表格值n=k,s)

　　

——从状态s出发下一步转移到s'的概率

　　

——从状态s出发下一步转移到s'的转移过程的回报(转移过程造成的伤害，边权值)

　　

——状态空间(所有状态的集合)

　　我们有

　　第一个式子给出初始值，第二个式子为递推公式。

　　我们发现了一个方式来甩开因果关系。我们只考虑第一个GCD发生了什么事情，第二个GCD进入了什么格局。至于从第二个GCD开始往后发生了什么事情，全都通过查表来解决。我们从n=1开始一行一行地建立这个表格，直到n足够大，就可以得到我们想要的结果。我们给出了第一行的结果(初始值)，然后给出通过上一行建立下一行的方法(递推公式)，有了这两个因素就可以建立任意大的表格，这称为归纳。例如求(n=5,

)的结果，我们先建立表格的前五行，然后用相同的递推公式求第六行得到想要的值。

出发状态	S0	S1	S2	S3
n=0	0.000000	0.000000	0.000000	0.000000
n=1	0.000000	1.000000	1.000000	1.000000
n=2	0.300000	1.300000	2.000000	2.000000
n=3	0.810000	1.810000	2.510000	3.000000
n=4	1.467000	2.467000	3.167000	3.657000
n=5	70%(0+1.467000)+30%(0+3.657000)

　　结果

为2.124。

　　任意给定n我们都能通过归纳得到伤害总量

，除以时间n即得到DPS，所以这个非平稳的伤害输出问题已经得解了。

　　2014年底，AK-48首次提出用动态规划求DPS并优化策略[Ref]+。

[HM]解析评估的决战：用矩幂表示的DPS解析式

　　我们到达了一个最终的高度。马尔科夫链和动态规划已经在理论上可以解决所有DPS评估问题了，而如果还想进一步地深入，我们希望能够以完全解析的形式来表达DPS。能够写出解析式具有很强的理论意义，也是一种精神象征——能够写出解析式，说明这个问题是可以解析的，说明它是有规律可循的，而不是大家所认为的那样神秘莫测、混乱无序的。 定义符号

——状态空间

——状态转移概率函数

——直接回报函数

——策略 非平稳的DPS(有始有终伤害输出过程)可以用下面的形式解析地表达

(1)

　　其中

　　

、

和

都与游戏机制有关，构建因素也能够影响它们。

则表示策略。 式(1)是由三个矩阵组成的，我们给这三个矩阵分别起个名字。左侧的称作“提取矩阵”，中间的称作“增广转移矩阵”，右侧的称作“累积矩阵”。求这个式子的值的时候，从物理意义来讲，是从右往左依次做矩阵乘法。累积矩阵每左乘一个增广转移矩阵，就相当于做了一步动态规划，累积矩阵前面的0值会累积你能够造成的伤害量，值会随n增大越来越高。

时间内状态转移了n次，那么就左乘n个增广转移矩阵，这就是幂次的由来。最后，提取矩阵将累积矩阵当中第一个值(初始状态的累积伤害量)提取出来，然后除以时间

，即得DPS。 此式表达了一个有始有终的伤害输出过程，与实际游戏切合得非常紧密。只要写出

、

和

来描述系统，给定策略

，给定初始状态(放置在矩阵中1号元素表示的状态上)，给定时长n和

，这个式子就解析地表达了DPS期望，而且令人欣喜的是，这个式子中不包含任何“近似”的成分，是一种精确的表达。 特别地，平稳的DPS(无始无终伤害输出过程)可以从式(1)变形得到。 要表达“无始”，我们需要将“提取矩阵”当中前m个值替换成平稳分布概率，表示我们从一个平稳状态开始累计伤害。“无始”已经使得输出过程变得无限长，所以表达输出过程长度的幂次n也就失去了意义，取任何非零自然数都不影响整个表达式的值，所以终点在哪里已经不重要了，为简化表达我们将n固定为1。

　　由于去除了幂次，这个式子可以化简为

　　简化后的式子有着明显的含义，它恰巧表达了我们在介绍马尔科夫链时所做的最后一步计算。

是从状态s转出的所有边的回报之期望，平稳DPS则是依平稳分布对各个状态上的

求期望。从这里可以看出，平稳分布不单在笨牧师问题当中发挥重要作用，它在每一个伤害输出问题中都扮演着重要角色。 平稳分布

可以从下面的方程组中求取，其中

表示状态转移概率矩阵。它与我们在马尔科夫链的讨论当中列写的方程组是一致的。

　　这组公式是由我写出的。写出此式是受到中国科学院计算技术研究所的王天宇启发，2015年10月16日他向我指出“线性的动态规划可以写作矩幂形式”，我在10月28日写下了式(1)。

升级的笨牧师

　　我们为后面的章节做一点点提前的铺垫。笨牧师问题是非常经典的问题，但是太简单了，只有一个技能一直无脑释放。

　　现在我们的笨牧师升级了，她学会了一个新技能“惩击”，可以在任何时候释放，立即造成0.5点伤害。痛的机制和命中率没有变化。

　　这个新技能对笨牧师提升DPS有帮助吗？试考察采用下面这个策略的笨牧师，DPS是多少：

　　处于

时，释放惩击。

　　处于

时，释放痛。

　　这个问题引入了一个新的因素：策略。解决它会帮助你理解策略在本章中刚刚介绍的方法里所处的地位。评估时我们只管评价策略，在优化问题中我们会具体讨论如何求一份最佳的策略。

　　请读者略作思考后再展开下面的折叠继续阅读。

　　改变策略影响的是状态转移的概率和回报。系统没有加入新的状态，

的情况没有任何变化，只有

的转出边发生了变化，因为在

上我们选择了一个不同的动作。

图 升级的笨牧师问题马尔科夫链

　　求取DPS的方法与前例相同，故略去。