Can a Machine Learn a Game by Itself?

Teach HER yourself

Play HER at the top of the page, five or six games. Each time you win, watch the box HER opened last: the bead it drew is taken out, its arrow turns into a faint dashed line, and an empty ring is left where the bead was. Each time HER wins, nothing changes at all.

• a.Find a way to beat HER. Then try the same moves again. How many times does the same trick work?
• b.HER sometimes plays the mirror image of an arrow (⇆ in the corner of its box). Why can one box serve for a position and its mirror image?

Many games at once

Here HER plays two players that live in the page. Random plays any move it can. Sharp is a strong player: whenever it can see a way to win however HER answers, it plays it; otherwise it plays any move.

Nobody told it how to play

Look at what HER was given. A box for each position, and a bead for each legal move: just the rules. Nothing about which moves are good, no “take a pawn when you can” or “keep your pawns together”. It plays by chance, and a single rule changes the chances: after a loss, take out the bead of the last move.

The rule blames the last move HER made, the one closest to the loss. If an earlier move was the real mistake, no harm done: the position it led to keeps losing, its box empties bead by bead, and when HER opens an empty box it gives up, and the bead of the move before is taken out. The blame works its way back, one loss at a time, to the real mistake.

Why HER never throws away a good move

Call a move good if, after it, Black can still win however White plays. A good move can never be followed by White winning on the very next move: if White had such a move, Black’s position wouldn’t have been a win. So the bead taken out after a loss is never a good one, and an empty box is always a position where every move was bad.

So the beads HER loses are all bad beads. There are 17 of them, among 47. Each loss costs one, and none is ever put back, so HER can lose at most 17 games, ever, whoever teaches it. Once the bad beads it can meet are gone, only good moves are left, and only good moves are needed to win.

Learning from rewards

In Grades 6 and 7, models learned from examples with labels: a person had already said what each example was. HER has no labels. Nobody tells it which move was wrong; it only finds out, at the end, whether it won or lost. Learning from what happens after you act, a reward or a punishment, is called reinforcement learning: it is how a dog learns a trick. HER’s is the simplest kind, punishment only. Donald Michie’s MENACE, the matchbox machine that gave Gardner the idea, learned noughts and crosses with rewards too, in about 300 boxes: you can train it in Can Matchboxes Learn to Play?.

The game file (Python, from Grade 8)

The programs below share a file the page keeps for you, hexapawn.py: the rules, and the players Random and Sharp. A board is a string of 9 characters, the squares 0 to 8 along the rows from the top: 'B' a black pawn, 'W' a white pawn, '.' an empty square. So the start is 'BBB...WWW'. A move is a pair of square numbers, (from, to).

random.choice(list) picks one item of a list at random, each as likely as the others: that is HER shaking a box.

Step 1: HER’s boxes

HER keeps its boxes in a dictionary: like a list, but each item is found by a name instead of a number. boxes = {} makes an empty one; boxes[name] = value puts in a box; name in boxes asks whether that box is there yet. Here a box’s name is the position, and what is in it is a list of moves: the beads.

from hexapawn import START, moves, play, mirror, showimport randomrandom.seed(3) boxes = {} def her_turn(board):    # HER looks at the board, or at it in a mirror: the same game either way    if mirror(board) < board:        board = mirror(board)    if board not in boxes:        boxes[board] = moves(board, 'B')    # a new box: a bead for every move    beads = boxes[board]    if len(beads) == 0:        return board, None                  # an empty box: HER gives up    return board, random.choice(beads) board = play(START, (6, 3))     # White moves its left pawnshow(board)board, bead = her_turn(board)print('HER looks at it as')show(board)print('The box holds', boxes[board], 'and HER drew', bead)

BBBW...WWHER looks at it asBBB..WWW.The box holds [(0, 3), (1, 4), (1, 5)] and HER drew (0, 3)

mirror(board) < board compares the two strings as a dictionary orders words ('.' comes before 'B', 'B' before 'W'), so a position and its mirror image always end up with the same name and share a box. HER then plays on the mirrored board: the game is the same, seen from the other side. return board, None gives back two things at once, and board, bead = her_turn(board) takes them apart.

Step 2: one game, and the punishment

play_game plays one game against a White player and teaches HER after it. It remembers HER’s last move in last, so that after a loss it can take out that bead with remove, which takes one item out of a list. It gives back 'W' if HER won and 'L' if it lost.

