Orden y concierto

Informática geek, matemáticas, pensamiento crítico y alguna otra cosa de vez en cuando.

2015-02-23

Tangerine Tycoon - Fulliverse

Tangerine Tycoon is an online Flash game written by Gaz Thomas, where you start by clicking on a tangerine to earn one tangerine per click, and then you can purchase buildings to earn them at a certain rate, given by the number of buildings that you have of each kind. There are four sources of income (tangerines), not counting the "running start" perk: clicking on the tangerine, the buildings, the stock market, and gambling. After you buy at least one of each building, you're given the opportunity to jump to another universe, starting again from zero (but with an increased tangerines-per-second rate for the buildings) in order to score more achievements. It's similar to a bunch of games of the genre, and with a touch of humour. In my case, it was the first I've played through. The current version as of this writing is 1.26. The present analysis is based on that version.

If you haven't played it, but plan to, better stop reading now, as this post contains spoilers. You can always get back to this post later.

The achievements screen has 100 entries that you can unlock as you progress, each adding 1% to your current TpS. Some of them are much harder than others. There is one that is really, really hard to get. The title is "The Fulliverse", and the legend reads: "The universe can not hold any more tangerines". It's unlocked when you reach 10300 tangerines. That's close to the limit of a 64-bit float, which is about 1.797E+308 (hey, that's a float notation that the game lacks! I hope that's fixed in a later version). The author imposed a limit slightly below that, to avoid having infinite tangerines and being able to buy everything unlimitedly, I presume. With that limit, there's the paradox that some buildings can't be bought; for example, when the number of mutants is between 7055 and 7253, you'll see the price of each between 1.060E+300 and 1.663E+308. Mutants aren't the best example, I know, as you wouldn't buy them anyway, but it's one that you can easily see. At 7254 and above, the price of mutants is displayed as Infinity (the float overflows).

I'm not going into an analysis of the optimal number of buildings; there is already one except it doesn't specify the optimal strategy about the cat. The base TpS for a cat are 400. The actual TpS (for all, not just the cat) is the base TpS times the percentage resulting from the sum of all the bonuses plus 100 (universe + perks + achievements + 100). You need at least 3 machines to unlock the cat. If you're after all achievements, in the first universes it's always faster to unlock it, and get the achievement corresponding to not unlocking it at a later universe. In that case, you buy 3 machines, letting one of them break, then 5 cats. The time for the cat to appear is random.

When you have all the Improved Efficiency perks, it's usually faster to buy 18 tangerine machines and aim for the lab, skipping the cat, as unlocking it will happen too late most of the times. I often get my first tangerine lab even before the machine explodes. Since I have the Running Start perk maximized, however, I still unlock it, so it doesn't disturb in the next universe and I can get started faster, improving my times screen. My current best for 50K is 0:14.

As your TpS rate increases, the strategy towards the Mutants needs to be changed. Your tangerines grow quadratically when you buy the first Mutant (actually it's faster than quadratic until they reach a spawn rate 14, but that doesn't make a significant difference), but that's too slow when your TpS multiplier is high, and it's faster to get 12 ETs and buy a mutant when available, and from there, increase the heroics up to 25 and wait for the first 5D to be available. That's always assuming you don't use anything else than the main (buildings) screen.

The Tangerine Exchange

One of the greatest features of the game is the stock market. There are five commodities all with the same behaviour. You can buy and sell. When you buy, you have to spend either all your tangerines, or half your tangerines; when you sell, you always sell all the stock you have of that commodity. Their prices range between 10 and 100. Each commodity has a trend, which can be increasing or decreasing. When it is increasing, the next price is given by an increment which is a uniformly distributed random number between –3 and +5, and when it is decreasing, it is incremented by a random number between –5 and +3. The expected value of the price of a commodity with an increasing trend is thus the previous price + 1 on each market tick (ticks happen every 5.5 seconds more or less), and the previous price – 1 if the trend is decreasing. When the trend is increasing and the price is above 80 (that is, 81 or higher), it keeps the same trend for one more tick and then reverses; the same happens when it's decreasing and the price is below 30 (29 or lower). Due to random fluctuation, it can actually go down to 10 even when the trend is increasing, or up to 100 even when the trend is decreasing. The Insider Trading perks reveal the trends, one for each commodity, but you can also figure it out by watching the increments or decrements of the price: if it increases by 4 or 5, the trend is increasing, and if it decreases by 4 or 5, the trend is decreasing. That happens every 4.5 ticks on average.

The following PHP program demonstrates the behaviour of the Tangerine Exchange (the signs indicate the trend, they do not apply to the value):

<?php

function MarketTick(&$prices, &$trends)
{
    for ($i = 0; $i < 5; $i++)
    {
        $trend = $trends[$i];
        if ($trend < 0 && $prices[$i] < 30)
            $trends[$i] = 1;
        else if ($trend > 0 && $prices[$i] > 80)
            $trends[$i] = -1;

        do
        {
            $newprice = $prices[$i] + $trend + mt_rand(-4, 4);
        }
        while ($newprice < 10 || $newprice > 100);
        $prices[$i] = $newprice;
    }
}

$prices = array();
$trends = array();
for ($i = 0; $i < 5; $i++)
{
    $prices[$i] = mt_rand(30, 80);
    $trends[$i] = mt_rand(0, 1) * 2 - 1;
}

do
{
    $oldtrends = $trends;
    MarketTick($prices, $trends);
    for ($i = 0; $i < 5; ++$i)
        printf(" %+4d", $prices[$i] * $oldtrends[$i]);
    echo "\n";
    usleep(5500000);
}
while (true);

Trading at low prices has the advantage that the increments imply a higher percentage than at high prices; for example, an increase from 10 to 11 is a 10% gain (if you bought at 10), but from 99 to 100 it's about 1% gain (if you bought at 99). Buying at above 80 is not recommended because there's no guarantee that you will sell above that price without at least one full decrease-increase round. 80 itself is still safe, assuming it was never above 80 for this run.

Gambling

Trading is helpful, especially at the beginning, but for reaching a Fulliverse achievement, it's too slow. Buying at 25 (a safe-ish price without missing that train) and going up to 50 then repeating, assuming there's another commodity immediately available at 25, would take you an average of more than two minutes, to just duplicate your gains. That's about 7 minutes to multiply your gains by 10. You can be lucky at times and grab a faster train (e.g. 16 happens relatively often) to triplicate or even quadruplicate your gains, but that doesn't happen often enough as to be significant. Fortunately, it's possible to go faster than that by gambling.

Gambling is a double-or-nothing game: you either lose all you have, or get double of what you have. With 50% probability, the expected value of every game is to stay as you are; however, for a repeated game the probability of losing everything increases exponentially as you play, so the strategy of just playing repeatedly obviously leads nowhere, unless the probability of losing once is less than the probability of winning 1000 times in a row, which obviously doesn't happen with this game's limits.

You can increase your chance of winning in two ways: by buying it from the gambling screen (you can buy up to 15 increases; each costs 10x the previous and adds 1% to your chances), and by perks (each perk adds 1%, up to 10 times). At the maximum, the chance of winning is 75%.

