[Math] The Two-Cycle Theorem of Spell Selection
 

This is an update of a result I posted a very long time ago on this forum. It has some new relevance in TBC, due to the increased number of spell-usage options for many classes (especially Mages).

After the reaction to my other thread today, I'll disclaim this one more explicitly as an abstract mathematical result. Though the analysis here does not at all take every real-world factor into account, the result is still a fundamentally correct principle of mana management.

If you're not into the math bit, you can skip the second half of "definitions" and all of "proof."

-----------

Definitions and assumptions
A cycle is a fully-defined algorithm for spell selection, specifying which spells you cast in which order, and how you react to any %-based procs. Examples are "cast Frostbolt," "cast 8 Fireballs and a Scorch, repeating," and "cast Arcane Blast twice and then Frostbolt twice, repeating, replacing the Frostbolts with an Arcane Missiles if an Arcane Blast procs a Clearcast."

A cycle has a long-term average DPS and MPS (mana usage per second). To be meaningful, a cycle should stay relatively close to its average DPS and MPS, even on short time scales.

The goal is to maximize damage done D in a set time T, with a set net mana M available.

Let a player have n cycles available, and index them by integers i. Call the DPS and MPS associated with the cycle i d_i and m_i. The player is to choose how much time t_i is spent in each cycle.

Constraints:
1) Sigma(t_i) = T. (All time is spend doing something).
2) (t dot m) = Sigma(t_i * m_i) <= M. (Cannot exceed M net mana usage).
3) each t_i >= 0.

4) The goal is to maximize D = (t dot d) = Sigma(t_i * d_i).


Theorem
All t_i, except for at most two, will be equal to 0. In other words, it is never optimal to use more than two cycles in a given fight.


Proof
Taking t_i to be a coordinates of a point t in an n-dimensional vector space, (4) specifies a function D(t) on that space, and the claim is that the maximum of the function is at a point at which at least (n-2) of the coordinates t_i are 0.

(1) above restricts us to an (n-1)-dimensional planar subspace. (2) and (3) provide further constraints that carve out the allowed region of space (worth noting that the allowed region is bounded).

The constraints given by (2) and (3) are planar. To see that (2) gives a planar boundary, recall that the set of vectors whose dot product with a fixed vector V is constant is a plane, normal to V. In total, we have (n+1) of these constraints (1 from (2) and n from (3)). The allowed region is a simplex in (n-1)-space, with each constraint contributing one of the (n+1) faces.

(4) is a linear function. Hence, its maximum will lie at a vertex of the allowed region. In (n-1)-space, the vertex of a simplex lies on (n-1) faces. In other words, equality holds for at least (n-1) of the constraints in (2) and (3).

Since (2) only provides one equality at most, equality must hold for at least (n-2) of the constraints in (3). At least (n-2) of the t_i are 0.


Results
What this means is that, when presented with an array of cycles to use at a fight of specified length, there are two possiblities:
1) All but one of the t_i are 0. This is corresponds to the case in which the mana constraint does not bind; you can cast your highest-DPS cycle the entire time, and not run out of mana. (Note: due to the presence of Arcane Blast, this is essentially never true for Mages).
2) All but two of the t_i are 0. There are precisely two cycles which, when combined, will allow you end the fight at 0 mana (a requirement of maximum efficiency) and do the best possible damage.


Many people regularly violate this principle without realizing it. For example, an Arcane/Fire Mage begins a fight using ABx2-Scx4. Halfway through the fight, he notices he hasn't used much mana, so he switches to ABx3-FBx2 (much higher MPS). When the boss reaches 20%, he still has a near-full mana bar after Evocation and some gems, so be burns into straight Arcane Blast until the boss dies. Or, a Warlock uses a high-mana cycle for half of a fight, then notices he's running low, so he cuts out some of his worst-DPM DoT's, and starts spending part of his time Lifetapping (a cycle in itself). As it turns out, both of these people would have been better off choosing exactly two of these cycles, and using them exclusively. Note that we do not know which two are correct, only that using all three is guaranteed to be suboptimal.

No kidding! ;)

They were also (provably?) better off using the three cycles than the incorrect two cycles.

There is also an optimal time split between the two optimal cycles, right? It is a sort of interesting point that planning to use more than two cycles is a fundamentally flawed approach.

There may be some sort of...time bound subcycles...that might violate this (e.g. bloodlust, AP). In which you'd use a 3rd cycle.

