Mathematics of dynamic cycles

Kavan · 12/28/08, 4:44 AM

I've seen a number of attempts to analytically compare the different options presented by the new arcane spec. Most however just compare static cycles so I thought it appropriate to give a short introduction to modeling of dynamic cycles. This applies to all specs, not just arcane, but in this introduction post I'll just give examples for those since they are currently most interesting. The explanations here should also give you enough information to better understand the cycle modeling in Rawr.Mage and if you ever want to see a new cycle added there, providing such a model of the cycle is the best you can do to make it happen. I'll try to explain things in lay terms, but I'll drop in enough keywords so that if you're interested in learning more about the theory behind it you'll know where to start the search.

A dynamic spell cycle can be expressed as a Markov process. This means that we have a number of states in which we can be, a number of actions that can be performed in each state and transition probabilities that tell us given a current state and action how likely it is that we'll end in a given state. Once we have such a description our goal is to compute the various characteristics of the cycle such as dps and mps. To do this we compute the stationary distribution which tells us in the long run how likely we are to be in a given state at any point in time and use this to compute the expected values of different properties.

Let's start with a simple example to see how this all works out and compare the results with how you would otherwise solve the case in such a simple scenario. Imagine we have two spells, A and B. We usually cast A, but there is a 50% chance that A will result in a proc in which case we cast B (and this consumes the buff, B cannot proc the buff). We ignore any delays in observing the procs. To have a better grasp on what's going on lets make up some numbers. Lets say A has a 2 sec cast and does 100 damage and B has a 1 sec cast and does 200 damage.

I'll show two ways of how you can model this. In first case we'll define two states. S0 will represent a state where there is no proc, S1 will represent a state with proc buff. We can then write our model as

S0:
A => S0 0.5
  => S1 0.5
S1:
B => S0 1

This means that in state S0 we perform action A and with probability 0.5 we end in state S0 and with probability 0.5 we end in state S1. In state S1 we perform action B and we always end in state S0.

