MENACE knows the rules of noughts and crosses and nothing else. It has no strategy, no opening book and no idea that the centre square is worth anything. What it has is 304 matchboxes full of coloured beads, and a rule for what to do with them after a game is over.
Beat it and it throws away the beads for the moves it made. Do that often enough, and it stops making them.
What is MENACE?
In 1961 Donald Michie and Roger Chambers built a machine out of matchboxes that could learn to play noughts and crosses. Not a model of one — a working one, on a table, that a human opponent could sit down and play.
Each matchbox stands for one board position. Inside are beads, one colour per square MENACE could play. To move, you find the box for the current position, shake it, and draw a bead without looking. Its colour is the move. You set the box aside with the drawn bead on the lid so you can find it again.
Nothing about that is clever. The clever part happens at the end of the game.
How does MENACE learn?
- MENACE loses — every bead it drew is thrown away.
- Drawn game — each bead goes back, plus one more of the same colour.
- MENACE wins — each goes back, plus three more.
That is the whole of it. Moves that lose become less likely to be drawn; moves that win become more likely. No rule is ever written down, no strategy is ever explained, and after a few hundred games the box of cardboard plays a decent game of noughts and crosses.
Why exactly 304 matchboxes?
This is the number everyone quotes and nobody shows. So we counted it.
There are 2,201 reachable positions in which MENACE has to move. 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 you can build and one you cannot.
The bead staircase — four, three, two, one — is the part that looks arbitrary and is not. Early positions come up in every single game, so with equal beads they would swamp the later ones. More beads at the front means the front changes more slowly, and the machine learns from the end of the game backwards, which is roughly how people learn too.
What MENACE learns depends on who it plays
Here is the question everybody asks — how long until it is good? — and the reason the usual answer is no answer at all.
After a thousand games it loses 4.2% against a careful opponent, 8.2% against perfect play — and 12.7% against an opponent moving at random, 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 work because the opponent blundered. It becomes very good at beating bad play and never learns to defend. There is a lesson in that which has outlived the matchboxes: what you train against is what you get.
The 8.2% against perfect play needs one more footnote. MENACE can never win against a perfect opponent, so it collects the small reward for a draw and the full penalty for a loss, and boxes drain faster than they refill. Almost every one of those losses is a resignation — a box emptied out, and no move left that it believes in.
What one box looks like after 500 games
The box for MENACE's very first move begins with four beads of each of the nine colours: no opinion whatsoever. After five hundred games, this particular machine had 372 beads for the top-left corner, 169 for the bottom-left, 16 for the centre, and four squares with none left at all.
But one machine is one machine. Run two hundred of them and the answer is more interesting than a single run suggests: 95 settle on the centre, 88 on a corner, and only 17 on an edge.
So MENACE reliably discovers the kind of opening that works — take the middle or take a corner, never an edge — which is exactly what the theory of the game says, and exactly what nobody told it. What it does not do is converge on one answer. Centre and corner are both good enough that whichever one gets lucky first tends to run away with the beads. That is not a flaw in the machine; it is what a reward loop does when two options are close.
How to use this board
Play it, and it learns from you. The matchbox on the right is the one it is using right now; the beads in it are its opinion about this position. After each game you can see exactly which beads it gained or lost.
If you would rather not play three hundred games by hand, train it — pick an opponent and a number of games and watch the curve move. Then try to beat it. Then press forget everything and watch it be hopeless again.
Your MENACE lives in your own browser. Close the tab and come back next week and it will be exactly as clever as you left it.
Why MENACE still matters
MENACE is reinforcement learning, thirty years before the phrase was common and without a computer anywhere in the room. A bead count is a policy. Adding and removing beads is a policy update. +3, +1 and −1 are a reward function.
What has changed since is the size of the problem. Noughts and crosses has 304 positions worth storing; Go has more than there are atoms in the observable universe, so you cannot keep a box for each and the counts have to be approximated by a network instead. The programs that beat human champions at Go are doing what these matchboxes do, with the storage problem solved differently and the learning rule barely altered.
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 people who founded artificial intelligence research in Britain. The BOXES algorithm he and Chambers published in 1968 came directly out of this cardboard.
It began as a machine built by someone who could not get computer time. It is still the clearest thirty seconds of explanation that machine learning has.
Where the numbers come from
MENACE needs one box per position it has to make a choice in, and that count — 304 — is the end of a longer piece of arithmetic. How many tic-tac-toe games there are works through all five figures people quote for this game and shows which question each one answers, including how 5,478 positions fold down to the 304 boxes here.
If you would rather build the machine than play it, build your own MENACE covers the beads, the rules and the first few hundred games. And for where the game itself came from — which is not where most people say — there is who invented tic-tac-toe.