Hai guyz can u tell me what mod it iz that tells you the exact lenght of a fight in advance???!? It would be REEELY useful to work out cyclez and shit. Until u tell me the mod I'll be stuck reacting to the situation on the ground AND THAT MIGHT BE SUBOPTIMAL IN HINDSIGHT OH NOES.

Warlocks don't have cycles, unless they aren't using dots and don't plan on going OOM. Every spell for the most part is chosen on-the-fly due to resists, dot timers expiring at different rates, having to take advantage of hots (especially lifebloom) before they are wasted, positioning concerns, and mana recovery needs.

Technically there are a finite number of cycles which make up a set of 'warlock attack chains' but the number of combinations is such a ridiculously large number I don't think I could even describe how big the number is to people without them degenerating into a blank stare and developing a strong desire to run away screaming. Even computing a 'perfect' lag free - resist free -infinite heals attack chain into an excel spreadsheet you will not get an exactly repeating cycle in a 10 minute simulation.

And as such, warlock dps is more of a heuristic:

Stand in the right spot
Keep primary debuff (or CC) up
Keep dots up
Keep health up
Keep mana up
Keep nuke damage up

I'm also using the same theorerical framework currently, that is optimizing total damage on a fight of given length by selecting from some set of cycles. While the above was a troll the fact that we don't know exact duration of the fight is a valid concern and I've been wondering how to correctly model this.

While we don't know what the exact fight duration will be, we have some expectations. It is important to note that the variation is usually not big. In most cases a large enough variation results in wipe. As the fight progresses one can make reassessments about how long the fight will be. If we look at an arrangement of cycles used in practice we can see that changing the fight length in most cases only results in change of distribution between the two cycles and not in use of totally two different cycles. This means that as long as we're mixing the two cycles along the fight and not just using one exclusively and then switching, it is possible to achive true optimal damage even if we know the exact fight length only in hindsight.

I haven't done an analysis of what requirements there would have to be on the characteristics of the available cycles and what the maximum allowed fight length variation would be. At least for arcane mages the two cycles used are almost always max dps Arcane Blast cycle and Arcane Blast spam given all the available regen options . Obviously if we're right on the border between two cycle combinations we can get into suboptimal if our esstimates change up and down as it would force us into using 3 cycles, but I think in most cases it is possible to achieve optimum even if fight length is only known in hindsight.

EDIT: Now that I'm thinking about this isn't it true that if you're only using two cycles and you finish with 0 mana that this had to automatically be optimum combination? At least it is optimum combination of these two cycles. And if we're close to our expected fight length and using the two cycles best for the expected fight length, then almost certainly we used optimum combination as long as we finished with 0 mana.

OK, I'll hold my hand up to trolling, but it's in service of a valid point. I'm not clear what the point of this theorem or this thread is. All it seems to be is a pretty mathematical way of stating the obvious. Furthermore, it has no predictive power to tell us what cycles you want to use at what time.

Yes, in any fight there are two quantities you want to optimise: DPS and DPM. Maximise damage while not running out of mana.

Any given cycle has a fixed DPS and DPM. It is unlikely to be optimal on both counts. However, by using a different cycle with different DPS/DPM values, you can mix and match: it's a simple simultaneous equation. Of course you don't need more than two cycles - you're only trying to optimise two values.

So all this is is a more formal way of stating the single rule every mage should know.

Any mana left at the end of a fight could and should have been converted into damage

From this one rule it follows that you should select a cycle that does as much damage as possible while not running out of mana too soon, and that towards the end of the fight you should shift into maximum nuke mode to make sure you use up your remaining mana.

However, unless it's a very boring fight, then all the important decisions are the ones that operate outside this rule. Movement, special buffs/debuffs, boss dying faster or slower than expected - all the reactive stuff that actually makes you a good player as opposed to an algorithm.

It is not as simple as selecting the highest dps cycle that doesn't run out of mana and burning the rest with highest dps cycle. The optimization problem as stated by Arawethion is called a linear program for which there are a number of established algorithms that solve it.

Let me show you an example where the simple rule of thumb does not work. Example I'll use is full arcane mage on 10 min fight with all regen options available (shadow priest, judgement of wisdom, pots, raid buffs).

Let's look at 3 cycles:

