Orden y concierto

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

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!

2013-04-24

Caps Lock Led Toggled problem

The cause: https://bugs.freedesktop.org/show_bug.cgi?id=16145

The solution: xdotool key Caps_Lock

Another alternative solution is to use xmacro: printf 'KeyStrPress Caps_Lock\nKeyStrRelease Caps_Lock\n' | xmacroplay $DISPLAY

Basically, the reason is that when faking a Caps Lock key press programmatically in order for an application to toggle the Caps Lock state, the led does not toggle and the state becomes out of sync between the led and the keyboard.

It used to happen when entering a word like tHIS in OpenOffice with Caps Lock on, though late versions seem to have fixed it. But I've also suffered it when using x11vnc and pressing Caps Lock in the client. At that moment, the keyboard becomes desynced. The command above syncs it again. The source code in the bug report linked above works well too, in case you can't find xdotool or xmacro. They come as Debian and Ubuntu packages, though, so they should be easy to find.

2013-04-22

Laboratorio de evolución

¿Qué hace falta para que la evolución se produzca?

Hacen falta organismos autorreplicantes. Es decir, algún tipo de entidad que pueda producir copias de sí misma. Por ejemplo, células, animales, plantas, pero sirven otras entidades. Dichas copias deberían ser inexactas, es decir, las réplicas deben ser parecidas pero no iguales al progenitor. Si son idénticas, no puede haber evolución.

Ha de haber un medio al que adaptarse (si los organismos ya están adaptados, poca evolución se puede dar). Las variaciones en las réplicas deben tener el potencial de que algunas están mejor adaptadas al medio (aunque sólo sea levemente) y otras peor.

Y hace falta tiempo, claro. La evolución no es un proceso instantáneo.

En el escenario típico en el que la evolución se produce, el medio suele tener alimento que los organismos requieren. Suele variar con el tiempo debido a factores muy diversos como climatología, ciertos eventos o fenómenos, o la propia interacción con los organismos. Éstos, por su parte, requieren adaptarse al medio para conseguir alimento; y el fracaso al hacerlo influye en su mortalidad, que repercute en la capacidad reproductiva.

Aquí presentamos un programa en JavaScript que pueden ejecutar en su navegador, que incluye todos esos elementos para demostrar cómo la evolución se produce de forma natural en él. Está basado en un programa en Pascal escrito por Javier Sebastián y refinado por Alejandro Valero y un servidor, que a su vez está basado en la descripción de un programa escrito por Michael Palmiter [1] que apareció en un artículo de A.K.Dewdney, en la sección Juegos de Ordenador de la revista Investigación y Ciencia.

La versión JavaScript aquí presentada, así como el presente texto, son, por supuesto, copyright © 2013 Pedro Gimeno Fortea. El generador de números pseudoaleatorios es ran_array, un generador de Fibonacci retardado (LFG) con retardos 37 y 100, diseñado por Donald E. Knuth.

El programa utiliza el elemento <canvas>, por lo que es necesario un navegador que lo soporte. Si su navegador es muy antiguo, es posible que no funcione; no hay como probar para saberlo.

¿En qué consiste la simulación? Se trata de un «mundo» rectangular en el que habitan unos organismos, que llamaremos protozoos, que pueden moverse libremente (la topología es toroidal, es decir, cuando un protozoo sale por arriba, reentra por abajo en el mismo punto, y similarmente con izquierda y derecha). En este «mundo» aparecen unas motas que llamaremos bacterias, que por simplicidad lo hacen por generación espontánea y permanecen en el sitio hasta que son comidas por un protozoo, si es que ocurre. Si se prefiere, en vez de bacterias se puede imaginar que se trata de polvo alimenticio que se acumula en una superficie. La velocidad de aparición de las bacterias es constante. Una zona del rectángulo es un «jardín del Edén», donde las bacterias florecen a un ritmo mucho más rápido. En su centro hay un foco luminoso.

Los protozoos se reproducen por bipartición y se alimentan de bacterias al pasar por encima de ellas (si no están saciados). Para poder reproducirse, deben tener una energía mínima necesaria y haber alcanzado una edad mínima de «madurez sexual». Cuando se dan ambas circunstancias, se produce la bipartición sin más demora. El tiempo se mide en «ciclos» o «ticks» de un reloj imaginario. La vida de un protozoo está limitada por dos factores: tiempo (es decir, pueden morir de viejos) y energía (muerte por inanición).

Por simplicidad, la única variación que hay en la reproducción de los protozoos afecta a la forma en que se mueven. Cada protozoo contiene un «material genético» que define la probabilidad de que haga ciertos movimientos. La retícula por la que se mueven (y en la que se colocan las bacterias) tiene una disposición hexagonal. Eso implica seis sentidos diferentes en los que se puede mover cada organismo.

Los protozoos tienen una «dirección actual» que cambia en cada ciclo de una forma aleatoria pero modulada por el material genético. Cada posible cambio de dirección tiene un gen asociado: hay un gen para seguir adelante, otro para girar 60° a la derecha, otro para hacerlo a la izquierda, otro para girar 120° a la derecha, otro para lo mismo a la izquierda, y otro para dar media vuelta. Además, hay un gen que indica si el protozoo es atraído por la luz. Si se activa, el protozoo gira inmediatamente en la dirección que más le acercaría a la luz. Si hay más de una que le acercaría más que las demás, se escoge una al azar de entre las posibles.