from hexapawn import START, moves, play, has_lost, mirror, random_whiteimport randomrandom.seed(3) boxes = {} def her_turn(board):    if mirror(board) < board:        board = mirror(board)    if board not in boxes:        boxes[board] = moves(board, 'B')    beads = boxes[board]    if len(beads) == 0:        return board, None    return board, random.choice(beads) def play_game(white):    board = START    last = None                    # HER's last move: its box and its bead    while True:        board = play(board, white(board))        if has_lost(board, 'B'):            break                  # White has won        board, bead = her_turn(board)        if bead is None:            break                  # an empty box: HER gives up        last = (board, bead)        board = play(board, bead)        if has_lost(board, 'W'):            return 'W'             # HER won: nothing changes    box, bead = last    boxes[box].remove(bead)        # HER lost: out goes its last move's bead    print('Lost: bead', bead, 'taken out of box', box)    return 'L' for game in range(5):    print(play_game(random_white))

WWLost: bead (2, 4) taken out of box B.B.WW.W.LWW

When HER gives up, last is still its move before, so Gardner’s rule for an empty box needs no extra code: the same two lines take out that bead.

Step 3: fifty games against Sharp

Now a whole training. record collects a letter a game, and the program prints it ten games to a line, so you can read HER’s learning from left to right, top to bottom, like Gardner’s chart.

from hexapawn import START, moves, play, has_lost, mirror, sharp_whiteimport randomrandom.seed(1) boxes = {} def her_turn(board):    if mirror(board) < board:        board = mirror(board)    if board not in boxes:        boxes[board] = moves(board, 'B')    beads = boxes[board]    if len(beads) == 0:        return board, None    return board, random.choice(beads) def play_game(white):    board = START    last = None    while True:        board = play(board, white(board))        if has_lost(board, 'B'):            break        board, bead = her_turn(board)        if bead is None:            break        last = (board, bead)        board = play(board, bead)        if has_lost(board, 'W'):            return 'W'    box, bead = last    boxes[box].remove(bead)    return 'L' record = ''for game in range(50):    record = record + play_game(sharp_white)for start in range(0, 50, 10):    print(record[start:start + 10])print('Lost', record.count('L'), 'of 50; the last loss was game', record.rfind('L') + 1)beads = 0for box in boxes:    beads = beads + len(boxes[box])print('Boxes opened:', len(boxes), ' beads left in them:', beads)

WLLLLLLLWWWWLWWWWWWWWLLWWWWWWWWWWWWWWWWWWWWWWWWWWWLost 10 of 50; the last loss was game 23Boxes opened: 15  beads left in them: 28

Seven losses in a row at the start, while Sharp punishes every bad move it finds; then a few more as HER meets new positions; from game 24 on, none. (record.rfind('L') is the place of the last 'L', counted from 0.) Change random.seed(1) for another training: the losses come in a different order, and a last one or two may come much later, in a position HER meets only rarely.

One HER might be lucky. To be sure, train 50 HERs, each from new boxes for 200 games, against each player, and count each one’s losses. This program also checks every bead taken out against Sharp’s look-ahead, can_win: was it really a bad move?

from hexapawn import START, moves, play, has_lost, mirror, can_winfrom hexapawn import random_white, sharp_whiteimport randomrandom.seed(1) boxes = {} def her_turn(board):    if mirror(board) < board:        board = mirror(board)    if board not in boxes:        boxes[board] = moves(board, 'B')    beads = boxes[board]    if len(beads) == 0:        return board, None    return board, random.choice(beads) def play_game(white):    board = START    last = None    while True:        board = play(board, white(board))        if has_lost(board, 'B'):            break        board, bead = her_turn(board)        if bead is None:            break        last = (board, bead)        board = play(board, bead)        if has_lost(board, 'W'):            return 'W'    box, bead = last    boxes[box].remove(bead)    return 'L' def bad(box, bead):    # True if this move lets White win, however HER plays after it    return can_win(play(box, bead), 'W') for name, white in [('Random', random_white), ('Sharp', sharp_white)]:    most = 0    total = 0    good_lost = 0    for her in range(50):        boxes = {}        losses = 0        for game in range(200):            if play_game(white) == 'L':                losses = losses + 1        most = max(most, losses)        total = total + losses        for box in boxes:            for bead in moves(box, 'B'):                if bead not in boxes[box] and not bad(box, bead):                    good_lost = good_lost + 1    print(name + ': most losses', most, '| average', total / 50,          '| good beads taken out', good_lost) boxes = {}for game in range(200):    play_game(random_white)count = 0bad_beads = 0for box in boxes:    for bead in moves(box, 'B'):        count = count + 1        if bad(box, bead):            bad_beads = bad_beads + 1print(len(boxes), 'boxes,', count, 'beads,', bad_beads, 'of them bad')

