Feature - Implemented Let maximizer stop when it is not finding a better score

Veracity · Feb 13, 2014

The following is an extreme example, but not uncommon for item drop, at least

Maximizing (1st time may take a while)...
79233 combinations checked, best score 441.75
173597 combinations checked, best score 441.75
267221 combinations checked, best score 441.75
355492 combinations checked, best score 441.75
445170 combinations checked, best score 441.75
537175 combinations checked, best score 441.75
630042 combinations checked, best score 441.75
724384 combinations checked, best score 441.75
815976 combinations checked, best score 441.75
908853 combinations checked, best score 441.75
1007947 combinations checked, best score 441.75
1107914 combinations checked, best score 441.75
1207033 combinations checked, best score 441.75
1307034 combinations checked, best score 441.75
1409171 combinations checked, best score 441.75
1512402 combinations checked, best score 441.75
1614380 combinations checked, best score 441.75
1716565 combinations checked, best score 441.75
1818166 combinations checked, best score 441.75
1920825 combinations checked, best score 441.75
2024208 combinations checked, best score 441.75
2126106 combinations checked, best score 441.75
2226503 combinations checked, best score 441.75
2329368 combinations checked, best score 441.75
2429643 combinations checked, best score 441.75
2532665 combinations checked, best score 441.75
2634710 combinations checked, best score 441.75
2734026 combinations checked, best score 441.75
2834823 combinations checked, best score 441.75
2936299 combinations checked, best score 441.75
3034494 combinations checked, best score 441.75
3134884 combinations checked, best score 441.75
3235460 combinations checked, best score 441.75
3336205 combinations checked, best score 441.75
3428360 combinations checked, best score 441.75
3524845 combinations checked, best score 441.75
3625181 combinations checked, best score 441.75
3726102 combinations checked, best score 441.75
3814932 combinations checked, best score 441.75

My usual experience with just about anything I try to maximize is that it does one iteration, finds a best score, does another one, improves on that slightly, and then does an arbitrary number of iterations with no further improvement.

Yes, I know that I can say "stop after X combinations".
How about "stop after an iteration did not improve on the best score from the previous iteration"?

lostcalpolydude · Feb 13, 2014

Not that I really understand how it works, but I thought there were plenty of iterations (combinations in the gCLI output), even early on, that don't improve the score. Only printing results once per second would cover that up. I guess stopping if the score hasn't changed in 1 second will work well at least the majority of the time.

Veracity · Feb 13, 2014

Well, I don't understand how it works, either. You are probably correct that what I want is "arbitrary number of seconds X is long enough to wait, if the score is not improving", rather than "arbitrary number of combinations X is enough to attempt, whether or not the score is improving".

fronobulax · Feb 13, 2014

Veracity said:
"arbitrary number of seconds X is long enough to wait".

I am unlikely to use the feature, if implemented, but I suspect the value of X will be one more thing that will frustrate users who synchronize KoLmafia across multiple computers and then run from whichever one is currently available, at least in the case when the computer speeds vary dramatically. At least we are not back in the days when the timing in games was tied directly the frequency of the CPU clock and so hardware upgrades made games unplayable.

ereinion · Feb 13, 2014

I would very much appreciate this future. I am pretty sure that I've run maximization attempts in aftercore which took at least half an hour before they completed (e.g. "maximize 0.01 item, -combat, sea, equip pantsgiving, equip bone abacus"). And as other people in the thread have noted, once it has found a combination which fulfills all the criteria it usually only prints out one or two further improvements to the score before cheking a ton of combinations which doesn't result in any improvement.

roippi · Feb 13, 2014

Veracity said:
Yes, I know that I can say "stop after X combinations".
How about "stop after an iteration did not improve on the best score from the previous iteration"?

That's not really possible/feasible. Well, I'll rephrase, it's easily possible, but that heuristic is pretty fragile, even if it often happens to work for reasons I'll get into later.

The maximizer is a straightforward combinatorics engine - form every combination of elements from the pools given, and brute-force test all of them, returning the best score found. There is an incredible amount of complexity involved in determining the "score," but that's it. So if I had two pools

Code:

 [2,1,3], [2,1]

we get

Code:

(2,2)
(2,1)
(1,2)
(1,1)
(3,2)
(3,1)

