不明觉厉系列之 输出手法（以及APL）的自动生成

附：[抛砖引玉]使用状态机和动态规划实现输出手法(以及APL)的自动生成

背景

　　为什么某个职业的输出手法是这样的，某个职业又是那样的循环？ 为什么精华帖的作者能给出输出优先级或循环？仅仅根据每个技能的伤害量，

　　技能效果以及冷却时间，能否输出一个最佳的输出循环？其实，精华帖的作者们大多也是参考技能伤害和说明，根据自己的感觉以及少量的验证(比如打木桩)

　　来慢慢优化自己的输出手法，从而给出自己认为较好的输出循环和优先级。SimC的出现也为验证输出手法的优劣提供了一定量的参考。

　　一些较为简单的输出循环，如防骑，也可以通过逻辑推理而得到：如果将十字军打击、审判的能量获取平摊到技能的CD中，由于十字军打击的冷却时间较短，

　　十字军打击的优先级较审判高。因此使用十字军打击>审判>其他技能的优先级进行输出，可以想象这个循环应该是最优的。

　　于是，输出循环的拟定和生成无非下面几种方法：

　　(1)凭借自己的感觉和尝试决定，或者使用SimC进行比对和调整，这种方法需要一定的经验和大量的手工尝试修改。

　　(2)进行一定的逻辑推理，可以推算出技能的优先级。这种方式对较为复杂的输出循环不适用，如暗牧的双目标输出，进行优先级的推理和证明较为困难。

　　能否利用机器进行寻找，找到较优或者最优的输出手法呢？我们知道机器最擅长的是尝试和搜索，然而暴力搜索并不适用：

　　每时每刻，我们都有四五种技能可以使用，如果每一种都尝试过去，那么搜索的数量会以指数级别上升。

方法

　　想想一下我们在实战的时候，如何进行伤害输出：有时候技能的CD好了，有时候DOT快消失了等等。其实这些量，技能的CD，目标DOT的剩余时间，

　　BUFF的时间等，都可以称作目前的状态，而每当施放一个技能(或者发呆)，总是会进入另一个状态，同时获得副产品伤害或者能量。

　　Code (c):

　　我们定义状态，是每个可以施法的时间点上，所有可以影响技能施放的量的集合。

　　以简单的防骑为例子(暂时不考虑飞盾的触发)，我们在打循环时，目的是使得获得的圣能最多(盾击有自己的GCD可以较为随意使用，因此是另一条循环，

　　不考虑在攒圣能的循环内)。回顾一下刚才状态的定义，于是我们发现，我们在决定下一个技能时，只需要看两个状态量就行了：十字军打击的CD，以及审判的CD。

　　Code (c):

　　下面使用CS=a, J=b 表示一个状态，其中a是十字军打击CD的GCD数，而b是审判CD的GCD数量。

　　施放技能时，我们其实是在做状态的转移。 比如在初始状态(CS=0,J=0)时，我们施放十字军打击，则施放完十字军打击，可以施放下一个技能时，

　　我们便在状态(CS=2,J=0)中了， (CS的冷却为3个GCD，等待CS本身的GCD转完后，便只剩两个GCD的冷却时间了)，同时在状态转移的过程中，

　　我们获得了副产品，一个圣能。

　　再以暗牧为例子，在暗牧的输出循环中，我们需要最大化的是伤害。而状态的组成成分较多。假设我们在痛目标上打出一个震爆，

　　实际上是从状态A(目标身上痛跳数：5，暗影球个数：2)转移到状态B(目标身上痛跳数：4.5，暗影球个数：3)

　　同时在转移的过程中得到了副产品(伤害)，等于(痛+震爆)的伤害。

　　因为在有限的时间精度内，状态的个数总是有限的。如果技能的冷却时间与GCD同步，那么以GCD作为时间的量纲可以减少状态的总个数。

　　有了状态，又有了状态的转移，其实我们的输出就是一个有限状态机，而输出的过程就是状态机中状态转移的过程。

找到最佳输出手法

　　有了状态，又有了状态的转移，于是我们理论上可以找到所有的状态和状态转移。因此，我们可以得到一张有向图，

　　其中的节点表示状态，边表示状态的转移(使用技能)，边的权值表示获得的伤害、能量的数量。

　　图：防骑的状态以及状态转移图。(CS=十字军打击，J=审判，x=填充技能)

　　于是我们的问题简化成，从在一张有向图上从某个起始节点开始走固定n步，要使走过路径边的权值的和最大。

　　图上的防骑只有10种状态，可以较为容易的找到输出循环所在(图中红色箭头)，而暗牧的单目标，则在不考虑急速的情况下大约有十万多种状态。

动态规划

　　可以看出这个问题无后效性，在某个状态时，你的后续动作获得的收益和你如何到达这个状态没有关系，因此可以使用动态规划解决。

　　假设我们已经有了走k步的所有路径，对于每一个路径终点V，我们都有最佳路径V(k)，那么在走第k+1步时，