Random: most losses 15 | average 12.06 | good beads taken out 0Sharp: most losses 12 | average 11.42 | good beads taken out 019 boxes, 47 beads, 17 of them bad

• No HER lost more than 15 games. Of 100 HERs, each playing 200 games, the one that lost most lost 15. Change the program to play thousands of HERs for thousands of games and, very rarely, one meets all 17 bad beads and loses 17 games. None can ever lose an 18th.
• Not one good bead was taken out, in 100 trainings and 20,000 games. Gardner’s rule only ever throws away mistakes.
• HER needs 19 boxes and 47 beads, as Gardner said (“otherwise nineteen boxes would suffice”).

And look at what the trained HER is: a player that wins every game as the second player. So a pile of matchboxes, told only the rules, has found out who wins hexapawn: with best play, Black always does. That is the whole idea of machine learning in one game. Nobody wrote the strategy down; it was squeezed out of the results.

Reward as well as punish. Gardner suggested that a robot could also be rewarded, with a bead of the right color added to each box it used when it wins: “Bad moves would not be eliminated so rapidly, but it would be less inclined to make the bad moves.” He also proposed a second robot, HIM, with a different system of reward and punishment. Make one: change play_game so that a win puts a second copy of each bead it drew back in its box (you will need a list of all HER’s moves in the game, not just last). Does HIM lose more games than HER, or fewer?

★ The mirror (Python, from Grade 8)

Write mirror(board) yourself: the board seen in a mirror, each row of three back to front. ('BB..W.W.W' has rows BB., .W., W.W.)

def mirror(board):    # board is 9 characters; give back each row of 3 back to front    return board print(mirror('BB..W.W.W'))

★★ Who has won? (Python, from Grade 8)

Write winner(board, side): side ('W' or 'B') is the player whose turn it is. Give back 'W' or 'B' if the game is over and that player has won, or '' if the game goes on. Remember Gardner’s three ways to win: a pawn on the far row, all enemy pawns taken, or the enemy to move and stuck.

def winner(board, side):    # board: 9 characters, rows from the top; side: whose turn it is    return '' print(winner('.B..WW...', 'B') == '')print(winner('W..BB...W', 'B'))

★★★ How many boxes? (Python, from Grade 8)

Without playing a single game, count the boxes HER needs: every position Black can face on its turn, in a game that isn’t over yet, from every possible game. Write count_boxes(use_mirror), giving back [boxes, beads] (the beads are the moves in all the boxes). With use_mirror True, a position and its mirror image count once.

def moves(board, side):    found = []    if side == 'W':        step = -3        enemy = 'B'    else:        step = 3        enemy = 'W'    for sq in range(9):        if board[sq] == side and 0 <= sq + step <= 8:            to = sq + step            if board[to] == '.':                found.append((sq, to))            if sq % 3 > 0 and board[to - 1] == enemy:                found.append((sq, to - 1))            if sq % 3 < 2 and board[to + 1] == enemy:                found.append((sq, to + 1))    return found def play(board, move):    a, b = move    squares = list(board)    squares[b] = squares[a]    squares[a] = '.'    return ''.join(squares) def has_lost(board, side):    if side == 'W' and 'B' in board[6:9]:        return True    if side == 'B' and 'W' in board[0:3]:        return True    return len(moves(board, side)) == 0 def mirror(board):    return (board[2] + board[1] + board[0] + board[5] + board[4] + board[3]            + board[8] + board[7] + board[6]) def count_boxes(use_mirror):    # every position Black can face, in a game not yet over    return [0, 0] print(count_boxes(True))

• Grade 6, Computers That Learn: a model that learns from examples, and Arthur Samuel’s checkers program that learned to beat its maker.
• Grade 7, How Machines Learn: features, labels, training and testing.
• Can You Beat a Computer at Rock-Paper-Scissors? A program that learns your habits by counting them.
• Can Eight Rules Play Tic-Tac-Toe Without Ever Losing? The other way: a person writes down the strategy.
• Can Matchboxes Learn to Play? (Grades 9–12): Michie’s MENACE, with rewards as well as punishments, learning noughts and crosses.