Arcane Missiles: 35.6 mps / 1046.5 dps
Arcane Blast x 3 + Arcane Missiles + Scorch: 45.269 mps / 1057.5 dps
Arcane Blast spam: 254.5 mps / 1401.7 dps

In this case the optimum combination is Arcane Missiles and Arcane Blast spam, even though AB cycle has higher dps. It might be obvious in this case that this is indeed better but in other situations it is not so clear and only solving the LP gives you the right combination.

This is exactly what you are wrong about, and what he is trying to prove. This is your third cycle, You should not have any extra mana needed to burn in the end, thus is why your option is lower total dps than his, and he will ultimately outdamage you, even though you come a bit closer in the end, you wont beat him.

How does the theorem hold up given subcycles? That is, are the cycles you're theorizing by definition not subsets of each other?

You could indeed in some cases reduce the cycles used to just single spells. You get problems if spells have cooldowns. In that case you no longer have only mana and total time constraint, but additional constraints that guarantee cooldowns are observed. You can either pack spells into sequences that have no cooldowns (i.e. you can repeat one after another) or you create a linear program with more constraints. As a consequence it can be optimal to use 3 spells if at least one of them has a cooldown.

I'd love to predict exactly how many clearcasting and master of elements procs I get before the fight. I'd also love to predict exactly at what time the boss dies or how much I need to move during the encounter.

It's already mentioned in the OP that this is pure theorycraft, and it exists as such ("abstract mathematical result"). It does not account for a sloppy SP, who produces variable mp5 during a fight, and as such, you cannot with 30 seconds of the encounter gauge how much he will produce for you. Or if he dies. Theorycraft does not exist to aid you in these situations. Only experience and quick thinking will. So arguing this is rather pointless, and adds nothing to a post which is very interesting from a TC PoV.

It's quite clear, that this is indeed a very simple LP, solvable by a simplex algorithm, weighing resources, against expenditure, while maximizing on 1 variable (namely DPS). Been a long time since I did optimizing, and digging out the books is more then I'm willing to do however, but a great and interesting post.

This is an important point. Yes, a cycle shouldn't be "separable." If a cycle involves two spells, but you can in fact reorder the spells as you wish and even use them in a different ratio without affecting the DPS and MPS contributions of each, then you don't have one cycle, you have two. An example is "cast Frostbolt and then Fireball, and repeat." Or the example given in the OP--Lifetap.

I think the best way to incorporate a spell with a cooldown is to make a larger cycle reflecting how the spell is actually used (i.e. "Fireball, with Fireblast when available").


In response to some of the above, there's much more going here than simple the fact that you should end at 0 mana. There are going to be a variety of ways to hit 0 mana in any given fight, only one of which is correct.

Certainly looks like an interesting mathwork. I think you may need to add to the definition of a cycle that it must be repeatable, i.e. cycles which contain cooldown abilites must encompass 1 cooldown. For example (illustrative numbers):

Cycle A: Frostbolts 100 DPS, 1 DPM, 1 second
Cycle B: Frostbolts with Arcane Power-Type Buff 200 DPS / 1 DPM, 15 seconds, 1 minute CD
Cycle C: Frostbolts with Trinket 200 DPS / 2 DPM, 10 seconds, 1 minute CD

Currently your theorem would predict that BCAAAAA... cannot be the optimal cycle?

Now if I changed my cycles to be

Cycle D: AP whenever up: 125 DPS, 1 DPM, 1 minute length
Cycle E: Trinket whenever up: 120 DPS, 1.2 DPM, 1 minute length
Cycle F: Only Frostbolts: 100 DPS, 1 DPM, 1 second

Then the conclusion is obvious, never just sit there and cast frostbolts if your CD's are ready, i.e. never use Cycle F. Technically you are doing DEDEDEDE.

Maybe I just answered my own confusions!

Some people have mentioned "Blah blah I'd like to predict the exact etc etc" and this is not a point the OP is trying to prove. I agree with his original statement that more than 2 cycles is not optimal. In my mind (deviating slightly from the OP), an individual would not try to predict too far ahead into the fight unless you've been farming the boss and your guild does him in exactly 2min 18sec or similar poppycock. The trick is to predict far enough ahead while giving yourself options to fall back on incase the circumstances change and your conditions are not optimal. I would not try to predict every second of the fight, I would much rather take notice the flow of the fight.

Anyways, just my 2c.
And to the OP: My apologies if I misunderstood your goal, this is merely my interpretation.