　　我们就有U(k+1) = max { V(k) + E(V,U) 对所有V} 其中V,U为节点，V和U之间存在边，E(V,U)为边的权值。

　　Code (c):

　　证明：假设U(k+1)不是最佳路径，则必然有一条路径V'(k)-U为最佳路径，使得U(k+1) < V'(k) + E(V',U)。

　　由于U(k+1) =  max { V(k) + E(V,U) 对所有V}，那么U(k+1) >= V(k) + E(V,U) 对所有V，因此有

　　U(k+1)  >= V'(k) + E(V',U) 与假设矛盾。

　　根据数学归纳法，可以知道这个算法的正确性。

　　如果在每部迭代时，维护一个数组表示走k步对于每个可达节点V的最佳路径，以及路径的权值。

　　生成第k+1步的数组是遍历这个数组所有节点(走k步所有可达节点)，导出走k+1步所有可达节点的最佳路径，以及路径的权值。

　　这个算法可以用数学归纳法证明正确。算法的复杂度为O(n*v*ne)=O(n*e)，n为步数，一般~50，v为节点个数，ne 为每个节点边的个数，一般<10。

　　e=v*ne则为总的边数，对于防骑循环e=17,对于暗牧循环e=500k

　　实现算法后，我们对上述防骑循环进行了验证，得到了下面的输出序列：(上图红色路径)

　　Code (c):

　　crusader_strike->judgement->x->crusader_strike->x->judgement->crusader_strike->x->x

　　与推理得到的输出循环一致。

　　暗牧作为例子 (已经尝试过精通25%，50%为一样的循环)

　　在机器完全没有攒球，泻球阶段的概念下的，如果不考虑偷狂鞭的情况下生成了下面的循环：

　　(mf表示2跳鞭子)

　　Code (c):

　　mind_blast->ms->ms->ms->

　　mind_blast->ms->ms->ms->

　　mind_blast->ms->ms->ms->

　　mind_blast->ms->ms->ms->

　　mind_blast->vt->sw_pain->dp->mind_blast->mf->mf->dp->mind_blast->mf->mf->ms->

　　mind_blast->ms->ms->ms->

　　mind_blast->ms->ms->ms->

　　mind_blast->ms->ms->ms->

　　mind_blast->vt->sw_pain->dp->mind_blast->mf->mf->dp->mind_blast->mf->mf->ms->

　　继续重复，此为8跳循环。

　　在考虑偷狂鞭的情况下，有下面的循环：

　　Code (c):

　　mind_blast->ms->ms->ms->

　　mind_blast->ms->ms->ms->

　　mind_blast->ms->ms->ms->

　　mind_blast->ms->ms->sw_pain->

　　mind_blast->vt->dp->mf->

　　mind_blast->mf->mf->dp->

　　mind_blast->mf->mf->mf->

　　mind_blast->ms->ms->ms->

　　mind_blast->ms->ms->ms->

　　mind_blast->sw_pain->vt->dp->

　　mind_blast->mf->mf->mf->

　　mind_blast->dp->mf->mf->mf

　　此为12跳以及10跳循环。

目前存在的问题

　　可以看到，我们并没有考虑到不同的急速，在搜索输出循环的例子时，我们也没有寻找带有触发的输出循环。

　　这是因为目前这种方式寻找输出循环还存在下面两个问题：

　　急速：对于防骑来说不影响，对于暗牧来说就则是dot跳数的相对变化，对于其他职业来说可能就对状态数量有较大的影响。

　　在前面两种情况下，我们以GCD作为时间的量纲，那么状态的数量还是不会改变(对暗牧来说，只需要对不同的dot跳数分别运行就可)，

　　而如果其他职业技能的CD时间无法换算成固定的GCD数量，则需要取一个合适的时间精度(例如10ms)，将该CD包含在状态内。于是便有100^(CD技能的个数) * 100k个状态。

　　如果技能的数量<5，则为TB级别。此时状态的数量很多，通过一般的方法已经无法解决，那么我们可以：

　　(1)由于这个算法很容易就可以写成MapReduce了，我们可以在集群上跑两个小时就出来了(前提是你又集群可用)

　　(2)可以在动态规划上面做一些剪枝，减少状态的扩展。但是无法证明剪枝的正确性

　　(3)使用某些机器学习算法进行探索

　　虽然存在这样的问题但是我们发现，目前很少有职业，他们的输出循环在很大程度上受到急速的影响。0急速下的输出手法，其实在高急速等级下同样适用。

　　因此，我们也可以先生成一个大致的输出手法然后再加上一些小技能、对急速进行一定调整。

　　触发：目前我还没有较好的解决方案，目前动态规划只适合确定的状态转移。

　　代码：在我github上面 https://github.com/ak48disk/sp_state

　　PS：我最近比较忙，有了一点结果之后就没有继续研究下去了，我没有将输出手法导入到simc中进行验证，也没有生成暗牧双目标的输出手法(状态较多，需要写成MapReduce)。