How to gamble without losing everything? This part gets tricky. The trick is to use the "Purchase Volume: 50%" feature in the Tangerine Exchange so that you don't lose all you have, using it as a kind of bank. The Insider Trading perks help here, as you can use trending info to ensure that your investment will not result in a loss in average.

There is a possibility of using martingale as a strategy, betting the base amount after each win and using the stock market to double your bet on each loss, as described in the same post linked before. That's a poor strategy in this case, as it only grows your gains linearly, barely taking advantage of the increased win rate, and making it exponentially slow to double your tangerines.

Here's a better strategy. Choose a commodity with an increasing trend, and buy 50%. Go to the Gambling screen, and play. Whatever the outcome, go back to the market, and sell. Rinse, repeat. With careful timing, it's even possible to do it without the value changing, by waiting for the tick to happen between selling and buying, enabling us to use the strategy without caring about the trend.

The analysis of this strategy turns out to be somewhat difficult. At first I did a mistake calculating it. First, if your initial amount of tangerines is n, you invest n/2 in the Exchange, and gamble the other n/2 for double or nothing. Thus if you lose and sell your stock (disregarding gains or loses coming from the stock market), you end up with n/2; and if you win and immediately sell your stock, you end up with 2·(n/2)+n/2 = 1.5·n tangerines. The expected value for every game when the chance of winning is p is therefore p·1.5·n+(1–p)·0.5·n = n·(p+0.5). Therefore, the expected value for a 75% win probability is n·1.25, so our gains will be multiplied by 1.25 after every game, right?

Wrong! It's not so easy. With 75% probability, the win rate is 3 out of 4, so if your gains get multiplied by 1.5 when you win and by 0.5 when you lose, after 4 games your gains will be on average multiplied by 1.5·1.5·1.5·0.5 = 1.6875. That's not the same as 1.25·1.25·1.25·1.25 = 2.44140625 which would be the result if we followed the other reasoning. The actual average multiplier per game for a probability of winning p is 1.5 p·0.51–p, which for p = 0.75 equals 1.1397535 approximately.

With that in hand, we can calculate the minimum percentage at which to try this strategy. Note that, against intuition, it doesn't work for p = 0.5. The expected multiplier for each game with a 50% chance of winning is approximately 0.866025 (it's exactly 0.750.5), therefore you end up losing more than 13% per game on average. Starting with a 64% winning chance, things get better. For 64%, the expected multiplier is approximately 1.01, so you win 1% on average. With 63% or less, you always lose something. I wouldn't risk on a 1% winning probability, though. It would take a huge amount of bets for that 1% to be noticeable. It takes about 231 attempts on average to just double your gains; in the short term, bad streaks can ruin you.

So, for a 75% winning chance, which is the maximum, what is the expected number of games needed to multiply your savings by 10? That's obtained by solving for x in 1.1397535...x = 10, whose solution is x = log(10)/log(1.1397535...) which is approximately equal to 17.6. And to double them? The expected number of games is then slightly less than 5.3. If you time your games with the Exchange ticks as described above, then the time it takes to double your gains is almost 5 times faster when compared to the winnings that you would get using the Exchange alone in the optimistic scenario explained earlier.

Is it possible to do better than that? That's not easy to answer, but I think so. A different strategy is to gamble twice in a row each time, before selling your stock and buying again. At first sight it may seem to not make a significant difference, but once we make the calculations, reality tells us otherwise.

The probability of winning twice in a row for a winning probability of p is p². For p = 0.75 that probability is 0.75² = 0.5625, so more often than not you win twice in a row. Each time you lose you still get n/2 because your other half is safe during both games. But if you win both games, your total after selling your stock is 2·2·(n/2)+n/2 = 2.5·n.

So what's the expected multiplier after each pair of games? In this case, it's 2.5 ·0.51–, which for p = 0.75 equals 1.23635 approximately. Is that clearly better, or are the gains negligible with respect to the previous method? The answer seems to lie somewhere in between. The number of attempts it takes to double your gains is 3.26, which is more than half the 5.3 times it took with the previous method. And since it takes two gambles every time, it takes longer to play, but switching back and forth to the market also adds a constant time independent of how many times you gamble, reducing the relative importance of the increased number of games. So, does one thing compensate the other? I think it feels faster, but that's a personal appreciation and not based on quantitative data, which was too difficult to gather for me. The minimum percentage to make this system return gains raises to 66%.

Note that when you lose the first of the two gambles, you don't need to play the second. That's a timing advantage. Does that introduce bias? I don't think so, but I haven't really thought it through. Also, with this method you can forget about coordinating it with the Exchange ticks, because there isn't enough time. You need to use a commodity with an increasing trend, and hope for some luck. That's kind of a timing advantage too, because coordinating it takes time (to wait for the expected tick). Choosing an increasing trend is important, and more so when losing at gambling. After a win, the market percentage is applied over the n/2 that was invested in the Exchange; the n from the gambling is not affected, therefore the percentage affects only 1/5 of your final tangerines. But when you lose, it affects the total you have remaining. For example, after a decrease in a commodity price from 30 to 27, if you lose that's a 10% decrease, but if you win the overall loss is only 2%. I only waited for the price to raise again when I lost and the Exchange price was low.

And what about a strategy of gambling three times in a row, then? Let's see. The multiplier per win is 4.5·n, and per loss it's the usual n/2. The chance of winning three times in a row is p³, which equals 0.421875 when p = 0.75. The average multiplier for that p is 4.5 p³·0.51–p³ = 4.50.421875·0.50.578125 ≅ 1.2634. That takes about 2.96 cycles to double your gains, and 9.85 to multiply them by a factor of ten. I say negligible when compared to the 10.85 it takes with the two in a row method, considering you have to gamble once more, which also takes its time. The minimum percentage for it to start to be profitable is 69%.

And with a strategy of four times in a row? With the game's limit of 75%, it's not worth it. The gains per cycle for 75% are about 1.2254, which is lower than with the two in a row method. It starts to be profitable at 71%.

So I stuck with the twice in a row strategy to reach that achievement. How many cycles does it take? For a starting point of 1E+75 (reasonable when the Upgod perk is maximized), you need to multiply your gains by 1E+300/1E+75 = 1E+225. Solving for x in 1.23635...x = 1E+225 gives us an average number of trials x of approximately 2441. So it's still a long trip.

But it was fun. The best of it was to figure out all this, of course. I noticed my mistake by running the following simple program. I expected the result to be around 3096 (since 1.253096 equals 1.07E+300), but it was actually above 5000 most often, and never less than 4700. The actual expected number of games with the first strategy and a starting amount of 1 is about 5281, and unsurprisingly, the program output is around that.

<?php

$count = 0;

$money = 1;
do
{
    if (mt_rand(0, 99) < 75)
        $money *= 1.5;
    else
        $money *= 0.5;

    $count++;
}
while ($money < 1e300);

echo "It took $count attempts to reach the goal.\n";

