Can Matchboxes Learn to Play?

One game, box by box

Press Start again in the widget above, then Play 1 game, and watch closely.

• Before each of its moves MENACE opens one box: the one for the position on the board. Each box appears beside the board as a small card, drawn the way the board looked then.
• Each empty square with a colored circle has beads of that color in the box; the number is how many. One bead is drawn at random and its square is played: it gets a dark ring.
• When the game ends, every card shows what happened to its beads: +3 after a win, +1 after a draw, −1 after a loss.

Watch it learn

Press Start again, then 100 games. The chart is Michie’s own kind: the line goes up 3 for each win, up 1 for each draw and down 1 for each loss, so its slope tells you how well MENACE is playing.

Now look at MENACE’s first box after a few hundred games. Which of its three colors has nearly all the beads?

A different opponent

Now set O: to Random, a player that picks any empty square, and press 100 games a few times. (A dashed line on the chart marks where the opponent changed.)

Try to beat it

Finally set O: to You, and play. Find a way to beat MENACE, then play the same way again. And again.

A box for every position

MENACE moves first, so before its 1st, 3rd, 5th and 7th moves it can meet many different positions. Each has one matchbox. Its 9th move needs no box: only one square is left.

There are far fewer boxes than you might think, because of the board’s symmetry. Turning the board a quarter turn, half a turn or three quarters, or flipping it over (each of those four, flipped), gives 8 versions of every position, and a good move in one version is the same move, turned, in the others. So the 8 versions share one box. In Program it you will count the boxes this needs, as Michie did.

Inside each box are beads, one color for each different move. Michie gave the boxes for early moves more beads of each color than the boxes for late ones:

Drawing a bead is a choice at random, but not a fair one: a color with more beads is more likely. That is how MENACE “prefers” a move, and how a preference can grow.

Reward and punishment

After each game, the beads MENACE drew are dealt with, in every box it opened:

• a win: each bead goes back, with 3 more of its color;
• a draw: each goes back with 1 more;
• a loss: each is kept out of its box.

This is the whole of MENACE’s learning. A move that led to wins becomes more likely next time; a move that led to losses becomes less likely, and if it keeps losing, its color runs out and the move is never played again.

What if a box runs out of beads? Then every move MENACE knows from that position has lost, and MENACE resigns, which counts as a loss. Against a player who never makes a mistake this happens a lot, early on: every loss takes a bead from the first box, and with only 12 beads in it at the start, it can empty before MENACE has learned anything. Michie’s papers don’t say what he did about an empty box. Matthew Scroggs, who has built copies of MENACE, warns that against skilled players the first box can run out, and his online MENACE starts with more beads than Michie’s for this reason. Our MENACE, in the widget and in your program, keeps Michie’s beads and instead puts a box’s starting beads back when it empties, so it can try that position afresh. This rule matters: we ran the Step 3 program 200 times without it, and against Perfect its first box ran out for good in 121 of the 200 runs.

Learning from rewards

MENACE was one of the first machines to learn by reinforcement: it acts, it gets a reward or a punishment at the end, and it changes so that rewarded actions become more likely. Michie took the word from the psychologists who studied how animals learn by trial and error. In today’s words:

• each state (a position on the board) has a box;
• the actions (the moves) are the colors of beads;
• the reward (+3, +1 or −1 for each bead) comes only at the end of the game;
• the beads in all the boxes are MENACE’s policy: how likely each move is, in each state.

Nothing in the machine knows what a line of three is, or whose turn it is. The rules of the game are kept by the people playing with it. The boxes only ever learn from how games end.

Step 1: how many boxes?

First, give every position one name, the same for all 8 versions of it. Join the board’s 9 squares into a string, make the 8 versions, and take the smallest (Python compares strings letter by letter, and a space comes before 'O', which comes before 'X'). Then search every game, as the tic-tac-toe topic’s count_games did, collecting the names of the positions where it is X’s turn.

