James Bridle built this version of Donald Michie’s Tic-Tac-Toe solving computer, MENACE (Matchbox Educable Noughts And Crosses Engine). Not what one would think of as a typical ‘computer’, the instruction to choose the next move is performed by the user. To do this, they select a bead at random from the matchbox that represents the current game state. The type of bead then represents the move that the computer makes.
At first, the machine has an equal chance of making each possible move, but this is corrected by adding or removing beans at the end of each round. The way this works is that if the computer won the round, an extra bean of the same type played is added to each box involved in that round, to make it more likely that the computer will choose the same path on the next game. Likewise, beans are removed from the path if the computer loses, to decrease the chance that it chooses that path next time. This way, the computer slowly ‘learns’ to play the game correctly, merely by counting beans.
James uses this algorithm to demonstrate the awesomeness of scale. This strategy should work for learning any game, however it quickly becomes infeasible to make a set of matchbooks large enough to represent anything but the simplest game. For instance, he estimates that a computer to play the game Go would be at least the size of the Crab Nebula!
If you are curious, there is a (Windows only) simulator of MENICE here. [via boingboing]
5 thoughts on “Tic-Tac-Toe computer learns with beans”
Comments are closed.
ADVERTISEMENT
Join Make: Community Today
Martin Gardner wrote a column in Scientific American detailing a similar computer for playing “Hexapawn,” a simple chess variant. MENACE predates it
http://en.wikipedia.org/wiki/Hexapawn
http://www.chessvariants.org/small.dir/hexapawn.html
Fred Saberhagen described a similar game played by a bead driven computer in “Without a Thought.”
I seem to remember something like this being a plot device in a short sci-fi story.
A spaceship pilot used this method to teach an animal (think of a cross between a chimpanzee and a dog) to play this game. The game was supposed to be a bit more complicated than tic-tac-toe, but it used the same method (except using colored beads instead of beans).
Aha, I found it! “Without a Thought” by Fred Saberhagen
If you use animals, then I think it becomes biological computing! I wonder if anyone is doing this with bacteria.
I remember doing this when I was a kid (50+ years ago?) with my dad. We followed a process, and used colored M&M’s in match boxes. As the ‘machine’ learned, we ‘ate the mistakes’. Eventually it couldn’t be beat. But it could be tied, if I remember right.
Aha, it seems like one could use this technique to build a computer that determines the tastiest kind of candy!