Why random moves troubled an AI trained against perfect play

After 20,000 training games apiece against our perfect-play opponent, five little software learners had an average calculated loss probability below two in ten thousand. Against random moves, the same five learned policies had an average loss probability of about one in five.

This happened in a software experiment built for this article, using a simplified version of MENACE: Donald Michie’s Matchbox Educable Noughts And Crosses Engine. The mismatch is visible enough to inspect move by move. It also gives a wonderfully modest machine something useful to say about learning.[1]

Memory you could shake

Michie’s route into artificial intelligence ran through wartime codebreaking and genetics. His own curriculum vitae records service at Bletchley Park, a doctorate in mammalian genetics and, later, the Experimental Programming Unit at Edinburgh. The matchbox work belongs to the early 1960s, when he was investigating how experience could change a machine’s future choices.[2]

In his 1963 paper, each recognisable game position has a box. Coloured beads stand for possible moves. Drawing a bead chooses a move; the result of the game changes the contents of the boxes used. A win adds three beads of each selected colour, a draw adds one, and a loss removes one. Moves associated with better results become more likely to be drawn again.[1]

The appeal is its physical clarity. There is no need to imagine a mysterious intelligence hiding behind an answer. A preference is a count of beads. Learning is a change in that count. If a move has become popular for the wrong reason, you can point to where that preference is stored.

Mathematician Matthew Scroggs built a modern copy in 2016 and offers an interactive version online. His account of training a copy for the Royal Institution’s 2019 Christmas lecture includes visualisations of changing bead counts. Some boxes accumulate strong preferences; others change less often because their positions arise less frequently. The machine’s history is distributed unevenly across its memory.[3][4]

The experiment: same learner, different schooling

Our reconstruction always plays first. It shares a virtual box between rotated or reflected versions of a board, while keeping a separate colour for every legal square. A box begins with four beads per move on the opening turn, then three, two or one at later decisions. Wins, draws and losses use the rewards above. If a box empties, our version refills it; that explicit adaptation prevents permanent resignation.

We trained five copies against random legal moves and five against a minimax opponent. Minimax looks through the remaining game tree and selects a move that secures the best possible result against perfect replies. Our opponent chooses randomly when several moves are equally good. It plays perfectly in that game-theoretic sense; it does not specifically hunt for the weaknesses of the learned policy.

Each copy played 20,000 training games, using fixed random seeds 0–4. We then froze learning and calculated outcome probabilities across the complete game tree against each opponent. These are exact probabilities for the resulting policies, averaged across five training runs. They are not percentages from a small sample of test games, and the five-run range is not a statistical confidence interval.

Before learning, the loss probability was 28.81% against random play and 77.75% against our minimax opponent. Training against minimax brought the latter down to 0.019%. Yet those learners still lost 20.64% of games against random play. Across their five runs, that random-opponent loss probability ranged from 14.29% to 25.67%.

Training against random moves produced a different balance: a 4.53% average loss probability against random play, but 37.88% against minimax. The same update rule, playing the same small game, had learned markedly different habits.

The positions an expert never gives you

There is no paradox in the rules of noughts and crosses. A perfect first player can avoid defeat against any legal reply. Our learner was never given that complete strategy. It was rewarded for the choices made in the particular games it experienced.

A perfect opponent rules out many of its own bad moves. Those omissions also remove opportunities for the learner to practise responding to them. A random opponent wanders into different branches. There, a previously reliable learner may encounter a thinly trained box and make a poor choice. Being exposed to a wider assortment of positions can matter more than the opponent’s skill alone.

Michie had already identified this issue. His 1963 account explains that stereotyped or expert opponents restrict the subtree a learner must explore, making comparison with random-opponent learning misleading. His computer simulations also used different reinforcement rules from the physical boxes. Our results are an illustration under declared rules, rather than a replication of his historical measurements.[1]

What remains useful is the machine’s legibility. A matchbox does not know that its opponent is an expert. It receives a sequence of positions and a final reward. Change the opponent, and you change the experiences from which its apparent expertise is made.

Report an error or suggest a correction