How Can a Computer Never Lose at Tic-Tac-Toe?

Play the computer a few more times, and watch what it does.

• When you have two in a row, it always blocks the third square (unless it can win at once instead).
• When it has two in a row and it is its turn, it always wins at once.
• When you take a corner first, it always takes the center.

Now give it a weaker opponent. Set X: to Random (a player that picks any empty square) and O: to Perfect, and press New game a few times. Then swap them.

Could a list of rules do it?

You might try to write down the computer’s rules. A well-known priority list a computer can follow is usually traced to a program in Allen Newell and Herbert Simon’s 1972 book Human Problem Solving:

• a.Win: if you have two in a row, play the third.
• b.Block: if the other player has two in a row, play the third.
• c.Fork: make two lines of two at once, so the other player can block only one.
• d.Block a fork the other player could make.
• e.Take the center.
• f.Take a corner opposite the other player’s corner.
• g.Take an empty corner.
• h.Take an empty side.

Rules like these do work for tic-tac-toe. But who checks that they are right in every game? And they are useless for the next game you want to play: chess, Bagh-Chal, or one you invent. This topic’s player has no rules about tic-tac-toe at all. It knows only what the game’s rules say: whose turn it is, which squares are empty, and who has three in a row. Everything else it works out.

The computer plays by imagining every way the rest of the game could go. Before each move it asks, for every empty square: “If I play here, and then we both play as well as possible, how does the game end?”

That question sounds as if it needs the answer it is trying to find (“as well as possible”). It doesn’t, because it can be answered from the end of the game backwards.

Scoring a board

Give every board a score from X’s point of view:

• a board where X has three in a row scores 1;
• a board where O has three in a row scores −1;
• a full board with no three in a row (a draw) scores 0.

Those are the boards where the game has ended. For any other board, look at whose turn it is:

• If it is X’s turn, X will choose the move that is best for X: the board’s score is the largest of the scores of the boards X could make.
• If it is O’s turn, O will choose the move that is worst for X: the score is the smallest of them.

X tries to make the score as large as possible and O tries to make it as small as possible, which is why this method is called minimax. A board’s score tells you how the game ends from there if both players make no mistakes: 1, X wins; −1, O wins; 0, a draw.

A game three moves from the end

Here is a game near its end. X is to move, and only the bottom row is empty.

Minimax works this out with a function, score(board), that scores a board. To score this board, it tries X in square 6 and scores that board; then X in 7, and scores that; then 8. To score “X in 7”, it must try each of O’s replies and score those. And so on, until a board is finished. A function that calls itself like this is recursive: each call works on a board with one more mark on it, so the calls always reach a finished board and stop. (Grade 11’s Recursion is all about functions like this.)

Step through the calls. Each box in the tree is one call of score, with the bottom row of its board; the top two rows don’t change.

Notice how the scores come back up the tree: at the boards where O is to move, the smaller score wins; at the top, where X is to move, the larger. Eleven calls were enough here because the game was nearly over. From the empty board, how many would there be? You will find out by counting.

You will build the player in four steps, each one running here on the page.

Step 1: the board and the rules

A board is a list of 9 strings, 'X', 'O' or ' ' (a space for an empty square), in the order of the square numbers. These two functions are all the program knows about tic-tac-toe: who has won, and whose turn it is (X goes first, so X is to move whenever the two have played the same number of times).

LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8),   # rows         (0, 3, 6), (1, 4, 7), (2, 5, 8),   # columns         (0, 4, 8), (2, 4, 6)]              # diagonals def winner(board):    for a, b, c in LINES:        if board[a] != ' ' and board[a] == board[b] == board[c]:            return board[a]    return None def to_move(board):    if board.count('X') == board.count('O'):        return 'X'    return 'O' board = ['X', 'O', 'X',         'X', 'O', 'O',         ' ', ' ', ' ']print(winner(board), to_move(board))board[6] = 'X'print(winner(board))

None XX

Step 2: how many games are there?

Before choosing moves, count the futures. count_games(board) gives the number of different ways a game can go on from board to its end. A finished board is one game. Otherwise, try each empty square in turn: put the mark there, count the games from the new board (a call to count_games itself), and take the mark off again.

There are a lot of games, so to keep this quick on a phone the program counts only the games where X starts in square 0 (a corner), square 1 (a side) and square 4 (the center). Turning the board round shows that every corner start has as many games as square 0, and every side as square 1, so the total is 4 × corner + 4 × side + center.

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 def to_move(board):    if board.count('X') == board.count('O'):        return 'X'    return 'O' def count_games(board):    if winner(board) or ' ' not in board:        return 1    total = 0    for i in range(9):        if board[i] == ' ':            board[i] = to_move(board)            total = total + count_games(board)            board[i] = ' '    return total def games_after(first):    board = [' '] * 9    board[first] = 'X'    return count_games(board) corner = games_after(0)side = games_after(1)center = games_after(4)print('X starts in a corner:', corner)print('X starts on a side:  ', side)print('X starts in the center:', center)print('All games:', 4 * corner + 4 * side + center)

