Gear Optimization Challenges

Last time I talked about the difference between simulation and models for dps computation.  Today I am going to talk about gear optimization and the associated challenges.

Gear optimization is interesting because it belongs to a class of problems called NP-Complete which are a class of problems that we do not yet have a way to solve in a reasonable time* and it may simply be not be solvable in a reasonable time.  What makes these problems hard is that we do not have a way to guarantee an optimal solution without checking all possible solutions.

To demonstrate this consider just the question of reforging and leave gems and enchants alone.  For a given (non-trinket) item there are 6 possible reforges, 2 stats on the item are each reforgable to one of 3 other stats.  Setting aside trinkets there are 14 pieces to a gear set.  That means there are 6^14 possible combinations or 78 billion possibilities.  If you could check 1 million possibilities per second it would take just under 22 minutes to check every combination.

With some care we can shrink this space somewhat by applying some logic, for instance we should never reforge something to a lower EP value stat unless it is a capped stat.  Best case scenario (every item with our two most valuable non-capped stats, haste, mastery for assassination or combat) this lowers our total problem space to 4^14, which would only take about 4 seconds which isn’t too bad.

Realistically we’re probably looking at around 5-5.2 possible reforges per item and 1 million possibilities per second is probably a bit optimistic for most people’s home computer so we’re probably looking at around 5-10 minutes which doesn’t seem bad until you realize that if you are looking at a variety of gear configurations you need to do this 5-10 minute reforge each time.

You may be wondering, if this takes so long to solve how do the various optimizers work as fast as they do?  The answer is they don’t attempt to give you an optimal solution.  These problems in the class NP-Complete have been a thorn in the side of computer scientists for a long time and large set of useful questions such as path finding (think Google Maps) fall into this class so there are lots of approximate solutions.  None of these solutions can guarantee optimality but they can get “good enough.”  The folks at AMR claim that their optimization algorithm (which considers more than just reforges) gets within 0.1% of optimal.

Talking about all the various approaches to approximate optimization is well beyond the scope of this post but as an example one approach would be a greedy cap based solution.  In this approach you would greedily start by attempting to cap all capped stats in order of highest to lowest values.  Once the capped stats were handled you’d simply reforge the remaining items from lowest to highest value stat.  This approach probably wouldn’t be that good and would likely result in some pretty substantial over or under capping of stats but it should be a decent example of how an approximate algorithm would function.

So optimization is non-trivial, but it gets harder still.  As pretty much everyone who has used ShadowCraft this expansion has seen EP values do not stay fixed across the stat space of single gear set.  That is, a set of reforges may change the EP values such that the set of reforges is no longer optimal.  As everyone who has used ShadowCraft knows this can cause some substantial problems for static value optimizers and will cause the optimizer to ring back and forth between two points when the suspected optimal is in between.

This is a difficult problem and one that we as a theorycrafting community are still grappling with.  The obvious solution is to make the optimizer aware of these shifts.  AMR recently unveiled an improved EP value system that handles caps of stats other than hit and expertise for certain classes.  The system, while a clear improvement over the old system it still has some limitations.  It works quite well for explicit haste caps like most casters have but for something like balanced haste and mastery like assassination rogues currently favor it doesn’t work so well.

Admittedly this is hard problem, partially because it is badly under-defined.  What does it mean for stats to be balanced or  more generally conform to some arbitrary ratio?  If optimal is exactly on the ratio how much EP fall off is it to be 1 off?  These answers are not obvious nor are they static, changes in gear will almost certainly change how your gear responds to ratios.  This really gets to the heart of a broader problem with static gear optimizers.  Static gear optimizers require relationships between current stat amounts and EP values and these may be gear specific themselves or at least not readily generalizable.

The obvious solution is an integrated calculation and optimization system like ShadowCraft however doing this in a performance conscious manner is difficult.  ShadowCraft uses a static optimizer partially because of performance issues, it would, in theory be feasible to create an iterative reforger that would recompute EP values after each reforger.  It would essentially do a local search, similar to the systems used by other optimizers I suspect, for optimal recalculating as it went.  In this approach a system would make a change or set of changes toward a higher dps point and then recompute EP values repeating until a static point was found.

The big issue with an iterative optimzier is performance.  When talking about ShadowCraft  server limitations are an issue.  Since 5.2 the ShadowCraft engine has gone down more often than anyone would like partially because of the increasing complexity of the model.  Allowing someone to automatically run the model many times in short succession would likely increase strain on the server even more.  I don’t pretend to have a good solution to this gear optimization problem but if I do come up with something I’ll post it here.

I was planning to talk about a couple other things, the difficulty of upgrade recommendation but this is even longer than yesterday’s post so that will have to wait for another time.

