This week’s submission is Matchbox Tic-Tac-Toe, which is based on an article in Martin Gardner’s Scientific American ‘Mathematical Games’ column from March 1962, which describes Donald Michie’s MENACE (Matchbox Educable Naughts And Crosses Engine), a Tic-Tac-Toe playing computer constructed from matchboxes and coloured beads. This is one of the first ever computer learning programs, and it didn’t even require an electronic computer. I’ve been meaning to program this for years. So, this was a good opportunity. I had originally intended this to be last week’s submission, but I underestimated the complexity of dealing with game position rotations and reflections, which took much longer to debug than anticipated.
A good write up of MENACE can be found here:
Each possible game state is represented by a matchbox (with a diagram of the game state affixed to it). If the computer always moves first, then 304 matchboxes are required. (This number excludes redundant rotations and reflections of the basic positions. Otherwise, several thousand boxes would be required.) Each matchbox contains several differently coloured beads, each colour representing a currently blank game cell. For the computer’s move, the box representing the current game state is selected. Then a random bead is drawn from the box. The colour of the bead indicates which cell is to be chosen for the computer’s move. At the end of the game, if the computer has won, it is rewarded. Each matchbox used in the game has 3 beads added to it, the colour being the same as the bead that was picked for the move. If the computer lost the game, it is punished by removing the bead that was picked for each move. The result of the reward/punishment scheme is that the bead distribution in each box eventually increases the probability of selecting winning moves and avoiding losing moves.
Project file is here: Matchbox TicTacToe Project
For additional info see app.RevisionNotes in the project file, or click on the help button in the main window, when the program is running.