August 22, 2018 | Author: Mircea Popescu

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!

Category : S.MG  | 16 responses.