applets.

MENACE

← All apps

About MENACE

Play noughts and crosses against MENACE, a machine that starts knowing nothing but the rules and learns from every game. You can watch it think: the matchbox for the position on the board, the beads inside it, and the bead it draws. Press TRAIN to let it play hundreds of games against a random player, a simple rule player, the perfect player or a second MENACE, and watch the chart as it learns. Or play the perfect player, which can't be beaten, with hints that show what every square leads to.

THE STORY

In 1961 Donald Michie, a British pioneer of artificial intelligence who had worked at Bletchley Park on breaking German codes during the Second World War, wanted to show that a machine could learn to play a game. He had no computer to hand, so he built one out of matchboxes: about 300 of them (his 1963 paper says 287; most accounts say 304), one for every position MENACE (the Machine Educable Noughts And Crosses Engine) could face, each holding coloured beads. It was one of the first examples of what is now called machine learning, and of learning by reinforcement: rewarding the moves that led to a win and punishing the ones that led to a loss.

Noughts and crosses is a draw if both sides play perfectly. MENACE never learns that in words; it just stops making the moves that lose.

HOW IT WORKS

MENACE moves first, as noughts, as in Michie's games. Each square has its own bead colour (the dot in the corner of each square). To move, MENACE finds the box for the position, shakes it and draws a bead at random: its colour is the square it plays. Boxes start with beads for every free square: as in Michie's, 4 of each colour for its first move, then 3, 2 and 1 for its 2nd, 3rd and 4th moves (or pick 8, 4, 2, 1 below the matchbox).

After each game, every bead it drew is rewarded: a win puts it back with 3 more of the same colour, a draw with 1 more, and a loss keeps it out. Moves that win become more likely, moves that lose die out. If MENACE meets a box with no beads left, it resigns. With so few beads, a run of early losses can empty even its first box, and then it resigns every game, so this page normally never takes a box's last bead. Untick that to play by the strict rule.

Why 304 boxes here? A position and its turns and mirror images are really the same, so they share a box (and moves that a turn or mirror of the position swaps over share a bead colour, so the first box holds just three: corner, edge and centre). Counting the positions MENACE can face with a real choice to make, before its 1st, 2nd, 3rd and 4th moves, gives 1 + 12 + 108 + 183 = 304. Positions where someone has already won don't need a box, and nor does its 5th move, as only one square is left.

The perfect player looks ahead through every possible game (minimax). A hint shows what a square leads to if both sides then play perfectly: +1 a win, 0 a draw, −1 a loss. The rule player is the computer from a Python script, TicTacToe.py: win if it can, block if it must, otherwise take a corner, then the centre, then a side. Keys: 1 to 9 play a square, laid out like a number pad (7 8 9 on the top row); N starts a new game.

MENACE lives in this page only and is forgotten when you leave, unless you tick Remember MENACE, which saves it in this browser.

FURTHER WATCHING AND READING

PLAY

THE MATCHBOX

MENACEBOX —

Games0
Boxes opened0
Beads0
Start beads

LEARNING

Train against
Games