Math Detours · Grade 9 · Around the corner · 23

Playing noughts and crosses perfectly

Draw every possible game as a tree, score the endings, and work backwards. With best play the game is always a draw.

Name ____________________Date ____________

Tonight's idea

Noughts and crosses (tic-tac-toe) is small enough to solve completely. Picture every possible game as a tree: the empty board at the top, a branch for each move, a finished game at the end of each path. There are 255,168 endings.

Score each ending from X's side: \(+1\) if X wins, 0 for a draw, \(-1\) if O wins. X wants the score high. O wants it low. Now work backwards.

Take a position one move from the end. If X is to move, X picks the branch with the biggest score, so the position is worth the maximum of the values below it. If O is to move, it is worth the minimum. Then do the same one level up, and keep going to the top. This is minimax.

X to move: take the max of the values below. O to move: take the min.

A computer fills in the whole tree in a blink. The empty board comes out as 0: with best play the game is a draw.

Watch one: three squares left

X a b O O X O X c example: X to move a b −1 c +1 −1 b a +1 c +1 +1 c a +1 b −1 −1 +1 X picks the max O picksthe min the six endings, scored for X X X O p O X q O r question 3
Squares hold the value for X to move, circles for O to move. The thick branch is X's best move.

X is to move in the left-hand board. Whichever square X takes, O chooses between the other two. Either O completes a line, or X fills the last square. That makes six endings, scored along the bottom of the tree.

O's choices: the min of each pair gives \(-1\), \(+1\), \(-1\). X's choice: the max of those is \(+1\). X should play b. It blocks O's diagonal and threatens the top row and the right-hand column at once.

Play a computer that uses minimax, and switch on the value of every square: mathdetours.com/demos/noughts.html.

Your turn

  1. X can choose move P, Q or R. After P, O chooses between endings worth \(+1\) and \(-1\). After Q, between 0 and 0. After R, between \(+1\), 0 and \(-1\). Find the value of each of the three O positions, the value at the top, and X's best move.
  2. (a) If every game filled all nine squares, how many different games would there be, counting the order of the moves? (b) The true count is 255,168. Why is it smaller? (c) How many moves long is the shortest possible game?
  3. In the right-hand board X is to move and squares p, q, r are empty. Draw the tree, score its six endings, and find the value of the position and X's best move.
  4. A different game: a pile of 4 counters. Players take turns removing 1 or 2. Whoever takes the last counter wins. Draw the whole tree (it has 5 endings), score each ending \(+1\) or \(-1\) from the first player's side, and work backwards. Who wins, and with which first move?

Stretch: the corner opening

X opens in a corner. Minimax gives seven of O's eight replies the value \(+1\): X can then force a win. Which single reply is safe for O? Then suppose O replies in the opposite corner. Find a plan for X that wins whatever O does.

Answers

  1. After P: \(\min(+1, -1) = -1\). After Q: 0. After R: \(-1\). Top: \(\max(-1, 0, -1) = 0\). X plays Q. A branch that might win is worth nothing if the opponent gets to choose.
  2. (a) \(9! = 9 \times 8 \times \cdots \times 1 = 362{,}880\). (b) A game stops as soon as someone has three in a row. One game that stops early stands in for all the ways the leftover squares could have been filled. (c) Five moves: X's third mark can complete a line.
  3. X takes p: O takes q and wins on the diagonal (\(-1\)), or O takes r and X completes the left column (\(+1\)). Min \(-1\). X takes q: O takes p and the board fills level (0), or O takes r and X completes the left column (\(+1\)). Min 0. X takes r: O takes q and wins (\(-1\)), or O takes p and it ends level (0). Min \(-1\). The value is \(\max(-1, 0, -1) = 0\), and X must play q. Anything else loses.
  4. Endings (the amounts taken in turn): 1,1,1,1 is \(-1\); 1,1,2 is \(+1\); 1,2,1 is \(+1\); 2,1,1 is \(+1\); 2,2 is \(-1\). If the first player takes 1, three counters are left and both of the second player's replies lead to \(+1\). If the first player takes 2, the second player takes 2 and wins. The value is \(\max(+1, -1) = +1\): the first player wins by taking 1.

Stretch. The centre. Every other reply loses. Against the opposite corner, X takes a third corner, making two in a row along one side. O must block between them. X takes the last corner. Now X has two lines open at once, one along a side and one through the centre, and O can block only one.

← PreviousNext: The unbreakable code →