What other strategies are there? Well, I haven't done the math, but there are some more that come to mind. One is to invest 50% in one commodity, and 50% of the remainder in another, so the total invested is 75% and you only gamble 25%. You can then choose how many times to gamble as above. Another more risky one is to do the same, but then sell the 50% one before gambling. Then you're gambling 75% and keeping 25% safe. And there are other possible strategies that don't involve selling the previous stock when you win, but to buy from a different stock, possibly selling the previous one afterwards. I'd like to know if someone does an analysis of them and finds one that gives better results than the ones presented here, or if someone presents some other strategy.

Acknowledgements

I am grateful to Otto Nyberg for pointing out where my error was and leading me in the right direction.

2014-12-26

Unicursal mazes and "Cavern" mazes

Mazes: Generalities

There are many kinds of mazes, and many ways to classify them. Some mazes have loops, but most don't. Most mazes have no inaccessible areas, and are usually drawn on a square grid. The mazes that meet the requirements of having no inaccessible areas (i.e. all passages are connected) and no loops are called perfect mazes.

Mazes are intimately related to graph theory. The most common type of maze can be represented by an undirected graph (but there are also many other types of mazes which need a directed graph to be represented, including arrow mazes and "mazes with rules"), it has no loops (and is therefore a tree) and has every room (vertex) connected to all others. In graph theory terms, that's exactly what a spanning tree is. In maze jargon, that's called a perfect maze. In other words, the terms perfect maze and spanning tree are equivalent, in their respective contexts.

Perfect mazes are the most common type because they meet two desirable properties. First, since there are no loops, the solution (the route from a given vertex labeled "start" to another given vertex labeled "end") is unique, not counting backtracking from a dead end. Second, since they don't have any unreachable areas, they make the most use of the available space (usually a rectangle). Actually, I personally think that the no loop condition makes them kind of boring, because it makes them trivial to solve (by wall-following). But this article is not about solving difficulty. It has more to do with aesthetics and graph theory.

Representing a maze

