Skip to content
Tutorials Center
My learning

Topics

Lesson 133 of 149 ยท Projects

Project: Tic-Tac-Toe

Build tic-tac-toe in Python step by step, from a list-based board and validated moves to win detection, a rule-based computer player and an unbeatable minimax AI.

Tic-tac-toe is small enough to fit on a napkin, but it's a surprisingly complete programming project. You need a data structure for the board, a way to read and check moves, logic that spots three in a row, and, if you want a computer opponent, a way for a program to think ahead. By the end of this project your program will play perfectly: it will never lose a game.

You'll build it in six stages, and every stage is a complete, runnable program. You'll use lists, tuples, functions, input validation, loops and, for the clever part, recursion. The final AI uses an algorithm called minimax, the same idea behind classic chess programs.

How the editor plays the game

As in the other projects, input() reads from the Input box under the code, one line per call. Every stage comes with moves already filled in, so pressing Run plays a whole game. Edit the Input box to try your own moves. If the program asks for more lines than the box has, you'll see an EOFError; just add more lines.

Players choose a square by its number, laid out like a phone keypad turned upside down:

TEXT
 1 | 2 | 3
---+---+---
 4 | 5 | 6
---+---+---
 7 | 8 | 9

Stage 1: the board as a list

A tic-tac-toe board has nine squares, so a list of nine strings is all you need. Each item is "X", "O" or " " (a space for an empty square). Square 1 is index 0, square 9 is index 8, so converting between them is just a matter of adding or subtracting 1.

Python Stage 1: store and draw the board

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

[" "] * 9 builds a list of nine spaces. Repeating a list like this is safe here because strings are immutable; it would be a trap with a list of lists, because every row would be the same inner list (see List Methods). A flat list of nine items avoids that problem entirely and makes every square easy to address with one index.

show() prints a number in each empty square, so the player can always see which numbers are still available. It builds each row with a list comprehension, joins the cells with " | " and then joins the rows with a divider line.

Stage 2: reading moves

Next, two human players take turns. The tricky part is input: people type 10, x, an empty line, or a square that's already taken. As in earlier projects, a function loops until the input is valid and only then returns it:

Python Stage 2: two players take turns

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The preset input contains three mistakes on purpose: 5 a second time (already taken), ten and 0. Each one gets a specific message, which is much friendlier than a generic "invalid input". The checks happen in a careful order: text.isdigit() runs first, so int(text) is only called on text that is known to be a number and can't raise a ValueError.

Swapping players is one line: mark = "O" if mark == "X" else "X". Run the program and look at the final board, though. O completed the top row (1, 2, 3) on the eighth move, but the game kept going, and X even filled the bottom row on the last move. Without win detection, both players "win". It's time to detect wins.

Stage 3: detecting a winner

There are exactly eight ways to get three in a row: three rows, three columns and two diagonals. Instead of writing eight if statements, list them as data, a tuple of index triples, and check each one in a loop:

Python Stage 3: wins and draws

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

for a, b, c in LINES unpacks each triple into three indexes. The chained comparison board[a] == board[b] == board[c] checks that all three squares hold the same mark, and the board[a] != " " part makes sure three empty squares don't count as a win.

play_game() checks for a winner right after each move, and only the player who just moved can have won, so it returns mark. The loop condition " " in board stops the game when no empty squares are left, which means a draw. In the preset game, O misses the threat on the diagonal after X plays 5 and 1, so X wins with 9. Change O's second move from 3 to 9 and the game goes on.

Stage 4: a computer player with simple rules

Now let's give the computer the O pieces. A good first attempt follows the rules many people use without thinking:

  1. If I can win right now, do it.
  2. If my opponent could win on their next move, block that square.
  3. Otherwise take the center, then a corner, then a side.

Rules 1 and 2 use the same helper: "is there a line with two of this mark and one empty square?"

Python Stage 4: a rule-based computer player

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The computer plays sensibly: it takes the center and blocks the obvious threat. But the preset moves beat it anyway. X takes two opposite corners (1 and 9), and the computer answers with corner 3, which forces X to block at 7. That block creates a fork: X now threatens both 4 and 8 at once. The computer can block only one, so X wins with the other.

The lesson is general: rules that only look one move ahead miss traps that are two or three moves deep. You could add a "don't let them fork" rule, but then there's another special case, and another. A better approach is to let the program look ahead all the way to the end of the game.

Stage 5: thinking ahead with minimax

Tic-tac-toe is small enough that a computer can try every possible continuation. Minimax does this with a simple recursive idea:

  • A finished game has a known value. We'll score it from X's point of view: positive if X won, negative if O won, 0 for a draw.
  • For an unfinished position, try every legal move and score the position that results, recursively.
  • X picks the move with the maximum score, and O picks the minimum. Each side assumes the other plays perfectly too.

