Boolean modifiers for certain types of equipment
Many things in Kingdom of Loathing function differently based on whether you have a certain type of item equipped. Utensil Twist requires you to have a utensil equipped, Lunging Thrust-Smack always hits if you have a club equipped (and are a Seal Clubber), etcetera.
However, the Modifier Maximizer is currently not very good at optimizing for this. If you include a flag like “+club”, it outright ignores everything that doesn’t satisfy the requirement, even though you only need to satisfy it once.
I think it would be much more effective to treat these scenarios like a boolean modifier, similar to “Adventure Underwater": equipping a club causes the modifier to be true. That would substantially increase the readability of the existing code, and more accurately reflect the expectations of the user.
To get a sense of how this would actually work, try using “Song Duration, 1 max” instead of “+accordion”. That isn’t ideal, of course, since it causes Song Duration to no longer be considered at all, but you can probably see what I’m thinking of. The first keyword might lead to dual-wielding a ranged weapon along with an accordion, whereas the second never will.
Last edited by Saklad5; 03-18-2019 at 08:43 PM.
Any thoughts on this? It would make the Modifier Maximizer much more orthogonal.
We probably should do something like this. I’d feel keener if it weren’t for the fact that the thing Maximizer does worst is these kind or prioritisations.
You mean Boolean modifiers?
Originally Posted by Darzil
I mean any time you try to prioritise two different things. So this can be boolean + maximization, or maximization with min or max supplied.
Ideally one day a maths guru will totally rewrite maximizer using advanced maths!
It seems to work pretty well if you disable the combination limit and be patient. At any rate, I feel this could only improve matters.
Originally Posted by Darzil
... and possibly explode required computation time.
I'm not sure there's much advanced maths that can be used for maximizer. It's all combinatorial optimization (which is NP-hard), so you can't really do much beyond branch and bound (and pruning items that are strictly suboptimal, which I imagine we already do).
IIRC someone actually solves the diet problem using integer programming, but that's assuredly a much smaller space, and this isn't linear.
I guess developing good heuristics is an open question if we do try out a branch-and-bound solution.
I'm curious where the current maximizer implementation has room for optimization, though.
(fwiw my stress test will probably be "maximize item, meat", which generates 1M+ combinations on heeheehee.)
I installed VisualVM to see if it could tell me anything about where the CPU was going. Looks like my test case ("maximize? meat, item") spent most of its time in KoLCharacter.recalculateAdjustments() specifically.
Some thoughts about the stack trace:
- I wonder why the stack trace shows 4 different tryAccessories() calls and 2 different tryOffhands() calls.
- 25% of the overall time was spent in Modifiers.parseModifiers(). Do we really need to execute a regex in this loop?
- The next biggest chunk of overall time (another 25% or so of total runtime) is in Modifiers.applyPassiveModifiers(), split between Modifiers.add() and Modifiers.getModifiers() which spends 56% of its subtree in HashMap.get(). Is our hash function poorly distributed? Who knows.
- getSmithsnessModifier() takes about 6% of overall runtime, checking getEffectModifiers() a bunch of times even though that doesn't change when the maximization command only considers changing gear, not effects.
Lots of good fodder for optimizations, IMO.
Ah, I see the regex usage, which shows up several times in KoLCharacter.recalculateAdjustments(). Modifiers.evaluateModifiers() takes a ModifierList and serializes it; Modifiers.parseModifiers() then takes that result and parses the modifiers back out of it (probably inefficiently, as we operate on the entire serialized string multiple times). We probably should have some mechanism for taking a ModifierList and turning that directly into a Modifiers object.
(incidentally, `String name = Modifiers.getNameFromLookup( lookup );` in Modifiers.java is unused.)