Wednesday, October 20, 2010

Combat Modelling

I am working on building a combat modelling program in Excel for the WOW expansion due out in December.  The only really tricky part about building such a program is figuring out how to model exactly what happens in combat and let the user know what sequences of abilities will be the most effective.  The hardest part about doing this by far is the random elements that are sometimes involved.  For example, in the last expansion I had to model an effect where 40% of the time a weapon swing would cause an ability to be usable right away.  I ended up modelling it by having the program keep track of a variable that started at 1 and incremented each time it was checked and when it got to 21 it was reset to 1.  I preset 8 different numbers (1,2,4,5,8,9,13,15) that would trigger a 'yes' result and otherwise the program assumed it was a 'no'.  Doing this allowed me to make sure that over time 8/20 or 40% of the results would be yes, and this system worked out well.  It wasn't random so it would generate the exact same results each time for any user but it gave results that were extremely close to actual game values.

The trick this time is I have % chances for specific things to occur that are not fixed.  For example, my Hand of Light (HoL) ability has a chance to go off on each attack but the chance of it going off starts at 8% and goes up with the gear I wear.  I need a modelling system that has the ability to model any particular % chance including decimal places and I want that system to also produce identical results each time it is run.  Unfortunately the only way I know how to do this is to make the program run the simulation for huge time periods so that the really large numbers can smooth out the data; otherwise the results will be different on each run and will ultimately make it very difficult to draw useful conclusions.  As I understand it I can control the seed that the program uses to generate random numbers but if that seed happens to be really wonky in some way my data would still be useless.

The only kludge I have been able to think up is to have a preset start sequence and then have the program check to see if the overall percentage so far is over/under the theoretical one and pick the next result based on that.  For example, I just assign the program to have the ability go off on the 4th, 14th and 24th try of the first 30.  On the 31st try we know that the current result is 3/30 or 10%, so if the theoretical chance is over 10% it goes off on the 31st try, and if the theoretical chance is below 10% then it does not.  Either way it follows up by calculating either 3/31 or 4/31, checking against the theoretical chance and going again.  This would at least give me identical results each run but it has big problems with plateaus.  If I run a test with 300 attacks I might raise the chance from 9.99% to 10.01% and see a significant gain because it made that 300th result change in value, whereas going from 10.01% to 10.03% no difference at all will be recorded.  I suppose I really have no way to avoid plateaus without using *immense* simulations so this may well be the best way to make this work.  If anyone else has any suggestions please feel free to let me know though.