To make the AI prefer quick wins (and slow losses), a win is worth more when more squares are still empty. This version works on tuples instead of lists, so positions can be used as keys in a cache later:

Python Stage 5: minimax scores every move

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the first block of output from O's point of view. Every corner scores +3 because X can win after it, so those are losing moves. Every side square scores 0: a side square forces X to respond, and with perfect play the game ends in a draw. That's exactly the move the rule-based player in stage 4 missed, and minimax found it without any special rule.

The second block shows the cost. From an empty board, plain minimax visits 549,946 positions and confirms that tic-tac-toe is a draw when both players are perfect. That takes a second or two in the browser (the exact time depends on your device), too slow for a responsive game. But most of those positions are the same board reached through different move orders. Wrapping the function with functools.cache remembers each result, so every distinct position is solved only once: 5,478 positions instead of more than half a million. This trick, called memoization, works because the board is a tuple, which is hashable; a list could not be a cache key.

Why minimax = cache(minimax) works: the recursive calls inside the function look up the name minimax in the global scope each time they run. After the reassignment, that name refers to the cached version, so the recursion goes through the cache too. In your own code you'd normally just write @cache above the function, as the next stage does.

Stage 6: the complete game

The final version puts everything together. The player chooses X or O, the computer uses minimax to pick its moves, and the program offers another round and keeps a scoreboard. best_move() scores each legal move and picks the best one for whichever side the computer is playing:

Python Stage 6: play against the unbeatable AI

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the first game you play X and try the opposite-corner trap from stage 4, but this time the computer answers with side square 2, and the game ends in a draw. In the second game you play O. The computer opens in corner 1, and the reply 2 (the side next to it) is a mistake: X plays 4, forcing you to block at 7, then 5, which threatens both 6 and 9. That's a fork, and the computer wins. Try to find a game the computer loses. You won't: tic-tac-toe is a draw with perfect play, and minimax plays perfectly.

A few design points:

  • best_move() reuses minimax() for both sides. Because scores are always from X's point of view, O just flips the sign with sign = -1 and looks for the largest result. max() with a key function picks the winning square in one line.
  • The board is now a tuple everywhere. play() returns a new board instead of changing the old one, which makes the cache safe and the game loop easy to follow: board = play(board, square, turn).
  • The cache lives between games. @cache keeps results for the whole run, so the second game's computer moves are instant.

Running it on your computer: save stage 6 as tictactoe.py and run python tictactoe.py. Replace the final main() call with if __name__ == "__main__": main() so other files can import the functions without starting a game (see Modules and Imports).

Ideas to extend the game

  1. Difficulty levels. On "easy", let the computer pick a random free square some of the time with random.random() < 0.3. On "medium", use the rule-based player from stage 4.
  2. Alpha-beta pruning. Skip moves that can't change the result: once O has found a reply that's worse for X than another option X already has, the rest of O's replies don't matter. Count positions searched with and without pruning.
  3. Use symmetry. A board rotated or mirrored has the same value. Store only one version of each position to shrink the cache to well under a thousand entries.
  4. Bigger boards. Generalize to a 4ร—4 board with four in a row. Full minimax becomes far too slow, which is why real game programs limit the search depth and estimate positions instead.
  5. Tests. Write unit tests for winner() with all eight lines, and for best_move() on positions where there's only one good answer.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. On the list-based board, which index holds square 7 (the bottom-left corner)?

    Squares are numbered 1 to 9 for players, but list indexes start at 0, so square 7 is board[6].
  2. 2. Why does winner() check board[a] != " " before comparing the three squares?

    Without that check, an empty row would satisfy board[a] == board[b] == board[c] and " " would be reported as the winner.
  3. 3. Why did the rule-based player from stage 4 lose to X's opposite-corner opening?

    Its rules check for immediate wins and blocks. Taking a corner forced it into a position where X could create two threats at once.
  4. 4. In the minimax function, which player chooses the move with the maximum score?

    Positive scores are good for X and negative scores are good for O, so X maximizes and O minimizes.
  5. 5. Why can functools.cache remember minimax results for tuple boards but not for list boards?

    The cache stores arguments as dictionary keys. Mutable lists can't be keys, so passing one raises a TypeError.

Summary

  • A flat list of nine strings is a simple, effective tic-tac-toe board; square n is index n - 1.
  • Validating input in its own function, with a specific message for each mistake, keeps the game loop simple.
  • Storing the eight winning lines as data turns win detection into one short loop.
  • Simple rules (win, block, center, corners) play reasonably, but they miss traps such as forks.
  • Minimax recursively scores every possible continuation: X maximizes, O minimizes, and the result is perfect play.
  • Memoization with functools.cache cut the search from 549,946 positions to 5,478, and it needs hashable arguments such as tuples.

Next: Project: Text Analyzer, where you'll turn any text into word counts, statistics and a tidy report.