Two friends play tic-tac-toe in the back of an exercise book during a free period. X, then O, then X, until someone has three in a row. After a few games something strange happens: nobody wins any more. Every game fills the board and ends in a draw.
Each of them follows a few rules without saying so: “If I can make three, I do it. If you are about to make three, I stop you.” Write rules like those down, in the right order, and a computer can follow them. The player called Rules on the board below knows eight rules and nothing else. It doesn’t look ahead and it doesn’t learn: it reads its list from the top and plays the first rule that fits.
You are X and go first. Try to beat it.
After a few games, what do you think: can anyone ever beat these eight rules?
Pick an answer to see why.
You need: if and if/else in blocks, from Grade 7. For the Python, loops, lists and functions, from Grade 8.
Try it
The eight rules
Here is the list. On each turn, go down it from the top and play the first rule that gives you a square.
- Win: if you have two in a row and the third square is empty, play it.
- Block: if the other player has two in a row and the third square is empty, play it.
- Fork: play a square that gives you two lines of two at once.
- Stop a fork: if the other player could make a fork on their next move, stop it.
- Center: play the center.
- Opposite corner: if the other player has a corner, play the corner opposite it.
- Empty corner: play any empty corner.
- Empty side: play any empty side square (the middle of an edge).
The squares are numbered 0 to 8 along the rows, from the top left. When a rule gives more than one square, Rules plays the lowest-numbered one.
A fork is the move that wins games between people who block. Here X has played 0, 8 and now 2:
O blocks 1, and X plays 5; or O blocks 5, and X plays 1. Whatever O does, X wins on the next move. That is why rule 3 says make a fork, and rule 4 says never let the other player make one.
In the picture above, O is to move. Which rule decides O’s move, and which square does it give?
Pick an answer to see why.
Switch a rule off
Which rules does Rules really need? On this board you can switch any rule off. Rules then skips it; if no rule left gives a square, it takes the lowest-numbered empty square.
- a.Switch off rule 2 (block). How quickly can you win?
- b.Switch rule 2 back on and switch off rule 4 (stop a fork). Go first, take a corner, and when Rules has taken the center, take the opposite corner. What does Rules do next, and what happens?
- c.Switch off one rule at a time, all eight in turn, and press Find a game it loses each time. Which rules can go without Rules ever losing?
How it works
Why does such a short list never lose? Because of the order, and because of one rule: rule 4.
The order matters
Rule 1 comes before rule 2: win if you can, and only then block. Does it matter? Rule 1 off, Rules found itself here:
In the picture above, X is to move. With rule 1 switched off, which square does Rules play, and what happens?
Pick an answer to see why.
Two rules in the wrong order are as bad as a rule missing: your program will show that block before win loses too.
Forks: the one way to beat a blocker
A player who always blocks can’t be beaten by one line of two: it just blocks. It can only be beaten by two lines of two at once, a fork. So the rules do two things about forks. Rule 3 makes one when it can. Rule 4 stops the other player making one, and rule 4 is the hard rule.
Rule 4, the hard rule
Here is the most famous trap in tic-tac-toe. X has two opposite corners, O the center, and O is to move.
X could fork at 2 (the top row and the right column) or at 6 (the left column and the bottom row). O can’t take both. The obvious idea, “take a square where they could fork”, loses here. If O takes 2, O has 2 and 4 on a diagonal, so X must block at 6, and 6 is X’s other fork square. X blocks and forks with the same move, and wins.
So rule 4 says: if there is one square where the other player could fork, take it. If there are two or more, attack instead: make two in a row yourself, so the other player has to block, and choose it so that their block is not one of their fork squares. Here O plays a side, square 1. Now O threatens 7, X must block there, and 7 makes no fork for X. The game is a draw.
X opened in the center and O took corner 0. Then X took the opposite corner, 8. Where could X fork next, and what should O do?
Pick an answer to see why.
The other rules: a good start
Rules 5 to 8 matter at the start, before anyone has two in a row. The center is in four lines (a row, a column and both diagonals), a corner in three, a side in only two: so the center first, then corners, then sides. Rule 6 sets up forks for later.
Program it
With blocks: rules 1 and 2 on one line
The block program below is the player X looking at one line of the board. Type the line’s three squares one at a time: X, O, or - for an empty square (capital letters). It counts X’s marks in mine and O’s in theirs, then tries rule 1, then rule 2. A whole player would look at all eight lines for a win first, and only then for a block.
In the block program, why does the condition for rule 1 say mine = 2 and theirs = 0, not just mine = 2?
Pick an answer to see why.
In Python (from Grade 8)
Step 1: rules 1 and 2 for the whole board
A board is a list of 9 strings, 'X', 'O' or ' ' (a space for an empty square), in the order of the square numbers. LINES lists the 8 lines as their three squares. finishing_squares looks at every line, as the blocks did at one: two of mark and one empty square means that empty square finishes the line.
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 finishing_squares(board, mark): # empty squares that would give mark three in a row found = [] for line in LINES: marks = [board[line[0]], board[line[1]], board[line[2]]] if marks.count(mark) == 2 and marks.count(' ') == 1: square = line[marks.index(' ')] if square not in found: found.append(square) return found board = ['X', 'X', ' ', 'O', 'O', ' ', ' ', ' ', ' ']print('X can finish a line at', finishing_squares(board, 'X'))print('O can finish a line at', finishing_squares(board, 'O'))Output
X can finish a line at [2]O can finish a line at [5]It is X’s turn. Rule 1 asks finishing_squares(board, 'X'): square 2, a win. Rule 2 would ask finishing_squares(board, 'O') and block at 5. Rules 1 and 2 are one function, asked about different players.
Step 2: all eight rules
Rule 3 uses the same function: a square is a fork square if, after you play it, finishing_squares gives two squares or more. The program tries each empty square, counts, and takes the mark off again. Rule 4 asks about the other player’s fork squares.
All eight are in a file the page keeps for you, eight_rules.py. Its function rule(n, board, me) gives the list of squares rule n offers the player me (an empty list if the rule doesn’t fit). Every rule is a few lines.
The corner opposite square c is always square 8 - c: 0 and 8, 2 and 6. That is how rule 6 finds it.
Step 3: a player that goes down the list
RULES_ON is the list of rules, in the order they are tried. choose_move goes down it, plays the first square a rule gives, and says which rule it was.
from eight_rules import rule, whose_turn, empty_squares, NAMES RULES_ON = [1, 2, 3, 4, 5, 6, 7, 8] def choose_move(board): me = whose_turn(board) for n in RULES_ON: squares = rule(n, board, me) if len(squares) > 0: print(me, 'plays', squares[0], 'by rule', n, '(' + NAMES[n] + ')') return squares[0] print(me, 'plays', empty_squares(board)[0], 'because no rule fits') return empty_squares(board)[0] choose_move([' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '])choose_move(['X', 'X', ' ', ' ', 'O', ' ', ' ', ' ', ' '])choose_move(['X', ' ', ' ', ' ', 'O', ' ', ' ', ' ', 'X'])Output
X plays 4 by rule 5 (center)O plays 2 by rule 2 (block)O plays 1 by rule 4 (stop a fork)The third board is the trap, and your player gets it right: square 1, a side.
Now play against it. The board below calls your choose_move (press Edit above to change it) every time Your code has to move.
Step 4: every possible opponent
A hundred games against Random prove little: Random hardly ever plays the trap. To be sure, play the rules against every opponent there could be. On the other player’s turn, try every empty square; on the rules’ turn, play their one move. to_do is a list of games not finished yet, each written as the squares played so far (X first). Take one off the front, and either count it (won, drawn or lost) or put every way it can go on at the end. When the list is empty, every game has been played. The program does this for all eight rules, then with each rule taken out in turn.
from eight_rules import rule, whose_turn, empty_squares, winner, other, NAMES def rules_move(board, rules_on): me = whose_turn(board) for n in rules_on: squares = rule(n, board, me) if len(squares) > 0: return squares[0] return empty_squares(board)[0] def every_game(me, rules_on): # the rules play as me against every possible opponent won = 0 drawn = 0 lost = [] to_do = [[]] # each game is the list of squares played while len(to_do) > 0: moves = to_do.pop(0) board = [' '] * 9 for i in range(len(moves)): board[moves[i]] = 'XO'[i % 2] w = winner(board) if w == me: won = won + 1 elif w != None: lost.append(moves) elif len(moves) == 9: drawn = drawn + 1 elif whose_turn(board) == me: to_do.append(moves + [rules_move(board, rules_on)]) else: for square in empty_squares(board): to_do.append(moves + [square]) return won, drawn, lost def report(rules_on): for me in ['X', 'O']: won, drawn, lost = every_game(me, rules_on) print(' as', me + ':', won + drawn + len(lost), 'games,', won, 'won,', drawn, 'drawn,', len(lost), 'lost') if len(lost) > 0: print(' the shortest it loses:', lost[0]) ALL = [1, 2, 3, 4, 5, 6, 7, 8]print('All eight rules')report(ALL)for n in ALL: print('Without rule', n, '(' + NAMES[n] + ')') without = [] for m in ALL: if m != n: without.append(m) report(without)Output
All eight rules as X: 140 games, 124 won, 16 drawn, 0 lost as O: 457 games, 346 won, 111 drawn, 0 lostWithout rule 1 (win) as X: 272 games, 208 won, 62 drawn, 2 lost the shortest it loses: [4, 5, 0, 7, 1, 8, 6, 2] as O: 831 games, 426 won, 368 drawn, 37 lost the shortest it loses: [4, 0, 5, 3, 2, 8, 6]Without rule 2 (block) as X: 132 games, 117 won, 0 drawn, 15 lost the shortest it loses: [4, 0, 8, 2, 7, 1] as O: 415 games, 301 won, 18 drawn, 96 lost the shortest it loses: [0, 4, 1, 3, 2]Without rule 3 (fork) as X: 145 games, 119 won, 26 drawn, 0 lost as O: 457 games, 346 won, 111 drawn, 0 lostWithout rule 4 (stop a fork) as X: 140 games, 124 won, 16 drawn, 0 lost as O: 585 games, 404 won, 175 drawn, 6 lost the shortest it loses: [0, 4, 8, 2, 6, 7, 3]Without rule 5 (center) as X: 95 games, 87 won, 8 drawn, 0 lost as O: 617 games, 346 won, 259 drawn, 12 lost the shortest it loses: [0, 8, 2, 1, 6, 3, 4]Without rule 6 (opposite corner) as X: 92 games, 82 won, 10 drawn, 0 lost as O: 457 games, 346 won, 111 drawn, 0 lostWithout rule 7 (empty corner) as X: 159 games, 137 won, 22 drawn, 0 lost as O: 473 games, 330 won, 133 drawn, 10 lost the shortest it loses: [4, 1, 0, 8, 3, 5, 6]Without rule 8 (empty side) as X: 140 games, 124 won, 16 drawn, 0 lost as O: 457 games, 346 won, 111 drawn, 0 lost('XO'[i % 2] is 'X' for moves 0, 2, 4… and 'O' for the others. Taking games off the front of to_do plays the short ones first, so the first lost game found is a shortest one.)
What your program shows
- All eight rules: 597 games, and not one lost. As X the rules met 140 different games, as O 457: every game any opponent could ever play against them. They lost none, and drew only where the opponent played well (16 games as X, 111 as O).
- Take out rule 1, 2, 4, 5 or 7, and the program finds a game that beats the rest. Without rule 4 it is the trap you found by hand,
[0, 4, 8, 2, 6, 7, 3]: X’s block at 6 is also a fork. - Rules 3, 6 and 8 can go without a single loss, but without rule 6 the rules win only 82 games as X instead of 124. They are rules for winning, not for not losing.
Why so few games? The rules play one move on each of their turns; only the opponent’s choices branch. All players together can play 255,168 different games (the Grades 9–12 topic’s program counts them), but only 597 of them are games against these rules.
Your program didn’t try a few games and hope. It tried every game there is, and so it proved that the list never loses. Checking every possible case like this is called exhaustive testing. It only works when the cases can be counted, as they can here; for most programs there are far too many, and testers must choose their cases carefully instead.
Going further still
Change the order. In your Step 4 program, change ALL to [2, 1, 3, 4, 5, 6, 7, 8], block before win, and run it: as O, the rules now lose 27 games. Try corners before the center, too.
The shortest list. How few rules can you keep and never lose? Change the program to report [1, 2, 4, 5], just win, block, stop a fork and center. Then try three rules.
An open question. Bagh-Chal, Nepal’s game of tigers and goats, is a draw when nobody makes a mistake: Lim Yew Jin and Jürg Nievergelt showed it in 2009 with a huge computer search. Is there a short list of rules, like these, that lets the goats never lose? That is a question you can explore.
Challenges
★ The opposite corner (blocks)
Rule 6 in blocks. The program asks which square the other player took. If it is a corner (0, 2, 6 or 8), say the square of the opposite corner. Otherwise say exactly Not a corner. Then press Test.
★★ Find the forks (Python, from Grade 8)
Write fork_squares(board, mark) yourself: a list of every empty square where mark would have two ways to win at once (two different finishing squares), in any order; [] if there are none. finishing_squares is given.
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 finishing_squares(board, mark): found = [] for line in LINES: marks = [board[line[0]], board[line[1]], board[line[2]]] if marks.count(mark) == 2 and marks.count(' ') == 1: square = line[marks.index(' ')] if square not in found: found.append(square) return found def fork_squares(board, mark): # give back every empty square where mark would make a fork return [] print(fork_squares(['X', ' ', ' ', ' ', 'O', ' ', ' ', ' ', 'X'], 'X'))★★★ Stop the fork (Python, from Grade 8)
The hard rule. Write stop_a_fork(board, me): the square me should play to stop the other player’s fork, or -1 if they have no fork square. One fork square: take it. Two or more: make a two in a row whose block won’t give them a fork. Any square that keeps me from losing is accepted.
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 finishing_squares(board, mark): found = [] for line in LINES: marks = [board[line[0]], board[line[1]], board[line[2]]] if marks.count(mark) == 2 and marks.count(' ') == 1: square = line[marks.index(' ')] if square not in found: found.append(square) return found def fork_squares(board, mark): found = [] for square in range(9): if board[square] == ' ': board[square] = mark if len(finishing_squares(board, mark)) >= 2: found.append(square) board[square] = ' ' return found def stop_a_fork(board, me): # give back the square that stops the other player's fork, or -1 return -1 print(stop_a_fork(['X', ' ', ' ', ' ', 'O', ' ', ' ', ' ', 'X'], 'O'))Questions
X has played corners 2 and 6, and O the center. Which move by O is safe?
Pick an answer to see why.
With all eight rules switched on, choose_move never reaches its last line, “because no rule fits”, while the board has an empty square. Why not?
Answer
Your Step 4 program says the eight rules never lose. A friend says: “It only played computer opponents. A person might find a trick.” Is your friend right?
Answer
Without rule 6 (opposite corner), the rules still never lose. So why keep it?
Pick an answer to see why.
Where to go next
- Grade 7, Variables and Choices: if and if/else, the blocks behind each rule.
- Grade 8, Functions: functions that answer a question, like
finishing_squares. - How do you always win at Nim?: a game where one short rule, written in binary, wins every game that can be won.
- How can a computer never lose at tic-tac-toe? (Grades 9–12): the same game played with no rules at all, by looking at every future and working backwards from the end.