Theck's MATLAB thread - MoP/5.x

Warning: Theorycraft inside.

Moderators: Fridmarr, Worldie, Aergis, theckhd

Postby theckhd » Thu Mar 22, 2012 6:18 am

FSM Simulation Details

The code now uses a "Finite-State Machine" or "FSM" implementation to calculate ability weight values. This is a pretty drastic change from our previous simulation methods, and a significant improvement in many areas.

For reference, the old analytical modeling, priority simulation, and numerical modeling methods are detailed in the appendix.

The basic idea behind a Finite-State Machine is to catalog every possible "state" of the system, along with the possible transitions between states. From that information, the code tries to determine the state distribution of the system in equilibrium. In many senses, it's very similar to a Markov chain.

There are pros and cons to each of the methods we've used, but the FSM implementation has the most pros and fewest cons by far:

Analytical Model
  • Pros
    1. very fast in MATLAB
    2. simple to debug
    3. gives exact DPS values
  • Cons
    1. limited to very simple queues
    2. not very flexible
    3. needs to be re-written every time game mechanics change
Priority Simulation + Numerical Modeling
  • Pros
    1. very flexible
    2. easy to update as game mechanics change
    3. fast once database is generated and modeled
  • Cons
    1. simulation is slow
    2. noisy even for long sim times
    3. generating the database takes ~days
    4. did I mention slow?