The search would visit 549,946 boards. But two positions with the same name have the same futures, only turned, so the program stops at a position it has already seen, and the search takes a moment.

LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8),         (0, 3, 6), (1, 4, 7), (2, 5, 8),         (0, 4, 8), (2, 4, 6)] def winner(board):    for a, b, c in LINES:        if board[a] != ' ' and board[a] == board[b] == board[c]:            return board[a]    return None # The 8 ways to turn or flip a board. A version's square i holds the# board's square way[i]; the first way leaves the board as it is.TURN = [6, 3, 0, 7, 4, 1, 8, 5, 2]       # a quarter turn clockwiseFLIP = [2, 1, 0, 5, 4, 3, 8, 7, 6]       # left to rightWAYS = []way = list(range(9))for _ in range(4):    WAYS.append(way)    WAYS.append([way[i] for i in FLIP])    way = [way[i] for i in TURN] def name(board):    """The smallest of the board's 8 versions, as a string, and the way that makes it."""    best, best_way = None, None    for way in WAYS:        version = ''.join(board[i] for i in way)        if best is None or version < best:            best, best_way = version, way    return best, best_way boxes = {1: set(), 3: set(), 5: set(), 7: set()}   # names, by MENACE's moveseen = set() def visit(board):    """Every game from board on, noting each position where X must choose."""    if winner(board) or ' ' not in board:        return    key = name(board)[0]    if key in seen:            # met before, maybe turned: same futures        return    seen.add(key)    marks = 9 - board.count(' ')    me = 'X' if marks % 2 == 0 else 'O'    if me == 'X' and marks < 8:        boxes[marks + 1].add(key)    for i in range(9):        if board[i] == ' ':            board[i] = me            visit(board)            board[i] = ' ' visit([' '] * 9)for move in boxes:    print(f'Boxes for move {move}:', len(boxes[move]))print('In all:', sum(len(names) for names in boxes.values()))print('Positions searched:', len(seen))

Boxes for move 1: 1Boxes for move 3: 12Boxes for move 5: 108Boxes for move 7: 183In all: 304Positions searched: 627

Your program finds 304 boxes, the number usually given for Michie’s machine.

Step 2: a box of beads

A box is a dictionary: for each color, the square it stands for and how many beads of it there are. new_box fills a box for a named position with one color for each different move (moves that give the same name share one) and Michie’s number of beads; draw_bead takes one at random, more beads more likely (random.choices with weights does exactly that).

From here on, the programs import winner and name from a file on this page, noughts.py, which also holds the page’s Perfect and Random players. You can use it without reading it.

import randomfrom noughts import name START = {9: 4, 7: 3, 5: 2, 3: 1}     # beads of each color, by empty squares def new_box(position):    """A new box for a named position: Michie's beads for each different move."""    box = {}    seen = []    for s in range(9):        if position[s] == ' ':            after = list(position)            after[s] = 'X'            if name(after)[0] not in seen:                seen.append(name(after)[0])                box[s] = START[position.count(' ')]    return box def draw_bead(box):    """A square from the box, at random: more beads, more likely."""    squares = list(box)    return random.choices(squares, weights=[box[s] for s in squares])[0] print('The first box:', new_box(' ' * 9)) board = ['X', ' ', ' ',         ' ', 'O', ' ',         ' ', ' ', ' ']position, way = name(board)print('X in a corner, O in the center is named', repr(position))print('Its box:', new_box(position)) random.seed(1)first = new_box(' ' * 9)print('Ten beads from the first box:', [draw_bead(first) for _ in range(10)])

The first box: {0: 4, 1: 4, 4: 4}X in a corner, O in the center is named '    O   X'Its box: {0: 3, 1: 3, 2: 3, 5: 3}Ten beads from the first box: [0, 4, 4, 0, 1, 1, 1, 4, 0, 0]

