Algorithmics problem seeking experts
Emboldened by recent discussion (did you know that algos is how you say "pain" in Greek btw ?), I should like to propose a problem to the kind readership.
Recitals. As you probably know, Eulora is a Bitcoin-based MMORPG published by Minigame, the MPEx listed corporation which during the years has effortlessly acquired both intellectual (example, further example etc) as well as market-share leadership (example, further example etc) and so following. Economics is a major focus, and realism is a fundamental consideration. Their interplay leads to exactly what you'd expect -- Eulora constitutes by far the most approachable model of industrial activity (and, in many cases, the only remaining). Consequently, the sort of problems your fathers and grandfathers resolved for the military and large commercial concerns, you may either resolve for Eulora or not at all. It's what it is.
The Problem. Most stackable items in Eulora have an associated quality, with 100 considered "average", 1 as a minimum, and 100`000 or so the maximum seen to date (as with most things in Eulora, an actual cap is not known to exist). Two stacks of the same kind can be mixed, and the resulting quality will be the count-weighted average of the two rounded down. It is here that the fun begins : if you mix a stack of 10`000 Coarse Frangible Thread quality 100 with a stack of 10 Coarse Frangible Thread quality 99 you will get a stack of 10`010 Coarse Frangible Thread quality 99. Rounded down, yes, and in the process losing one quality point over 10`000 units, or roughly 100 normal units equivalent. Ouch.
The [current] Solution. Currently, stack mixing relies on a "Towers of Hanoi" approach, whereby given a selection of mixable stacks, the outliers will be mixed so that equal size stacks of the same parity are mixed together until no stacks satisfying these conditions remain. You can review dpb's specification or Mocky's implementation (botactivity.cpp ln 632+) if that helps. The advantages of this algorithm are that it always terminates ; that it works well with any set of stacks of whatever qualities (ie, reasonable performance throughout the space) and that it goes reasonably fast in the general case (I don't recall any practically encountered set gnarly enough so as to take more than a few hundred iterations).
Matter sought. Can you come up with a better algorithm ? Bear in mind that calculation is (relatively) cheap whereas permutation is (relatively) expensive as it requires talking to the server, getting a response etc. Alternatively, can you prove that no better algorithm exists ?
Thanks for reading in any case!
Wednesday, 22 August 2018
You can see an independent, 90 line python reference implementation of my current stacking routine, examples and a concise description of the steps at http://mocky.org/Meanwhile-in-Perfectly-Stacked/
If you wanted a quick way to compare alternate algos to mine, you could modify stacker.py to include your own findBestStackingPair(), or computeNextMove() functions. or just use the same input file format for the test data.
With respect to an optimal solution: since the time I published that, I have come to see that this is indeed not optimal for every case, yet still close to optimal or optimal in many cases. One reason being the simplifying assumption I have listed as my first step: if multiple stacks have the same quality, then fully combine them immediately. This is almost always an optimal move, yet sometimes I've seen that one or two moves can be shaved off a long sequence if you knew just when to not take this step.
Another thing to consider is that the end result is going to be 1 or 2 stacks in the (weighted) middle of the quality range. So the other thing my algo does is to sort the available stacks by quality and then always mix the ones furthest apart first, so as to most quickly converge to the middle. There may be a more optimal selection criteria, but this was the primary insight i gained while manually stacking.
The brute force approach, of course, would be to compute all possible sequences of moves and then select the shortest. The runtime complexity is something like O(N^N!), where N is the number of possible moves at the outset.
Another solution to this problem would be the dynamic programming (dp) approach, where all the solutions are computed recursively based on a recurrence relationship, but with intermediate states memoized and with converging paths coalesced. The runtime complexity is still something like O(N^N). Typically there are 4 or less slots that need stacking (in my noob experience) but, interestingly, since the current max number of slots is about 100, and the number of possible moves is bounded by slot count, and due to the network round trip time for a slot move request, you've got to spend about 2 billion clock cycles per move saved before your cpu will start to become the bottleneck. So this dp approach might even be viable despite the ridiculous time complexity. The output sequence would always be optimal with respect to the number of moves, since all unique paths are examined.
My c++ and python skills are not at the point where I could just bang out the dp solution. but now that you post about it maybe I'll bang out a java solution just to satisfy my curiosity. Examining known optimal output may yield further insight. The insight might even be how many initial moves does it take to make the dp solution cost prohibitive.
Wednesday, 22 August 2018
An interesting problem that I don't have a solution for (yet) is for answering what-if questions like:
given all the reeds in my storage, what's the largest single stack I could get with quality >= 50
or how many more 50q flotsam would I have to mine to get all my current flotsam to stack to 30q
Wednesday, 22 August 2018
> what's the largest single stack I could get with quality >= 50
Let DQ be the desired quality, let TC be the total count.
1. calculate AQ=sum(all reeds count*respective quality)/sum(all reeds count)
2. Calculate AQ/DQ * TC, and return.
> or how many more 50q flotsam would I have to mine
Let DQ be the desired quality, let TC be the total count, let PQ be the produced quality (50).
1. calculate AQ=sum(all flotsam count*respective quality)/sum(all flotsam count)
2. calculate (AQ - PQ)/(DQ - AQ) * TC and return.
Wednesday, 22 August 2018
I would say that this is actually turning into a most interesting discussion.
Seems to me Anon's answers are correct, unless I misunderstand something. I should probably say that
is entirely off base -- I've had >30 slots of varying qualities mixed (on a private implementation of the same algorithm) which would be the basis for the "a few hundred steps at the most" guess.
Wednesday, 22 August 2018
The problem with your calculations anon, is that you have omitted all the interesting parts of the problem:
1) that you can't get *all* the items into a single stack without losing quality (implicit requirement) you'll get them into two stacks (with near certainty).
e.g. 100x50q & 100x51q which cannot be losslessly mixed. Hence 'single stack' criteria.
2) you can't 'mix upwards' unless you actually have the higher quality item. If I have 2x25q, your algo says I can get 1x50q, but this can't be done.
3) if it is the case that the average quality of reeds is below 50 (and it is for me which is why I pose the problem) then you can't mix *all* of the reeds, only the highest quality ones. If you mix too many, as you approach average quality you dip below 50.
So how many to mix, and what will be the result? Maybe the biggest single stack is 60q because there is a way to make it come out almost evenly with only a tiny 59q stack. This info would be nice for auctions where you are selling a single stack.
@MP, I would amend the 'typical' comment to be 'typical while mining' since regardless of how many stacks you have at the beginning, they will be down to 2 (max) after the first restack and will remain there for however many 1000's of mining attempts. And if you get 2 two different quality items in a mining attempt, that's 4.
That said, if you tell me that the typical case for high level miner is to get more than 2 different quality items in the *same* quality band, I'll believe.
Wednesday, 22 August 2018
> you have omitted all the interesting parts of the problem
I apologize, I guess. Bear in mind that interesting is subjective though.
> If I have 2x25q, your algo says I can get 1x50q, but this can't be done.
You didn't asks for algorithms, did you? You asked for answers. Seems to me numbers make better answers than algorithms. And since you multiply with TQ throughout, your claim is not factual anyway.
> If you mix too many, as you approach average
I don't know why this isn't getthing through. Let's try a numeric approach. Suppose you have one reed of each quality from 1 to 100 (inclusive). Applying my formula,
AQ=n(n-1)/2 / n
AQ100 = 44.5
ret = 44.5/50 * 100 = 89.
Indeed by excluding the first eleven reeds, with qualities from 1 to 11, you will obtain a final quality over 50.
Wednesday, 22 August 2018
No, see Anon, your approach requires you to exclude 11 average reeds. But you don't have such a thing as "the average reed" at your disposal, you're dealing with actual reeds such as they are.
It's true that excluding 11 from the "wrong" end of the sorted list is a fine heuristic, but you're discreetely marrying a numeric method with a heuristic approach, meaning your numeric results aren't reliable anymore (practically : you will obtain "a final quality over 50" as you claim, but not the smallest quality over 50, nor arbitrarily close to 50.)
In the end, Mocky has a point, Eulora's a lot more interesting than meets the eye on the first pass.
This is not true because quality bands. Think about this : your example shows a "default" of 100, I use 200, and nevertheless I end up with no less than four, because my mining can actually produce q800+ even if it usually produces q ~100ish.
Moreover, the situation I had in mind was that you just dump your products in storage at the end of a run. The next run, you will probably get different qualities (for instance, because you gain skill, or because the small/tiny proportion interplay is different, or for whatever other long tail reasons), and dump them in also. After however many runs, you have many piles of different qualities in storage, possibly one for each common quality. Looking at my storage right now I got Flotsam of every kind from mid 60s to low 90s. These will have to be mixed, eventually.
This said, I beleive your "optimize for stack size" thoughts are not as important as they seem to you -- the simplest solution to the problem is to just mine more, it's self-resolving so to speak.
Wednesday, 22 August 2018
The use of quality bands does change the number of stacks you have total, but is actually irrelevant to the time complexity of a single optimum stacking computation since only the in-band stacks are considered there will still only be 2 existing stacks in that band (after the first round) plus however many different qualities were just mined *in that band*.
In the degenerate case you use quality band 1 and get maximum number of stacks yet each restack computation is trivial to compute.
But yes, I agree that the case of many stacks in storage is an important one and that my characterization of 'typical' fails to cover it. I do see the issue, I have a similar situation with dozens of different stacks in storage for all basics, although I'm sure with much lower quantity and quality than ~everyone else.
Thursday, 23 August 2018
First (0), if all stacks need to be merged, you cannot do better than taking the mean of all the stacks at once. Your loss can be calculated by the modulo of the weighted sum of items (sum quality * amount) and the sum of the items.
(This should be easy to proof, just proof that you cannot to better than this. You'll also need to prove that you can do worse or else any algorithm would do (this is also not that hard))
Next (1), you can consider 2 different operations (a) mix any 2 stacks (this may incur a loss if the modulo is not zero) (b) split a stack (this occurs a cost as you'll need to go the server).
Now (2), the current algorithm pushes the possible losses in step (a) to the end at the cost of more (b) operations. (For a proof, you would then need to show how this will always end and get the closest to minimal loss, maybe it is even possible to show you'll always get to the exact minimal loss with this algorithm)
If you want to also optimize for a minimal number of (b) operations the algorithm would probably involve first selecting all the possible pairs that can be mixed with zero loss. And once mixed, select the next pairs that could be mixed. If no pairs can mix with zero loss, do a split (how to split in the best way?). You can do this only 2 pairs are left and then "take the loss" if any. Note that the whole even/odd with same amount simplifies the math but is not needed, the goal is to get pairs that mix without loss.
P.S. I was trying this in a "man alone" mode and although I had some interesting thoughts, I could not get to an answer (Probably also, lack of a proper education). So all of this is still a bunch of unfinished thought unfortunately.
Thursday, 23 August 2018
The loss with the present algo is always 0, so that's an easy enough proof.
This situation is possible in exactly one circumstance : when you have exactly two stacks, and they're of different parities. This is used as a stop condition by the current algo.
I think maybe your mental model of what's going on would benefit from a coupla actual mining/crafting runs irl ?
In any case splitting helps nothing, if you do have two stacks of different parities, splitting either results in no benefit, as now you have three stacks, of which one is a parity and the two other are equal quality, so mixing them changes nothing.
Thursday, 23 August 2018
Based on my experience in-game, I made the assumption
1) that the basic unit of action is moving x items from one stack to another, not mixing stacks whole. So if you have 2 stacks of 10 items, there are 20 possible moves (19 if you consider moving the full stack from a to b as the same case as moving full stack b to a). asciilifeform's forum comment and ave1's comment above make me suspect that (at least initially) we didn't share this prior.
Based on how mircea_popescu and diana_coman explained this to me in #eulora I came to understand
2) that the basic unit of *lossless* action is either:
2.1) an instance of (1) where x is the same as the size of the target stack and the quality of a and b are either both even or both odd. or
2.2) any mixing of two stacks where the quality is the same. always in my current algo this is full mix.
If these are wrong, would be good to know. If they are right, good to make sure others know.
Thursday, 23 August 2018
This is not strictly speaking true : taking 11 items out of a quality 120 stack and dropping them on a stack of 132 items quality 55 will result in a stack of 143 items quality 60 with no loss. This'd be the spark through the dielectric, basic properties of numbers, as hinted in the logs.
Thursday, 23 August 2018
Mocky:
Let Na be the size of pile A, Qa quality of same, Nb is size of pile B, Qb is quality of same.
A mix satisfies equation K(Na+Nb) == NaQa + NbQb.
K is the quality of the resulting mix, and must be integer if you want "mass-conservation".
Now work out the table for all 4 possible oddnesses and evennesses for Na,Qa,Nb,Qb, see which ones allow an integer K.
Thursday, 23 August 2018
Which indeed reduces to factorizing the sum of the "masses", ie count-quality products.
Friday, 24 August 2018
Would it be acceptable while mixing quantities of different quality to (sometimes) preserve quality at the expense of quantity (the condition being quality as a number is smaller than quantity)?
Ex: ending in your example with 10 009 Coarse Frangible Thread quality 100
Friday, 24 August 2018
What does this mean, "at the expense of quantity" ? Stack counts are invariant, there's nothing you can do mixing that'll change the quantity of items. That's reserved for crafting.