Feature Boolean modifiers for certain types of equipment

Saklad5

Member
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:

Darzil

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

Darzil

Developer
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!
 

Saklad5

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

heeheehee

Developer
Staff member
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.)
 

heeheehee

Developer
Staff member
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.
 

Attachments

  • profile.png
    profile.png
    270.4 KB · Views: 31

heeheehee

Developer
Staff member
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.)
 

heeheehee

Developer
Staff member
r19148 adds the proposed change from #10. A sample run saw improved runtime of the sample maximizer command by something like 30%.
 

Darzil

Developer
I have toyed with adding a comparison of outfit sets whose bonus changes with number with the best of other items, so we can prune items that only might help before the full iteration. It should be possible, and make a big difference, but is quite a big project.
 

heeheehee

Developer
Staff member
When I manually calculate value of combinations with variable effects (e.g. hobo power), I consider the value on a per-item basis to be averaged across all the items. For instance, full hodgman outfit + sock + Hodgman's garbage sticker (150 hobo power -> 150% meat) would be worth +30% meat drop each.

I'd need to think some more to figure out how to translate that into code. What works for me in the time being is just maximizing with lots of +equip clauses.


Some tangential ramblings about meatfarming:

30% per slot is actually pretty bad in today's climate -- cajun carrot rawhide latte lover's mug, great wolf's beastly trousers, crumpled felt fedora puts you at 40% meat, 25lb which with fish head + robortender is always worth >= 140% from just three items, and at typical operating points (less than 160lb which becomes 185lb buffed robortender), is worth 160%+.

It might be worth considering for the 5 hobo summons a day, but even then that's only 50% meat on average, which is no longer worthwhile when you consider additional value from, say, Screege drops, which my notes consistently say is worth ~196 meat / combat, which in Barf with boombox song is worth an additional ~71% meat... with cheap sunglasses and belt of loathing, there's not really room in Barf for even +50% meat accessories, and that's ignoring other crazy stuff you might be doing.
 

Saklad5

Member
I feel this is getting a bit off-topic. I simply want to eliminate the existing hardcoded behavior for things like equipping a certain weapon type by expanding the existing boolean modifier system.
 

Saklad5

Member
... and possibly explode required computation time.
That’s actually not what causes the combinatorial explosion. No, what really makes it suffer is writing a personal ASH library that allows you to specify modifiers and required equipment using records, then telling it to explicitly consider every accessible familiar that either has an impact on the specified modifiers or has the “variable” proxy record field set to true.

I’ve had it calculate over 12,000,000 combinations once. It’s worth it, too: this approach is clever enough to account for extremely complicated behavior such as different familiar weights, accessible equipment, effect combinations, underwater requirements, and special cases like the Fancypants Scarecrow.

I’m actually fine with that sort of wait, since I can do other things while it runs, but I can see why familiars are usually ignored. Disabling the portion of my script that concerns familiar switching makes the Maximizer finish almost instantaneously in comparison.
 

Darzil

Developer
I feel this is getting a bit off-topic. I simply want to eliminate the existing hardcoded behavior for things like equipping a certain weapon type by expanding the existing boolean modifier system.

It does look like making club, utensil, knife and accordion into Boolean modifiers would make this work better (and needed as getScore considers only modifiers, not items).

So I think it's converting bitmaps to longs (as this will take us over 32 booleans), adding 4 boolean modifiers, and remove the current handling for them in Maximizer.

We've also either got to add these Modifiers when reading equipment.txt, or add them to modifiers.txt and add recognising them on new items in DebugDatabase etc. Or I guess just add them during Maximization to the item may be simpler.
 
Last edited:

Darzil

Developer
Well, it isn't quite that simple.

Most items that give a boolean exist on relatively few items, and Maximizer just passes them all through.

However, there are loads of items that meet these booleans, so we need to prune the list to just the best one in these cases.
 

Darzil

Developer
This isn't done yet, but I think I've hit the wall for today.

It works, badly and slowly, for +club, as it hasn't yet got pruning.

It doesn't work, yet, for +accordion, +knife or +utensil, I suspect I've missed turning an int into a long somewhere.

If anyone wants to take a look, feel free, have attached the patch so far. View attachment boolean.patch
 

Saklad5

Member
It’s worth noting that “Club” has a special case: if you have the effect “Iron Palms” (or possibly just the skill “Iron Palm Technique”, so the Maximizer could toggle it as beneficial), then swords qualify as clubs.
 

Saklad5

Member
Well, it isn't quite that simple.

Most items that give a boolean exist on relatively few items, and Maximizer just passes them all through.

However, there are loads of items that meet these booleans, so we need to prune the list to just the best one in these cases.
I’m not sure I entirely understand why handling like that is necessary. The Maximizer is fine with “min” on a numeric modifier, which seems much more difficult in terms of relevant items. Couldn’t you just use the same techniques for boolean modifiers, with a minimum value of “true”/1?

On a related note, why make modifiers maximizer-only? It is easy to conceive of use cases for such modifiers in scripts.
 
Top