## Monday, July 5, 2010

### Maximizing Damage

Today we're going to learn how to maximize damage. I developed this theory first with respect to World of Warcraft, but the assumptions required are surprisingly general, and apply to all sorts of games. This will require math. College level math. If that's not your cup o' tea, then thank you, please come back another time. Or read over it and hope that you can pick through the details. I'm also going to be going through the simplest version of the calculation, with the simplest assumptions to show how it works. You can add more assumptions to make it more complicated and get better results if you'd like. Anyway, on to the problem!

Suppose you're playing a RPG. You have the option of selling your Sandals of Water Skiing and acquiring some War Boots of Goose Kicking. Is the deal worth it? Which item will allow your character to deal more damage, survive more hits or what have you? Well, I'm just going to assume you want to deal more damage, that you'll worry about defenses and peripherals (the sandals let you freaking water ski!) elsewhere. So how do we measure how much damage you do? Well, let's take a look at a fight. Or better yet, one attack with your weapon.

You swing your sword, what happens? Well, it hits, or it misses. He might dodge, block, parry, evade or what have you. And, if you're lucky, you might get a critical hit. Now, how much damage do you do with each of those outcomes? Well, if you hit, you'll do H damage, let's say. If you miss, you'll do M damage, and if you crit, you'll do C damage. Got that? This part's important: We can figure out how much damage you do on average by multiplying the probability of a particular swing type by the amount of damage it does:

1) Avg. Damage = Hh+Mm+Dd+Bb+Pp+Ee+Cc

Where the upper case letter is the amount of damage and the lower case letter is the probability of getting that outcome. It's also important to note that the probabilities are stochastic, that is, they add up to one. Or rather, that there's a 100% chance of getting one of those outcomes, and that there aren't any other possible outcomes. If we swing, one of those things will happen. Mathematically:

2) h+m+d+b+p+e+c=1

Ok? Now, I said I was going to keep this simple, so we're going to cut the options down to two possibilities, that you hit, and that you get a critical hit. Rewriting those equations (respectively) we get:

3) Avg. Damage = Hh+Cc

4) 1=h+c

Ok? See, this is the problem with physics. We get a problem, and then we have to assume away all sorts of stuff to make it solvable, and we end up with massless frictionless pulleys dropping weights in a vacuum, and it doesn't correspond with the real world at all. Or real video game in this case. But yeah, I fully intend to add this stuff back in at the end, so bear with the simple version for a bit. Anyways, we're gonna want to stick those two equations together. Solving equation 4 for h we get

5) Avg. Damage = H(1-c)+Cc

Which makes sense, as the probability of getting a hit is exactly the probability of not getting a crit, since those are the only two options we allow. The next question we have to ask is "What happens when we get a crit?" Here I'm going back to explaining in terms of World of Warcraft, since the mechanic in WoW is extraordinarily simple: A crit deals twice as much damage as a hit. Simply:

6) C = 2H

Substituting that back into equation 5, we get

7) Avg. Damage = H(1-c)+2Hc

Simplifying:

8) Avg. Damage = H(1+c)

And that's your average damage, in all it's glory. If you know your average hit damage, and your chance of getting a critical hit you can figure this out. Well, actually it's your average damage per swing. If we divide your average damage by your attack speed (how many swings you make in a second) we get your damage per second (DPS)

9) DPS = H(1+C)/attack speed = A(1+c)

Where I define "A" as your hit damage divided by your attack speed. Same basic equation, but now it also accounts for weapon speed. I'm going to assume your attack speed remains constant, but later I'll also discuss changes to your attack speed.

Here's the tricky part. We need to maximize this equation. I mean, I can see that increasing your basic damage (H) increases your DPS, and increasing your crit chance (c) increases your DPS, but which one increases it faster? Well, multivariable calculus gives us a function for maximizing functions of more than one varaible. We take the gradient:

10) grad DPS = <1+c, A>

Ok? That gives us a vector, which points in the direction that'll increase the function most. Or decrease; the canny reader will point out that it's possible that it'll show the direction the function will decrease the quickest, but in this case it's definitely increase. You can check it yourself. Basically, the vector points in the direction of increasing c and A, and we already stated that as they increase, so does your damage. Anyways, let's move along.

