In 1961 Donald Michie built a machine that learns to play noughts and crosses out of 304 matchboxes and a few thousand glass beads. It works. It has been rebuilt in classrooms for sixty years, and it is still the shortest honest explanation of what machine learning actually does.
It is also much harder to build than anybody tells you. Every guide reaches the same sentence — take 304 matchboxes and label them with the positions — and then moves on to the interesting part. But the labelling is the job. You would have to derive 304 board positions by hand, without missing any, and without accidentally building two rotations of the same position as separate boxes. That is where most attempts die, at around box forty.
So we worked them out. All of them, from the same engine that runs the machine you can play in a browser, and put them on a printable sheet with the beads drawn in.
What you actually need to build MENACE
Three things: containers, beads, and labels.
The containers do not have to be matchboxes. Michie used matchboxes because he had matchboxes — small envelopes, paper cups, a chest of small drawers or 304 chalked squares on a floor all work identically. What matters is that each one holds its beads separately and can be shaken.
The beads do not have to be glass, either. You need nine visually distinct things, one per square of the board. Nine colours of dried bean will do.
The labels are the part you cannot improvise, and the part that is now done.
Why exactly 304 boxes?
Because that is how many positions MENACE can be asked to choose in, once you notice that a rotated board is the same board.
There are 2,201 positions where MENACE is on move and the game is still running. Fold in the eight symmetries of a square — four rotations, each of them also mirrored — and they collapse to 304. That is a factor of 7.2, and it is the difference between a machine that fits in a cupboard and one that fills a room.
Broken down by move: 1 box for MENACE's first move, 12 for its second, 108 for its third, 183 for its fourth. There is no box for the fifth, because by then only one square is free and there is nothing to choose. That missing row is easy to forget — our first counting script crashed on it, which was better than quietly returning 338.
The part every guide leaves out: turning the label
Here is the consequence nobody warns you about. If eight boards share one box, then seven times out of eight the label will not match the board in front of you. You have to recognise that the position on your table is a rotation of the one printed on some label, find that label, and then translate the bead you drew back into a square on the real board.
Done in your head, that is genuinely difficult, and it is the reason physical MENACE builds get abandoned.
The fix is a design decision, not a cleverness: put the bead colours inside the squares on the label rather than in a legend down the side.
Turn the label until the crosses and noughts line up with the board. If it will not line up by turning, hold it up to the light and read it from behind — that is the mirror, and there is no more dignified way to do it. Now draw a bead without looking and find that colour on the turned label. The square it is lying on is MENACE's move.
The turning has performed the conversion. Nobody has to work anything out, and the one step where a mistake would go unnoticed is now done by physically rotating a piece of paper.
How many beads, and which colours
1,917 beads for the full machine, and the number of each colour is not what you would guess.
You need 412 red beads and only 141 pink ones. That looks like it ought to mean something about the game, and it means nothing of the sort. It is an artefact of which of the eight turnings we chose to print as the official one. Pick a different convention and the beads pile up in a different corner. Michie's own set would have had its own lopsided shopping list, determined entirely by how he happened to orient his labels.
It is worth knowing anyway, because you have to buy them.
The bead staircase
Four beads of each colour go in the box for MENACE's first move, three for its second, two for its third, one for its fourth. Each label prints its own number inside each coloured dot, so there is nothing to memorise.
The staircase looks arbitrary and is not. Early positions come up in every game, so with equal beads everywhere they would swamp the later boxes and change far too fast. More beads at the front means the front changes more slowly — and the machine ends up learning from the end of the game backwards, which is roughly how people learn too.
Building it in a lesson instead of a fortnight
Three hundred and four boxes is a real commitment. If what you want is a class to watch a machine learn on a Tuesday afternoon, print the 13-box version instead: MENACE's first two moves, one sheet, thirteen boxes, 288 beads.
This is a simplification and the sheet says so — once MENACE runs out of boxes it plays at random from there. Michie had all four moves. But thirteen boxes fit in a lesson and three hundred do not, and children can watch beads change hands inside twenty minutes, which is the entire point.
For a class set, print in ink saver. Three hundred labels of nine coloured dots is most of a cartridge; without colour the dots carry a letter instead.
How MENACE learns — the whole rule
MENACE always goes first. Find the box, shake it, draw a bead blind, play the square, and leave the box open with the bead on the lid so you can find it again. Nothing is decided during the game.
At the end:
- MENACE lost — every bead it drew is thrown away.
- Drawn — each bead goes back, plus one more of the same colour.
- MENACE won — each goes back, plus three more.
That is all of it. No rule is ever written down. Nobody explains that the centre is good. Moves that lost become less likely to be drawn, moves that won become more likely, and after a couple of hundred games a box of cardboard plays a decent game.
If a box runs out of beads, MENACE resigns. That is in the original and worth keeping rather than quietly topping the box up: it is the machine telling you it has no move left that it believes in.
Who you train it against matters more than how long
The question everyone asks is how many games until it is good, and the usual answer — a few hundred — is not an answer, because it depends entirely on the opponent.
After a thousand games it loses 4.2% of games against a careful opponent, 8.2% against perfect play — and 12.7% against an opponent moving at random, which is the weakest of the three.
That looks backwards and is not. Against random play MENACE wins three quarters of its games, so it is constantly rewarded for moves that only worked because the opponent blundered. It gets very good at beating bad play and never learns to defend at all.
So do not let the class throw games to be kind to it. Play properly. The machine you get is the machine you trained.
What it is really teaching
A bead count is a policy. Adding and removing beads is a policy update. Win, draw and loss at +3, +1 and −1 are a reward function. This is reinforcement learning with the computer removed, which is why it has survived sixty years of curriculum reform, and why a child who has actually run one understands what a training loop is doing in a way that no diagram achieves.
Michie was not a hobbyist with a spare afternoon. He spent the war at Bletchley Park working on the German Tunny cipher alongside Alan Turing and Max Newman, and afterwards became one of the founders of artificial intelligence research in Britain. MENACE came out of arguments with Turing about whether a machine could learn from experience, and out of not having a computer to settle them with. The BOXES algorithm he and Chambers published in 1968 came directly out of this cardboard.
The labels are on the printable kit page, free, in A4 and US Letter. If you would rather see where a trained one ends up before committing a fortnight to glue, play ours first — it starts knowing nothing, exactly like yours will.