*Reasonable time here means polynomial time or less.  A more detailed discussion of computational complexity theory is beyond this post, the linked wikipedia articles have more information if you are curious.

Simulations and Models

For those who haven’t clicked on my about page, my day job is a PhD student in electrical engineering.  When doing a PhD one of the things you start thinking about a lot are tools, what the most appropriate tool to measure something with, what are the trade offs to hacking functionality into one tool vs. the other.  With that in mind, and because questions about tools come up very often, this inaugural post will be about theorycrafting tools.  Specifically SimCraft, ShadowCraft and Ask Mr. Robot.

SimCraft, ShadowCraft and AMR are interesting because they are all different kinds of tools, SimCraft is a simulator, ShadowCraft is a model and AMR is an optimizer.  To begin with lets draw a distinction between simulation and model because they are the most directly comparable.

A simulation is focused on events, it moves forward through time just like the phenomenon it is simulating.  If the player needs to make a decision at this point in time a simulation makes a decision.  If there is randomness, does this ability proc crit for instance, then the simulation generates a random number.

A model by contrast is focused on mathematical relationships.  Where a simulation says a mutilate generates 2 or 3 cps by generating its own random number a model says, mutilate generates 2.3 cps (assuming 30% crit).  A model is a set of mathematical relationships that compute something about some phenomenon.

To put things in more concrete terms if I wanted to simulate how often I get 3 heads from 3 coin flips I would write a program that generated three randoms numbers, 1 or 2, a few thousand times and average up how many times I got 3 1s.  A model would simply say, the chance of 1 head is ½ so the chance of 3 is (1/2)^3 or ⅛.

Now that we understand the difference between a model and simulation the next, and obvious, question is, which is better?  The answer as is often the case is, it depends on what you want to do.

The coin toss example above shows the two weaknesses of simulations, speed and precision.  Since a simulation simulates the actual RNG the character experiences it is susceptible to RNG.  To minimize the effect of RNG you have to do a lot of simulations, for example SimCraft recommends 10K iterations for low error EP value calculations.  Simulations can be very precise given a long time or they can be quite fast but with limited guaranteed precision.

On the upside simulations are easier to write and debug.*  If a phenomenon can be described algorithmically writing a simulation can be pretty easy.  Simulations can also be very adaptable, questions about rotation issues are very well handled by simulation because simulations map close to directly to player experience.  The last thing simulations can do very well is reason about variability.  This is the least obvious advantage but a very important one, consistency is important in high end raiding, only meeting a dps check when the stars align isn’t a sustainable solution.  Obviously there will be some dps variance no matter what but being able to see the range of expected dps given correct play is very valuable.

Looking at the coin example you can see the advantage of a model, a model is deterministic, it will give the same result every time, and a model has a constant execution time, a single run gives you maximum available precision.  The downside is models are hard to write, most models make simplifying assumptions to make the model easier to write however these simplifying assumptions can mask potentially relevant behaviors.  For example the cata combat model in ShadowCraft used a time average of energy, the energy regen of AR was distributed over the entire fight time.  In practice this was incorrect and made the combat unable to properly reason about energy capping.  For many complex physical phenomenons it simply isn’t feasible to write a model because of the complexity of the phenomenon.

Another consequence of models being hard to write is models work in rotational abstractions that don’t necessarily map to how players play the game.  Whereas a simulation can allow you to simulate arbitrary rotations and encounter types models can generally only support a small number of rotation options and rotation changes may require substantial changes to a model.  Similarly SimCraft has support for more complex encounter types while ShadowCraft probably never will.

The goal of a model is to make simplifying assumptions minimally impactful to the overall accuracy.  It may be the case that you miss certain 2nd or 3rd order effects but if those effects are small enough it shouldn’t impact accuracy too much.  Of course it is hard with just a model to determine if those effects are sufficiently small.

To summarize, models are best used for rapid iteration on gear sets or gear optimization and simulations are best for exploring new rotations and effects that models do not currently support.  We in the rogue community are lucky to have both a model and a simulation tool available to us, this gives us the best of both worlds.  SimCraft can help us determine what effects are small enough to discount, drive exploration into new rotations and help verify accuracy.  ShadowCraft meanwhile can benefit from this exploration and create a more accurate tool for rapid gear iteration.

I was planning on talking about optimization and the challenges that poses but this post is long enough already so that will have to wait till next time.  Tomorrow, Ask Mr. Robot, WoW optimization tools and their weaknesses and limitations.

*The fact that simulations are easy to write does not take away from the work of the folks who work on SimCraft.  A trivial simulation is easy to write but writing a simulation with good performance can be very difficult.  The tricks and techniques for writing an efficient simulation are beyond the scope of this post but suffice it to say they can make things very complex.