不会高数别玩魔兽 论牧师伤害输出的评估方法

[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的情况。我们把结果填写在一个表格里。

　　假设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,)的位置查到的。

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

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

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

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

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

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

　　我们有

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

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

　　结果为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的方法与前例相同，故略去。

上一页 1 2

新浪声明：新浪网登载此文出于传递更多信息之目的，并不意味着赞同其观点或证实其描述。