In the maximizer, the "pools" are referred to as "shortlists" - i.e. we don't try every item in every slot, just the n best-scoring ones for that individual slot. So in the above, you might say, why don't we just sort the pools, and take the best score from individual ones? Well that works in the simplest possible model, but in kol we have complications:

- items can take up two slots (main/offhand), and other various mutex conditions
- synergistic items exist, like cloathing and/or brimstone gear

This latter part is what is getting us into trouble nowadays. The approach to synergistic gear is "always add it to the shortlists, always." We have to do this because our previous pruning heuristic - determine an item's individual score in a vacuum - just doesn't apply; the item needs to know the entire state of what's equipped. It might have zero contribution to score itself, but its synergy makes it included in the best-scoring combination.

So every time kol adds an item with synergy (and you have it in your inventory), that item expands a shortlist by one item. Given enough items, this quickly gets us up into the millions of combinations area - which takes a while.

------

Back to solving the problem. The reason (I think) that you usually see score never changing is that either synergy dominates - and you want to take all of the synergistic items - or it's unimportant, and the best individually-scoring items end up being correct for the global score maximization. Rarely does synergy incompletely dominate (often because the items that feature synergy also have very good base stats).

I could envision an alternate approach to synergy - leave them out completely from the base maximization (unless they are individually the best scoring item for a given pool). Then after that's computed, forcibly try each entire set of synergistic gear. So instead of adding (pools)**(synergistic_items) combinations, we only add (synergistic_sets) combinations. That's the difference between 4 million and 4.

I have no mathematical basis for why this heuristic/optimization is anywhere close to correct. But it feels to me right - equipping 3 brimstone items and 3 cloathing items is almost certainly worse than just equipping the whole set of either one or the other. Hodgman gear gets more complex - both because it only takes up 3 slots, and because there's an offhand involved. Perhaps leaving the hodgman brute-forcing intact and just optimizing out brimstone/cloathing is more feasible.

Anyway I'm in a bit of a rush to head out the door so I can't really think this through much further, but it seems better for us to reexamine why the earlier combinations are almost always best, and just.. don't do the ones after that.

Darzil · Feb 13, 2014

Yeah, I was thinking about this when I changed it to stop having to consider card sleeve and folder holder as almost always useful, thus reducing the possible combinations. Only easy way I could think of doing it was to exclude synergies if the item + synergistic bonus still wasn't as good as the best item for a slot. However, in practice the bonus on most of they synergies is so large that it is rarely the case, and would add more complexity to an already complex area for little gain.

Theraze · Feb 13, 2014

Personally, I often find that it goes through 3-5 iterations without any advance before it finds something better, and then that one stays the best for the other 20 or so iterations. But yeah... either setting a max total iterations, maximum total attempts (already available now), or max iterations without an improvement would be ways to avoid the forever maximization. But changing the default to skip as soon as it fails to improve once would end up with my maximizations ending up worse, as it does improve for me after several attempts.

Or if roippi can figure out how to make it more efficient, that would be nifty too.

fronobulax · Feb 14, 2014

roippi said:
Rarely does synergy incompletely dominate

I love it when you talk dirty, especially when it reminds me of things I studied long ago.

And long ago means my memory may be faulty, but I think I recall one strategy that might be worth thinking about. If this is a combinatorial problem where we have X slots to fill and we want to do so in order to maximize some value, one possibility for synergy would be to define new artificial slots. These are created from the individual slots that have synergistic effects. So a new slot might be the set of hat, pants and on hand weapon. The only things that could fill that slot would be items that when used together had a greater contribution to the result when used together. While this superficially seems to increase the number of combinations to be tried, the fact that it can only be filled by a set and that filling it "eliminates" three other slots tends to reduce the number of valid things to be checked.

My mind is still reeling from trying to formulate the Eat/Drink problem as an integer LP and convince myself that someone else's (sorry, I said my memory was shot, but I recall the interaction fondly even if I can't remember who it was with) knapsack formulation thereof was really the same problem my LP addressed, but it does seem as if this is intriguing enough to make some simple test cases and analyze.

Darzil · Feb 14, 2014

There is a syntax or command for showing a debug version of maximizer which shows the shortlist of items to consider for maximization I believe? I'm sure I've come across it but haven't worked out how to get it when I've looked recently. Can anyone tell me what it is ?