The first box has three colors, square 0 (a corner), 1 (a side) and 4 (the center), with 4 beads each. The second position has seven empty squares but only four different moves: the board is the same flipped along the diagonal through X and O, so squares on either side of it are the same move. Michie gives the same kind of example in his 1963 paper, a position with the center and a corner taken: “At first sight there are seven possible moves available. Considerations of symmetry, however, reduce these to four.”

The name is the board’s smallest version, so X is on square 8 in the name, not square 0 where it is on the board. A bead for square s of the name is played on the board’s square way[s]: that is the job of the way that name gives back.

Step 3: play, and learn

Now the whole machine. play_game keeps the boxes in a dictionary, boxes, the name of a position as its key; a box is made the first time its position comes up, as if the matchbox were filled just then. For each of MENACE’s moves it finds the box, draws a bead and plays it, remembering which bead came from which box. At the end it puts the beads back, or not.

It plays 300 games against the perfect player and prints how they went, 50 games at a time. The picture shows every game as a square, 30 to a row: green a win, gray a draw, red a loss. (pixels is this page’s own module for small pictures.)

import randomfrom noughts import winner, name, perfect_move, random_movefrom pixels import show_grid START = {9: 4, 7: 3, 5: 2, 3: 1}             # beads of each color, by empty squaresREWARD = {'win': 3, 'draw': 1, 'loss': -1}   # beads added to each one drawn def new_box(position):    box = {}    seen = []    for s in range(9):        if position[s] == ' ':            after = list(position)            after[s] = 'X'            if name(after)[0] not in seen:                seen.append(name(after)[0])                box[s] = START[position.count(' ')]    return box def draw_bead(box):    squares = list(box)    return random.choices(squares, weights=[box[s] for s in squares])[0] def play_game(boxes, opponent):    """MENACE (X) plays one game against opponent (O), then learns from it."""    board = [' '] * 9    drawn = []                                # (position, bead) for each move    while True:        if board.count(' ') == 1:             # one square left: no choice            board[board.index(' ')] = 'X'            result = 'win' if winner(board) else 'draw'            break        position, way = name(board)        if position not in boxes:            boxes[position] = new_box(position)        box = boxes[position]        if sum(box.values()) == 0:            # an empty box: MENACE resigns,            boxes[position] = new_box(position)   # and the box is filled again            result = 'loss'            break        bead = draw_bead(box)        drawn.append((position, bead))        board[way[bead]] = 'X'        if winner(board):            result = 'win'            break        board[opponent(board)] = 'O'        if winner(board):            result = 'loss'            break    for position, bead in drawn:              # the beads go back, or not        box = boxes[position]        box[bead] = max(0, box[bead] + REWARD[result])    return result def choose_move(board):    """MENACE's move in a game against you: a bead from its boxes."""    if board.count(' ') == 1:        return board.index(' ')    position, way = name(board)    box = boxes.get(position) or new_box(position)    if sum(box.values()) == 0:        box = new_box(position)    return way[draw_bead(box)] random.seed(1)boxes = {}results = [play_game(boxes, perfect_move) for game in range(300)]for start in range(0, 300, 50):    games = results[start:start + 50]    print(f'Games {start + 1}–{start + 50}:', games.count('win'), 'won,',          games.count('draw'), 'drawn,', games.count('loss'), 'lost')print('Boxes opened:', len(boxes))print('The first box:', boxes[' ' * 9])show_grid([results[row:row + 30] for row in range(0, 300, 30)],          {'win': 'green', 'draw': 'lightgray', 'loss': 'firebrick'})

Games 1–50: 0 won, 15 drawn, 35 lostGames 51–100: 0 won, 47 drawn, 3 lostGames 101–150: 0 won, 49 drawn, 1 lostGames 151–200: 0 won, 49 drawn, 1 lostGames 201–250: 0 won, 50 drawn, 0 lostGames 251–300: 0 won, 50 drawn, 0 lostBoxes opened: 38The first box: {0: 0, 1: 0, 4: 245}

Picture

Look at the last line: almost every bead in the first box is on square 4. Your MENACE has learned to open in the center, which nobody told it. (Michie’s MENACE, playing against Michie, settled on a corner instead. What a learner learns depends on whom it learns from.)

