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]
ADVERTISEMENT
