Feature - Rejected Add storage capabilities to maximize for query optimization purposes

[Ulti]

I'm sure we can agree there's gotta be a better way of accomplishing this and having to wait for the same maximize query each day in case you gained access to a new item:

Maximizing (1st time may take a while)...
15711     combinations checked, best score 1,177.74
34013 combinations checked,     best score 1,177.74
52626 combinations checked, best score 1,177.74
71261     combinations checked, best score 1,177.74
90072 combinations checked,     best score 1,177.74
108762 combinations checked, best score 1,177.74
127482     combinations checked, best score 1,177.74
146291 combinations checked,     best score 1,177.74
164537 combinations checked, best score 1,177.74
180528     combinations checked, best score 1,177.74
196353 combinations checked,     best score 1,177.74
212652 combinations checked, best score 1,177.74
229142     combinations checked, best score 1,177.74
245383 combinations checked,     best score 1,177.74
261457 combinations checked, best score 1,177.74
277927     combinations checked, best score 1,177.74
294068 combinations checked,     best score 1,177.74
310399 combinations checked, best score 1,177.74
327137     combinations checked, best score 1,177.74
343764 combinations checked,     best score 1,177.74
360995 combinations checked, best score 1,177.74
377714     combinations checked, best score 1,177.74
394767 combinations checked,     best score 1,177.74
411847 combinations checked, best score 1,177.74
428975     combinations checked, best score 1,177.74
446212 combinations checked,     best score 1,177.74
463280 combinations checked, best score 1,177.74
480404     combinations checked, best score 1,177.74
496696 combinations checked,     best score 1,177.74
512945 combinations checked, best score 1,177.74
529913     combinations checked, best score 1,177.74
546155 combinations checked,     best score 1,177.74
562826 combinations checked, best score 1,177.74
579471     combinations checked, best score 1,177.74
596619 combinations checked,     best score 1,177.74
613734 combinations checked, best score 1,177.74
631225     combinations checked, best score 1,177.74
648276 combinations checked,     best score 1,177.74
665119 combinations checked, best score 1,177.74
682419     combinations checked, best score 1,177.74
699941 combinations checked,     best score 1,177.74
717403 combinations checked, best score 1,177.74
734878     combinations checked, best score 1,177.74
751452 combinations checked,     best score 1,177.74
768750 combinations checked, best score 1,177.74
786082     combinations checked, best score 1,177.74
802816 combinations checked,     best score 1,177.74
820378 combinations checked, best score 1,177.74
837889     combinations checked, best score 1,177.74
855502 combinations checked,     best score 1,177.74
872407 combinations checked, best score 1,177.74
890083     combinations checked, best score 1,177.74
907494 combinations checked,     best score 1,177.74
925305 combinations checked, best score 1,177.74
943179     combinations checked, best score 1,177.74
960726 combinations checked,     best score 1,177.74
978739 combinations checked, best score 1,177.74
996724     combinations checked, best score 1,177.74
1014354 combinations checked,     best score 1,177.74
1032147 combinations checked, best score 1,177.74
1050055     combinations checked, best score 1,177.74
1067857 combinations checked,     best score 1,177.74
1085815 combinations checked, best score 1,177.74
1103216     combinations checked, best score 1,177.74
1120983 combinations checked,     best score 1,177.74
1138753 combinations checked, best score 1,177.74
1157099     combinations checked, best score 1,177.74
1176878 combinations checked,     best score 1,177.74
1187840 combinations checked, best score 1,177.74
Putting     on Boris's Helm (askew)...
Equipment changed.
Wielding garbage     sticker...
Equipment changed.
Holding Half a Purse...
Equipment     changed.
Putting on Buddy Bjorn...
Equipment changed.
Putting on     Pantsgiving...
Equipment changed.
Putting on cheap sunglasses...
Equipment     changed.
Putting on Uncle Hobo's belt...
Equipment changed.
Putting     on droll monocle...
Equipment changed.
Putting on Snow Suit...
Equipment     changed.

It had it right on the first line, must it really loop through a million other combinations? (rhetorical question)
In the above my query was:

maximize meat, +equip cheap sunglasses -tie

At first thought, I was thinking a rough estimate flag would be nice.
But, after thinking about the issue a bit longer, I think what we really need is storage capabilities for storing eliminated items to make all future executions of the same query faster. Imagine:

maximize meat, +equip cheap sunglasses -tie +cache ultibot_barf_mountain.txt

In the above it would check if the file "ultibot_barf_mountain.txt" exists, if not create it.
Then loop through the file's contents and add them to an exclusion list for maximize to avoid considering.
Then preform the maximizing logic as usual and add newly discovered items to the exclusion list array for writing purposes if it scores a "0".
Then write to the "ultibot_barf_mountain.txt" file if there's any new items in our exclusion list array.
Presto.
For problematic items, we could add a nocache flag if there happens to be an item out there which doesn't work well with the cache.
As an added bonus, by storing the data in an easy to access map file, scripts can easily clear the cache.
Finally, SVNs can distribute pre-generated exclusion lists to make your first maximize speedy.