Was thinking of checking which items can be used to see if there would be effective ways to reduce the list, whilst not hard coding too much stuff for specific item sets (as there are so many). I noticed today in aftercore that 100k isn't enough combinations for +item drop for me even at level 13, needing a second iteration to get better items (mostly honey items by 100k combinations, then if you put all on it's coming back with bounty equipment/smithsness for me - which suggests to me there should be shortcuts, the honey outfit gives only +5% items, so just comparing item+outfit bonus to another item it wouldn't get shortlisted. I suspect we may be able to add an additional filter level, for outfits at least, where we just compare each outfit to the best individual items that cover the same slots. That'd possibly significantly reduce the options (maybe, I'm basing that on just the presence of the honey item, I've not checked the code on outfits).

Cool12309 · Feb 14, 2014

I haven't looked into it, but when I maximize for 2 seconds, equip all, and maximize until complete it seems to use a lot less combinations than if I let it maximize all immediately. I don't know if that's really the case, but if it is, could this be implemented into the maximizer as it's maximizing?

Theraze · Feb 14, 2014

I believe what you wanted was the dump command. It's documented in the maximizer help box, but not the quick-help because it's another keyword rather than an additional command. Basically, "maximize? muscle, dump" to see all of the best muscle slot considerations - generally 1-5 results depending on how many synergistic items you have. If you love spam, "maximize? muscle, 2 dump" will show you EVERYTHING that it considered for each slot.

Edit:

Cool12309 said:
I haven't looked into it, but when I maximize for 2 seconds, equip all, and maximize until complete it seems to use a lot less combinations than if I let it maximize all immediately. I don't know if that's really the case, but if it is, could this be implemented into the maximizer as it's maximizing?

This is because the items you currently have equipped are always added to the short-list of items to consider. If you are already wearing one of the best items, that means that the amount of items to be considered are going down massively...

Darzil · Feb 15, 2014

Ok, playing devils advocate, is there a reason we don't make the following checks :
Only consider outfits as useful if they are better than the best individual items in the same slots. Currently we include outfits if they are better than nothing.
Only consider synergies as useful if they are better than the best individual items in the same slots. Currently we include synergies if they are better than nothing.
Only consider current equipment as useful if they are better than the best individual items in each slot, or keywords like min and max are included (which may mean not changing something even though better exists).

It would mean more work for evaluator, but less for maximizer speculation, which is what takes the greatest time.
(Incidentally, it doesn't look like dump shows outfits or synergies that are considered. I was getting recommended Honey outfit pieces that didn't appear in dump on a 100k combination limit for +item).

Theraze · Feb 15, 2014

The problem with synergies is that if for some reason you don't have great, let's say accessories, but you do have the cloathing outfit, then as it synergizes as you add more pieces it keeps getting more powerful, and you don't know if it's better than a slot until you know how many pieces you're actually wearing, which you can't know until you finish. Unless you have pieces that individually are better than the best possible synergistic result.

xKiv · Feb 15, 2014

Darzil said:
Only consider synergies as useful if they are better than the best individual items in the same slots. Currently we include synergies if they are better than nothing.

That should work unless there are somehow 'overlapping' synergies.
Example: pantshat+lackofpants=0 score from items, 20 score from synergy; lackofpants+plinkshirt=0 score from items, 20 score from synergy; besthat=11 score, bestpants=11 score, bestshirt=11 score -- simplistic synergy pruning would say that since 22>20, don't even consider pantshat+lackofpants or lackofpants+plinkshirt, even though the two synergies together make pantshat+lackofpants+plinkshirt 7 points better than besthat+bestpants+bestshirt

...
BTW I added a "best score since last printout" and maximized for items ...

Code:

