Orden y concierto

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

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!