I know mafia already has the ability to deal with "cached" maximizing logic the 2nd time in a day which it runs a specific query.
But, what I'm suggesting here can speed up its first execution in a day.

 

[Theraze]

You can set a maximum amount of matches that you'd like it to check. Otherwise, effects or items or zones or... anything else could affect things.

 

[Darzil]

Note that items are eliminated before the first combinations are checked, so this isn't a problem of item elimination. Add debug or 2 debug to see what is going on - The first shows items that are considered and their base score, the second shows all item scores in addition.

If you work out a way to get something to actually work, let me know. At the moment a particular maximization would only be definitely valid as long as none of the following change : Your base stats, your inventory, your meat, your settings, your adventuring zone, florist friar plants, etc.

The way maximizer used to work is that it goes through all available items and works out the best in each slot. It also considers any outfit, synergistic items, and set that gives increasing bonuses with number of pieces.

The way it now works is the same, but also prunes any outfit where the pieces replaced by the best items (aren't better, and any synergistic items where the best items aren't better. It also now gets rid of items competing in slots specified with +equip X (or reduces them for accessories). [note first accessory actually compares with 3rd best, 2nd accessory with 2nd best, and 3rd accessory with best] I added this because increasing item sets (especially Dread) and increasing partial set items (especially Smiths) added loads of 'useful' items to the pool to be evaluated in combination, which slowed it down enormously. I also added Crown of Thrones, Buddy Bjorn and Card Sleeve support, which didn't add much, as I just work out the best thing to stick in them, then consider it if better than the best item. Don't do that for folder holder as things in it are destroyed.

After that it brute forces combinations.

Things that would definitely help speed this up, but I haven't worked out logic for yet :

Comparing all combinations of sets where the number of items affect the bonus (Brimstone, Smiths etc), and throwing out set pieces that are never better than the best individual items in those slots, in all combinations. This would probably have a significant effect, but the logic will be tricky. My gut feel is a few days work, as it's easy to break, and needs huge testing before going live.

Doing something other that brute force of combinations - If the maths logic exists to do this with the mass of constraints around items.

The simplest way to cache results of a script is this - Run maximization, save as outfit, then put on outfit when you want it, thereafter check if outfit exists before running maximization. To clear cache, delete outfit.

 

[Darzil]

Definitely the best candidate for improving things will be pruning Smiths etc. I know that in aftercore for +items that only offhand smiths is worthwhile for me, but I need a logical way to calculate that for all combinations and all characters and all maximization strings. I'm sure it is possible.

 

[xKiv]

I know mafia already has the ability to deal with "cached" maximizing logic the 2nd time in a day which it runs a specific query.

The only ways that can speed up second execution of the same query are
1) having already retrieved mall prices (only applies when you ask maximizer to display mall prices)
b) having a better starting point (i.e. when you still have equipped the things that were chosen by maximizer the last time) - because it doesn't need to consider some of the items you had equipped before the first maximation. So the brute forcing is N1*N2*N3*N4 steps ... instead of (N1+1)*(N2+1)*(N3+1)*(N4+1)*... - those +1 are really big when they each add at least all the other N!*N@*N#*...

Definitely the best candidate for improving things will be pruning Smiths etc. I know that in aftercore for +items that only offhand smiths is worthwhile for me, but I need a logical way to calculate that for all combinations and all characters and all maximization strings. I'm sure it is possible.

How about some sort of heuristic pruning *during* the brute-force phase?
As in, given what's currently being "fixed" in the first few slots, calculate some upper bound on what score is possible from filling the other slots, and if it's lower than "highest score so far", don't bother checking those combinations.
- needs a good upper bound; one that can be calculated quickly (much faster than bruteforcing the remaining combinations), but tight enough that it gets hit significantly often
- each synergy would have to implement some way of calculating possible score additions based on "these slots are fixed with those items, and the remaining slots have such-and-such candidates"
(easier for outfits and other synergies that just check for a particular combination of equips, harder for synergies that calculate score based on equipped number of items in their class?)
- needs some thought put into handling of things like "we are maximizing for items, but have a +item familiar, so +weight increases score ... but nonlinearly"
- needs some thought put into handling of maximizer strings with nontrivial terms

 

[Darzil]

Outfits and synergies pretty much don't matter any more, since we now prune them first. It made a huge difference to processing times (x5-x20 times faster depending on maximization for me in aftercore). No need therefore to prune them during brute force. I suspect if the same was done for stuff like Smithness, Brimstone and Hodgeman's gear it would be much faster again.

 

[Theraze]

b) having a better starting point (i.e. when you still have equipped the things that were chosen by maximizer the last time) - because it doesn't need to consider some of the items you had equipped before the first maximation. So the brute forcing is N1*N2*N3*N4 steps ... instead of (N1+1)*(N2+1)*(N3+1)*(N4+1)*... - those +1 are really big when they each add at least all the other N!*N@*N#*...

Actually, your equipped gear is irrelevant normally, as -current is the normal state, not +current. So your current gear is considered just like anything else in your owned set, and isn't added to the consideration if it's not the best.

 

[Darzil]

In aftercore, anyway. In Ronin/Hardcore +current is still default.