41279 combinations checked, best score 905.01, best since last = 905.01
93251 combinations checked, best score 905.01, best since last = 902.01
144988 combinations checked, best score 905.01, best since last = 905.00
191192 combinations checked, best score 905.01, best since last = 895.00
237138 combinations checked, best score 905.01, best since last = 892.00
286662 combinations checked, best score 905.01, best since last = 895.00
338108 combinations checked, best score 905.01, best since last = 892.00
387403 combinations checked, best score 960.00, best since last = 960.00
437007 combinations checked, best score 960.00, best since last = 940.00
486894 combinations checked, best score 960.00, best since last = 935.00
536528 combinations checked, best score 960.00, best since last = 925.00
586377 combinations checked, best score 960.00, best since last = 915.00
636191 combinations checked, best score 960.00, best since last = 915.00
685142 combinations checked, best score 960.00, best since last = 912.00
735116 combinations checked, best score 960.00, best since last = 912.50
785399 combinations checked, best score 960.00, best since last = 910.00
837536 combinations checked, best score 960.00, best since last = 890.00
889171 combinations checked, best score 960.00, best since last = 455.00
940746 combinations checked, best score 960.00, best since last = 455.00
992353 combinations checked, best score 960.00, best since last = 445.00
1044142 combinations checked, best score 960.00, best since last = 442.00
1096129 combinations checked, best score 960.00, best since last = 442.50
1148289 combinations checked, best score 960.00, best since last = 440.00
1200490 combinations checked, best score 960.00, best since last = 450.00
1252370 combinations checked, best score 960.00, best since last = 450.00
1303510 combinations checked, best score 960.00, best since last = 440.00
1354708 combinations checked, best score 960.00, best since last = 437.00
1405777 combinations checked, best score 960.00, best since last = 437.50
1456477 combinations checked, best score 960.00, best since last = 435.00
1507248 combinations checked, best score 960.00, best since last = 450.00
1557304 combinations checked, best score 960.00, best since last = 430.00
1607714 combinations checked, best score 960.00, best since last = 430.00
1658589 combinations checked, best score 960.00, best since last = 417.00
1709833 combinations checked, best score 960.00, best since last = 417.50
1760055 combinations checked, best score 960.00, best since last = 427.00
1810637 combinations checked, best score 960.00, best since last = 430.00
1861728 combinations checked, best score 960.00, best since last = 417.00
1914583 combinations checked, best score 960.00, best since last = 417.50
1967417 combinations checked, best score 960.00, best since last = 415.00
2020110 combinations checked, best score 960.00, best since last = 417.00
2072782 combinations checked, best score 960.00, best since last = 417.50
2125430 combinations checked, best score 960.00, best since last = 415.00
2178723 combinations checked, best score 960.00, best since last = 420.00
2232024 combinations checked, best score 960.00, best since last = 415.00
2284348 combinations checked, best score 960.00, best since last = 414.50
2336104 combinations checked, best score 960.00, best since last = 412.00
2388410 combinations checked, best score 960.00, best since last = 414.50
2440670 combinations checked, best score 960.00, best since last = 412.00
2493914 combinations checked, best score 960.00, best since last = 412.50
2546698 combinations checked, best score 960.00, best since last = 412.50
2601209 combinations checked, best score 960.00, best since last = 410.00
2653802 combinations checked, best score 960.00, best since last = 410.00
2706840 combinations checked, best score 960.00, best since last = 945.00
2758683 combinations checked, best score 960.00, best since last = 920.00
2810408 combinations checked, best score 960.00, best since last = 915.00
2862090 combinations checked, best score 960.00, best since last = 910.00
2912662 combinations checked, best score 960.00, best since last = 900.00
2963759 combinations checked, best score 960.00, best since last = 897.00
3015391 combinations checked, best score 960.00, best since last = 897.50
3067153 combinations checked, best score 960.00, best since last = 895.00
3120221 combinations checked, best score 960.00, best since last = 890.00
3173796 combinations checked, best score 960.00, best since last = 450.00
3225934 combinations checked, best score 960.00, best since last = 440.00
3279157 combinations checked, best score 960.00, best since last = 430.00
3332750 combinations checked, best score 960.00, best since last = 430.00
3387124 combinations checked, best score 960.00, best since last = 427.50
3441498 combinations checked, best score 960.00, best since last = 425.00
3496638 combinations checked, best score 960.00, best since last = 435.00
3551543 combinations checked, best score 960.00, best since last = 435.00
3606242 combinations checked, best score 960.00, best since last = 425.00
3661322 combinations checked, best score 960.00, best since last = 422.00
3715626 combinations checked, best score 960.00, best since last = 422.50
3769653 combinations checked, best score 960.00, best since last = 420.00
3824466 combinations checked, best score 960.00, best since last = 435.00
3879049 combinations checked, best score 960.00, best since last = 415.00
3933889 combinations checked, best score 960.00, best since last = 402.00
3988612 combinations checked, best score 960.00, best since last = 402.50
4043363 combinations checked, best score 960.00, best since last = 400.00
4097906 combinations checked, best score 960.00, best since last = 415.00
4152552 combinations checked, best score 960.00, best since last = 402.00
4207412 combinations checked, best score 960.00, best since last = 402.50
4261967 combinations checked, best score 960.00, best since last = 400.00
4315123 combinations checked, best score 960.00, best since last = 402.00
4368890 combinations checked, best score 960.00, best since last = 402.50
4421266 combinations checked, best score 960.00, best since last = 400.00
4475211 combinations checked, best score 960.00, best since last = 405.00
4528555 combinations checked, best score 960.00, best since last = 400.00
4581723 combinations checked, best score 960.00, best since last = 399.50
4635157 combinations checked, best score 960.00, best since last = 397.00
4688358 combinations checked, best score 960.00, best since last = 399.50
4741803 combinations checked, best score 960.00, best since last = 397.00
4795037 combinations checked, best score 960.00, best since last = 397.50
4849083 combinations checked, best score 960.00, best since last = 397.50
4903365 combinations checked, best score 960.00, best since last = 395.00
4957688 combinations checked, best score 960.00, best since last = 395.00
5010659 combinations checked, best score 960.00, best since last = 945.00
5063189 combinations checked, best score 960.00, best since last = 920.00
5115474 combinations checked, best score 960.00, best since last = 915.00
5167367 combinations checked, best score 960.00, best since last = 910.00
5218533 combinations checked, best score 960.00, best since last = 900.00
5269767 combinations checked, best score 960.00, best since last = 897.00
5319612 combinations checked, best score 960.00, best since last = 897.50
5370341 combinations checked, best score 960.00, best since last = 895.00
5422293 combinations checked, best score 960.00, best since last = 890.00
5475623 combinations checked, best score 960.00, best since last = 450.00
5529910 combinations checked, best score 960.00, best since last = 440.00
5584308 combinations checked, best score 960.00, best since last = 430.00
5636905 combinations checked, best score 960.00, best since last = 430.00
5689335 combinations checked, best score 960.00, best since last = 427.50
5742904 combinations checked, best score 960.00, best since last = 425.00
5795519 combinations checked, best score 960.00, best since last = 435.00
You are now in away mode, chat will update more slowly until you say something.

