The 2-Cycle Theorem and You… Part 1!

Theorycraft is frequently rather dense, and often its practitioners seem to take a kind of perverse joy in making it so. The same applies to science. In my view, simplicity of language and simplicity of ideas are of utmost importance; simplicity is the best route to understanding. I love Theorycraft and the things that the community does, and I love science and the things we do there. Part of being a practitioner makes me want to communicate it, and so I come to write an article about an obscure, elegant, but specialized piece of Theorycraft called The Two Cycle Theorem. Bear with me, and you will learn why it is interesting and relevant now, even though it was invented in the heady days of 2007.

2cycle

This post is Part 1 of a 2-part series. In this post, I describe what the 2-cycle theorem does and why it’s not quite right for Healers in modern Warcraft settings. In Part 2, I’ll look in more detail at how we can change it to solve the problem and how it will Solve Spirit Gearing Forever (TM).

The theorem was originally put forward by Hamlet of Elitist Jerks sometime back in 2007. The aim was simple: describe Arcane Mages in an elegant way and come out with an interesting insight into how DPS works. Back then, the idea of a rotation didn’t seem to be fully established, so you could quite happily call it “The Two Rotation Theorem” and it would mean the same thing.

The Two Cycle Theorem says this: if the aim of a DPS player is to do the maximum damage done throughout a fight and to use up as much mana as possible, then the optimal number of different rotations to use is at most two.

How do we know that?

The result comes from a part of mathematical theory called Linear Programming, which is widely applied in the real world (e.g; if I have my facts right, it’s how large service providers assign staff schedules). I will explain it like this;

Imagine you have a bunch of variables; x1x2, x3, and so on; there are N of them in total. You might just call them x most of the time to make things simple.

Imagine that you have a function which represents how good a particular x is. This is called the Objective Function, f. You want to make this as high as possible.

Imagine that you have a set of limitations (called constraints) based around x. It might be: “the sum of x1 and x2 is always 3″; x1x2 = 3, or “the sum of x2, x5, and x3 is always less than ten”; x2x5x3 < 10. These are equalities and inequalities respectively. The number of inequalities is m, and the total number of constraints is M.

The aim is to find the combination x which has the highest value of the Objective Function f but which satisfies the constraints we talked about above; this is the “best possible way of doing things” – it is optimal.

Now there are a few standard things which one has to assume to work anything out easily:

  • f is “linear” in x.
  • The constraints are “linear” in x.
  • There are more constraints than variables, NM (or at worst NM), and at least N of the inequalities are “x1 (or x2 or x3, etc…) is not negative”.

Linearity just means that you have something looking like; constant + number times x1 + number times x2. You can’t, for example, square x1; that makes it non-linear. This is why the theory is called “linear” programming.

LinearExample

Given those assumptions, the following remarkable thing is true;

If one exists at all, the best possible value of f is at a point where m of the variables x are exactly zero.

Author’s note: Someone asked me a question based on this statement which ended in me concluding that I have made a mistake somewhere. My apologies for this, and I will correct it as soon as is practical.

So for example, if I have x1x2x3, two inequalities m = 2, and one equality, in order for f to be maximized then at least two of the co-ordinates must be zero. You might find that x1x2 = 0. This is called “The Fundamental Theorem of Linear Programming”, and is always true. The actual proof is too complicated for me to want to go into in this post*.

* – if you want to read about it, I suggest going to a library and trying to find “Numerical Recipes” by Press et al and look for Chapter 10.10. The book is remarkably lucid and written with a sense of humour, and it even shows you how to write code to solve a linear programming problem.

Hamlet’s genius stroke was to take this result and apply it to Mages; f is the total damage done in a fight, each x1x2, etc, is the amount of time you spend in a specific rotation. Assuming that you don’t spend negative time in any rotation, that means you have x1 >= 0 and so on for each x. Now, you want to also;

  • Spend all your mana.
  • Spend all your time casting.

Both of these concepts can be expressed as equalities! So you have m = N inequalities and 2 equalities. All of the equations involved are linear – we meet all the requirements for the fundamental theorem of linear programming to apply!

As a result, the maximum number of rotations you should spend any time in at all is exactly 2. If you can’t spend all your mana, it’s exactly 1. If you aren’t doing this, you are by definition playing sub-optimally. (or you were back in the earlier days of WoW…)

That is a rather elegant and surprising result. Of course, these days almost nobody in the DPS world is severely limited by their resources, with the possible exceptions of Warlocks (Burning Embers) and Hunters (Focus), but that’s not something I’m interested in exploring.

