Elitist Jerks Kahorie's DK simulator 2.0 Beta - Including Cataclysm.

 01/27/11, 12:48 PM #1141 Martialbob Glass Joe   Martialbob Worgen Death Knight   Cenarius Unless you can put the algorithm in to different modes dependent upon the current status of hit/expertise with the current most optimal set that it has found. If this current most optimal set has above hit cap, it goes into a don't reforge to hit mode, if it finds a more optimal setup below hit cap, it goes back into reforge to hit mode. This way, at small times, we can reduce the value of N from 3 to 2 or sometimes 1. I do agree though that there is a way to decrease the big O value. I'll run the problem by my CS professors and my discrete math professor. It could work something like finding 0's using derivatives in calculus, it bounces back and forth above and below hit/expertise caps until it finds the closest to 0's(0's being optimal hit/expertise cap spots).
01/27/11, 12:55 PM   #1142
Anathem
Glass Joe

Orc Death Knight

Blackrock
 Originally Posted by JMBattista 1 - find the optimal setup, this *will* be an exhaustive search, you can try to optimize it... but its still exhaustive .
We can almost certainly drastically reduce the search space with a Branch and bound - Wikipedia, the free encyclopedia algorithm, which is what integer programming solvers do -- the problem is that I couldn't manage to formulate this as a linear integer programming problem and just use a solver, which would have been ideal (NOTE: I'm not saying it isn't possible, someone with more experience with modeling combinatorial optimization problems should keep trying to do this).

We'll probably have to write a custom branch and bound algorithm, which is pretty straightforward with caveat that someone has to figure out how to do pruning.

Another advantage of branch and bound is that subdivision means we can effectively parallelize the search (spawn a thread for each branch), which is something we can't do effectively by enumerating the combinations.

 01/27/11, 2:39 PM #1143 Anathem Glass Joe   Mitsuro Orc Death Knight   Blackrock delete Last edited by Anathem : 01/27/11 at 5:29 PM. Reason: combined multiple posts into one
 01/27/11, 4:12 PM #1144 Anathem Glass Joe   Mitsuro Orc Death Knight   Blackrock delete please Last edited by Anathem : 01/27/11 at 5:29 PM.
01/27/11, 4:47 PM   #1145
JMBattista
Glass Joe

Blood Elf Death Knight

Hydraxis
 Originally Posted by Anathem Just to kind of limit expectations, this is O(Branching factor ^ tree depth) no matter how you look at it.
yea, like I said if you find an algorithm give it to me and I'll retire =p

I may have misused the term, but my reference to exhaustive is simply that *all* possibilities must be accounted for to reach an optimal solution. Optimizations that allow you to trim out some set of possibilities as a "well this *definitely* is where we want to go!" can reduce the search space dramatically but you are still 'exhausting' those possibilities.

ie - mastery as our lowest stat (unholy live) you can safely assume that we will *never* choose to reforge into mastery, so a rather large number of possibilities fall by the way side right there. Similarly on gear with hit/haste it is clear we will never reforge the amount of haste (unholy live) since we can't improve on the haste and it is uncappable, ect, ect. Or that on a haste/crit piece we would consider the crit for reforge not the haste, and then the crit only to hit/expertise (depending on personal stat weights).

These are optimizations that allow you to prune the tree, but they don't change that fact that it is NP.

Also - O(3^n) isn't really considered constant time just because you know n, the algorithm is still np... even if it is restricted to 129,140,163 (dw) or 43,046,721 (2h). Big O constant time refers to constant with respect to the variables, not to some specific case of your data size.

A definite performance improvement, aside from the optimizations is the simple trick of caching. I was playing around with comparing a few different sets of gear, and ended up going back to the same setup I had previously and re-running with a slight tweak to sim settings... but I had to completely re-run the optimizer on my gear, even though it had done the exact same computation only moments prior. Its far too big to store all of the potential gear combinations, but short term caching would be a good idea, especially if your number of users is large. Its likely many different people have the same gear, and that some of the potential combinations simply wont' be seen or will rarely be seen.

01/27/11, 5:28 PM   #1146
Anathem
Glass Joe

Orc Death Knight

Blackrock
 Originally Posted by JMBattista I may have misused the term, but my reference to exhaustive is simply that *all* possibilities must be accounted for to reach an optimal solution. Optimizations that allow you to trim out some set of possibilities as a "well this *definitely* is where we want to go!" can reduce the search space dramatically but you are still 'exhausting' those possibilities. ie - mastery as our lowest stat (unholy live) you can safely assume that we will *never* choose to reforge into mastery, so a rather large number of possibilities fall by the way side right there. Similarly on gear with hit/haste it is clear we will never reforge the amount of haste (unholy live) since we can't improve on the haste and it is uncappable, ect, ect. Or that on a haste/crit piece we would consider the crit for reforge not the haste, and then the crit only to hit/expertise (depending on personal stat weights). These are optimizations that allow you to prune the tree, but they don't change that fact that it is NP.