5847975 combinations checked, best score 960.00, best since last = 435.00
5901000 combinations checked, best score 960.00, best since last = 425.00
5952762 combinations checked, best score 960.00, best since last = 425.00
6005246 combinations checked, best score 960.00, best since last = 422.50
6057946 combinations checked, best score 960.00, best since last = 420.00
6110484 combinations checked, best score 960.00, best since last = 435.00
6163675 combinations checked, best score 960.00, best since last = 415.00
6218360 combinations checked, best score 960.00, best since last = 415.00
6271429 combinations checked, best score 960.00, best since last = 402.50
6325659 combinations checked, best score 960.00, best since last = 400.00
6378713 combinations checked, best score 960.00, best since last = 412.00
6432081 combinations checked, best score 960.00, best since last = 415.00
6486495 combinations checked, best score 960.00, best since last = 402.00
6538290 combinations checked, best score 960.00, best since last = 402.50
6591925 combinations checked, best score 960.00, best since last = 400.00
6645605 combinations checked, best score 960.00, best since last = 402.00
6698462 combinations checked, best score 960.00, best since last = 402.50
6751730 combinations checked, best score 960.00, best since last = 400.00
6804331 combinations checked, best score 960.00, best since last = 405.00
6857817 combinations checked, best score 960.00, best since last = 399.50
6909793 combinations checked, best score 960.00, best since last = 397.00
6964596 combinations checked, best score 960.00, best since last = 399.50
7016197 combinations checked, best score 960.00, best since last = 397.00
7070119 combinations checked, best score 960.00, best since last = 397.50
7122508 combinations checked, best score 960.00, best since last = 397.50
7175945 combinations checked, best score 960.00, best since last = 395.00
7228761 combinations checked, best score 960.00, best since last = 395.00
7281065 combinations checked, best score 960.00, best since last = 957.00
7330166 combinations checked, best score 960.00, best since last = 937.00
7378490 combinations checked, best score 960.00, best since last = 932.00
7427243 combinations checked, best score 960.00, best since last = 927.00
7475485 combinations checked, best score 960.00, best since last = 922.00
7522725 combinations checked, best score 960.00, best since last = 912.00
7569696 combinations checked, best score 960.00, best since last = 909.00
7617098 combinations checked, best score 960.00, best since last = 909.50
7664525 combinations checked, best score 960.00, best since last = 907.00
7711540 combinations checked, best score 960.00, best since last = 907.00
7762665 combinations checked, best score 960.00, best since last = 462.00
7812496 combinations checked, best score 960.00, best since last = 452.00
7861985 combinations checked, best score 960.00, best since last = 442.00
7911242 combinations checked, best score 960.00, best since last = 442.00
7961679 combinations checked, best score 960.00, best since last = 439.00
8012774 combinations checked, best score 960.00, best since last = 439.50
8062462 combinations checked, best score 960.00, best since last = 437.00
8112967 combinations checked, best score 960.00, best since last = 447.00
8162747 combinations checked, best score 960.00, best since last = 447.00
8212608 combinations checked, best score 960.00, best since last = 437.00
8264751 combinations checked, best score 960.00, best since last = 437.00
8314489 combinations checked, best score 960.00, best since last = 434.50
8364188 combinations checked, best score 960.00, best since last = 432.00
8414049 combinations checked, best score 960.00, best since last = 447.00
8464541 combinations checked, best score 960.00, best since last = 427.00
8514299 combinations checked, best score 960.00, best since last = 427.00
8564595 combinations checked, best score 960.00, best since last = 414.00
8612756 combinations checked, best score 960.00, best since last = 414.50
8662471 combinations checked, best score 960.00, best since last = 412.00
8710695 combinations checked, best score 960.00, best since last = 427.00
8760441 combinations checked, best score 960.00, best since last = 414.00
8809708 combinations checked, best score 960.00, best since last = 414.50
8859092 combinations checked, best score 960.00, best since last = 412.00
8908436 combinations checked, best score 960.00, best since last = 414.00
8958470 combinations checked, best score 960.00, best since last = 414.00
9007196 combinations checked, best score 960.00, best since last = 414.50
9056395 combinations checked, best score 960.00, best since last = 412.00
9105668 combinations checked, best score 960.00, best since last = 417.00
9155796 combinations checked, best score 960.00, best since last = 411.50
9204675 combinations checked, best score 960.00, best since last = 409.00
9255471 combinations checked, best score 960.00, best since last = 409.00
9306185 combinations checked, best score 960.00, best since last = 411.50
9355907 combinations checked, best score 960.00, best since last = 409.00
9405070 combinations checked, best score 960.00, best since last = 409.50
9456118 combinations checked, best score 960.00, best since last = 409.50
9504035 combinations checked, best score 960.00, best since last = 407.00
9553305 combinations checked, best score 960.00, best since last = 407.00
9602024 combinations checked, best score 960.00, best since last = 942.00
9650850 combinations checked, best score 960.00, best since last = 922.00
9699060 combinations checked, best score 960.00, best since last = 917.00
9748257 combinations checked, best score 960.00, best since last = 907.00
9797528 combinations checked, best score 960.00, best since last = 897.00
9847028 combinations checked, best score 960.00, best since last = 897.00
9896619 combinations checked, best score 960.00, best since last = 894.00
9946046 combinations checked, best score 960.00, best since last = 894.50
9993746 combinations checked, best score 960.00, best since last = 892.00
10044259 combinations checked, best score 960.00, best since last = 887.00
10095508 combinations checked, best score 960.00, best since last = 447.00
10146603 combinations checked, best score 960.00, best since last = 437.00
10196526 combinations checked, best score 960.00, best since last = 427.00
10249110 combinations checked, best score 960.00, best since last = 427.00
10299865 combinations checked, best score 960.00, best since last = 424.50
10350233 combinations checked, best score 960.00, best since last = 422.00
10401110 combinations checked, best score 960.00, best since last = 432.00
10453331 combinations checked, best score 960.00, best since last = 432.00
10505385 combinations checked, best score 960.00, best since last = 422.00
10557898 combinations checked, best score 960.00, best since last = 422.00
10610275 combinations checked, best score 960.00, best since last = 419.00
10661838 combinations checked, best score 960.00, best since last = 419.50
10712688 combinations checked, best score 960.00, best since last = 432.00
10763703 combinations checked, best score 960.00, best since last = 412.00
10813893 combinations checked, best score 960.00, best since last = 412.00
10865410 combinations checked, best score 960.00, best since last = 399.00
10916220 combinations checked, best score 960.00, best since last = 399.50
10968591 combinations checked, best score 960.00, best since last = 397.00
11020766 combinations checked, best score 960.00, best since last = 412.00
11073345 combinations checked, best score 960.00, best since last = 399.00
11124365 combinations checked, best score 960.00, best since last = 399.50
11176860 combinations checked, best score 960.00, best since last = 397.00
11229021 combinations checked, best score 960.00, best since last = 399.00
11282647 combinations checked, best score 960.00, best since last = 399.50
11334196 combinations checked, best score 960.00, best since last = 397.00
11385536 combinations checked, best score 960.00, best since last = 399.00
11435753 combinations checked, best score 960.00, best since last = 402.00
11488488 combinations checked, best score 960.00, best since last = 396.50
11540202 combinations checked, best score 960.00, best since last = 394.00
11593078 combinations checked, best score 960.00, best since last = 396.50
11644305 combinations checked, best score 960.00, best since last = 394.00
11695521 combinations checked, best score 960.00, best since last = 394.50
11745538 combinations checked, best score 960.00, best since last = 394.50
11796459 combinations checked, best score 960.00, best since last = 392.00
11846619 combinations checked, best score 960.00, best since last = 392.00
11896177 combinations checked, best score 960.00, best since last = 942.00
11944812 combinations checked, best score 960.00, best since last = 922.00
11993446 combinations checked, best score 960.00, best since last = 917.00
12041470 combinations checked, best score 960.00, best since last = 907.00
12090380 combinations checked, best score 960.00, best since last = 907.00
12139309 combinations checked, best score 960.00, best since last = 897.00
12188419 combinations checked, best score 960.00, best since last = 894.00
12236584 combinations checked, best score 960.00, best since last = 894.50
12285642 combinations checked, best score 960.00, best since last = 892.00
12334726 combinations checked, best score 960.00, best since last = 892.00
12385555 combinations checked, best score 960.00, best since last = 447.00
12435821 combinations checked, best score 960.00, best since last = 437.00
12485818 combinations checked, best score 960.00, best since last = 427.00
12535496 combinations checked, best score 960.00, best since last = 427.00
12587001 combinations checked, best score 960.00, best since last = 424.00
12638178 combinations checked, best score 960.00, best since last = 424.50
12690132 combinations checked, best score 960.00, best since last = 432.00
12739852 combinations checked, best score 960.00, best since last = 432.00
12789689 combinations checked, best score 960.00, best since last = 422.00
12839612 combinations checked, best score 960.00, best since last = 422.00
12890068 combinations checked, best score 960.00, best since last = 419.00
12939924 combinations checked, best score 960.00, best since last = 419.50
12989703 combinations checked, best score 960.00, best since last = 417.00
13039138 combinations checked, best score 960.00, best since last = 432.00
13089203 combinations checked, best score 960.00, best since last = 412.00
13139514 combinations checked, best score 960.00, best since last = 412.00
13191100 combinations checked, best score 960.00, best since last = 399.50
13241501 combinations checked, best score 960.00, best since last = 397.00
13292200 combinations checked, best score 960.00, best since last = 409.00
13341334 combinations checked, best score 960.00, best since last = 412.00
13392458 combinations checked, best score 960.00, best since last = 399.00
13442743 combinations checked, best score 960.00, best since last = 399.50
13493568 combinations checked, best score 960.00, best since last = 397.00
13542206 combinations checked, best score 960.00, best since last = 399.00
13592312 combinations checked, best score 960.00, best since last = 399.50
13642469 combinations checked, best score 960.00, best since last = 397.00
13695245 combinations checked, best score 960.00, best since last = 402.00
13745658 combinations checked, best score 960.00, best since last = 397.00
13796696 combinations checked, best score 960.00, best since last = 396.50
13847213 combinations checked, best score 960.00, best since last = 394.00
13897705 combinations checked, best score 960.00, best since last = 396.50
13947367 combinations checked, best score 960.00, best since last = 394.00
13998319 combinations checked, best score 960.00, best since last = 394.50
14047954 combinations checked, best score 960.00, best since last = 394.50
14098342 combinations checked, best score 960.00, best since last = 392.00
14148201 combinations checked, best score 960.00, best since last = 392.00
14184588 combinations checked, best score 960.00, best since last = 387.00