Now that I have the gradient vector, well, what am I supposed to do with it? That's an excellent question, I'm glad you asked. Well, the gradient points in the direction of the maximum increase in damage. So if you boost your crit chance and your damage in precisely the ratio that the gradient dictates, you'll be boosting your total damage the most with the same amount of stat points. If you're getting stats along a different vector, then we can compare the relative efficiency of the vectors by seeing how closely they align with the gradient.

Ok, so where are we getting these other vectors? We get them from items. Items? Yeah, at the start I mentioned that I was trying to compare items; this is where it comes in. If I've got some boots that give 42 attack power and 1% crit, and I've got some other boots that give 70 attack power, which one is better? Well, you can render them down into item vectors, as long as you're talking in the same units as in equation 9, that is A in damage per second and c in crit%. In this case we have to remember that

11) 1 dps = 14 attack power

So we can set up two item vectors like this:

12) Item 1 = <3 , .01>

13) Item 2 = <6 , 0 >

There's a mathematical quibble here; can we treat items as vectors? Yes, yes we can. So long as we stay away from some not-gonna-happen ranges of data we're fine. (negative attack power or crit chances, over 100% crit chance, sticking more than one item in the same slot, that sort of thing.)

But on to the real problem. How do we compare item vectors to the gradient vector? We take the dot product. I'm gonna switch in bold letters to represent the contribution from the items, so A is the dps the item gives you, and c is the item's bonus to crit chance.

14) Item (dot) grad dps = A(1+c) + cA

If you sum that up, you get a number. Take that number and compare it against the number you get from other items. The largest number wins; using that item most increases your dps. If you keep doing the calculation you can select your items to maximize your dps. Neat, huh?

Ok, now step back a bit. What else does this apply to? Buffs? If you're trying to decide between blessing of might and blessing of kings then you can work them like items, make vectors and add it up. Sure it's probably going to be kings but it'd be nice to be sure. Ok, so you can also measure buffs. What about talents? Some basic ones yeah; + attack power or + crit chance talents, although odds are you'll want to get both. More? Skills, we can evaluate the efficacy of skills. All those numbers compare "white" damage, that is the damage you do when you automatically attack in each fight. "Yellow" damage from skills can be calculated much the same way.

What about more complicated stuff? Talents that give you benefits from increased critical hits, that sort of thing. Yeah, it can be done. It's a lot more complicated, it's manageable though.

Now think for a minute about the original assumptions; that there are only a couple possible outcomes of a swing, hits, crits, misses and so forth; that we can calculate the amount of damage in a critical hit, and that we can vary either damage or critical hit chance. Those are very general conditions, they can be applied to a vast range of potential games. Or other calculations in this game; you can figure out damage mitigation for tanks or rage generation or such.

Ok, there's the calculation and the big picture. I'm going to go through it quickly with miss chance and changing your attack speed.

Now, in equation 1) up there I posted factors for other outcomes to the swing; dodges, blocks, parrys, etc. Here I'm going to combine them generally into a "miss" factor

15) Avg. Damage = hH + cC + mM

And again those are the only possible outcomes.

16) 1 = h + c + m

Combining those two:

17) Avg. Damage = (1-c-m)H+cC+mM

Ok? Again C=2H, but this time we also know that M=0, the definition of a miss being that it deals no damage. Substituting these in

18) avg. Damage = (1-c-m)H + 2cH+0 = (1+c-m)H

Ok? We're also going to deal with the time factor, which we can't hide with a change of variable. Giving "T" as your attack speed:

19) dps = (1+c-m)H/T

Ok/ Now we take the gradient again

20) grad dps= < (1+c-m)/T, H/T, -H/T, -(1+c-m)H/(T^2) >

Four dimensional vector now since we're dealing with four variables. It's a little harder to read, what with the negative numbers. The vector is in order of Since you're attempting to decrease your miss chance and attack speed, so an item that gave you +1% hit would read like -1% miss. Here, let me make an item vector for you, with 1% hit and 3% faster attack speed

21) <1, .01, -.01, -.03>

See? The negatives will multiply by negatives and you'll get a larger dot product that way. So yeah, here you take the dot product again.

22) H(1+c-m)/T + cH/T -mH/T - T(1+c-m)H/(T^2)