X starts in a corner: 27732X starts on a side:   29592X starts in the center: 25872All games: 255168

There are 255,168 different games of tic-tac-toe. Nobody could play them all, but the program just did, about 83,000 of them, in well under a second.

Step 3: minimax, and a player

Now the same search, but instead of adding up the games, score gives back the best score, as in the tree above: the largest when X is to move, the smallest when O is. choose_move then tries every empty square and keeps the one with the best score for the player to move.

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 def to_move(board):    if board.count('X') == board.count('O'):        return 'X'    return 'O' def score(board):    w = winner(board)    if w == 'X':        return 1    if w == 'O':        return -1    if ' ' not in board:        return 0    me = to_move(board)    results = []    for i in range(9):        if board[i] == ' ':            board[i] = me            results.append(score(board))            board[i] = ' '    if me == 'X':        return max(results)    return min(results) def choose_move(board):    me = to_move(board)    best = None    for i in range(9):        if board[i] == ' ':            board[i] = me            s = score(board)            board[i] = ' '            if best is None or (me == 'X' and s > best_score) or (me == 'O' and s < best_score):                best = i                best_score = s    return best board = ['X', 'O', 'X',         'X', 'O', 'O',         ' ', ' ', ' ']print(choose_move(board))

6

It finds square 6, as the tree did. Now let it play. The board below takes choose_move from the program just above, as you have it (press Edit above to change it), and calls it for every O move. You are X.

Step 4: remember what you have worked out

The search is slow because it scores the same boards again and again. Look at these two openings: X in 0, O in 4, X in 8; and X in 8, O in 4, X in 0. Different orders, the same board. The plain search scores it, and everything after it, twice. Many boards can be reached in hundreds of different ways.

The fix is to keep a dictionary, memo, of the boards already scored. The board’s 9 squares joined into one string, such as 'XO X O', is its key. Before searching, score looks the board up; after searching, it writes the answer down. This is called memoization (writing a memo to yourself), and Grade 12’s Dynamic programming is built on it.

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 def to_move(board):    if board.count('X') == board.count('O'):        return 'X'    return 'O' memo = {} def score(board):    key = ''.join(board)    if key in memo:        return memo[key]    w = winner(board)    if w == 'X':        result = 1    elif w == 'O':        result = -1    elif ' ' not in board:        result = 0    else:        me = to_move(board)        results = []        for i in range(9):            if board[i] == ' ':                board[i] = me                results.append(score(board))                board[i] = ' '        if me == 'X':            result = max(results)        else:            result = min(results)    memo[key] = result    return result def choose_move(board):    me = to_move(board)    best = None    for i in range(9):        if board[i] == ' ':            board[i] = me            s = score(board)            board[i] = ' '            if best is None or (me == 'X' and s > best_score) or (me == 'O' and s < best_score):                best = i                best_score = s    return best print('Score of the empty board:', score([' '] * 9))print('Different boards scored:', len(memo))

Score of the empty board: 0Different boards scored: 5478

This time it scored the empty board itself, every game from the very first move, and it was quick: 5,478 different boards, each scored once, instead of the hundreds of thousands of boards met along the 255,168 games. How much quicker? This program times both searches from the same board, after X has taken a corner:

import time 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 def to_move(board):    if board.count('X') == board.count('O'):        return 'X'    return 'O' def score(board, memo):    key = ''.join(board)    if memo is not None and key in memo:        return memo[key]    w = winner(board)    if w == 'X':        result = 1    elif w == 'O':        result = -1    elif ' ' not in board:        result = 0    else:        me = to_move(board)        results = []        for i in range(9):            if board[i] == ' ':                board[i] = me                results.append(score(board, memo))                board[i] = ' '        result = max(results) if me == 'X' else min(results)    if memo is not None:        memo[key] = result    return result board = ['X'] + [' '] * 8start = time.perf_counter()score(board, None)plain = time.perf_counter() - startstart = time.perf_counter()score(board, {})remembered = time.perf_counter() - startprint(f'Without a memo: {plain:.3f} seconds')print(f'With a memo:    {remembered:.3f} seconds')print(f'{plain / remembered:.0f} times faster')

Your times depend on your computer, so they aren’t printed here. These are ours:

The times changed a little from run to run, so these are typical ones. From the empty board the difference is bigger still: on the laptop, about 0.5 seconds without a memo and 0.01 seconds with one, about 50 times faster. The more ways there are to reach each board, the more the memo saves. A phone is several times slower than a laptop, which is why the plain search from the empty board is too slow there, and the memoized one isn’t.

Now your memoized choose_move can play X from the empty board without a wait, and play many games quickly. The board below takes it from the program above. Set the two players and press Play 100 games.

Your program, not a person, has just proved three things.

• a.There are 255,168 different games of tic-tac-toe (Step 2).
• b.The empty board scores 0 (Step 4): if both players play perfectly, every game is a draw. Neither X nor O can force a win. That is why good players draw.
• c.A player that searches every future never loses, without a single rule about forks or corners. The rules Newell and Simon wrote down aren’t needed: minimax finds them.

