mnk-bench
1961, rebuilt in JavaScript

Teach a pile of matchboxes to play

MENACE (Machine Educable Noughts And Crosses Engine) was built by Donald Michie in 1961 from about 300 matchboxes and a bag of coloured beads. It knows nothing about the game except which moves are legal, and it learns only from wins, draws and losses. This page runs the same algorithm. Train it, watch how its beads change, and then try to beat it.

In one sentence: each position has a box of beads, one colour per possible move. MENACE moves by drawing a random bead, then after the game it adds beads for the moves of a game it won or drew and takes them away after a loss, so good moves slowly become likely and bad ones rare.

Reading the board: the number on an empty cell is how many beads MENACE holds for that move in the box for the position shown. Darker cells have more beads, so MENACE is more likely to pick them. Cells that are mirror images of each other show the same number because they share one bead colour. During Watch one game, the drawn bead is outlined.

Learning curve

Share of the last 200 games won, drawn and lost, plotted as training goes on. Switching the training opponent mid-run shows up as a change in the curve.

wondrawnlost

How MENACE works

1

One matchbox per position

Every position MENACE might have to move from gets its own box. Positions that are rotations or reflections of each other share a box, which is how Michie fit tic-tac-toe into about 300 boxes. Positions with only one sensible move (after symmetry) get no box at all. For X on tic-tac-toe that leaves exactly 304 possible boxes, and this page reproduces that count.

2

One bead colour per move

A new box starts with the same number of beads for every distinct move: 4 each for MENACE's first move, then 3, 2 and 1 for its later moves (Michie's schedule). Early moves start with more beads, so they change more slowly.

3

Move by drawing a bead

To move, MENACE opens the box for the current position and draws a bead at random. A move with 6 beads in a box holding 8 in total is chosen 75% of the time. Even after training, a move with a few beads left can still be drawn now and then.

4

Learn from the result

After the game, every move MENACE made gets +3 beads for a win, +1 for a draw and −1 for a loss. Moves that keep losing run out of beads and stop being played. If a whole box runs empty, Michie's machine resigned; this version refills it.

That is the whole algorithm: there is no search and no evaluation of positions. MENACE only remembers which beads came out in games that went well, the simplest form of reinforcement learning.

What to expect on tic-tac-toe

Typical results for this page's MENACE, averaged over 8 training runs. Each cell is the share of the last 200 games won / drawn / lost. Your run will differ by a few points, because every bead draw is random.

MENACE playstraining opponent100 games3001,0005,000boxes used
XRandom66 / 12 / 2270 / 12 / 1880 / 9 / 1185 / 9 / 6~285
XPerfect play0 / 70 / 300 / 97 / 30 / 100 / 00 / 100 / 0~31
XMix (half random, half perfect)36 / 24 / 4146 / 30 / 2560 / 32 / 868 / 29 / 3~210
XRule-based0 / 69 / 310 / 99 / 10 / 100 / 00 / 100 / 0~21
ORandom34 / 13 / 5444 / 16 / 4061 / 16 / 2375 / 13 / 13~274
OPerfect play0 / 5 / 950 / 18 / 820 / 93 / 80 / 100 / 0~97
OMix (half random, half perfect)14 / 11 / 7522 / 23 / 5541 / 42 / 1746 / 50 / 4~222

Against perfect play it can only draw

Tic-tac-toe is a draw with best play, so a perfect opponent can never be beaten. The best MENACE can do is learn to draw every game. It manages that within a few hundred games as X, and about 1,000 as O, which is harder.

Fast learning can be narrow learning

A perfect or rule-based opponent steers every game down the same few lines, so MENACE meets only 20 to 100 positions and learns just those. Against random play it sees almost all of them but learns more slowly: random opponents rarely punish a bad move, so its losses fade gradually and never quite reach zero.

Try it

Train against Perfect play until it draws every game, then switch the opponent to Random. Losses reappear, because random play reaches positions MENACE never met. The mix of both teachers is the best all-round training: in the benchmark it reached 100% non-loss against perfect play within about 2,000 games.

Why it can't scale

MENACE needs a box for every position it might face, and it only learns about positions it has actually played. On tic-tac-toe that is a few hundred boxes. Switch the board to (4,4,4) and the box count climbs into the thousands while the learning curve barely moves. A board like (6,6,4) has up to about 3×1015 positions, even after symmetry. In the benchmark, tables trained for 3,000 games had seen only 28 to 50% of the positions they met there, and they lost to the rule-based player every game. On gomoku it would need more boxes than there are atoms in the universe. Exact search fails at about the same size; the overview shows where every method breaks.

MENACE elsewhere on this site

On the Play and Arena pages, MENACE is listed under Learning: MENACE-style matchboxes. There it trains before its first move (2,000 games by default, half against random play and half against perfect or rule-based play), then plays the move with the most beads instead of drawing at random. When it reaches a position it never saw in training, it says so and moves at random. On big boards that happens almost every move, which is the scaling problem in action.

Full experiments, including symmetry ablations and the comparison with Q-learning and TD(0): results report.