FSM
  • Pros
    1. very fast compared to priority sims
    2. results can be easily cached and stored for re-use
    3. gives exact DPS values
    4. very flexible
    5. easily updated when game mechanics change
  • Cons
    1. a little more complicated to code
    2. limited Matlab support for graphs (overcome by using C#)


As a simple example of how the FSM code works, let's look at a limited system of a Paladin with two spells, Crusader Strike and SotR, and a priority queue of SotR>CS. There are only two things to track in this system - the cooldown of Crusader Strike and the amount of Holy Power the Paladin has. We can represent that with two digits, one for the cooldown and one for the amount of Holy Power.

For our initial state, let's just start with no holy power and no cooldown on CS. We represent this state as:

Code: Select all
state0=[0 0]  (cooldown=0, holypower=0)


So far so good. To determine the transitions between states, we consider the priority queue. In this state, we can't cast a 3-HP SotR, so the only transition is to use CS, which takes us to one of two state:
Code: Select all
state1=[3 1] (cooldown=3, holypower=1)  (if CS hits)
state2=[3 0] (cooldown=3, holypower=0)  (if CS misses)


Since the GCD is active we can't cast anything, so the transitions out of these states are all "do nothing and wait 1.5 seconds." If we do that, we knock 1.5s off of the CS cooldown, leading to the states [1.5 1] and [1.5 0]. In both of those states, we'd again "do nothing" for another 1.5s, leading to states [0 1] and [0 0]. At that point, we again consult the queue and see that in both of those states, we'd choose to cast CS again, leading to the following new transitions (we already know what happens in [0 0]):
Code: Select all
[0 1] -> [3 2] (if CS hits)
[0 1] -> [3 1] (if CS misses)


We could draw this out, with each state as a node and each transition between states being an arrow pointing from the beginning state to the end state. If we did that, it would look a lot like a graph or a flow chart (see any of the figures in the Wikipedia article).

If we continued this process, we'd eventually reach a point where we've cataloged all possible states and transitions, at which point we'd have a complete graph of the "state space." For our simple system, we have a very small state space - it's even simpler than I've shown, because we can skip all of the possible states where the GCD blocks transitions. That narrows it down to:
Code: Select all
[0 0]  [1.5 0]
[0 1]  [1.5 1]
[0 2]  [1.5 2]
[0 3]  [1.5 3]


In other words, 8 different states. In practice, we'd be tracking more things - the cooldowns of 5-8 different spells, the duration of several buffs (Inq, Grand Crusader, Sacred Duty), internal cooldowns (Eternal Glory), and so forth. An actual state space in one of our sims can be as large as 20k-30k states. And we need to store the transitions between states, as well as the probability of each transition.

Creating the graph is just the first step, we also need to solve the system to find its equilibrium. You can think of this as figuring out what the average process flow through the graph is.

A simple process flow for our graph would look something like this, assuming every CS was successful:
Code: Select all
[0 0]->[1.5 1]->[0 1]->[1.5 2]->[0 2]->[1.5 3]->[0 0]
CS  - (empty)-  CS  - (empty)-  CS  -  SotR  -

That's just one way a sequence could go - you could also imagine an endless string of CS misses that just bounces you back and forth between [0 0] and [1.5 0], or any other combination. What we want is the weighted average of every possible process.

The old priority simulation code effectively did this by starting at one point on the graph and traveling through it many, many times. It just kept track of the current state and rolled the dice to see what the next transition was. That's pretty good, but it takes a long time and is always susceptible to statistical noise. The even older, analytical code could only do this for very limited systems in which there were very few states with well-defined transitions.

FSM implementations can be solved in a variety of ways. One can construct a transition matrix M that contains all of the transition probabilities and solve the linear system associated with it using standard linear algebra techniques. Unfortunately, when you're dealing with matrices of this size (20,000 x 20,000 elements) many of those techniques take an incredibly long time unless the matrix is particularly well-behaved. Instead, we've used an iterative technique that starts in a given state (usually one where each state has a probability of 1/N, where N is the number of states) and then calculates the change in each state from one step (essentially matrix multiplication of state vector v, v_out=M*v). It then repeats that process until the change in any state is smaller than a predefined tolerance threshold.

It turns out that the state generation and iterative solving process is quite a bit faster to do in C# than Matlab, so our implementation calls an executable file to do the state generation and crunching. We then import the results into Matlab and do our post-processing on the stat weights like we've always done.

The C# code that handles the FSM logic can be found in the RotationCalculator\Matlabadin\ folder within the trunk. You should be able to use any C# development environment to fool with it, including the free Microsoft Visual C# express 2010. If you want to compile it, you'll need a C# compiler or the Microsoft .Net framework.

Finally, to give credit where credit is due, the FSM implementation we're using wouldn't exist without all the hard work put in by Iminmmnni, who suggested we try this route. He has written and maintained the vast majority of the C# code, and been absolutely essential in getting it working and implemented.
"Theck, Bringer of Numbers and Pounding Headaches," courtesy of Grehn|Skipjack.
MATLAB 5.x, Simcraft 6.x, Call to Arms 6.0, Talent Spec & Glyph Guide 5.x, Blog: Sacred Duty
User avatar
theckhd
Moderator
 
Posts: 7957
Joined: Thu Jul 31, 2008 3:06 pm
Location: Harrisburg, PA

Postby theckhd » Thu Mar 22, 2012 6:19 am

Code

If you'd like to mess around with the code yourself, you'll either need MATLAB or a variant thereof. MATLAB is stupidly expensive itself, but there are free alternatives, including FreeMat, Octave, and Scilab. I haven't tested any of the code in these programs, but I haven't used any fancy functions or anything, so they should natively be able to run the m-files. If you run into errors, let me know and I'll see if there's anything simple I can do to help make the code more compatible with the free versions.

The files themselves are hosted on Google Code this time around to make collaboration easier. You can read and review all of the code directly through the Google Code interface, including color-coded diffs. If you want to grab the latest code, you can do so over http or with any SVN client. It's immensely easier to work with than the old system, which was me having a local copy and re-coding all the suggested changes myself.

The project name is matlabadin. Here's a bunch of useful links:

Project home page
Direct link to the trunk.
Revision hisotry
Changelog, from which you can click on any revision to see files changed, get diffs, etc.
Issue tracker
Wiki - completely empty at this point, but will (hopefully) eventually contain a page for each file describing what it does, how it works, etc.
RSS Feeds for all sorts of changes, including one that tracks every SVN commit.

The easiest way to get the whole batch is through SVN, however I hope to set up a nightly .zip repository down the line once the code has stabilized. Please contact me via PM or through the Google Code system if you'd like to help contribute to the code base in any way, even if it's just helping to keep the wiki up to date (or at this point, building it from scratch).

I hope to add a "user's guide" of sorts when I find some time, but it may be a while.
"Theck, Bringer of Numbers and Pounding Headaches," courtesy of Grehn|Skipjack.
MATLAB 5.x, Simcraft 6.x, Call to Arms 6.0, Talent Spec & Glyph Guide 5.x, Blog: Sacred Duty
User avatar
theckhd
Moderator
 
Posts: 7957
Joined: Thu Jul 31, 2008 3:06 pm
Location: Harrisburg, PA

Postby theckhd » Thu Mar 22, 2012 6:19 am

Outstanding Requests

See the Call to Arms thread.
"Theck, Bringer of Numbers and Pounding Headaches," courtesy of Grehn|Skipjack.
MATLAB 5.x, Simcraft 6.x, Call to Arms 6.0, Talent Spec & Glyph Guide 5.x, Blog: Sacred Duty
User avatar
theckhd
Moderator
 
Posts: 7957
Joined: Thu Jul 31, 2008 3:06 pm
Location: Harrisburg, PA

Re: Theck's MATLAB thread - MoP/5.x

Postby theckhd » Thu Mar 22, 2012 6:27 am

As of today, I'm opening this thread for discussion. Tlitp, Iminmmnni and I have been working hard on the code to get the basic framework in place. Things like, "how do we represent/store this information" are mostly taken care of, and the code is surprisingly readable.

Note that at this stage, the thread is focused on getting the simulations running smoothly, NOT on the results.
It's far too early in beta to determine what our optimal rotation will be at release, for example. Things can and will change during beta. The goal in these first few months of beta is making sure that we're modeling everything properly and deciding what things we'll want to know.

Questions such as "What rotation/talents/glyphs/etc should I be using at level 90" will be deleted.

Note also that this time around, I'm not going to bother modeling our mechanics below max level (90). I don't think it's worth the extra hassle for less than one month of relevance.

Here's where the community comes in. I need volunteers willing to help flesh out the code base and get it up and running. There are a number of ways that you, the dedicated forum poster, can contribute. For example:
  1. Code Monkey - someone with a basic knowledge of MATLAB who's interested/willing to help maintain the code base. Stuff like making minor corrections to different modules or writing calculation files. Prerequisites would be that you know enough not to screw up the code, and have a passing familiarity with how to do SVN checkouts/commits or are willing to learn how to do so. The project is hosted on Google Code: Project matlabadin.
  2. Error checkers - People who will look through the code and try and spot mistakes. Things like, "You missed the Seals of the Pure modifier for Seal of Awesomeness" or "I ran the code in Octave and got an error on line x of module y, here's how I fixed it." If you don't want to mess around with SVN commits but can read MATLAB code, this could be the job for you!
  3. Wikinators - Eventually I want the wiki to include a page for each module describing what it does and how it's used. At this point, I don't have a specific idea how I want to do this, and won't have time to work on it until much farther down the line. If someone else wanted to make this their pet project, it would be an immense help.
  4. Data Miner - Willing to do simple fetch/retrieve operations. Things like "Here's a list of all of the spell coefficients and base damages for our abilities at level 85, according to wowhead." Beta access isn't even necessary for this. If you're able to read MATLAB code and willing to check these sorts of things against the code and post about possible errors, that's even better.
  5. Tester - I'll need people to go in and test things in the Beta from time to time. Things like "Does Talent X affects the damage of Ability Y or not" or "What's the proc rate on Talent Z?" This would probably require beta access.

How to contribute
  1. If you are interested in helping and need project access on Google Code: Send me a PM with your Google Account e-mail address and the type of work you'd like to help out with. You can contact me either on the boards here or via theckhd@gmail.com. You need a Google Account to gain access to the project. If you contact me via e-mail, please mention your forum name so I have some clue who I'm talking to.
  2. If you are interested in helping with the code but do not need project access: Simply do whatever it is you're willing to do to help, and post your findings, observations, comments, or whatever in this thread. Also, keep an eye on this thread and the Call to Arms thread, as tlitp and I will periodically be posting requests when we need things checked or tested. I will be keeping a "master list" of unresolved issues/requests in the Call to Arms thread.

Feel free to post questions about the code as well. If you're trying to help but don't understand what a certain line of code (or even an entire module) is doing, ask! Chances are one of us will have a good answer, but who knows - you might catch us making a bad assumption or doing something in a more complicated fashion than is necessary.
"Theck, Bringer of Numbers and Pounding Headaches," courtesy of Grehn|Skipjack.
MATLAB 5.x, Simcraft 6.x, Call to Arms 6.0, Talent Spec & Glyph Guide 5.x, Blog: Sacred Duty
User avatar
theckhd
Moderator
 
Posts: 7957
Joined: Thu Jul 31, 2008 3:06 pm
Location: Harrisburg, PA

Re: Theck's MATLAB thread - MoP/5.x

Postby Iminmmnni » Wed Mar 28, 2012 9:02 pm

Some more terms for the MoP glossary:
DP - Divine Purpose (unless Holy in which case it's Divine Plea)
HA - Holy Avenger
SW - Sanctified Wrath
SH - Selfless Healer
FoL - Flash of Light (potentially in rotation if SH chosen)
Iminmmnni
 
Posts: 46
Joined: Thu Mar 24, 2011 4:41 pm
Location: Melbourne

Re: Theck's MATLAB thread - MoP/5.x

Postby Jaitee » Fri Mar 30, 2012 3:48 am

Iminmmnni wrote:Some more terms for the MoP glossary:
DP - Divine Purpose (unless Holy in which case it's Divine Plea)
HA - Holy Avenger
SW - Sanctified Wrath
SH - Selfless Healer
FoL - Flash of Light (potentially in rotation if SH chosen)


DP is already taken by divine protection! (we have to many divine abilities)
Jaitee
 
Posts: 149
Joined: Mon Apr 19, 2010 12:11 am

Re: Theck's MATLAB thread - MoP/5.x

Postby benebarba » Sun Apr 01, 2012 11:36 am

The wiki will now be getting less empty. Sloooowly.

And if you have grammar complaints, I claim engineering as a defense :P
benebarba
 
Posts: 2469
Joined: Tue Oct 19, 2010 7:30 am

Re: Theck's MATLAB thread - MoP/5.x

Postby Fetzie » Mon Apr 02, 2012 5:53 am

You could use DP, DivP, and DivPl to differentiate between Divine Protection, Divine Purpose and Divine Plea
Fetzie | Protection Paladin | EU-Kazzak
Author of the TankSpot Protection Paladin Guide
Image
Sagara wrote:You see, you need to *spread* the bun before you insert the hot dog.

bldavis wrote:we are trying to extend it as long as we can...it just never seems to last very long
User avatar
Fetzie
 
Posts: 2212
Joined: Sat Feb 07, 2009 9:43 am
Location: Karlsruhe, Germany

Re: Theck's MATLAB thread - MoP/5.x

Postby theckhd » Mon Apr 02, 2012 6:21 am

Pyrea wrote:You could use DP, DivP, and DivPl to differentiate between Divine Protection, Divine Purpose and Divine Plea

We don't have Divine Plea anymore in MoP. DP should probably be clear from context, given that you can't "talent" Divine Protection, nor would you put it as a conditional in a rotation. If a situation arises where it's not clear form the context, DivPurp will suffice.
"Theck, Bringer of Numbers and Pounding Headaches," courtesy of Grehn|Skipjack.
MATLAB 5.x, Simcraft 6.x, Call to Arms 6.0, Talent Spec & Glyph Guide 5.x, Blog: Sacred Duty
User avatar
theckhd
Moderator
 
Posts: 7957
Joined: Thu Jul 31, 2008 3:06 pm
Location: Harrisburg, PA

Re: Theck's MATLAB thread - MoP/5.x

Postby xstratax » Thu May 10, 2012 3:27 pm

Ive seen AM used in other threads, but dont see a reference in the glossary. Ive tried searching for it, but without knowing the meaning its been fruitless (plus the search is limited to 4+ character strings only). Im not sure if its a Prot thing, but if so I can only assume it would be good to add it here.
xstratax
Maintankadonor
 
Posts: 118
Joined: Fri Aug 14, 2009 1:18 pm

Re: Theck's MATLAB thread - MoP/5.x

Postby Worldie » Thu May 10, 2012 3:33 pm

AM means Active Mitigation usually as far as i know.
theckhd wrote:Fuck no, we've seen what you do to guilds. Just imagine what you could do to an entire country. Just visiting the US might be enough to make the southern states try to secede again.

halabar wrote:Noo.. you don't realize the problem. Worldie was to negative guild breaking energy like Bolvar is to the Scourge. If Worldie is removed, than someone must pick up that mantle, otherwise that negative guild breaking energy will run rampant, destroying all the servers.
User avatar
Worldie
Global Mod
 
Posts: 13435
Joined: Sun Sep 02, 2007 1:49 pm
Location: Italy

Re: Theck's MATLAB thread - MoP/5.x

Postby benebarba » Thu May 10, 2012 3:46 pm

Worldie wrote:AM means Active Mitigation usually as far as i know.

Yeah, now that it's become a buzzword for tanks, it's getting used a lot.
benebarba
 
Posts: 2469
Joined: Tue Oct 19, 2010 7:30 am

Re: Theck's MATLAB thread - MoP/5.x

Postby theckhd » Thu May 10, 2012 5:44 pm

xstratax wrote:Ive seen AM used in other threads, but dont see a reference in the glossary. Ive tried searching for it, but without knowing the meaning its been fruitless (plus the search is limited to 4+ character strings only). Im not sure if its a Prot thing, but if so I can only assume it would be good to add it here.

Seems reasonable, nice catch.
"Theck, Bringer of Numbers and Pounding Headaches," courtesy of Grehn|Skipjack.
MATLAB 5.x, Simcraft 6.x, Call to Arms 6.0, Talent Spec & Glyph Guide 5.x, Blog: Sacred Duty
User avatar
theckhd
Moderator
 
Posts: 7957
Joined: Thu Jul 31, 2008 3:06 pm
Location: Harrisburg, PA

Re: Theck's MATLAB thread - MoP/5.x

Postby benebarba » Fri May 11, 2012 7:06 am

I'll go ahead and mirror the glossary here in the matlabadin documentation as well, since many of the same acronyms are used. It certainly couldn't hurt.
benebarba
 
Posts: 2469
Joined: Tue Oct 19, 2010 7:30 am

Re: Theck's MATLAB thread - MoP/5.x

Postby theckhd » Mon Aug 27, 2012 5:12 pm

We have gotten to the point where the majority of the code is working properly (we think). I'll be posting a bunch of data in the next few days for people to peruse and sanity-check. Some things aren't yet finished (primarily dynamic effects, like enchants).
"Theck, Bringer of Numbers and Pounding Headaches," courtesy of Grehn|Skipjack.
MATLAB 5.x, Simcraft 6.x, Call to Arms 6.0, Talent Spec & Glyph Guide 5.x, Blog: Sacred Duty
User avatar
theckhd
Moderator
 
Posts: 7957
Joined: Thu Jul 31, 2008 3:06 pm
Location: Harrisburg, PA

PreviousNext

Return to Advanced Theorycraft and Calculations

Who is online

Users browsing this forum: Petrus and 1 guest

Who is online

In total there are 2 users online :: 1 registered, 0 hidden and 1 guest (based on users active over the past 5 minutes)
Most users ever online was 380 on Tue Oct 14, 2008 6:28 pm

Users browsing this forum: Petrus and 1 guest