Kahorie's DK simulator 2.0 Beta - Including Cataclysm. - Page 77

Martialbob · 01/27/11, 12:48 PM

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).

Anathem · 01/27/11, 12:55 PM

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.

Anathem · 01/27/11, 2:39 PM

delete

Anathem · 01/27/11, 4:12 PM

delete please

JMBattista · 01/27/11, 4:47 PM

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.

Anathem · 01/27/11, 5:28 PM

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.

Anathem · 01/28/11, 3:37 PM

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

Saranrap · 02/01/11, 9:34 AM

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).

skiarr · 02/01/11, 8:12 PM

Just a sidenode: The Sim doesn't recognize the random stats on items like [Cloudburst Ring], making the EP summary calculation a bit tricky.

Velk · 02/02/11, 1:53 AM

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.

Saranrap · 02/02/11, 11:58 PM

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.

sp00n · 02/05/11, 7:46 AM

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:

← Click Here

<?xml version="1.0" encoding="utf-8"?> <character> <race>Draenei</race> <skill1>Jewelcrafting</skill1> <skill2>Mining</skill2> <food /> <flask /> <DW>True</DW> <TwoHand>False<id>49623</id><gem1>40111</gem1><gem2>40111</gem2><gem3>40111</gem3><enchant>3368</enchant><reforge><from></from><to></to><value>0</value></reforge></TwoHand> <ManualInput>false</ManualInput> <Head> <id>59487</id> <gem1>52298</gem1> <gem2>52206</gem2> <gem3>0</gem3> <enchant>4208</enchant> <reforge> <from>Haste</from> <to>Mast</to> <value>91</value> </reforge> </Head> <Neck> <id>67138</id> <gem1>0</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>0</enchant> <reforge> <from>Haste</from> <to>Exp</to> <value>50</value> </reforge> </Neck> <Shoulder> <id>63470</id> <gem1>52206</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>4202</enchant> <reforge> <from>Crit</from> <to>Exp</to> <value>60</value> </reforge> </Shoulder> <Back> <id>62383</id> <gem1>0</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>4087</enchant> <reforge> <from>Dodge</from> <to>Crit</to> <value>50</value> </reforge> </Back> <Chest> <id>59316</id> <gem1>52255</gem1> <gem2>52255</gem2> <gem3>0</gem3> <enchant>4063</enchant> <reforge> <from>Haste</from> <to>Mast</to> <value>91</value> </reforge> </Chest> <Wrist> <id>57870</id> <gem1>52206</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>4095</enchant> <reforge> <from>Hit</from> <to>Exp</to> <value>36</value> </reforge> </Wrist> <TwoHand /> <MainHand> <id>59521</id> <gem1>0</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>3370</enchant> <reforge> <from></from> <to></to> <value>0</value> </reforge> </MainHand> <OffHand> <id>61344</id> <gem1>0</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>3368</enchant> <reforge> <from>Crit</from> <to>Mast</to> <value>38</value> </reforge> </OffHand> <Sigil> <id>63480</id> <gem1>52206</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>0</enchant> <reforge> <from>Haste</from> <to>Exp</to> <value>25</value> </reforge> </Sigil> <Hand> <id>60340</id> <gem1>52255</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>4075</enchant> <reforge> <from>Haste</from> <to>Exp</to> <value>67</value> </reforge> </Hand> <Waist> <id>62384</id> <gem1>52206</gem1> <gem2>52206</gem2> <gem3>0</gem3> <enchant>0</enchant> <reforge> <from>Crit</from> <to>Hit</to> <value>59</value> </reforge> </Waist> <Legs> <id>67141</id> <gem1>52206</gem1> <gem2>52206</gem2> <gem3>0</gem3> <enchant>4126</enchant> <reforge> <from>Haste</from> <to>Mast</to> <value>96</value> </reforge> </Legs> <Feets> <id>62432</id> <gem1>52206</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>4094</enchant> <reforge> <from>Parry</from> <to>Crit</to> <value>55</value> </reforge> </Feets> <Finger1> <id>67139</id> <gem1>0</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>0</enchant> <reforge> <from>Haste</from> <to>Exp</to> <value>50</value> </reforge> </Finger1> <Finger2> <id>59518</id> <gem1>0</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>0</enchant> <reforge> <from>Haste</from> <to>Mast</to> <value>50</value> </reforge> </Finger2> <Trinket1> <id>56393</id> <gem1>0</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>0</enchant> <reforge> <from>Haste</from> <to>Mast</to> <value>114</value> </reforge> </Trinket1> <Trinket2> <id>58180</id> <gem1>0</gem1> <gem2>0</gem2> <gem3>0</gem3> <enchant>0</enchant> <reforge> <from>Hit</from> <to>Exp</to> <value>128</value> </reforge> </Trinket2> <stat> <Strength>3999</Strength> <Agility>124</Agility> <Intel>36</Intel> <Stamina>5005</Stamina> <Armor>20173</Armor> <SpecialArmor>0</SpecialArmor> <AttackPower>190</AttackPower> <MasteryRating>1740</MasteryRating> <HitRating>570</HitRating> <CritRating>696</CritRating> <HasteRating>961</HasteRating> <ArmorPenetrationRating>0</ArmorPenetrationRating> <ExpertiseRating>781</ExpertiseRating> </stat> <weapon> <count>2</count> <mainhand> <dps>462.3</dps> <speed>2.60</speed> </mainhand> <offhand> <dps>462.3</dps> <speed>2.60</speed> </offhand> </weapon> <Set></Set> <trinket> <HeartofSolaceHeroic>1</HeartofSolaceHeroic> <LicensetoSlay>1</LicensetoSlay> </trinket> <WeaponProc></WeaponProc> <misc> <HandMountedPyroRocket>false</HandMountedPyroRocket> <HyperspeedAccelerators>false</HyperspeedAccelerators> <ChaoticSkyflareDiamond>false</ChaoticSkyflareDiamond> <TailorEnchant>false</TailorEnchant> <AshenBand>false</AshenBand> <PrePullIndestructiblePotion>false</PrePullIndestructiblePotion> <PrePullPotionofSpeed>false</PrePullPotionofSpeed> <IndestructiblePotion>false</IndestructiblePotion> <PotionofSpeed>false</PotionofSpeed> <SaroniteBomb>false</SaroniteBomb> <SapperCharge>false</SapperCharge> </misc> <racials> <MHExpertiseBonus>0</MHExpertiseBonus> <OHExpertiseBonus>0</OHExpertiseBonus> <Orc>false</Orc> <Troll>false</Troll> <BloodElf>false</BloodElf> <Dreani>true</Dreani> <Worgen>false</Worgen> <Goblin>false</Goblin> </racials> </character>

