Serendipity is a wonderful thing. Comments on my other blog lead me to contact the author of Itatsi, a game based on a simple search algorithm presented in Richard Dawkins book The Blind Watchmaker. First though, a description of the game itself:
The ideas is very simple, starting with 50 strings of three random letters, pick one that will be the parent of the next generation. With each new generation there is a random chance each letter will be randomly replace by another letter. The game has a database of some 30,000 words (3 letters or more), and choosing a parent that spells one of these words will score points - more points for longer words. In the example below there is also a chance the string will become longer, allowing longer words to be found.
The game also gives a "fitness" score, when is related to how close the parent string is to other words in the database. A higher fitness indicates a greater chance that the next generation will contain words that can be scored. Each word can only be scored once, so the strategy is to choose parents that not only score points, but also lead to new words that can be scored.
I'll be describing the screen-shots as I go along, but you might find it easier to see if you open another tab or window.
Those are the controls for starting the game (most of them). Word length controls the number of characters randomized. Remember that longer words also score more points. For this example I'm playing with variable length words. For starters you will want to select "Training Weasel: Yes".
So here is the first turn or "generation" of the game. It doesn't say, but because about half of the 50 children are "CAU" it appears that "CAU" was also the original parent string.
The gold or yellow "CAW" string is the child with the highest fitness, or the most likely to generate scoring words if chosen as the parent. The silver/grey "CAN" is the second highest fitness.
The other colors indicate children that have mutated (one or more letters changed) from the parent. Note that some of the children have randomized to become longer (4 characters instead of 3).
This turn I select the string "CAW", and the next generation will be created by randomizing that string 50 times. (below)
You can see I scored 2 points for the word "CAW" and its fitness score was 46.
In generation 2 the highest fitness is again "CAW" (I could choose any of them), but since I already scored "CAW", I choose "WAW" instead.
Above is generation 3. I scored 2 more points for "WAW", and "CAN" is now the highest fitness. The "Training Weasel" is the feature is what marks the highest two fitness as gold/silver. You will want to use this feature to learn, but the game does not track your points when it is giving you these hint.
Now here comes a a bunch of turns.
At generation 12 now, and you can see my chpices over on the right. "NAGS" scored 8 points. Let's zoom ahead now ...
... to generation 20. I scored big on turn 17 (12 points for HEAL and HEALS), and another 14 on turn 18. I'm up to 7 letters now, and that might be trouble because it gets harder with longer strings.
At generation 38 now, and I think that's enough to give you the general idea. I had one more screen-shot to show, but I must have forgotten to save it. Too bad, because it the Weasel found the string "BEHE" (a little joke there).
In part two, I'll share my exchange with the game creator.