But guess what role does care about mana…

“Why, healers are mana-limited and always aim to use their total mana in one fight. Let’s try to apply the 2-cycle theorem to healers and win at WoW.”

Great idea, rhetorical person, but how?

Well, in order to demonstrate that the 2-cycle theorem works for healers, you have to show that the gameplay for healers meets the requirements of the fundamental theorem of linear programming; the ones which I showed you earlier. I’ll work through Hamlet’s assumptions to see if things match up;

1) You want to spend all of your time doing something. Of course you do – whether it’s casting a heal, or pre-casting, or regenerating mana, healers fill their time with whatever is most urgent. One big tick.

2) You want to use all your mana up. Of course you do – if you haven’t used all your mana by the end of the fight, you have too much Spirit or you’re not trying hard enough. Common knowledge. Second big tick.

3) Regardless of context, more healing = better. Of cou– wait. That is true for damage dealers, but is it true for healers? Well, no; you can overheal players and this is more often useless than useful. In contrast, it’s somewhat difficult to significantly overkill a boss.

So the problem with applying the two cycle theorem to healers is that the assumption which works fine for damage isn’t quite right to apply here. We need to come up with a good way of describing what healers do, and then apply the same fundamental theory of linear programming in order to prove the two-cycle theorem holds for healers.

So… When do we start?

We already have; if this was an academic paper, what you just read would be a very very long introduction. While it’s normal to write things with less words in academia, introductions are full of phrases that don’t make sense and far too much jargon. So what I’m trying to say is that you, dear reader, are doing science with me. Isn’t this fun!

This is how I imagine you right now.

Now, I’ve established that context is the problem for the 2-cycle theorem’s application to healers. Basically, it’s not a healer’s job to go all-out whenever they have the mana; doing that would be a very bad idea indeed. No, healing is responsive to the damage level at the time! We need to suggest some functions for f which describe what healers do – then we can start to tell whether the two cycle theorem applies.

Time to explore some funcitons!

1. Maximize Healing Done

We’ve just discussed this one; it doesn’t apply to healers. Although it’s lovely and linear as a function of the time spent in each rotation, it simply isn’t sufficient for healers. Move along!

2. Minimize the Difference Between Healing Done and Damage Taken

For this kind of function, you’re looking at the “absolute value” of the difference between the healing needed and what you’re putting out. “absolute value” means that you remove all minus signs from your calculation results, so f(x) is the same in both of the following cases;

I have to do 12 healing and I do 6 healing.

I have to do 12 healing and I do 18 healing.

This is quite close to the real thing that healers actually do, but the major problem is that it’s not linear! This isn’t entirely obvious at first, so let me draw you a picture;

You can see that the function goes down at first… and then it meets the optimal value and it goes up again! This means that the function is “discontinuous” – also a problem for Linear Programming. We have to throw this one out.

3. Minimize the Least Squares Between Healing Needed & Healing Done

Here is a function which is really obvious to a practising scientist; the “least squares” approach looks at the _square_ of the difference between the healing done and the healing needed. This is intended to avoid the discontinuous nature of problems like what we see above, which is a really nice idea.

The main problem is… well, remember earlier when I said you weren’t allowed to square anything? Yes, it’s non-linear by nature and therefore completely useless in the context of Linear Programming.

4. Minimize Difference Between Rate of Healing Incoming and Outgoing

This one is slightly different to the above; we are now talking about the “rate” of required healing, which is roughly the same as the DTPS graph you can plot on sites like WarcraftLogs. Again, this is a really accurate description of the job that healers have to do… but are your DTPS graphs ever constant? Are they ever even close to that? Hell no! Even if they were, we would again run up against the problem of either nonlinearity or discontinuity which we have seen just above in 2 and 3.

Houston, We Have A Quandray

None of these work! We can specify any kind of function which we like, and none of them will work because we are looking at the problem in a fundamentally wrong way. The thing is, in terms of time, healing is approximately smooth but not linear by any stretch of the imagination! I believe that the problem lies in the scope over which we look at the healing done – which I will explain further in the next post.

I hope you enjoyed this guide to the 2-cycle theorem and its intricacies when applied to healers. My next post will be focused on describing and addressing my view of the flaw in the assumptions we have made in this post. Until then, have fun and good theorycrafting!

Advertisements

About stoove

A physicist, researcher, and gamesman. Likes to think about the mathematics and mechanics behind all sorts of different things, and writing up the thoughts for you to read. A competent programmer, enjoys public speaking and mechanical keyboards. Has opinions which might even change from time to time.
This entry was posted in General Science. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s