<?xml version="1.0" encoding="utf-8"?> <Talents> <Glyphs> <Major> <Empty>0</Empty> <AntiMagicShell>1</AntiMagicShell> <BloodBoil>0</BloodBoil> <BoneShield>0</BoneShield> <ChainsofIce>0</ChainsofIce> <DancingRuneWeapon>0</DancingRuneWeapon> <DeathGrip>0</DeathGrip> <HungeringCold>1</HungeringCold> <Pestilence>0</Pestilence> <PillarofFrost>0</PillarofFrost> <RuneTap>0</RuneTap> <Strangulate>1</Strangulate> <VampiricBlood>0</VampiricBlood> </Major> <Prime> <none>0</none> <DeathandDecay>0</DeathandDecay> <DeathCoil>0</DeathCoil> <DeathStrike>0</DeathStrike> <FrostStrike>1</FrostStrike> <HeartStrike>0</HeartStrike> <HowlingBlast>1</HowlingBlast> <IcyTouch>0</IcyTouch> <Obliterate>1</Obliterate> <RaiseDead>0</RaiseDead> <RuneStrike>0</RuneStrike> <ScourgeStrike>0</ScourgeStrike> </Prime> </Glyphs> <Butchery>2</Butchery> <BladeBarrier>0</BladeBarrier> <BladedArmor>3</BladedArmor> <ImprovedBloodTap>0</ImprovedBloodTap> <ScentOfBlood>0</ScentOfBlood> <ScarletFever>0</ScarletFever> <HandOfDoom>0</HandOfDoom> <BloodCakedBlade>0</BloodCakedBlade> <BoneShield>0</BoneShield> <Toughness>0</Toughness> <AbominationMight>0</AbominationMight> <SanguineFortitude>0</SanguineFortitude> <BloodParasite>0</BloodParasite> <IBloodPresence>0</IBloodPresence> <WillNecropolis>0</WillNecropolis> <RuneTap>0</RuneTap> <Vampiric>0</Vampiric> <ImprovedDeathStrike>0</ImprovedDeathStrike> <CrimsonScourge>0</CrimsonScourge> <DRW>0</DRW> <RunicPowerMastery>0</RunicPowerMastery> <IcyReach>2</IcyReach> <NervesofColdSteel>3</NervesofColdSteel> <Annihilation>3</Annihilation> <LichBorne>0</LichBorne> <PaleHorse>0</PaleHorse> <EndlessWinter>2</EndlessWinter> <MercilessCombat>2</MercilessCombat> <ChillOfTheGrave>2</ChillOfTheGrave> <KillingMachine>3</KillingMachine> <Rime>3</Rime> <PillarOfFrost>1</PillarOfFrost> <ImprovedIcyTalons>1</ImprovedIcyTalons> <BrittleBones>2</BrittleBones> <ChillBlains>2</ChillBlains> <HungeringCold>1</HungeringCold> <IFrostPresence>2</IFrostPresence> <ThreatOfThassarian>3</ThreatOfThassarian> <MightOfFrozenWastes>0</MightOfFrozenWastes> <HowlingBlast>1</HowlingBlast> <UnholyCommand>0</UnholyCommand> <Virulence>0</Virulence> <Epidemic>3</Epidemic> <Desecration>0</Desecration> <ResilientInfection>0</ResilientInfection> <Morbidity>0</Morbidity> <RunicCorruption>0</RunicCorruption> <UnholyFrenzy>0</UnholyFrenzy> <Contagion>0</Contagion> <ShadowInfusion>0</ShadowInfusion> <MagicSuppression>0</MagicSuppression> <RageOfRivendare>0</RageOfRivendare> <UnholyBlight>0</UnholyBlight> <AMZ>0</AMZ> <ImprovedUnholyPresence>0</ImprovedUnholyPresence> <DarkTransformation>0</DarkTransformation> <EbonPlaguebringer>0</EbonPlaguebringer> <SuddenDoom>0</SuddenDoom> <SummonGargoyle>0</SummonGargoyle> </Talents>

<?xml version="1.0" encoding="utf-8"?> <Priority> <Rime></Rime> <FrostFever></FrostFever> <BloodPlague></BloodPlague> <FrostStrikeMaxRp></FrostStrikeMaxRp> <KMObliterate></KMObliterate> <Obliterate></Obliterate> <BloodStrike></BloodStrike> <FrostStrike></FrostStrike> <HowlingBlast></HowlingBlast> <DeathandDecay></DeathandDecay> <BloodTap></BloodTap> <EmpowerRuneWeapon></EmpowerRuneWeapon> </Priority>

Zynus · 02/15/11, 5:58 AM

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

EwokChilli · 02/15/11, 10:37 AM

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?

Cabal · 02/17/11, 7:58 AM

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.