The program also defines choose_move, MENACE’s move from its trained boxes, for the board below. Play it: it is your MENACE, after its 300 games.

Step 4: against a random player

Michie’s matchbox machine was later copied as a program on a Pegasus 2 computer, which played about a game a second, and Michie could set it against a random player. He found that learning against random play was “an enormously more difficult and time-consuming task” than against an expert. Check it: here is the same MENACE against random_move, for 1,000 games.

import randomfrom noughts import winner, name, random_movefrom pixels import show_grid START = {9: 4, 7: 3, 5: 2, 3: 1}REWARD = {'win': 3, 'draw': 1, 'loss': -1} def new_box(position):    box = {}    seen = []    for s in range(9):        if position[s] == ' ':            after = list(position)            after[s] = 'X'            if name(after)[0] not in seen:                seen.append(name(after)[0])                box[s] = START[position.count(' ')]    return box def draw_bead(box):    squares = list(box)    return random.choices(squares, weights=[box[s] for s in squares])[0] def play_game(boxes, opponent):    board = [' '] * 9    drawn = []    while True:        if board.count(' ') == 1:            board[board.index(' ')] = 'X'            result = 'win' if winner(board) else 'draw'            break        position, way = name(board)        if position not in boxes:            boxes[position] = new_box(position)        box = boxes[position]        if sum(box.values()) == 0:            boxes[position] = new_box(position)            result = 'loss'            break        bead = draw_bead(box)        drawn.append((position, bead))        board[way[bead]] = 'X'        if winner(board):            result = 'win'            break        board[opponent(board)] = 'O'        if winner(board):            result = 'loss'            break    for position, bead in drawn:        box = boxes[position]        box[bead] = max(0, box[bead] + REWARD[result])    return result random.seed(1)boxes = {}results = [play_game(boxes, random_move) for game in range(1000)]for start in range(0, 1000, 200):    games = results[start:start + 200]    print(f'Games {start + 1}–{start + 200}:', games.count('win'), 'won,',          games.count('draw'), 'drawn,', games.count('loss'), 'lost')print('Boxes opened:', len(boxes), 'of 304')show_grid([results[row:row + 50] for row in range(0, 1000, 50)],          {'win': 'green', 'draw': 'lightgray', 'loss': 'firebrick'})

Games 1–200: 129 won, 31 drawn, 40 lostGames 201–400: 145 won, 23 drawn, 32 lostGames 401–600: 151 won, 22 drawn, 27 lostGames 601–800: 156 won, 25 drawn, 19 lostGames 801–1000: 162 won, 20 drawn, 18 lostBoxes opened: 230 of 304

Picture

It wins most games from the start, since a random player makes many mistakes. But the losses fall slowly and never stop. Against Perfect, MENACE opened about 40 boxes; against Random it opened most of the 304, and each of those boxes has to learn on its own, from the few games that pass through it. A random opponent shows MENACE everything, a little at a time; an expert shows it a few positions, again and again.

Your programs, not a person, have shown three things.

• a.MENACE needs 304 boxes (Step 1), thanks to the board’s 8 symmetries; without them it would need 2,201.
• b.Beads alone learn to stop losing (Step 3). Against a perfect player your MENACE lost 35 of its first 50 games and none of its last 100, and nobody gave it a rule. It even found an opening, the center, by itself.
• c.What it learns depends on its teacher (Steps 3 and 4). Against an expert it learns a narrow path fast and is lost off it; against a random player it sees everything but learns slowly.

That is reinforcement learning, small enough to hold in your hands. Its weakness is size: one box for every position works for noughts and crosses, but chess has around 10⁴⁴ positions, a 1 followed by 44 zeros. So learners of today keep no boxes. A neural network (Grade 11) takes a position it has never seen and guesses how many beads each move should have, and the rewards adjust the network’s weights instead of the beads. That is how AlphaGo, the program that beat the Go champion Lee Sedol in 2016, got better: it learned first from people’s games, then by playing millions of games against itself, rewarded only for winning (Grade 12’s Learning from rewards tells its story).