Ignoring some obviously wrong reforging options just decreases the branching factor -- those tree nodes aren't generated at all. This is not what I'm talking about when I say we can prune the tree with bounding.

I've synthesized my previous posts here into a proposed algorithm for finding the optimal reforging of a item set:

1. Create the root node, consisting of the item set with no reforges made.

2. Calculate the upper and lower bounds of the root node - the upper bound being the value of the current node plus the most we could possibly gain by reforging every item perfectly.The lower bound is just the value of the current item set as-is, because we don't want to consider any reforged item sets where the best we can do is worse than its parent!

3. Branch by creating a child node for every possible reforging option for a single item slot. (remember to include leaving the item un-reforged as a child node!).

4. Calculate the upper and lower bounds for each child node. The upper bound is, again, the value of the current node plus the most we could possibly gain by reforging every item perfectly (except this time we don't include the item we set in this child node). Lower bound is always the value of the current node as-is.

5. Eliminate all nodes on this level where the upper bound is less than the global maximum lower bound -- that is, we prune any subtrees where the best we could do is lower than the worst some other subtree we have seen could do.

6. For any remaining nodes at this level, branch on the next item slot.

7. Again calculate upper and lower bounds for each new child node, not including the item slot of the current node or any parent nodes in the calculation because they are now fixed (because you picked a specific reforging option for them already).

8. If you have no items left to reforge, you're done. Else: GOTO 5

So, the hard question is, how do you find the upper bound for a subtree?

Here's how:

Before you start searching the tree you need to find the range of possible item values for every item in your input:
lower bound: [ItemScore(item) when ALL hit and exp is over the cap]
upper bound:[ItemScore(item) when NO hit and exp is over the cap]

Now when we are tasked with finding the upper bound of a subtree, we can say that the upper bound on that subtree is:
(The value of the current node taken as a whole, not including any items that have already been reforged at this level or in a parent node) + (the sum of the highest upper bound for each of the lower-level item slots)

Note that because we are looking at individual item slots, we can't take into account hit/exp caps for this bounds calculation, but that actually makes the pruning LESS restrictive, so we're still guaranteed to find the optimal solution.

Expect an implementation and benchmarks vs naive enumeration of all sets from me within the next few days.

Last edited by Anathem : 02/01/11 at 2:03 PM.

01/28/11, 3:37 PM   #1147
Anathem
Glass Joe

Orc Death Knight

Blackrock
 Originally Posted by JMBattista On the reforging, this problem is as Anathem pointed out.... the *optimal* reforge calculation will always run in non-polynomial time - ie take effing forever. If someone comes up with an efficient solution to finding the optimal setup... please let me know so I can jack your work, publish a paper and retire o0.
Haha. While I was working on formulating this as an integer programming problem one of the papers I read claimed to have, as a side effect of making an IP formulation for the set partitioning problem, proved that P=NP. I'm not buying it though =D

 02/01/11, 9:34 AM #1148 Saranrap Banned   Saranrap Human Death Knight   No WoW Account So I guess the armory import was fixed, as it now show correct stat values. Also, the reforging tool manages to miss the hit cap by only 2 points while having haste on all my items, which is superb. The only odd thing is it chooses to reforge Mastery => Haste instead of Expertise => Haste on my weapon, even though priority is set for 4.0.6 (2,7 for mastery and 2,6 for expertise). Last edited by Saranrap : 02/03/11 at 1:13 AM.
 02/01/11, 8:12 PM #1149 skiarr Glass Joe     Deneroc Worgen Death Knight   Die Silberne Hand (EU) Just a sidenode: The Sim doesn't recognize the random stats on items like [Cloudburst Ring], making the EP summary calculation a bit tricky.
02/02/11, 1:53 AM   #1150
Velk
Von Kaiser

Human Death Knight

Khaz'goroth
 Originally Posted by Saranrap So I guess the armory import was fixed, as it now show correct stats value. Also, the reforging tool manages to miss the hit cap by only 2 points while having haste on all my items, which is superb. The only odd thing is it choose to reforge Mastery => Haste instead of Expertise => Haste on my weapon, even though priority is set for 4.0.6 (2,7 for mastery and 2,6 for expertise).
that would be perfectly normal if the amount of mastery is larger than the amount of haste. For example 100 mastery to haste is obviously better than 10 expertise to 10 haste for almost any value of mastery/expertise. With close values the required gap is pretty small.

02/02/11, 11:58 PM   #1151
Saranrap
Banned

Saranrap
Human Death Knight

No WoW Account
 Originally Posted by Velk that would be perfectly normal if the amount of mastery is larger than the amount of EXPERTISE. For example 100 mastery to haste is obviously better than 10 expertise to 10 haste for almost any value of mastery/expertise. With close values the required gap is pretty small.
Nope 228 of each: [Akirus the Worm-Breaker].
Yet it reforged from Expertise. Also, fix'd.

Last edited by Saranrap : 02/04/11 at 9:08 AM.

02/05/11, 7:46 AM   #1152
sp00n
Bald Bull

Night Elf Rogue

Wrathbringer (EU)
I'm seeing some weird results with Frost DW and haste/Unholy presence.

First, I posted in the Frost thread that for my gear, haste seems to scale better than crit. Then I've read two posts that stated that switching to Unholy presence was a DPS increase according to the simulator, which I tried and proved true for me as well (around +250 DPS compared to Frost presence with dual wield and 4.0.3 settings).

Also, stat scaling in Unholy presence even favors haste more than in Frost:

Now, is this expected behaviour or some sort of bug? Does it truely carry over into real game DPS?

Settings I used for this specific graph:
 ``` Draenei Jewelcrafting Mining True False4962340111401114011133680 false 59487 52298 52206 0 4208 Haste Mast 91 67138 0 0 0 0 Haste Exp 50 63470 52206 0 0 4202 Crit Exp 60 62383 0 0 0 4087 Dodge Crit 50 59316 52255 52255 0 4063 Haste Mast 91 57870 52206 0 0 4095 Hit Exp 36 59521 0 0 0 3370 0 61344 0 0 0 3368 Crit Mast 38 63480 52206 0 0 0 Haste Exp 25 60340 52255 0 0 4075 Haste Exp 67 62384 52206 52206 0 0 Crit Hit 59 67141 52206 52206 0 4126 Haste Mast 96 62432 52206 0 0 4094 Parry Crit 55 67139 0 0 0 0 Haste Exp 50 59518 0 0 0 0 Haste Mast 50 56393 0 0 0 0 Haste Mast 114 58180 0 0 0 0 Hit Exp 128 3999 124 36 5005 20173 0 190 1740 570 696 961 0 781 2 462.3 2.60 462.3 2.60 1 1 false false false false false false false false false false false 0 0 false false false true false false ``` ``` 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 2 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 3 0 0 2 2 2 3 3 1 1 2 2 1 2 3 0 1 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ``` ``` ```

Stopped Playing

 02/15/11, 5:58 AM #1153 Zynus Glass Joe   Zynus Orc Death Knight   Gul'dan (EU) Hi everyone, First excuse me for my bad school english. Can everyone explane me all settings for "Kahorie's DK simulator" in german in a Private Messages. I have with "Kahorie's DK simulator" a fewer dps as with "simcraft" and i mean the settings are wrong. thx
 02/15/11, 10:37 AM #1154 EwokChilli Piston Honda   Coopstrocity Draenei Death Knight   Medivh I dug around as best I could, but is Kahorie's still using Blood Strike on Death Runes? Certain outcomes as far as % dps by abilities just isn't panning out compared to what you would see on WoW Meters Online. Also, the sim is putting a way above average weight on frost strike as % damage compared to oblit as % damage. Usually in actual execution, Oblit is weighing in at about 30-31% of my dps and frost strike is at 28-30% of my dps, not 23% and 42% respectively. Should I just take the numbers with a grain of salt and think of it as a useful tool for comparing stat weights and leave it at that?
 02/17/11, 7:58 AM #1155 Cabal Piston Honda     Wünju Orc Warrior   Turalyon (EU) There seems to be some kind of problem, when I switch from my current weapon [Shalug'doom, the Axe of Unmaking] (359 weapon) to [Akirus the Worm-Breaker] (372) the dps calculated is exactly the same. In fact. even with a ilvl 300 weapon it remains the same.

 Elitist Jerks Kahorie's DK simulator 2.0 Beta - Including Cataclysm.

 Similar Threads Thread Thread Starter Forum Replies Last Post WoW Simulator - What do you want? Ullas User Interface and AddOns 60 08/30/11 10:23 AM EnhSim, DPS simulator tukez Shamans 2763 11/30/09 11:45 AM DPS Simulator Grim13 Warriors 133 11/12/08 7:20 AM [Mage] DPS Simulator zurmagus Class Mechanics 41 11/08/07 9:11 PM