19 comments:

  1. I like simulations and you don't have to run them for a really absurd amount of time to get meaningful results. That being said, the advantage of using formula based models is that your spreadsheet updates as you go, rather than having to wait for the simulation to run.

    In one way getting plateaus for mastery makes a lot of sense, since that's how mastery actually works. On the other hand, if you want stat weightings it doesn't do you much good.

    Historically there have been a few classes that have had weird problems with stats, where a stat would be worth a lot up to a certain point, then be worth almost nothing, and sometimes then be worth a lot again later. If you want a single number out of that, you could calculate the value you get out of the stat for having an awful lot of it (say, reaching the last plateau you can reasonably reach) and then just value every point along the way at a constant rate (though obviously if you have a stat that works like that you should actually know the numbers you need).

    You could do the same thing with mastery. Get the value by modelling with both 0 and some theoretical maximum and just take the average as the value. Then just leave the plateaus in the dps out for the sheet since they would be an accurate representation of how mastery really works.

    ReplyDelete
  2. Actually you are wrong there. Paladins have done extensive testing on the beta and mastery does not have plateaus and does not operate in 1% chunks. They confirmed that mastery has full effect with any amount of it even if it does not raise your 'mastery' stat on your sheet by 1.

    For paladins, and most melee in general I expect, hit and expertise will be capped at all times and crit/AP/Str/Agil should all scale in some reasonable, nonplateaued fashion. Unfortunately haste and mastery scale in completely crazy ways for paladins based on procs, GCD usage and other things so their value is going to be all over the map.

    ReplyDelete
  3. Wendy and I talked about my problem here and came up with a pretty good solution. I will just have Excel randomly put the numbers 1 - 1000 in column A on one of my spreadsheet pages and then use those as my random number generator. I can just start at row 1 each time and get pretty decent 'random' results that will be repeatable.

    ReplyDelete
  4. I'm surprised to hear that about mastery, I guess it's pretty easy for me to check for myself if I'm incredulous (since discipline priest mastery can be tested with one cast of PW:S).

    I can see how haste and mastery are going to do insane things for ret paladins. I especially like that haste simultaneously gives you more mastery procs and fewer opportunities to fit mastery proc use into your rotation (or, to look at the other side, more mastery gives you less ability to take advantage of haste on crusader strikes). Sounds like it might be dual-wield windfury cooldown level of complexity to create a precise formula.

    ReplyDelete
  5. Maybe I don't understand what you're using the random numbers for but if every number is distinct what is it accomplishing?

    ReplyDelete
  6. @Sthenno

    It isn't very complicated to create a formula, but rather nearly impossible since weapon speed, haste, priority sequence, mastery and buffs all factor in. I can't make a formula, I just have to make a simulator and get some rough values.

    @Ziggyny

    I want to check on each autoattack if mastery procced or not. My base chance to proc is 8% and goes up from there with mastery, most likely not exceeding 20%. The idea is to convert those 1-1000 numbers into a probability by dividing by 1000. Example:

    Get random number, result is 452. Divide by 1000 to get 0.452 Compare that to my mastery of .08, and since .452 is > .08 mastery does not proc. If I got 18 as my random number then it would proc since .018 < .08. Make sense?

    ReplyDelete
  7. Yes, though if you're using even close to 1000 checks it's not actually going to be very random. Assuming you're ever GCD locked you'd want a true random distribution to cause those moments to show up because their existance - rare though they may be - will decrease the value of mastery. This sort of thing will show up in the long run but with your system will either show up too often or not often enough because of the specific seeding you've fixed on.

    I understand you want the sheet to be completely deterministic but since combat itself isn't completely deterministic you're not going to give absolutely correct valuations with your current plan. Maybe close enough, but not absolutely correct.

    To get there I think you'd have to forgo the deterministic aspect and just accept the need to run a few simulations. If speed for the user is a concern you could pre-run the simulations for every feasible combination and build a look-up table of the stat values at each combination of mastery/haste/whatever else.

    ReplyDelete
  8. By comparing it to dual-wield windfury I was meaning to imply that it was essentially impossible to find a formula.

    ReplyDelete
  9. Sthenno: We agree then.

    Ziggyny: I don't see how that is. Given that my procs will be pretty randomly scattered througout my 1000 checks I will be getting them in all kinds of random places throughout my rotation. I will absolutely be GCD locked for 90% of my time at least so mastery is going to be pushing back other finishers and overwriting filler attacks most of the time. Most people seem to think mastery is going to be hopeless trash but I figure it will only be my worst stats, something on the order of 1/6 of a Strength.

    ReplyDelete
  10. Yes, you will, but because getting a proc reduces the chance of getting a future proc you're not going to see the same clumps of procs and non-procs that you would in a truly random system.

    If you have 1000 numbers and only use 10 of them then this effect isn't going to really show up, but if you have 1000 numbers and use all of them you absolutely will. The last few will be completely determined by the previous checks and be nowhere near completely random.

    It's exactly like using a deck of dice instead of actual dice. Deck of dice in the long, long run approximates actual dice but in the short run it comes nowhere close to doing so. You just can't get lucky or unlucky with a deck of dice the same way you can with dice. If you like this mechanic or not is a matter of opinion and in a game like FMB you can make a choice one way or the other and be happy with it.

    Here you can't be, because you're using a deck of dice to try to model dice and you're not going to see the same natural clumps that actually occur in the game. The game isn't going to change the way it works because your spreadsheet uses deck of dice instead of dice and the differences between the two are going to negatively impact your numbers.


    You say you're GCD locked, so I'd imagine getting 4 procs in a row would be really bad. Does your random set of only 1000 numbers have the right distribution of 4 procs for every mastery number? If not then you're deviating from the actual value of mastery. If you have too many then you're making mastery look worse than it is. If you have too few then you're making it look better than it is.

    If it was just a proc that did damage immediately then a simple way of modeling it would really be close enough. But since the proc needs a GCD to use and is therefore going to change when you use abilities and could get wasted due to a second proc before you use the first one then you need a more accurate picture of the timing of the procs. You need the right clumping distribution if you want to get absolutely correct valuations.

    ReplyDelete
  11. I don't see how that is. If I took a truly random set of data I would obviously end up with more than the expected or less than the expected number of procs most of the time so that data is going to generate bad results. If the set of 1000 data points happens to have them distributed extremely evenly with little clumping I will also end up with bad results. However, if the 1000 data points have some reasonable clumping that vaguely resembles randomness they are going to generate extremely good data. The only way that the 1000 pregenerated points aren't going to make things better is if they randomly have really 'bad' clumping which there is no reason to expect they will. They are going to be entered onto the sheet randomly and obviously I am going to check them personally to make sure things aren't completely out of whack so the distribution should be quite a good approximation of random.

    ReplyDelete
  12. Yes, any given set of 1000 data points (random or not) is going to be flawed at some mastery level. That's why I initially said you need to forgo the need for determinism and actually run the number of simulations needed to smooth all this out.

    If something is supposed to happen .05% of the time then your method has no way to accurately model how often it happens. (And to show this isn't outside the realm of plausibility getting 3 8% procs in a row is a .0512% chance.) If it shows up at all in your list of 1000 numbers then it showed up too often. If it never shows up then it didn't show up enough.

    With a 3 second autoattack this situation will come up every 98 minutes. Maybe you don't care if you're throwing away a proc every hour and a half in your simulation (either by discounting an extra proc you should be counting or by counting an extra proc you should be ignoring) but it's not going to be right.

    ReplyDelete
  13. The thing is, that whatever data set you come up with, it will "reasonably resemble" randomness exactly as well as the numbers 1 to 1000 in order will. That's what randomness means.

    I'm not saying your method won't produce the results that you want, it might do just what you want. You are going for a trade-off between repeatability and actually being an accurate model of the events you want to model. I think in the end that it is a trade-off between modelling everything else well or modelling mastery well.

    Imagine, for example, you were modelling crit this was instead of modelling mastery this way. Obviously you would end up with a skewed result, either giving a bunch of crits on Seal of Truth ticks or a bunch of crits on Templar's Verdicts. This would either inflate or deflate your damage, but it would inflate it or deflate it the same way every time. So if you changed your haste or mastery value then you'd get a good picture of how much that improved things overall.

    But if you increased the crit value by 1% using that model then which additional 1% of your attacks will crit is predetermined. Again, it wlll be either lower damage attacks or higher damage attacks. It will show crit scaling below or above what it should be.

    The exact same thing will happen with mastery. As Ziggyny points out, if something is supposed to happen .05% of the time then once it too much and nonce is too few. But there will be some amount of mastery rating that will change the model from 0 to 1 occurrences of such an event. Whether or not a particular increase in mastery causes an event like that will skew the value of that amount of mastery up or down.

    Anyway, I appreciate the desire for a deterministic evaluation of stats rather than a random one, but the *only* way for determinism to accurately model randomness is to count every possibility.

    ReplyDelete
  14. There are a few constraints that make true random modelling completely infeasible. The first is that I need the program to be lightning fast. Every single time someone changes any value on the sheet it needs to rerun its code so ideally I want it to be able to do a complete run in under a tenth of a second. Doing a proper 1,000 hour random test to really nail down the values will take a huge amount of time - even a test modelling 10 hours of combat time was totally unusable in my last model and this model is drastically more complex. This needs to be incredibly fast and if I can only use 1000 'random' numbers then I am much better off using pregenerated numbers rather than real random numbers that don't have the distribution I want.

    The other consideration is that I want the test to be 100% repeatable. Every user inputting a particular data set should get an identical result out the other side so that we can do bug testing and such. I need that internally too so that as I am moving things around I can always go back to a previous state and make sure the numbers are identical.

    I suppose it is entirely feasible to implement both. I can simply have a setting where the numbers come from my pregenerated list or are truly randomly created and let the user pick their poison.

    ReplyDelete
  15. Is there a problem with running large simulations once and storing the results for fast look-up later?

    ReplyDelete
  16. Yes. Every time mastery, haste, hit or expertise changes the entire rotation is different. Also, there are 5 different toggles for rotation types as well as a priority list that has 6! permutations. I can't just do a basic rotation and use it, I need different values for every single combination of relevant stats and every rotation setting, and obviously storing that amount of data is completely infeasible. If some of this stuff didn't affect the rotation it would be fine, but it all does. There are some changes the user can make that won't affect the rotation (like Strength, for example) but so many things do affect it that I have to account for it.

    ReplyDelete
  17. Isn't the rotation fixed for any given set of stat values? If so can't it just be part of the same look-up table?

    I'm a little confused as to the point of the sheet, possibly because I'm not a paladin. Let's pretend I don't know what I'm doing (I don't!) and get a copy of your sheet to help me play better. How am I supposed to use it and what is it supposed to accomplish? Do I just punch in my stats and have it tell me what buttons to press? Do I punch in my stats and have it tell me how to reforge? Do I select my gear from lists and have it give me my theoretical DPS number?

    ReplyDelete
  18. The purposes of the sheet:

    1. Tell you what the optimal rotation is given gear, set bonuses, latency, etc.

    2. Tell you what the optimal gear configuration is given other factors.

    3. Tell you how to weight stats against each other for gemming and upgrading purposes.

    Ideally for novice users the sheet will allow them to input the rotation that they use which EJ analysis agrees is optimal and then the sheet can tell them how to weight stats. The relative weights of hit and expertise aren't very relevant since they are significantly above crit/haste/mastery and significantly below Str so we mostly need to know the relative value of Str vs. crit/haste/mastery and reforge hit/expertise to the most valuable of those 3. Crit scales nicely and I can give very precise numbers for it as does Str. Unfortunately mastery and haste scale in extremely chunky, unpredictable ways that are based on both real mechanics and simulator limitations so to calculate their value I add a large amount of them and figure out the average benefit of a point over a substantial gain.

    The basic thing a novice gets is the ability to figure out what gear is best for them given what they already have. A veteran gets the ability to test new priorities, set bonuses and rotations along with the gear benefits.

    You ask if the rotation is fixed for any set of stat values, and the answer is sort of. To figure out the rotation I need the following information:

    % Time below 20%
    Target swap time
    Heroism use y/n
    AW use y/n
    Zealotry use y/n
    Use Two fillers y/n
    CS before Inq y/n
    Inq wasted time #

    Then I need the user to order 6 abilities in a priority queue.

    Then I need their *exact* haste, hit, expertise, and mastery values.

    If every single one of those is identical, then yes, the rotation should be identical given identical random procs. If any of those things changes the entire rotation changes. I don't see how it would be remotely feasible to build a lookup table for all these values considering mastery for example can be most of the integers between 12 and 3000, just to name one stat.

    The type of rotation you would use may work out to be identical given any reasonable gear/buff situation but it may not. It is entirely feasible that the rotation priorities and toggles would change based on your gearing but I need to have that flexibility in there.

    ReplyDelete
  19. I hear what you're saying there, but here's my issue consolidating your goals with what you're doing:

    Clearly small changes in these stats can have massive consequences including changing the optimal order of ability use. It would seem, then, that getting precise values for them would be important. But you're throwing precision out the window by forcing a specific ordering of your mastery procs. How good mastery is in reality compared to the other stats could have little to no bearing on how good it is compared to the other stats on your sheet.

    Unless adding extra mastery (or haste, or whatever) could actually decrease your damage it still seems like an at least simplified look-up table would be close enough. If you don't want to do every single value (though I don't know why you couldn't just write a program to do it) you could at least do discrete chunks which, while not exact, would at least always be close.

    I really worry that your fixed list of 'random' numbers isn't even going to be close for at least some values of these stats.

    ReplyDelete