So why do people still lose? Because the other player can make it hard to see the right move. This program scores every first move for X, and counts how many of O’s 8 replies lose for O:

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 def to_move(board):    if board.count('X') == board.count('O'):        return 'X'    return 'O' memo = {} def score(board):    key = ''.join(board)    if key in memo:        return memo[key]    w = winner(board)    if w == 'X':        result = 1    elif w == 'O':        result = -1    elif ' ' not in board:        result = 0    else:        me = to_move(board)        results = []        for i in range(9):            if board[i] == ' ':                board[i] = me                results.append(score(board))                board[i] = ' '        result = max(results) if me == 'X' else min(results)    memo[key] = result    return result for first, name in [(0, 'a corner'), (1, 'a side'), (4, 'the center')]:    board = [' '] * 9    board[first] = 'X'    losing = []    for reply in range(9):        if board[reply] == ' ':            board[reply] = 'O'            if score(board) == 1:                losing.append(reply)            board[reply] = ' '    print(f'X takes {name} ({first}): score {score(board)},',          f'{len(losing)} of 8 replies lose for O:', losing)

X takes a corner (0): score 0, 7 of 8 replies lose for O: [1, 2, 3, 5, 6, 7, 8]X takes a side (1): score 0, 4 of 8 replies lose for O: [3, 5, 6, 8]X takes the center (4): score 0, 4 of 8 replies lose for O: [1, 3, 5, 7]

Every first move scores 0: none of them wins by force. But after a corner, only one reply out of eight is safe for O, the center. So against a person, a corner is the best start, and the perfect player’s habit of answering a corner with the center isn’t a rule someone gave it: it is the only move that doesn’t lose.

Win quickly, lose slowly

Play your Step 4 program against Random and watch closely: sometimes, with a win right in front of it, it plays somewhere else and wins two moves later. To minimax, a win is a win (score 1) however long it takes. Change the scores so that a quicker win is worth more: score a win for X as 1 + board.count(' '), a win for O as -1 - board.count(' '). More empty squares means the game ended sooner. Then it takes a win at once, and when it is losing, it holds out as long as it can. That is Challenge ★★★ below.

Turning and flipping the board

Many of the 5,478 boards are the same board turned round or flipped over, and their scores are the same.

Bigger games

Minimax works for any game where two players take turns and both can see everything: noughts and crosses, Bagh-Chal, chess. The trouble is size. Claude Shannon worked out in 1950 that chess has something like 10¹²⁰ possible games, a number with 121 digits. No computer will ever play them all, so chess programs look only a few moves ahead and then guess a score for the board they reach, from the pieces and their positions. Deep Blue, the IBM computer that beat the world champion Garry Kasparov 3½–2½ in May 1997, searched like this, through 200 million positions a second, skipping moves that couldn’t change its choice (a trick called alpha–beta pruning).

A question to think about: tic-tac-toe on a 4 × 4 board, four in a row to win. It is known to be a draw too, but your program can’t simply be run to show it. Each of the 16 squares is empty, X or O, so there are at most 3¹⁶, about 43 million, boards. Roughly how long would your memoized search take on a phone, and how much would memo have to hold?

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.

★ Win in one move

Write winning_square(board, mark): the number of a square where mark ('X' or 'O') makes three in a row with its next move, or -1 if there is none. If there are two such squares, either is right. (This is rule a. in Newell and Simon’s list.)

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 winning_square(board, mark):    # Give back a square where mark completes a line, or -1.    return -1 print(winning_square(['X', 'X', ' ', 'O', 'O', ' ', ' ', ' ', ' '], 'X'))

★★ Who wins the games?

Write count_results(board): of all the games that can follow board, how many X wins, how many O wins and how many are draws, as a list [x_wins, o_wins, draws]. A board that is already finished is one game. (Start from Step 2’s count_games.)

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 def to_move(board):    if board.count('X') == board.count('O'):        return 'X'    return 'O' def count_results(board):    # Give back [x_wins, o_wins, draws] for all the games from board.    return [0, 0, 0] print(count_results(['X', 'X', 'X', 'O', 'O', ' ', ' ', ' ', ' ']))

★★★ The quickest win

Write quickest_move(board): a move for the player whose turn it is that wins as soon as possible against any defense. Every test board is one where the player to move can force a win. (Your Step 4 choose_move finds a winning move, but not always the quickest.)

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 def to_move(board):    if board.count('X') == board.count('O'):        return 'X'    return 'O' def quickest_move(board):    # Give back the square that wins soonest for the player to move.    return 0 print(quickest_move(['O', ' ', ' ', ' ', ' ', 'O', 'X', 'X', ' ']))

• Grade 11, Recursion: functions that call themselves, from factorials to merge sort, and how to be sure they stop.
• Grade 12, Algorithms for Hard Problems: remembering answers (dynamic programming), and problems where even a memo isn’t enough.
• Grade 10, Graphs, Maps, Routes and Networks: the game’s futures form a tree, one kind of graph.
• How Does a Computer Play Chess?: looking a few moves ahead, guessing a score, and alpha–beta pruning.