Este material genético está en forma de enteros. Dado lo restringido de la simulación, para que ésta sea más rápida, los enteros se aplican de forma exponencial para decidir el giro siguiente. Para decidir en qué forma girará el protozoo, el valor de 2 elevado a cada gen se usa como peso en una elección aleatoria. Por ejemplo, si el gen de avanzar tiene el valor 3 y todos los demás tienen el valor 0, entonces es ocho (2³) veces más probable que el protozoo avance que que haga cada uno de los otros movimientos.

La simulación empieza con cierta población inicial de protozoos y de bacterias. Los genes se precargan con números al azar. Al principio, típicamente se mueven de forma tan errática e indecisa que, a la larga, apenas se desplazan de su posición original. Esto es ineficiente en ese medio, ya que pronto consumirán las bacterias que tienen a su alrededor, se quedarán sin alimento y morirán. Pero unos pocos tienen algo más de movilidad y consiguen sobrevivir unos ciclos más. Los más afortunados sobrevivirán lo suficiente como para que, ante el declive del número de depredadores que se llevan el alimento, la zona se llene de bacterias y puedan comer mucho más rápido, llegando a alcanzar la energía de reproducción.

En cada reproducción se produce una mutación (un cambio de una unidad, al alza o a la baja, en un gen al azar). Como en cualquier proceso evolutivo, las mutaciones pueden ser buenas o malas. Si la progenie está peor adaptada, morirá más facilmente, y si se adapta mejor al medio, lo que en este caso implica tener más movilidad para alcanzar más alimento, tendrá más facilidad para sobrevivir y por tanto reproducirse.

Y eso es lo que se observa en la simulación. Aunque no tiene ninguna preferencia para ser elegido en el código, con el transcurrir de las generaciones, el gen de ir en línea recta predomina sobre los demás, ya que esto facilita al protozoo desplazarse alrededor del área en vez de «enquistarse» en una zona más pequeña, lo cual le supone una ventaja sobre otros protozoos que no tienen esa característica. Y al comer más, también deja menos comida para los peor adaptados, haciendo, por tanto, más facil que mueran de inanición.

Esto se observa con las semillas aleatorias de 1 a 3. Con la semilla 4, sucede algo diferente. Algunos de los protozoos empiezan a tener «curiosidad» por la luz; cuando llegan, descubren que por allí hay comida en abundancia. Tímidos todavía, siguen mayormente haciendo lo único que saben hacer, que es moverse erráticamente, pero si se alimentan lo suficiente, parte de su descendencia desarrollará mayor afinidad por la luz, con lo que tendrá más acceso al jardín del Edén. Teniendo sus necesidades cubiertas, aventurarse a las proximidades en busca de otros métodos para alimentarse va a resultar contraproducente. Mientras tanto, los que no han desarrollado una afinidad por la luz suficiente, siguen su curso. El resultado es la especiación: dos especies de protozoos, una afín a la luz que ronda el jardín del Edén, que llamaremos Polilla, y la otra afanosa por cubrir la mayor área posible, que llamaremos Explorador. Y, como en la evolución natural, esta especiación es producto del azar.

Una vez las dos especies se han diferenciado, es difícil que se produzca un cambio. Si uno de los genes empieza a cobrar importancia, el otro se reducirá en importancia, con lo que en este mundo competitivo, tendrá menos ventaja sobre sus hermanos. Así, es poco probable que la descendencia de una Polilla acabe transformándose en Explorador, porque los genes no mutan tan deprisa, y una vez empieza a separarse de la luz, el alimento escasea demasiado en comparación; similarmente, es poco probable que la descendencia de un Explorador acabe siendo Polilla, porque en cuanto la predisposición a ir en línea recta decrece para dar importancia a girar hacia la luz, sus hermanos Exploradores darán cuenta del alimento y el individuo estará en desventaja competitiva, haciendo más fácil que muera antes de evolucionar. Sin embargo, ese tipo de saltos de comportamiento han sido observados durante el ajuste de parámetros, lo cual implica que no son imposibles.

Además de permitirnos contemplar cómo, con los ingredientes adecuados, la evolución es un proceso que surge de forma natural, este programa también tiene otro efecto secundario. Nos ofrece también la posibilidad de observar el fenómeno de la fluctuación en las poblaciones de un sistema depredador-presa, del tipo modelado por las ecuaciones diferenciales de Lotka–Volterra. En este caso, los depredadores son los protozoos y las presas son las bacterias. Cuando el número de protozoos aumenta, éstos comen bacterias y hacen que la población de bacterias disminuya. Esa disminución pronto provoca muerte por inanición de protozoos, con lo que la población de éstos empieza a disminuir a su vez. Al haber menos depredadores, las bacterias tienen oportunidad de volver a crecer en número, lo que hace que los protozoos tengan más comida, con lo que su número aumenta y el ciclo se repite. No ha sido fácil encontrar parámetros que hacen la relación lo bastante estable; durante la búsqueda, en algunos casos he encontrado un baby boom que causa una superpoblación que arrasa con la gran mayoría de bacterias, seguido de una caída en picado de la población que acaba con todos los protozoos antes de que las bacterias se recuperen en número.

Así que, he aquí el programa. Que lo disfruten.

Referencias

[1] Michael Palmiter, Simulated Evolution. http://lifesciassoc.home.pipeline.com/instruct/evolution/