Note that
1) it took 40 seconds (and 380k combinations) to find the best score
2) most of the scores are either in the 890-960 range, or 430-460 range
3) there are results way down (2.7M comb., and again at 5M comb, and especially at 7.2M comb, less so at 9.6M, and so on) that are back in the >890 range, and different synergies might have pushed some of those over the optimal line
4) holy moly 14M combinations, 22 minutes O_O

I suppose there's no way to teach maximizer/evaluator that a synergetic item has a possible extra "worth" of 1/N of the synergy bonus (where N is number of items participating in the synergy)? Especially since it's complicated by items like brimstone and cloathing whose synergy bonus depends on number of them equipped ...
Because if we could do that, then maybe we could do some simplistic alpha(?)-pruning during the maximalization itself, based on comparing the best-score-so-far with we-can-prove-this-is-an-upper-bound-for-this-combination at every slot (sum of upper-bound scores from all already selected items + sum of best upper-bound scores for all not-yet-selected slots).

Darzil · Feb 15, 2014

xKiv said:
I suppose there's no way to teach maximizer/evaluator that a synergetic item has a possible extra "worth" of 1/N of the synergy bonus (where N is number of items participating in the synergy)? Especially since it's complicated by items like brimstone and cloathing whose synergy bonus depends on number of them equipped ...
Because if we could do that, then maybe we could do some simplistic alpha(?)-pruning during the maximalization itself, based on comparing the best-score-so-far with we-can-prove-this-is-an-upper-bound-for-this-combination at every slot (sum of upper-bound scores from all already selected items + sum of best upper-bound scores for all not-yet-selected slots).