Next we have to compute the stationary distribution. To compute this we use the fact that when we have stationary distribution and we move one step forward in the simulation we remain in stationary distribution (or in other terms we're looking for unit eigenvector associated with eigenvalue 1 if we express the transitions in a transition matrix). We do this by looking at how we can get into each of the states. We can get into state S0 with probability 0.5 if we are in S0 and with probability 1 if we are in S1. Similarly we can get into state S1 with probability 0.5 if we are in state S0. We can write this down as

S0 = 0.5 * S0 + S1
S1 = 0.5 * S0

At the same time we know that since this is a probability distribution the sum must be 1

S0 + S1 = 1

We now solve this set of equations (notice that one is redundant) and get the result

S0 = 2/3
S1 = 1/3

Once we have the stationary distribution we can start computing the values we want. Let's express expected value in general. Since in state S0 we always perform A and in state S1 we always perform B this is simply

value = S0 * value(A) + S1 * value(B)

We use this to compute both expected time and expected damage as

time = S0 * time(A) + S1 * time(B) = 2/3 * 2 sec + 1/3 * 1 sec = 1.67 sec
damage = 2/3 * 100 + 1/3 * 200 = 133.33

And finally the dps of this cycle is 80.

We can express this cycle in another way by realizing that if A procs, we always follow with B. Looking at it in this way we can express the cycle in a one-state model.

S0:
A  => S0 0.5
AB  => S0 0.5

Stationary distribution here is very simple since we're always in state S0. Let's look at the values now.

time = 0.5 * time(A) + 0.5 * time(AB) = 0.5 * time(A) + 0.5 * time(A) + 0.5 * time(B) = 2.5 sec
damage = damage(A) + 0.5 * damage(B) = 200

And finally dps = 200 / 2.5 = 80.

This final model is also very easy to see how you would usually approximate a dynamic cycle with a static one. Since half the time you cast A and half the time you cast AB this is basically equivalent to AAB. And for this static cycle we know its cast time is 5 sec with 400 damage which again gives 80 dps.

Hopefully this simple example was enough to help you work through the following examples. First we will look at AB-ABar cycle where we replace AB with MBAM on proc. We will use two states, in S0 the last ABar did not proc MB, in S1 the last ABar procced MB.

S0:
AB-ABar1 => S0 0.8 * 0.8
         => S1 1 - 0.8 * 0.8
S1:
MBAM-ABar => S0 0.8
          => S1 0.2

We solve for stationary distribution:

S0 = 0.64 * S0 + 0.8 * S1
S1 = 0.36 * S0 + 0.2 * S2
S0 + S1 = 1

S0 = 0.69
S1 = 0.31

And the values are

value = 0.69 * value(AB-ABar1) + 0.31 * value(MBAM-ABar)

If we had damage and timing information for the spells it would be simple then to compute the expected time and damage of the action in a state and to get the dps. Note that to compute mps you do exactly the same but replace damage with mana.

Next lets look at ABx3-ABar. We have to be very specific when specifying the spell selection. For this cycle if ABar procs we always follow it with MBAM. If first AB procs we cast MBAM as soon as we notice the proc (that is after second AB) and follow MBAM with ABar. Similar if second AB procs we cast MBAM-ABar after the third AB. In both cases if the ABar after MBAM procs we follow with another MBAM. If third AB procs we won't notice it until after ABar. The easiest way to express all this is with an expanded one-state model.

S0:
AB0-AB1-AB2-ABar3            => S0  0.8 * 0.8 * 0.8 * 0.8
AB0-AB1-AB2-ABar3-MBAM       => S0  0.8 * 0.8 * (1 - 0.8 * 0.8)
AB0-AB1-AB2-MBAM3-ABar       => S0  0.8 * 0.2 * 0.8
AB0-AB1-AB2-MBAM3-ABar-MBAM  => S0  0.8 * 0.2 * 0.2
AB0-AB1-MBAM2-ABar           => S0  0.2 * 0.8
AB0-AB1-MBAM2-ABar-MBAM      => S0  0.2 * 0.2

This looks a bit scary so let's try to simplify it a bit

value = value(AB0) + value(AB1) + 0.8 * value(AB2) + 0.36 * value(ABar) + 0.64 * value(ABar3) + 0.2 * value(MBAM2) + 0.16 * value(MBAM3) + 0.3024 * value(MBAM)

If we wanted to do further analysis with this we could then take into account that cast time is the same regardless of number of debuffs present and the various damage relations between spells with different number of debuffs up.

Last lets look at the AB spam with MBAM whenever it procs (with delay of one AB to notice the proc). We'll use two states to model this. State S0 is the ramp up state with 0 stacks of AB debuff. State S1 is the ramped up state with 3 stacks of AB debuff.

S0:
AB0-AB1-AB2           => S1  0.8 * 0.8 * 0.8
AB0-AB1-AB2-AB3-MBAM3 => S0  0.8 * 0.8 * 0.2
AB0-AB1-AB2-MBAM3     => S0  0.8 * 0.2
AB0-AB1-MBAM2         => S0  0.2
S1:
AB3                   => S1  0.8
AB3-AB3-MBAM3         => S0  0.2

We compute the stationary distribution:

S0 = 0.488 * S0 + 0.2 * S1
S1 = 0.512 * S0 + 0.8 * S1
S0 + S1 = 1

S0 = 0.28
S1 = 0.72

And finally the expected value:

value = 0.28 * (0.512 * value(AB0-AB1-AB2) + 0.128 * value(AB0-AB1-AB2-AB3-MBAM3) + 0.16 * value(AB0-AB1-AB2-MBAM3) + 0.2 * value(AB0-AB1-MBAM2)) + 0.72 * (0.8 * value(AB3) + 0.2 * value(AB3-AB3-MBAM3))

Or in a simpler way

value = 0.576 * value(AB3) + 0.28 * (0.512 * value(AB0-AB1-AB2-AB3-AB3-MBAM3) + 0.128 * value(AB0-AB1-AB2-AB3-MBAM3) + 0.16 * value(AB0-AB1-AB2-MBAM3) + 0.2 * value(AB0-AB1-MBAM2))

Hopefully this will be enough information to give you an idea how you can compare dynamic cycles analytically. So if you have an idea for a cool new cycle that noone else thought of before, this would be how you can start to compare it to others.

Muphrid · 12/28/08, 3:47 PM

For the physicists in the room (...Bueller?), the modeling a Markov process is conceptually similar to finding the eigenvectors and expectation value of an operator in Hilbert space.

We can start with a casting operator, $\hat B$ . Let's consider the problem of FFB spam with Hot Streak, with a set of basis states $|0\rangle , |1\rangle, |2\rangle$ , which denote 0, 1, and 2 consecutive crits (2 meaning you have the Hot Streak buff).

Thus, we have this set of operator equations:

$\begin{align} \hat B |0\rangle &= c |1\rangle + (1-c) |0\rangle \\ \hat B |1\rangle &= c |2\rangle + (1-c) |0\rangle \\ \hat B |2\rangle &= |0\rangle \end{align}$

If we crit, it increments the counter. If we have HS, we go back to the 0 state because we've cast Pyroblast.

As a simple finite-dimensional matrix, we can project $\hat B$ into the aforementioned basis.

$\begin{pmatrix} 1-c & 1-c & 1 \\ c & 0 & 0 \\ 0 & c & 0 \end{pmatrix}$

We then set about to find the eigenstates of this operator, the eigenvectors of this matrix, such that...

$\hat B \psi = \lambda \psi$

To do this, we find the characteristic polynomial by taking the determinant of the following matrix:

$\begin{pmatrix} 1-c-\lambda & 1-c & 1 \\ c & -\lambda & 0 \\ 0 & c & -\lambda \end{pmatrix}$

...and setting it equal to 0 and solving for lambda, yielding the following:

$-\lambda^3+(1-c)\lambda^2+c(1-c)\lamda +c^2 = 0$

With the help of a calculator, we can see this has 3 eigenvalues:

$\lambda = 1,c \left (-\frac{1}{2} \pm i\frac{\sqrt{3}}{2} \right )$

Taking lambda = 1, we get the following linear system:

$\begin{pmatrix} 1-c & 1-c & 1 & 1 \\ c & 0 & 0 & 1 \\ 0 & c & 0 & 1 \end{pmatrix}$

Solving this linear system yields the following equations:

$\begin{align} \psi_0 - \frac{1}{c^2} \psi_2 = 0 \\ \psi_1 - \frac{1}{c} \psi_2 = 0 \end{align}$

If we set $\psi_0 + \psi_1 = 1$ and combine these two equations, we get $\frac{1+c}{c^2} \psi_2 = 1 \implies \psi_2 = \frac{c^2}{1+c}$ , which is Roywyn's result. If, instead, we impose the normalization condition that the sum of the psi's be 1, then we get the following:

$\begin{align} \psi_0 + \psi_1 = \frac{1+c}{1+c+c^2} \\ \psi_2 = \frac{c^2}{1+c+c^2} \end{align}$

The top number represents the proportion of casts that are FFB, the bottom the proportion that are Pyros.

From here, calculating the DPS of the rotation is straightforward.

galzohar · 12/28/08, 5:07 PM

Why are you neglecting the fact you need to react to the procs, though? It shouldn't be that hard to take into account, as all you have to change is that B|2>=|3> and B|3>=0 (casting another FFB when you see the proc and only pyroblasting on the next cast). While reaction times are hard to estimate, I think it's safe to assume they're much significantly higher than 0 (or at least 0.2s, since it should be pretty impossible to react to *anything* faster than that, you could make an easy test application to see for yourself).

Or is it worth it to cancel a FFB mid-cast for pyro if it's already 0.2~0.5s in?

Sapp · 12/28/08, 5:17 PM

Galzohar, you could model that as an additional state and treat it as a Hot Streak discharge with an arbitrary .5sec extra delay, and you might find if there's a point at which interrupting a cast in progress to expend a Hot Streak is beneficial.

Muphrid · 12/28/08, 5:33 PM

In the model that you cast an 1 FFB after HS procs and then Pyro (because you were already partway through the FFB), I don't think you need to model it as an extra state. You can simply say that when you're in the 2 state you cast an FFB and then a Pyro. The only issue there is whether that FFB could increment a new counter or not. Basically what you would do, though, is introduce an expected damage operator.

$\begin{align} \hat E |0\rangle &= E_f |0\rangle \\ \hat E |1\rangle &= E_f |1\rangle \\ \hat E |2\rangle &= (E_f + E_p)|2\rangle \end{align}$

E_f and E_p being the expected damage of FFB and Pyro, respectively. You can do a similar thing with a casting time operator and, thus, derive the following for the DPS of the rotation eigenstate.

$D = \mbox{DPS} = n_f D_f + n_p D_p$

Where...

$n_f = \frac{(1+c+c^2) T_f}{(1+c+c^2) T_f + c^2 T_p}$

And...

$n_p = \frac{c^2 T_p}{(1+c+c^2) T_f + c^2 T_p}$

Similar logic should be applicable to the ABx3 -> Abar with MBAM, as that has a similar effect in play. It was because of that problem, actually, that I was thinking of this solution.

Sancus · 12/28/08, 5:36 PM

You don't really "react" to Hot Streak procs though. Your reaction time occurs at the same time as your currently casting FFB, as Hot Streak usually procs somewhere in the middle of a cast. So you then start spamming your Pyroblast button, it goes off as soon as the server accepts one of the Pyro cast requests, and then you go back to spamming FFB. It's not like you wait at the end of a cast to press your Pyro button, that'd be silly.

I am curious whether it's ever beneficial to interrupt a FFB to cast Hot Streak though. My guess is that it's not., especially since that would cost reaction time.

slackiepop · 12/28/08, 6:27 PM

what if combustion if up and you're "guaranteed" a crit on the next ffb (as well as the pyro)

completely situational and extremely unlikely, could happen though.

Muphrid · 12/28/08, 6:28 PM

Well, Combustion could indeeed be modeled as a Markov process. It would suck, because you need a counter for the number a crits that have happened, a counter for the number of casts since Combustion was activated...the matrices start getting pretty hefty.

Zaldinar · 12/28/08, 10:47 PM

For the reactivity of Hot Streak, it's a non-issue logically assuming you correctly precast the HS Pyro, since:

FFB Crit
FFB Crit
FFB Crit + HS Pyro
FFB Crit

Results in a second hotstreak buff as long as you get that Pyro off before the 3rd FFB lands. You can effectively add the damage of a HS pyro multiplied by its proc chance to any given event capable of proccing it.

My question for the Gurus of Mathematics, the way the TCoM currently handles Hot Streak is exactly that, it calculates using the (C*C)/(1+C) formula the proc chance of HS on any given cast, then adds the damage of a pyro to that spells damage multiplied by that proc chance, and the cast time of an instant modified by haste effects and multiplied by the proc chance to its cast time. The only junk assumption it makes is that all the Cs are equal, which they arent really.

If you lead into an unglyphed fireball with a scorch, you have a higher chance of having a HS present, by:

Scorch->Fireball

But then again, if its a:

Scorch->Scorch->Fireball

You also have a higher chance that scorch 2 ate the HS proc because of scorch 1. Is there a method that can account for this? Or does the chain effect end up accounting for it?

slackiepop · 12/28/08, 10:55 PM

Originally Posted by Zaldinar

For the reactivity of Hot Streak, it's a non-issue logically assuming you correctly precast the HS Pyro, since:

FFB Crit
FFB Crit
FFB Crit + HS Pyro
FFB Crit

Results in a second hotstreak buff as long as you get that Pyro off before the 3rd FFB lands. You can effectively add the damage of a HS pyro multiplied by its proc chance to any given event capable of proccing it.

normally always true for me, so the problem i had listed is as you say, a non-issue.

however, under heroism and cooldowns my FFB casts become rather short, and dependent on boss distance, i can normally have fired off another bolt (and a half) before the previous hits- thats when i might have the HS overlap.

i guess i could stand closer, but its less time to invis on wipes! i guess i should stop being awkward though, as it shouldn't happen

Muphrid · 12/28/08, 11:52 PM

Zaldinar: adjusting the model to work as you say, I got the following: c^2/(1+c) is the proportion of events in the |2> state, c/(1+c) in the |1> state, and (1-c^2)/(1+c) in the |0> state.

This yields the following DPS formula:

$D = \frac{(1+2c-c^2) T_f}{(1+2c-c^2) T_f + c T_p} D_f + \frac{c T_p}{(1+2c-c^2) T_f + c T_p} D_p$

Somebody might want to check that, though. When I just did rref on the matrix it got me a weird answer, which may mean I did the math wrong.

Edit: I'm not sure how to address the second question because I'm not clear on the rotation being used. Basically, Markov chains work because the transition from state to state only depends on the current state. If we have a mix of Scorches and Fireballs going on, though, then we need to account for that with more distinct states (because whether you cast Scorch or Fireball doesn't depend on where you are in the HS counter but on other factors).

So, I think we'd have to construct a new scenario and go from there.

Zaldinar · 12/29/08, 2:08 AM

Originally Posted by Muphrid

Zaldinar: adjusting the model to work as you say, I got the following: c^2/(1+c) is the proportion of events in the |2> state, c/(1+c) in the |1> state, and (1-c^2)/(1+c) in the |0> state.

This yields the following DPS formula:

$D = \frac{(1+2c-c^2) T_f}{(1+2c-c^2) T_f + c T_p} D_f + \frac{c T_p}{(1+2c-c^2) T_f + c T_p} D_p$

I'm confused by your formula, Muphrid. If I am assuming correctly, and Tf is Time of Fireball, and Tp is Time of Pyro, and Df and Dp are damage of each...

This is how I've been handling it thus far with the TCoM (which may be bassed ackwards):

(first latex attempt, lets see how it goes)

$D = \frac{ D_f + (C^2)/(1+C) * D_p}{T_f + (C^2)/(1+C) * T_p}$

Since we know for certain that the fireball event is going to happen, so its numbers don't need to be modified by anything, the unsure event is the Pyro, which has that theoretical (C^2)/(1+C) chance of happening, so multiply its damage potential and time by the proc chance, and add them to the fireballs values, then that gives you your average resulting damage and time from each fireball event including the proc.

This may be a case of the simple formula works in simple situations, but doesnt when it gets more complex (IE the two formulas for crit gain).

So the question for rotations is this... I hate assuming I know what the user wants to do, currently in development for the TCoM is an ability to feed in a series of spells, even if its ridiculously stupid, and see what happens. FFB->Scorch->Fireball->Scorch->Scorch->FFB->Fireball is entirely likely.

If we look at a baseline crit rate of C, the FFB if glyphed will have C+0.02, the Fireball glyphed will have C+0.05, the Scorch if specced will have C+0.06.

Lets assume everything has its best crit rate possible, you're crazy and did both glyphs to try to maximize damage from FFB DoTs, or something crazy like that.

The first FFB has a C + 0.02, but is based off of the fireball at the end of the sequence, which is C+0.05, so its proc chance is ((C+0.02) * (C+0.05)) / (1 + C + 0.02), right? Or is it C+0.05 on the bottom?

But anyway, my concern is that this assumes the two spells are in a vacuum, which is fine if all C values are the same, but since they aren't the potential exists that you have a rotation like:

Scorch->Scorch->Scorch->Fireball

The first scorch will have a lower proc rate than the second, since its lead in is the fireball, whereas the seconds lead in is a scorch. The third scorches proc rate should be lower than the second, since its more likely that the first scorch plus the second scorch would generate a proc than it is that fireball plus scorch would generate one, and reset the counter so the third scorch could have one.

Then again, I may also be overcomplicating all this in major ways.

Muphrid · 12/29/08, 3:04 AM

The formula I just posted was an attempt to model this: FFB crit -> FFB crit (HS procs) -> FFB crit + HS Pyro (because you were already partway through that 3rd FFB when HS procced), where the 3rd FFB can put the HS crit counter to 1 because Pyro lands before FFB lands.

The choice of how to write the formulas is mostly an aesthetic one. I write mine the way I do to reinforce the notion that overall DPS is a weighted sum of individual spells' DPS. They're all equivalent to each other in the sense that you can divide the numerator and denominator of each fraction by the same quantity to make it look however you like, however makes the most sense.

As far as the different rotations go, I think the only way to go about this problem is to brute-force it. This means using another variable to track where we are in the rotation. In the case of "FFB -> Scorch -> Fireball -> Scorch -> Scorch -> FFB -> Fireball," this means there are 7x3 = 21 distinct states: a different state for each place in the rotation and each distinct number of consecutive crits. To some extent, we can cheat: we already know if we've set up this problem correctly, 1 is an eigenvalue of the matrix, and we can find the corresponding eigenvector by solving a linear system...

...of 21 variables.

Then again, I'm still fairly new to this math, so perhaps there's some simplifying assumption that can be made to reduce the number of meaningful states/components.

Kavan · 12/29/08, 3:30 AM

Problem with fixed rotations like Scorch->Scorch->Scorch->Fireball is that it doesn't give you enough information to specify the model. You also need to specify what happens on hot streak. Do you start from the start of the cycle? Do you just insert the Pyro and continue the cycle where you had to interrupt?

The FB/FFB with Scorch, Living Bomb and Pyro was definitely one of the more complex cycles that I modeled in Rawr. I didn't attempt to model it exactly, instead I used an approximation model. Instead of encoding the remaining time of Scorch and Living Bomb into the state (which would dramatically increase the number of states, I can only see solving that numerically, not symbolically) I modeled the spell selection as in each spell choice you have an X chance to cast FB/FFB, Y chance to cast LB and (1-X-Y) to cast Scorch. And on hot streak followed by Pyro. Approximating it this way I was able to remain with a two-state model which wasn't too hard to solve. The values for X and Y were solved with conditions for LB and Scorch debuff durations. One nice property of setting it up in this way (at least now that LB can also proc hot streak) is that the chance of hot streak gets expressed in terms of the crit rates of FB, Sc, LB weighted by proportion in which they are cast.

Zaldinar · 12/29/08, 3:43 AM

Aah, gotcha. I was completely lost as to why it was so complicated.

As far as simplifying it, if the method can be understood, recursive functions can make the math itself easy.

For instance, the TCoM handles Fingers of Frost by recursing a function that runs a given FoF rotation (FB->FB->IL, FB->FFB->IL, etc), and at each point where another FoF proc could happen, it recurses down and adds the chance of that happening to the previous levels total.

Meaning, doing FB->FB->IL on FoF...

Step 1: FB 1 Damage is always going to happen
Step 2: FB 1 may proc FoF, if so, the FB->IL combo won't happen, start the process again and multiply the result by the proc rate of FoF, then multiply the FB->IL result (calced next) by 1 - the chance of the FoF proc.
Step 3: Add the damage of a FB->IL combo, the FB 2 has a chance of proccing FoF that won't have charges eaten by the FB->IL, so recurse again at this step, multiply the result by the proc rate of FoF.

I limited it to 5 (I think?) levels of recursion to save time, and because its silly to go any deeper than that, the difference was so low (0.0001 DPS) that it wasnt worth doing anything farther.