A simple tic tac toe
constructed out of just 300 matchboxes
and coloured beads
MENACE (Matchbox Educable Naughts and Crosses Engine) is the invention of Donald Michie, a biologist at the University of Edinburgh. He first described the machine in 'Trial and Error', in Penguin Science Survey 1961, Vol. 2, as follows:
On each box is pasted a drawing of a possible tictactoe position. The machine always makes the first move, so only patterns that confront the machine on odd moves are required. Inside each box are small glass beads of various colours, each colour indicating a possible machine play. A V-shaped cardboard fence is glued to the bottom of each box, so that when one shakes the box and tilts it, the beads roll into the V. Chance determines the colour of the bead that rolls into the V. First-move boxes contain four beads of each colour, third-move boxes have three beads of each colour, fifth-move boxes contain two beads of each colour, and seventh-move boxes have one of each colour.
The machine's move is determined by shaking and tilting a box, opening the drawer, and noting the color of the 'apical' bead (the bead in the V's apex). Boxes involved in a game are left open until the game ends. If the machine wins, it is rewarded by adding three beads of each apical colour to each open box. If the game is a draw, the reward is one bead per box. If the machine loses, it is punished by extracting the apical bead from each open box. It is obvious that the more games MENACE plays, the more it will tend to adopt winning lines of play, and shun losing lines.
Michie's first tournament with MENACE consisted of 220 games over a two-day period. At first the machine lost easily. After 17 games the machine had abandoned all openings except the corner opening. After the twentieth game it was drawing consistently, so Michie began trying unsound variations in the hope of trapping it in a defeat. This paid off unti the machine learned to cope with all such variations. When Michie withdrew from the contest after losing eight out of ten games, MENACE had become a grand master.
Although Michie used V boards, a simpler way would be simply to close your eyes and pick a random bead out of the box. Skittles and M&Ms make handy 'beads'.
It is possible to try this with other simple games, in some cases with fewer matchboxes.
Another interesting experiment is to construct two, and have them play each other from the beginning, and see what the outcome is.
I have no idea how to model this in programming language, but if you know of a coding for it, or have written one, please msg me or do a writeup.