That's basically the sort of thing I'm suggesting for outfits and two item synergies. It should be easy enough to compare them with the best basic items in the same slots. Brimstone, Cloathing, Hobo and Smithsness are a bit trickier, and often best, so I'm not suggesting changing them. They also tend to end up with large scores.

roippi · Feb 15, 2014

I still think trying to do it all in one pass is the wrong approach. My thoughts:

First, do a straightforward maximization with shortlists. Don't add in any synergistic items. Find the best spec.

Then, sequentially try adding entire synergistic sets to the spec - inserting the entire set into the spec if the score improves. Do this sequentially for all synergistic sets - probably sorted by total set score or number of items in the set (maybe both), descending. Once you're out of sets to try, you're done.

This adds a paltry n combinations to test, where n is the number of sets, instead of (n[sub]i[/sub]k[sub]i[/sub])! where k[sub]i[/sub] is the ith set's number of elements. Might have the math wrong on that last bit, but point is that it's a lot, compared to basically none

This heuristic works for brimstone/cloathing/whatever just fine. I'm certain it will end up with not-quite-optimal results some percentage of the time, which means it would probably need a checkbox somewhere. It would be very fast to run, though.

Theraze · Feb 15, 2014

So does that mean that the maximizer will no longer suggest using 3 parts of brimstone gear if it's best, as it often does for me when I have to wear the makeshift scuba or use a ranged weapon or something similar but the benefits of synergies mean that it beats out 'normal' gear?

roippi · Feb 15, 2014

Obviously I left out some complications. +equip imperatives would imply that slots masked by that item need to be omitted from each synergy set, and synergies recalculated accordingly (some sets discarded entirely as that would break the synergy).

ereinion · Feb 26, 2014

Um... So I don't mean to nag, but I am wondering if any progress has been made on this feature... Today I think my copy of mafia made a personal record on spending ~3 hours on testing 181.3M combinations for this maximizer string: item, equip pantsgiving, equip navel ring, sea.

I think some of the problem was that I had forgotten to move my selection away from pullable/buyable on the equipment selection, but even so it seems a bit excessive. It didn't change all that much in the last few combinations checked either:

Code:

101902043 combinations checked, best score 380.94
...
181229330 combinations checked, best score 380.94
181297079 combinations checked, best score 380.94
181314048 combinations checked, best score 380.94

(the first value I wrote down was at ~100M. It may well have reached 380.94 before that)

Feature - Implemented Let maximizer stop when it is not finding a better score

Developer

Developer

Developer

Developer

Member

Developer

Developer

Active member

Developer

Developer

Member

Active member

Developer

Active member

Active member

Developer

Developer

Active member

Developer

Member