Change the rewards

Michie chose +3, +1 and −1. Do the numbers matter?

Two learners

Michie’s computer version could let both players learn at once. He reported that “after a few hundred games the two sides were both producing near-expert play”. To try it, give O boxes of its own (named from O’s side: count the boxes it needs in Challenge ★★), and in play_game let each player draw from its own boxes and learn from its own result.

Questions to think about

How many matchboxes would MENACE need for a 4 × 4 board, four in a row to win? Your Step 1 program could find out, but it would search for a long time: think first about how many positions there could be. And chess? Then think about what a learner must do differently when it can’t have a box for every position.

Three challenges, each checked on the page: write your function in the program above the checker (press Edit), then press Check my program. The examples show what your function should give; there are more tests you can’t see.

★ Back into the box

Write after_game(beads, square, result). beads is a list of 9 numbers, how many beads of each square’s color a box holds (0 for squares without a color); square is the bead MENACE drew from it; result is 'win', 'draw' or 'loss'. Give back the new list after Michie’s rules: 3 more beads of that color for a win, 1 more for a draw, 1 fewer for a loss, but never fewer than 0. Don’t change the list you were given.

def after_game(beads, square, result):    # Give back a new list of 9 bead counts.    return beads print(after_game([4, 4, 0, 0, 4, 0, 0, 0, 0], 4, 'win'))

★★ Boxes for the second player

MENACE always moved first. A MENACE that plays O, second, would need boxes for the positions before O’s 2nd, 4th, 6th and 8th moves. Write count_boxes(mark): a list of how many boxes the player mark ('X' or 'O') needs before each of its moves, in order. For 'X' it gives Step 1’s numbers, [1, 12, 108, 183]. Count a position once however it is turned or flipped, leave out finished games, and leave out a move with only one square left (it needs no box).

LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8),         (0, 3, 6), (1, 4, 7), (2, 5, 8),         (0, 4, 8), (2, 4, 6)] def winner(board):    for a, b, c in LINES:        if board[a] != ' ' and board[a] == board[b] == board[c]:            return board[a]    return None TURN = [6, 3, 0, 7, 4, 1, 8, 5, 2]FLIP = [2, 1, 0, 5, 4, 3, 8, 7, 6]WAYS = []way = list(range(9))for _ in range(4):    WAYS.append(way)    WAYS.append([way[i] for i in FLIP])    way = [way[i] for i in TURN] def name(board):    return min(''.join(board[i] for i in way) for way in WAYS) def count_boxes(mark):    # Give back the number of boxes before each of mark's moves.    return [] print(count_boxes('X'))

★★★ The first box after the tournament

Suppose a tournament’s games are written down as they were played on a real board, so MENACE’s opening may be in any corner, but every corner is the same corner bead. Write opening_box(games). Each game is the list of squares played in order, MENACE (X) first, to the end of the game. Starting from Michie’s first box (4 beads each on squares 0, 1 and 4: corner, side, center), give back its 9 bead counts after MENACE learns from every game in turn: the color of the game’s first move gets 3 more beads for a win, 1 more for a draw, 1 fewer for a loss (never below 0).

def opening_box(games):    # Give back the first box's 9 bead counts after all the games.    return [4, 4, 0, 0, 4, 0, 0, 0, 0] print(opening_box([[8, 4, 0, 2, 6, 3, 7]]))

• Grade 12, Learning from rewards: Q-learning, a walker that learns the shortest way to a tea shop from points won and lost, and AlphaGo.
• Grade 11, Neural Networks: how a network learns by small corrections, the step from a box for every position to a guess for any position.
• Grade 9, Machine Learning: the kinds of AI, and learning from examples.
• How Can a Computer Never Lose at Tic-Tac-Toe?: the other way to play perfectly, by searching every future.