For a compact representation, two-dimensional mazes are usually represented in a bitmap by having the vertices (rooms, in maze jargon) at odd-numbered rows and columns (assuming the first row and column is 0, as we're usually dealing with bitmap coordinates), then having some cells that are always walls and some cells that may or may not be walls, depending on whether the corresponding graph has an edge at that position (passage) or not (wall).

2D grid graph vs. a compact bitmap template
12×12 grid graph as is commonly represented in a compact way in a cell grid. The white cells are always walls, the black cells are always empty, and the blue cells represent pixels that are to be turned into white or black to give shape to the maze. In the corresponding grid graph, the blue cells represent the edges, the black cells represent the vertices, and the white cells are empty spaces. The cross-faded image depicts the graph itself for comparison. A perfect maze is a spanning tree of that graph.

There's another common way of depicting mazes, using squares with missing sides for the rooms, where the present sides are the walls. But we're not interested in it now.

Observe that a maze constructed using that kind of template will always have the passages and the walls one pixel wide, and that there won't be any walls or passages touching only diagonally. In other words, there are three 2×2 patterns that no 2×2 subset of the bitmap will match: all walls, all passages, and a checkerboard pattern. That's guaranteed by the fact that every single 2×2 subset of the bitmap will always have at least one black cell in one corner (the vertex) and one white cell in the opposite corner (the empty space), regardless of the values of the other two.

Excluded patterns vs. all patterns
The top row shows the 2×2 patterns that will never appear in any 2×2 subset of the maze image (2×2 wall, 2×2 passage, and 2×2 checkerboard in its two variants). The rest of the patterns can appear anywhere.

Unicursal mazes

There is a kind of maze that is... well, hardly a maze actually. It's called a unicursal maze, which is a maze with no dead ends and no loops. That's right: it is just a single path that can be followed from the beginning to the end without finding any intersections in the way. Sounds dull? Keep reading!

A unicursal maze is not necessarily perfect: it may not meet the condition of going through all possible rooms. Obviously, a perfect unicursal maze is a Hamiltonian path in graph theory terms: a path that goes from one point to another, visiting every vertex in the graph exactly once. This equivalence has at least two major implications. First, we can't always have a perfect unicursal maze with any arbitrary starting point and any arbitrary ending point, even in a rectangular grid graph. Second, creating a perfect unicursal maze with chosen endpoints is not a trivial task, if possible at all. Turns out unicursal mazes aren't that dull, after all!

Let's quickly review the conditions that the endpoints must meet, in order to be possible to have a perfect unicursal maze. The maze dimensions should both be 4 or more, or 3×(odd number ≥ 3), to exclude some special cases that are hard to handle, as some have a solution and some don't. The rest of the conditions depend on whether the associated rectangular grid graph has an odd number or an even number of vertices. If the number is even, then the only condition is that the sum of row + column of the starting point and the sum of row + column of the ending point must have different parity. If the number of vertices is odd, the parity of the endpoints must be the same, but there is another condition: they also need to have the same parity as the vertices in the corners. There's a demonstration in [1]. If a rectangular grid graph with the required dimensions meets these conditions, it's guaranteed that at least one Hamiltonian path exists between both. If not, it's guaranteed that none exists. In other words, the conditions are necessary and sufficient for those grid graphs. The conditions for 2×n, 1×n, and 3×(even number) are too complex for this quick synopsis; take a look at the paper if interested. Of course, what is said for m×n is valid also for n×m.

Creating perfect unicursal mazes

So, how to create a random perfect unicursal maze? One possible way is to create a Hamiltonian cycle and break it, using the split points as start and end. This obviously reduces the problem to creating a Hamiltonian cycle. A trick used to create such a cycle consists of applying the following concept: create a regular maze, and then add a wall in the middle of each passage.

Spanning tree and Hamiltonian loop
Perfect maze (left) and unicursal loop resulting from it (right). The loop can be broken at any edge next to one of the exterior walls and parallel to it (marked in red), to give a unicursal maze that starts and ends at a border.

But that method creates unicursal mazes with a very clear pattern: every single-step edge (in the sense of not turning while walking it) is preceded and followed by two-or-more-steps edges. That's certainly not what one expects from a random Hamiltonian path with any signs of uniformity. It is only able to generate a small subset of the possible Hamiltonian paths. Even if the algorithm is modified to enable arbitrary starting and ending points (arbitrary among the ones that meet the necessary conditions for a Hamiltonian path to be possible), that problem will still exist with that method. Is there an algorithm that allows for the whole range of possibilities of Hamiltonian paths?

Fortunately, yes. Not exactly uniformly distributed, but not too far either. It's capable of generating every possible Hamiltonian path, with a probability distribution that is empirically not distinguishable from a uniform distribution. The paper describing the method and the empirical results is [2], and to the surprise of many, including me, it's about polymers. Yes, the molecules. It turns out that random Hamiltonian paths have an important role in the field of polymer chemistry. Live and learn.

Let me outline the method. Start with a non-random, easy to build Hamiltonian path, consisting of going in zig-zag from one end of the top row to one end of the bottom row. Actually, the starting pattern does not matter much, but that's an easy way to build one in a rectangular grid graph. Then repeatedly apply a transformation of that path that they call "backbite", using one of the two endpoints at random every time. A backbite transforms a Hamiltonian path into a different one that is also Hamiltonian, and it consists of the following: from one endpoint, choose a neighbouring vertex at random that is not connected to the current one. If the chosen vertex turned out to be the opposite endpoint, add an edge to it and remove the edge that it was connected to originally. If it is not the opposite endpoint, add an edge that connects to it. That will create a loop for sure, and the destination vertex will now have three edges. One of them will be the one just created and another one will lead to the opposite endpoint. The third edge loops back to itself. Remove it to obtain a graph that is again a Hamiltonian path, but with a different endpoint. That's the backbite move.

Backbite move illustration
Backbite move on a 3×3 graph. Starting with a Hamiltonian path (1), choose an endpoint (red in this case) and a neighbouring vertex at random that is not connected to that endpoint. In this case there's only one, so an edge is added that connects to it (2, in green). The target vertex (3, in green) has two other edges apart from the one just added: one leading to the opposite end (blue) and another looping to ourselves (red). Complete the move by removing the latter, resulting in another Hamiltonian path (4) with a new endpoint (in red). The new endpoint is always one step far diagonally from the original one.

By repeating the backbite move enough times, the authors of the paper show how the resulting path is approximately uniformly distributed, according to several criteria.

This method has two main disadvantages. First, it's not easy to determine when to stop, and given that the backbite move is relatively expensive, making many more moves than necessary to be in the safe side is slow. Second, both endpoints end up at unknown locations.

Another method that also uses the backbite move, is to perform a (non-overlapping) random walk starting from one chosen point, and when it is not possible to go on because all neighbours are already visited, perform one single backbite (on the blocked end only) and then try again the random walk. (One rare exceptional case: if the backbite move leads to the original endpoint, switch endpoints, as we want one of them to be at a fixed location.) Repeat the process indefinitely. Eventually, if the starting endpoint was chosen so that it obeys the conditions, we will obtain a Hamiltonian path with a known start and a random end. A series of backbites on that end can help us now place the endpoint at a desired location (always chosen by the rules). That path may not be uniform, but visually it's hard to tell the difference. The main advantage is that it has better guarantees that all edges are visited and randomized. With the other method, some areas may remain unvisited by the repeated backbite and therefore left in their original state.

Unicursal maze (Hamiltonian path) and unicursal loop (Hamiltonian cycle)
12×12 perfect unicursal maze (Hamiltonian path) and 12×12 perfect unicursal loop (Hamiltonian cycle) created with the technique described.

Cavern mazes

It is possible to construct mazes that do not obey the pattern in the first figure, that is, mazes whose walls are not aligned in a grid of the kind described. Every pixel would be a vertex, and every pair of passage pixels vertically or horizontally adjacent would be connected by an edge. These mazes are no longer spanning trees of a grid graph, as there are many disconnected vertices (one per wall pixel), but compared to the perfect mazes we've seen so far, they share the characteristics of having no isolated connected areas or loops and being trees, so we'll extend the concept of "perfect maze" to also include those that have isolated vertices, for discussion purposes. Walter D. Pullen [3] calls those "cavern" mazes, and we're using the same term here for lack of any others. There are several ways to construct them. Usually, not all the 2×2 exclusion patterns mentioned earlier are absent in the mazes created this way; most of the times, there are 2×2 checkerboards and/or 2×2 walls and/or 2×2 passages at some points.

Let's take as an example the maze generated by the good old ZX81 program Mazogs. Mazogs is a game in which you are in a 62×46 dungeon or cavern, with passages organized like a maze, and your aim is to search for the hidden treasure in the cavern with the help of the prisoners scattered around the maze, avoiding to run into a Mazog (or if you do, you better hava a sword with you; swords are also scattered around), then return to the entrance. It had a very well done atmosphere at the time (1982). You really felt like it was a cavern with dark passages. And part of the ambience was provided by the fact that the maze did not look too geometric, but more like random passages in a real cavern. When its successor, Maziacs, came for the ZX Spectrum, I was disappointed because it lost that feeling due to the change in the style of maze: it was of the kind described at the beginning, and thus no longer a cavern maze. It lost the sensation of being dungeon-ish, and felt more geometric due to the longer passages. The added complications didn't really improve the gameplay in my opinion. But the point here is that the shape of the maze did have an important role in the overall feeling of the game. The name "cavern" is well deserved.

One characteristic of the mazes created by Mazogs is that it could easily create 2×2 checkerboard blocks, as well as wall-only 2×2 blocks, but never 2×2 passage blocks.

Mazogs maze
Example of a maze generated by Mazogs. "1" is the player (at the starting point in this case), "T" is the treasure, "X" are mazogs, "S" are swords, "P" are prisoners that reveal the solution when run into. The generation method is a "hunt and kill" variant, where the hunt phase is random rather than sequential, and the kill phase considers whether there are passages next to the candidate to be carved, and carves one cell at a time. The program has a time limit for generating the maze, and a minimal amount of passages for it to be considered valid. If that minimum is not met, the algorithm restarts.

Pullen has a program for Windows, called Daedalus, that is able to generate cavern mazes with no 2×2 checkerboards, and you can decide whether you want no 2×2 passages, or no 2×2 walls, but not both (unless you're really, really lucky and get one by chance). Daedalus runs under Wine although with some flicker, at least in my system.

Daedalus Cavern maze with 2×2 walls (left) and 2×2 passages (right)
Cavern mazes generated by Daedalus. Neither has a 2×2 checkerboard pattern (passages touching diagonally). The one on the left was generated by passage carving, and has 2×2 walls. The one on the right was generated by wall adding, and has 2×2 passages. The scarceness of walls that start at the border in the right image (there are long passages that run throughout most of the side walls) is typical in this program when generating a cavern maze this way.

Is it possible to generate cavern mazes that are guaranteed to meet all three criteria (no 2×2 checkerboard, walls, or passages)? The answer is of course yes, but here comes the funny part: the problem of generating such a maze is equivalent to generating a Hamiltonian cycle in a grid graph.

How's that possible? Note the frontier between the wall and the passage, imagining it as a graph. Having a 2×2 checkerboard pattern somewhere, would mean we have a vertex with four edges converging to it, but that's excluded. Having a 2×2 wall or passage would mean that one vertex has no edges leading to it, but these patterns are also excluded. Every other combination of 2×2 cells has a frontier that has exactly 2 edges, therefore every vertex of that graph has exactly 2 edges connecting it. That means that it must form loops that pass through every vertex in the graph. But since it encloses the passage area, which is (by definition of a perfect maze) one single area, it can't form more than one loop. Consequently, it is one single loop that passes through all vertices, i.e. a Hamiltonian cycle. Effectively, this process is equivalent to doing the reverse operation to adding a wall in between the passages, that we mentioned as one method of creating a perfect unicursal maze. In this case, since the loop encloses a wall, we remove it.

13×13 Cavern maze resulting from the 12×12 Hamiltonian cycle shown before
This is a 13×13 cavern maze generated by using the 12×12 Hamiltonian cycle shown earlier as the frontier of the walls. It has no 2×2 checkerboard, wall or passage block.
Graph for the cavern maze above
Equivalent graph for the cavern maze above. The red dots represent unconnected vertices.
65×65 cavern maze
65×65 cavern maze generated from a 64×64 Hamiltonian cycle.

Cavern mazes generated this way look quite nice in my opinion. Of course that's a question of taste, so YMMV. One problem they have, however, is that, just like with uniform random spanning trees, they tend to have lots of short passages, instead of being primarily made of long winding ones that would play a better role in confusing the player. So far I've found no solution for this, but a promising idea is to start by building a cavern maze with the desired properties except for the 2×2 wall blocks, then modify it to make these blocks disappear. It's not easy to do the latter; it's impossible to make just one single block disappear (other than by creating a 2×2 passage block, which obviously isn't the desired result). However, it's possible to use two such blocks so that with local modifications in between, they cancel each other. So far I haven't figured out an algorithm that is able to do that, but I've been able to do it by hand. Not all pairs of 2×2 blocks can be cancelled this way; they have to be of opposite parity (the parity of such a block is the parity of its central vertex, when seen as the frontier graph, obtained from the sum of its row and column, modulo 2).

Cancelling blocks example
Example of a section of a maze that has two 2×2 wall blocks (left) with the parity of the vertices marked with green and yellow dots, showing that the blocks have different parity. When that's the case, it's possible to modify some pixels in such a way that the blocks cancel each other and disappear. The image on the right shows one of many possible ways to do it.

Is there a move, similar to the backbite, that allows displacing an isolated vertex of a certain parity to another position without changing any characteristics of the graph? If so, joining vertices of opposite parity should not be difficult: when they are next to each other, usually one pixel change suffices to cancel both. I'd be interested in knowing about an algorithm that can do that.

References

[1] Alon Itai, Christos H. Papadimitriou and Jayme Luiz Szwarcfiter, Hamilton paths in grid graphs. SIAM Journal of Computing, 11(4):676—686, 1982.
[2] Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen and Jané Kondev: Secondary Structures in Long Compact Polymers (2008) (preprint).
[3] http://www.astrolog.org/labyrnth/daedalus/daedalus.htm

2013-08-07

Inside-out Fisher-Yates algorithm

The inside-out Fisher-Yates shuffling algorithm looks like this:

  outputlength = 0
  while there are input elements:
    r := random number between 0 and outputlength inclusive
    if r <> outputlength:
      output[outputlength] := output[r]
    output[r] := next input element
    outputlength := outputlength + 1

Here's an animation that shows it in action:

For artistic purposes, the animation shows how the "pushed" element goes to the end of the array after the position where it was originally is replaced by the incoming element. In the algorithm, that step actually precedes the replacement.

2013-05-11

From cryptoloop to dm-crypt in Debian

I've been struggling with it for a while and finally found the solution. I was using cryptoloop in Lenny and needed to migrate to Squeeze, from which cryptoloop is removed. The tutorials tell me to just use cryptsetup, but none of them mentions one important detail.

From the dm-crypt page:

The defaults [for cryptsetup] are aes with a 256 bit key, hashed using ripemd160. [...]

Migration from cryptoloop and compatibility

[...]

You'll need to figure out how your passphrase was turned into a key to use for losetup. [...]

That last one turned out to be very sound advice. My losetup man page says in the section about the -e (encryption) option:

AES128 AES
Use 128 bit AES encryption. Passphrase is hashed with SHA-256 by default.

Aaaaaah... so that was why the decryption wasn't correctly giving a mountable volume. Ok, there's a -h option to select the hash, and a -s option to select the cipher's block size which I already was using. Putting all together:

cryptsetup create -c aes -s 128 -h sha256 mappername devicename

finally did the trick and I could mount my encrypted device. The whole recipe to substitute mount -o loop,encryption=AES file mountpoint was:

modprobe dm-mod
losetup -f # outputs /dev/loopX to be used below
losetup /dev/loopX file
cryptsetup create -c aes -s 128 -h sha256 mappername /dev/loopX
mount /dev/mapper/mappername mountpoint

2013-05-04

You know you've played too much Elite when...

... you want to visit Ribilebi just to taste their famous fabulous goat soup.

2013-04-25

Wii Sports - Tennis skill points system

I've been for a while trying to figure out the skill points rating system used by Wii Sports Tennis. I think I have it mostly figured out for the case of always the same rivals. My current problem is how the next rivals' skill level is determined.

First, a brief intro. The ranking system only applies to playing against the computer (otherwise I guess it would be too easy to cheat by playing against an unresponsive player). It rewards you more the more skilled your rivals are, the better score you get and the lower your ranking is, and penalizes you harder the higher your ranking is, the lower your score is and the worse your rivals are. If you win, your rivals' skill grows (up to a maximum); if you lose, it decreases (down to a minimum). There, I said it was brief.

The variables that influence the skill points are: current skill, current rival's skill, and score in each game (note "game", not "match", though I haven't thoroughly investigated multiple game matches). How exactly?

The skill points are a floating point number, of which only its integer part (its floor, i.e. rounded down, not rounded to nearest) is visible. A combination of the game score and the rival's skill gives the limit (the asymptote) for an exponential decay function that when starting with zero points, has the form a·(1-b-t) for a certain asymptote a and a certain base b which equals 20/19 in this case, with t being the number of games played so far. That function is "factory-tuned" as follows: first, with a zero skill rival and starting at zero points, depending on the score you get, you earn the following skill points:

  • Win 40-0: 60 points
  • Win 40-15: 52.5 points
  • Win 40-30: 45 points
  • Win Adv-40: 40 points
  • Lose 40-Adv: 20 points
  • Lose 30-40: 15 points
  • Lose 15-40: 7.5 points
  • Lose 0-40: 0 points

(Note it doesn't matter how you reach the win or lose situation, or how many times you get to deuce during a game; only the final result matters). The asymptote of the exponential function will always be 20 times that value:

  • Series of 40-0 wins: the asymptote will be 1200 points
  • Series of 40-15 wins: the asymptote will be 1050 points
  • Series of 40-30 wins: the asymptote will be 900 points
  • Series of Adv-40 wins: the asymptote will be 800 points
  • Series of 40-Adv losses: the asymptote will be 400 points
  • Series of 30-40 losses: the asymptote will be 300 points
  • Series of 15-40 losses: the asymptote will be 150 points
  • Series of 0-40 losses: the asymptote will be 0 points

Based on the above, we can now figure out the function and parameters for a zero skill rival. Here it is:

Snew = (a + 19·Sprevious)/20

where a is the asymptote, and Sprevious and Snew are the skill points before and after the game, respectively. The 20 (and the 19 which is just one less than that) is the multiplier between the score in the first game and the corresponding asymptote as explained above.

The effect of the rival's skill seems to be to offset the asymptote. When the rival's skill is maxed out (Elisa and Sarah), the offset is 1200. That gives the famous asymptote of 2400 that nobody can reach (because that's how asymptotes work). For example, if you won all your games by 40-15 against Elisa and Sarah, the asymptote would be 2250 (1200+1050). That also means that when you get a skill of 2250 or more, you always lose points if you don't win 40-0 (ok, ok, technically it's more proper to say that you never earn points).

(By the way, there's a couple claims of reaching more than 2399 points but I don't believe them. One claims to get 2403 but it's obviously fake; the other claims 2400 exactly.)

The only big remaining problem I have is how to determine what's the skill of the next rival you will confront. Using a spreadsheet, I've found that the asymptote offset seems to resemble a sigmoid function as the player keeps winning, which is funny because the Elo rating system uses it, though not in the same way, I think (I know very little about it so I can't judge). And not only the offset needs to be determined, but it would be nice to find out the actual ranking too. There seems to be some kind of higher level rounding in the rivals' visible skills: you don't face rivals with a skill of 1317, for example; they are rounded to 1300.

Other problems I have not investigated are how a second player affects your rating, and how exactly your score varies in case of a multi-set match. If you win all games of a match with the same score, the effect on the skill points seems to be like playing these games in one-game matches one by one, except that the rivals' skill doesn't change.

Game Logs

If you want to help, here are some logs of scores I got from the game and the values I got from the spreadsheet. If there is a testable hypothesis that you think could be resolved with an experiment to help determine the rivals formula, but don't feel like launching Tennis just to test, please say so in the comments, and I may take the task of finding out the result. Currently I'm quite lost on how to determine it.

The first table below determines how many points you get at start. It gave me the first hints on how the scoring system works. Note that even if the points are rounded down, the skill raises to 8 and 53 instead of 7 and 52 for 15-40 and 40-15 respectively. That's because the first rivals skill is not zero, and that difference makes that score give something between 0.5 and 1 more points, that bumps the number. I actually tested that later (see Table 6 below).

Unlike the rest, this table is restarted using a new guest player at every row. The rest are restarted only for the first row.

Table 1: Scores at the beginning
Rivals
skill
Skill
before
ScorePointsSkill
after
Next
rivals
skill
63/49040-0+606083/65
63/49040-15+535378/49
63/49040-30+454573/49
63/490Adv-40+404070/49
63/49040-Adv+202057/35
63/49030-40+151554/35
63/49015-40+8850/35
63/4900-40±0045/23

Now a series of all 40-0. It's interesting to note that at first, the skill increment decreases, but as the rivals' skill rate grows, the increment rate goes from decreasing to increasing and keeps being that way until dealing with the best rivals, at which moment it suddenly switches to decreasing again.

Table 2: Series of 40-0 wins
Rivals
skill
Skill
before
ScorePointsSkill
after
Next
rivals
skill
63/49040-0+606083/65
83/656040-0+58118120/100
120/10011840-0+55173190/160
190/16017340-0+54227270/230
270/23022740-0+53280380/340
380/34028040-0+53333520/490
520/49033340-0+53386670/650
670/65038640-0+55441850/840
850/84044140-0+574981100/1000
1100/100049840-0+615591300/1200
1300/120055940-0+656241500/1400
1500/140062440-0+686921600/1600
1600/160069240-0+717631800/1800
1800/180076340-0+728351900/1800
1900/180083540-0+739081900/1900
1900/190090840-0+739812000/1900
2000/190098140-0+7110522000/1900
2000/1900105240-0+6711192000/1900
2000/1900111940-0+6411832000/1900
2000/1900118340-0+6112442000/1900
2000/1900124440-0+5813022000/1900
2000/1900130240-0+5513572000/1900
2000/1900135740-0+5214092000/1900
2000/1900140940-0+4914582000/1900
2000/1900145840-0+4715052000/1900
2000/1900150540-0+4515502000/1900
2000/1900155040-0+4315932000/1900
2000/1900159340-0+4016332000/1900
2000/1900163340-0+3816712000/1900
2000/1900167140-0+3717082000/1900
2000/1900170840-0+3417422000/1900
2000/1900174240-0+3317752000/1900
2000/1900177540-0+3118062000/1900
2000/1900180640-0+3018362000/1900
2000/1900183640-0+2818642000/1900
2000/1900186440-0+2718912000/1900
2000/1900189140-0+2519162000/1900
2000/1900191640-0+2519412000/1900
2000/1900194140-0+2219632000/1900
2000/1900196340-0+2219852000/1900
2000/1900198540-0+2120062000/1900
2000/1900200640-0+2020262000/1900
2000/1900202640-0+1820442000/1900
2000/1900204440-0+1820622000/1900
2000/1900206240-0+1720792000/1900
2000/1900207940-0+1620952000/1900
2000/1900209540-0+1521102000/1900
2000/1900211040-0+1521252000/1900
2000/1900212540-0+1321382000/1900
2000/1900213840-0+1321512000/1900
2000/1900215140-0+1321642000/1900
2000/1900216440-0+1221762000/1900
2000/1900217640-0+1121872000/1900

A series of 0-40 followed by a series of 40-0. Observe how our skill increases to 1 even if we were losing from the very beginning. That's because the rivals' skill was not zero, thus the asymptote goes a bit over 1. But as games progress and rivals are weaker, that point drops again. Note also how the second rival's skill increases at some point. I believe that what we see is the absolute value of the second rival's computed skill, which goes actually down to -4 (from 4/0 to 4/-3 to 2/-4 to 1/-4 to 0/-4).

Table 3: Series of 0-40 losses followed by a series of 40-0 wins
Rivals
skill
Skill
before
ScorePointsSkill
after
Next
rivals
skill
63/4900-40±0045/23
45/2300-40±0032/12
32/1200-40+1123/12
23/1210-40±0117/4
17/410-40±0112/0
12/010-40±018/0
8/010-40±016/0
6/010-40±014/0
4/010-40±014/3
4/310-40±012/4
2/410-40±012/4
2/410-40±011/4
1/410-40-101/4
1/400-40±001/4
1/400-40±000/4
0/400-40±000/4
0/400-40±000/4
0/400-40±000/4
0/400-40±000/4
0/400-40±000/4
0/400-40±000/4
0/400-40±000/4
0/4040-0+60606/0
6/06040-0+5711727/12
27/1211740-0+5417168/49
68/4917140-0+52223130/100
130/10022340-0+51274220/180
220/18027440-0+49323340/310
340/31032340-0+50373480/460
480/46037340-0+50423640/620
640/62042340-0+52475820/800
820/80047540-0+555301000/990
1000/99053040-0+585881300/1200
1300/120058840-0+636511500/1400
1500/140065140-0+667171600/1600

Results for a short series of three-game matches won 40-0, 40-0:

Table 4: Series of 40-0, 40-0 wins in three-game matches
Rivals
skill
Skill
before
Score
1st
game
Score
2nd
game
Score
3rd
game
PointsSkill
after
Next
rivals
skill
63/49040-040-0-+118118120/100
120/10011840-040-0-+108226270/230
270/23022640-040-0-+103329520/490

Same for a short series of five-game matches won 40-0, 40-0, 40-0:

Table 5: Series of 40-0, 40-0, 40-0 wins in five-game matches
Rivals
skill
Skill
before
Score
1st
game
Score
2nd
game
Score
3rd
game
Score
4th
game
Score
5th
game
PointsSkill
after
Next
rivals
skill
63/49040-040-040-0--+172172190/160
190/16017240-040-040-0--+154326540/440
540/44032640-040-040-0--+1734791100/1000

In the next series, I first went as close to 0.0 points as my patience could bear, with the rivals as low as possible. Then I scored a 15-40 to confirm my hypothesis that the points are rounded down, not to nearest, by checking whether it went up to 7 or to 8. As I expected, it went up to only 7, proving my hypothesis. Then I did a few more experiments to get a bit more understanding on how the rates of the rivals worked, specifically if they never increased if I lost, even if my skill increased. That seems to be the case, but I need more experimenting in this field.

Table 6: Series of 0-40 losses followed by a 15-40 loss, and more checks on the effects of various scores over the rivals' skill.
Rivals
skill
Skill
before
ScorePointsSkill
after
Next
rivals
skill
(First 15 rows as in Table 3)
0/400-40±000/4
(Repeat the previous row 24 more times, total 25 times)
0/4015-40+770/4
0/470-40-160/4
0/460-40±060/4
0/460-40±060/4
0/460-40-150/4
0/450-40±050/4
0/450-40±050/4
0/450-40±050/4
0/450-40-140/4
0/440-40±040/4
0/440-40±040/4
0/440-40±040/4
0/440-40-130/4
0/430-40±030/4
0/430-40±030/4
0/430-40±030/4
0/430-40±030/4
0/430-40±030/4
0/430-40-120/4
0/420-40±020/4
0/420-40±020/4
0/420-40±020/4
0/420-40±020/4
0/420-40±020/4
0/420-40±020/4
0/420-40±020/4
0/420-40-110/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40±010/4
0/410-40-100/4
0/4015-40+880/4
0/480-40±080/4
0/480-40-170/4
0/4715-40+7140/4
0/41415-40+7210/4
0/42115-40+6270/4
0/42715-40+7340/4
0/43430-40+13470/4
0/44740-Adv+17640/4
0/464Adv-40+371011/4

This time I went close to zero again, then tested several series of scores. That allowed me to test what the asymptotes were for scores from 0-40 to 40-Adv, while keeping the rivals' scores minimized. It's the longest-running experiment. Believe me, it was tedious to do, but the results were worth it. I gave up on checking if the asymptotes were really asymptotes after 50 tries in two cases. I also tried "jumping to the other side" of the asymptote in the case of 400, just to be sure. For some of them, I suspected what the asymptotes were, so I scored the necessary points to get there as fast as possible without crossing the line.

Table 7: Series of 0-40 losses followed by a series of 40-Adv losses, then test the asymptotes for other scores.
Rivals
skill
Skill
before
ScorePointsSkill
after
Next
rivals
skill
(First 15 rows as in Table 3)
0/400-40±000/4
(Repeat the previous row 29 more times, total 30 times)
0/4040-Adv+20200/4
0/42040-Adv+19390/4
0/43940-Adv+18570/4
0/45740-Adv+17740/4
0/47440-Adv+16900/4
0/49040-Adv+161060/4
0/410640-Adv+141200/4
0/412040-Adv+141340/4
0/413440-Adv+141480/4
0/414840-Adv+121600/4
0/416040-Adv+121720/4
0/417240-Adv+111830/4
0/418340-Adv+111940/4
0/419440-Adv+112050/4
0/420540-Adv+92140/4
0/421440-Adv+102240/4
0/422440-Adv+82320/4
0/423240-Adv+92410/4
0/424140-Adv+82490/4
0/424940-Adv+72560/4
0/425640-Adv+72630/4
0/426340-Adv+72700/4
0/427040-Adv+72770/4
0/427740-Adv+62830/4
0/428340-Adv+62890/4
0/428940-Adv+52940/4
0/429440-Adv+52990/4
0/429940-Adv+53040/4
0/430440-Adv+53090/4
0/430940-Adv+53140/4
0/431440-Adv+43180/4
0/431840-Adv+43220/4
0/432240-Adv+43260/4
0/432640-Adv+43300/4
0/433040-Adv+33330/4
0/433340-Adv+33360/4
0/433640-Adv+43400/4
0/434040-Adv+33430/4
0/434340-Adv+23450/4
0/434840-Adv+33510/4
0/435140-Adv+23530/4
0/435340-Adv+23550/4
0/435540-Adv+33580/4
0/435840-Adv+23600/4
0/436040-Adv+23620/4
0/436240-Adv+23640/4
0/436440-Adv+13650/4
0/436540-Adv+23670/4
0/436740-Adv+23690/4
0/436940-Adv+13700/4
0/437040-Adv+23720/4
0/437240-Adv+13730/4
0/437340-Adv+13740/4
0/437440-Adv+23760/4
0/437640-Adv+13770/4
0/437740-Adv+13780/4
0/437840-Adv+13790/4
0/437940-Adv+13800/4
0/438040-Adv+13810/4
0/438140-Adv+13820/4
0/438240-Adv+13830/4
0/438340-Adv+13840/4
0/438440-Adv±03840/4
0/438440-Adv+13850/4
0/438540-Adv+13860/4
0/438640-Adv+13870/4
0/438740-Adv±03870/4
0/438740-Adv+13880/4
0/438840-Adv±03880/4
0/438840-Adv+13890/4
0/438940-Adv+13900/4
0/439040-Adv±03900/4
0/439040-Adv+13910/4
0/439140-Adv±03910/4
0/439140-Adv±03910/4
0/439140-Adv+13920/4
0/439240-Adv±03920/4
0/439240-Adv+13930/4
0/439340-Adv±03930/4
0/439340-Adv±03930/4
0/439340-Adv+13940/4
0/439440-Adv±03940/4
0/439440-Adv±03940/4
0/439440-Adv±03940/4
0/439440-Adv+13950/4
0/439540-Adv±03950/4
0/439540-Adv±03950/4
0/439540-Adv±03950/4
0/439540-Adv+13960/4
0/439640-Adv±03960/4
0/439640-Adv±03960/4
0/439640-Adv±03960/4
0/439640-Adv±03960/4
0/439640-Adv±03960/4
0/439640-Adv+13970/4
0/439740-Adv±03970/4
0/439740-Adv±03970/4
0/439740-Adv±03970/4
0/439740-Adv±03970/4
0/439740-Adv±03970/4
0/439740-Adv±03970/4
0/439740-Adv±03970/4
0/439740-Adv+13980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv±03980/4
0/439840-Adv+13990/4
0/439940-Adv±03990/4
(Repeat the previous row 49 more times, total 50 times)
0/4399Adv-40+204191/4
1/441940-Adv-14181/4
1/441840-Adv-14171/4
1/441740-Adv±04170/4
0/441740-Adv-14160/4
0/441640-Adv-14150/4
0/441540-Adv-14140/4
0/441440-Adv-14130/4
0/441340-Adv±04130/4
0/441340-Adv-14120/4
0/441240-Adv-14110/4
0/441140-Adv±04110/4
0/441140-Adv-14100/4
0/441040-Adv±04100/4
0/441040-Adv-14090/4
0/440940-Adv±04090/4
0/440940-Adv-14080/4
0/440840-Adv±04080/4
0/440840-Adv-14070/4
0/440740-Adv±04070/4
0/440740-Adv±04070/4
0/440740-Adv-14060/4
0/440640-Adv±04060/4
0/440640-Adv±04060/4
0/440640-Adv-14050/4
0/440540-Adv±04050/4
0/440540-Adv±04050/4
0/440540-Adv-14040/4
0/440440-Adv±04040/4
0/440440-Adv±04040/4
0/440440-Adv±04040/4
0/440440-Adv±04040/4
0/440440-Adv-14030/4
0/440340-Adv±04030/4
0/440340-Adv±04030/4
0/440340-Adv±04030/4
0/440340-Adv±04030/4
0/440340-Adv-14020/4
0/440240-Adv±04020/4
0/440240-Adv±04020/4
0/440240-Adv±04020/4
0/440240-Adv±04020/4
0/440240-Adv±04020/4
0/440240-Adv±04020/4
0/440240-Adv±04020/4
0/440240-Adv-14010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv±04010/4
0/440140-Adv-14000/4
0/440040-Adv±04000/4
(Repeat the previous row 49 more times, total 50 times)
0/440030-40-53950/4
0/439530-40-53900/4
0/439030-40-53850/4
0/438530-40-43810/4
0/438130-40-43770/4
0/437730-40-43730/4
0/437330-40-43690/4
0/43690-40-183510/4
0/43510-40-183330/4
0/43330-40-163170/4
0/431715-40-93080/4
0/430830-40±03080/4
0/430830-40-13070/4
0/430730-40±03070/4
0/430730-40±03070/4
0/430730-40-13060/4
0/430630-40±03060/4
0/430630-40±03060/4
0/430630-40-13050/4
0/430530-40±03050/4
0/430530-40±03050/4
0/430530-40-13040/4
0/430430-40±03040/4
0/430430-40±03040/4
0/430430-40±03040/4
0/430430-40±03040/4
0/430430-40-13030/4
0/430330-40±03030/4
0/430330-40±03030/4
0/430330-40±03030/4
0/430330-40±03030/4
0/430330-40-13020/4
0/430230-40±03020/4
0/430230-40±03020/4
0/430230-40±03020/4
0/430230-40±03020/4
0/430230-40±03020/4
0/430230-40±03020/4
0/430230-40±03020/4
0/430230-40-13010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40±03010/4
0/430130-40-13000/4
0/430015-40-72930/4
0/429315-40-72860/4
0/42860-40-152710/4
0/42710-40-132580/4
0/42580-40-132450/4
0/42450-40-122330/4
0/42330-40-122210/4
0/42210-40-112100/4
0/42100-40-111990/4
0/419915-40-21970/4
0/41970-40-101870/4
0/41870-40-91780/4
0/41780-40-91690/4
0/41690-40-91600/4
0/41600-40-81520/4
0/415215-40±01520/4
0/415215-40±01520/4
0/415215-40±01520/4
0/415215-40±01520/4
0/415215-40±01520/4
0/415215-40±01520/4
0/415215-40-11510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40±01510/4
0/415115-40-11500/4

At this point, I thought that the asymptote was multiplied by a factor depending on the rival's skill, and that that factor would be 2 for Sarah/Elisa, giving 2400. But the next experiment proved me wrong: the differences between the asymptotes for different scores were not doubled, but remained the same. That suggested that they were offset instead. But first I wanted to be sure that the 0/4 skill rivals were reached losing by with 40-Adv. This particular series can be quite valuable to help finding out how the rivals ranking works.

Table 8: Series of 40-Adv losses followed by a series of Adv-40 wins.
Rivals
skill
Skill
before
ScorePointsSkill
after
Next
rivals
skill
63/49040-Adv+202057/35
57/352040-Adv+204046/23
46/234040-Adv+185833/12
33/125840-Adv+177524/12
24/127540-Adv+179217/4
17/49240-Adv+1510712/0
12/010740-Adv+131209/0
9/012040-Adv+141346/0
6/013440-Adv+131474/0
4/014740-Adv+131603/4
3/416040-Adv+111712/4
2/417140-Adv+121832/4
2/418340-Adv+111941/4
1/419440-Adv+102041/4
1/420440-Adv+92151/4
1/421540-Adv+102250/4
0/422540-Adv+82330/4
0/4233Adv-40+292622/4
2/4262Adv-40+272896/0
6/0289Adv-40+2531414/4
14/4314Adv-40+2433826/12
26/12338Adv-40+2436244/23
44/23362Adv-40+2238466/49
66/49384Adv-40+2140592/65
92/65405Adv-40+21426120/100
120/100426Adv-40+20446160/140
160/140446Adv-40+20466200/160
200/160466Adv-40+19485240/210
240/210485Adv-40+20505290/260
290/260505Adv-40+19524340/310
340/310524Adv-40+19543400/370
400/370543Adv-40+20563460/430
460/430563Adv-40+20583520/490
520/490583Adv-40+21604580/550
580/550604Adv-40+21625640/620
640/620625Adv-40+22647710/690
710/690647Adv-40+23670780/760
780/760670Adv-40+23693860/840
860/840693Adv-40+25718930/910
930/910718Adv-40+267441000/990
1000/990744Adv-40+277711100/1100
1100/1100771Adv-40+287991200/1200
1200/1200799Adv-40+298281300/1200
1300/1200828Adv-40+318591300/1300
1300/1300859Adv-40+338921400/1400
1400/1400892Adv-40+339251500/1500
1500/1500925Adv-40+369611600/1600
1600/1600961Adv-40+379981700/1700
1700/1700998Adv-40+3810361600/1600(*)
1600/1600(*)1036Adv-40+4110771900/1900
1900/19001077Adv-40+4211192000/1900
2000/19001119Adv-40+4311622000/1900
2000/19001162Adv-40+4212042000/1900
2000/19001204Adv-40+4012442000/1900
2000/19001244Adv-40+3812822000/1900

(*) That is probably 1800/1800 and is a transcription error on my side. Sometimes I confuse the 6s and the 8s with that font.

With a Libreoffice spreadsheet I was able to determine the asymptote from just the last few data points, when the rivals were maxed out. It turned out to be 2000.

It's easy to construct the spreadsheet. In cell B2 put the starting value of the series you want to analyze. In cell A2 put the asymptote to test. Then in cell B3 write this formula: =($A$2+C3+B2*19)/20. Column C will be for offsets (a series of 0's for 0/4 rivals, a series of 1200's for 2000/1900 rivals, and you can adjust by hand cell by cell in other cases). Then extend B3 to the rest of column B up to where you want. Then in cell D2 you write: =INT(B2) and extend it to the rest of column D. If you want, in cell E2 you can put: =(D3-D2) and extend it to the column; that column will have the computed differences. You can also add an extra column F with the real differences or with the real skill points, starting at F2, and a column G with this formula: =IF(E2<>F2;"Diff";"=") to tell you which cells don't match (change E2 to D2 if you put real skill points in column F instead of differences).

So, that's what I have so far. If you are willing to help me out with the rivals' skill points formula, please state so in the comments. Thanks!