7
Part II · Games with turns

Seeing the whole tree

Tic-tac-toe is small enough that Robo can look at every possible future before it moves. That is not a figure of speech. This chapter shows how a computer plays a game perfectly by drawing the tree of everything that could happen, how big that tree is, and the trick that lets it skip most of the branches.

You are X. Robo is O. Robo plays perfectly, and it does it in the most honest way possible: before every move it works out every game that could still happen from here, all the way to the end, and picks the move whose worst ending is as good as possible. That plan has a name, minimax (say: MIN-ee-max): assume the other player will play their best, and choose your best against that.

Nobody can beat a minimax player at tic-tac-toe. But you can hold it to a draw, and the counter below tells you how much thinking it took.

Tic-tac-toe

You are X. Robo is O.
Robo has not moved yet.

Perfect Robo walks the entire tree of futures. Shallow Robo only looks two moves ahead: its own move and your reply. It will always block an immediate threat, and it will always miss a trap that takes three moves to spring.

Drawing the tree

A game tree starts with the current position at the top. Each possible move is a branch down to a new position. Each of those positions branches again, and so on until every branch ends in a win, a loss, or a draw. To solve the tree, work from the bottom up, exactly like Chapter 5: a finished game gets its value (+1 if X wins, 0 for a draw, −1 if O wins); a position where X is to move gets the biggest value among its branches, because X will pick it; a position where O is to move gets the smallest, because O will. Max, then min, then max. Minimax.

Here is a position with three empty squares, so the whole tree fits on the screen. It is X's move. Click the square you think is best. Then show the tree and see whether the values agree with you. Three right answers earn a star.

Tree puzzle

X to move. Which square?
Click a square.
Puzzles solved0

How big is the tree?

From an empty board the first move has 9 choices. Then 8 squares are left, then 7, and so on, so if every game went the full nine moves there would be 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362,880 ways to play. Mathematicians write that as 9! and say "nine factorial". Many games end early with a win, so the real number of different complete games is 255,168. Either way, a computer can check them all in a fraction of a second.

Chess is different. A chess position has about 30 legal moves, and a game lasts about 80 moves in total, so the tree has roughly 3080 branches. That is a 1 followed by about 120 zeros. There are only about 1080 atoms in the observable universe. No computer will ever draw the chess tree, which is why chess programs need a smarter idea.

Skipping branches. The smarter idea is called pruning. Suppose Robo is considering a move and finds that one of your replies already makes it a losing move. Robo does not need to look at your other replies. That move is dead; on to the next one. Robo above counts both ways after every move: the futures it actually examined, and how many it would have needed with pruning. Done well, pruning lets a program look about twice as many moves ahead for the same amount of thinking.

Three kinds of first move

Symmetry shrinks the tree.

Nine first moves, but a corner is a corner no matter which one, because turning or flipping the board changes nothing. So there are really only three different openings, and Robo only needs to think about those.

Math corner

Factorials. n! means n × (n − 1) × ... × 2 × 1. It counts the ways to put n things in order. 5! = 120, 9! = 362,880, 10! = 3,628,800. Factorials grow faster than any power: 20! is already bigger than 2 million million million.

Tree size. If a game has about b moves at every turn (the branching factor) and lasts d turns, the tree has about bd leaves. Tic-tac-toe: 99 is a generous upper bound. Chess: 3080. Go: 250150. The exponent is what makes these games hard, not the rules.

What pruning buys. With perfect pruning (checking the best moves first), the number of positions examined drops from about bd to about bd/2, the square root. Same answer, far less work. The counter above shows the real savings in tic-tac-toe.

Big idea

A game with turns is a tree. Solving it means labeling the tree from the leaves up: the player to move takes the branch with the best value for them. When the tree is too big to draw, look as deep as you can, skip branches you have already ruled out, and use judgment at the edge of what you can see. That is how every chess program works.

Try it on paper

1. How many different ways can the first two moves of tic-tac-toe be played?

Answer

9 × 8 = 72. Nine choices for X, then eight for O.

2. On a 4 by 4 board, how many different kinds of first move are there once you count symmetry?

Answer

Three: a corner (4 of them), an edge square (8 of them), or an inner square (4 of them). Turning and flipping the board moves each kind onto itself.

3. A game has exactly 3 choices at every turn and lasts exactly 4 turns. How many leaves does its tree have? How many if it lasts 8 turns?

Answer

34 = 81, and 38 = 6,561. Doubling the depth squares the size of the tree.

Challenge

Write down a set of rules, in order, that a second player could follow to never lose tic-tac-toe, without any tree at all. Then test your rules against Robo going first. Hint: the rules start with "if you can win, win" and "if they can win next move, block".

One set that works

1. Win if you can. 2. Block if they threaten to win. 3. If you can make a fork (two threats at once), do it. 4. If they can make a fork next move, block it, preferring a block that also threatens to win. 5. Take the center. 6. If they hold a corner, take the opposite corner. 7. Take any empty corner. 8. Take any empty side. Following these in order never loses. Proving that is a nice long evening's work.

True story

In 1950 Claude Shannon, the engineer who invented the mathematics of information, wrote the first paper on programming a computer to play chess and worked out that the chess tree was hopelessly large: the estimate 10120 is still called the Shannon number. Two years later, a Cambridge student named Sandy Douglas wrote a tic-tac-toe program called OXO for the EDSAC computer, one of the first computer games ever made. In 1997 IBM's Deep Blue, examining 200 million positions per second, beat the world chess champion Garry Kasparov. It used minimax with pruning, the very ideas on this page, plus a great deal of engineering.

Stars in this chapter

Earn them by doing the clever thing, not by clicking around.