Tic Tac Toe
Build an unbeatable Tic-Tac-Toe AI with minimax
CS Room originalPython4-5 class periods27 graded tests
Tic-Tac-Toe AI
Build a Tic-Tac-Toe player that can't be beaten. It uses minimax, the same idea chess engines are built on.
Steps
Right-click this lesson's folder in the file list and choose Open in terminal. Then write five functions, in this order:
| Step | Function | File | Test it with |
|---|---|---|---|
| 0 | factorial(n) | warmup_factorial.py | python test_warmup.py |
| 1 | check_winner(board) | main.py | python test_game.py |
| 2 | is_board_full(board) | main.py | python test_game.py |
| 3 | minimax(board, is_ai_turn) | main.py | python test_game.py |
| 4 | get_best_move(board) | main.py | python test_game.py |
test_game.py tests all four functions in main.py, so tests for the steps you haven't reached yet will fail. Watch the count of passing tests go up as you go. If your teacher assigned this lesson, the Run Tests button above the editor runs every test at once.
When all the tests pass, play your AI:
python main.py
Hints
Step 0: factorial(n). A recursive function has a base case, which it answers directly, and a recursive case, which calls the function again on a smaller input. For factorial, factorial(0) is 1, and factorial(n) is n * factorial(n - 1). Minimax has the same shape.
Step 1: check_winner(board). There are eight winning lines: three rows, three columns and two diagonals. A line only counts if its three squares are the same player. Three empty squares in a row are not a win.
Step 2: is_board_full(board). Check whether EMPTY is still in the board, or use get_valid_moves(board).
Step 3: minimax(board, is_ai_turn). Write the base cases first: the AI won (10), the human won (-10), or the board is full (0). Then the recursive case: try every empty square, call minimax on the board after that move, and keep the best score. On the AI's turn the best score is the highest; on the human's turn it's the lowest.
Step 4: get_best_move(board). For each empty square, play the AI's move there and score the result with minimax(new_board, False). It's False because after the AI moves, it's the human's turn. Return the square, not the score.
How minimax works
Minimax plays out every possible rest of the game from the current board, assuming both players play perfectly. Each finished game gets a score: +10 if the AI wins, -10 if the human wins, 0 for a draw. Those scores are passed back up the tree. On the AI's turns it takes the highest score (it's the maximizer), and on the human's turns it takes the lowest (the human is the minimizer).
minimax(board, is_ai_turn):
if the game is over:
return +10, -10 or 0
if is_ai_turn:
best = -infinity
for each empty square:
score = minimax(board with O there, False)
best = max(best, score)
return best
else:
best = +infinity
for each empty square:
score = minimax(board with X there, True)
best = min(best, score)
return best
is_ai_turn flips on every call because the players take turns.
Troubleshooting
RecursionError: maximum recursion depth exceeded. A base case never fires. Checkcheck_winnerandis_board_fullfirst.- The AI makes strange moves. Check that the AI is
PLAYER_Oand the human isPLAYER_Xeverywhere, and that the AI's wins score+10. get_best_movefails its tests. Make sure it returns a square (0–8), not a score.
Going further
Once every test passes, try these in a copy of main.py. Some of them change the scores, which makes test_game.py fail.
- Count positions. Add a counter that goes up on every
minimaxcall and print it after each AI move. How many positions does the AI look at for its first move on an empty board? - Win faster. The AI treats a win now the same as a win in five moves. Pass a
depththroughminimaxand score a win as10 - depthso it prefers the quicker one. - Alpha-beta pruning. Stop exploring a branch as soon as it can't beat a move you've already found. Your counter should drop sharply.
- Another game. Try minimax on Connect Four or Nim.
Learn more
- Minimax on Wikipedia
- Python Tutor: step through a recursive function one call at a time
For teachers
Tic-Tac-Toe AI
Students write an unbeatable Tic-Tac-Toe player using minimax. It's about 50 lines of code across five functions. The hard part is the idea: recursion, and searching a tree of future games. A factorial warm-up comes first, so students who have never written a recursive function get one working before minimax.
Time: 4 class periods of 45 minutes, plus an optional fifth. Minimax is where students stall, and most classes need two periods for it. Prerequisites: Python functions, loops, conditionals and lists. No recursion needed. Tests: 27 (5 for the warm-up, 22 for the game), set up for you when you import the lesson
Goals
By the end, students can:
- write a recursive function with a base case and a recursive case
- explain how minimax picks a move by scoring every possible rest of the game
- trace minimax by hand on a small board
- use a test suite to check their work one function at a time
Before class
- Import the lesson into your class from the Lessons page, or with New assignment → Use a lesson on the class's Assignments tab. It arrives as a draft with its tests already set up.
- Publish it. Students get a Run Tests button, and their scores appear in the Gradebook.
In class
Day 1: game trees and win detection
-
Ask: can Tic-Tac-Toe be solved? What would "unbeatable" mean? (Perfect play from both sides always ends in a draw.) (5 min)
-
Hand-trace minimax as a class on this board, with the AI (O) to move. Draw the tree on the whiteboard and score each finished game +10, −10 or 0. (15 min)
X | O | X O | X | _ _ | _ | OO has to block at the bottom-left square, and the game ends in a draw (score 0).
-
Tour the files:
README.md,warmup_factorial.py,main.pyand the two test files. (5 min) -
Students write
check_winnerandis_board_full. They should reach 10 of 22 ontest_game.py. (20 min)
Day 2: recursion
- Teach recursion with factorial on the whiteboard: the base case, the recursive case, and how
factorial(3)calls down and returns back up. (10 min) - Students write
factorialand get 5 of 5 ontest_warmup.py. Pair up anyone who can't: a student who can't write factorial won't get through minimax. (15 min) - Bridge: factorial has one base case and one recursive call. Minimax has three base cases and one recursive call per empty square. (5 min)
- Write the three base cases of
minimaxtogether. (15 min)
Day 3: minimax
- Students write the recursive case of
minimax. Walk the room; the common mistakes are in the table below. (35 min) - Students who finish start
get_best_move. (10 min)
Day 4: best move and play
- Students write
get_best_moveand reach 22 of 22. Anyone still on minimax keeps going. (20 min) - Students play their AI with
python main.pyand try to beat it. (10 min) - Discuss: why can't you beat it? Why wouldn't this work for chess? How is it different from how a chatbot picks its next word? (15 min)
Day 5 (optional): speed
- Students add a counter to
minimax. With the AI moving first on an empty board it looks at about 550,000 positions. Chess has about 35 legal moves a turn, so looking just 8 moves ahead is about 2 trillion positions. (10 min) - Teach alpha-beta pruning on a small tree: once the AI has found a move that draws (0), it can stop exploring any other move as soon as it sees a human reply there that wins (−10), because that move can only be worse. Students add it. The first move drops to about 31,000 positions, and the AI plays just as well. (25 min)
- Compare the counts as a class. (10 min)
Where students get stuck
| Symptom | Cause |
|---|---|
check_winner says " " won | They didn't check that the line isn't empty: board[a] != EMPTY and board[a] == board[b] == board[c] |
RecursionError | A base case never fires, usually because check_winner or is_board_full is wrong |
| The AI plays badly | Score signs are flipped, or is_ai_turn isn't flipped on the recursive call |
get_best_move fails its tests | It returns the score instead of the square |
Check for understanding
- The test score: 27 of 27.
- Exit ticket: in one sentence, how does minimax choose a move?
- Give students a board with three empty squares and have them trace minimax by hand.
Going further
The README lists extensions: counting positions, preferring faster wins, alpha-beta pruning, and minimax for Connect Four or Nim. Some of them change the scores and fail the tests, so the README tells students to work in a copy of main.py.
Standards
CSTA standards
2017 standards
- 3B-AP-08Describe how artificial intelligence drives many software and physical systems.
- 3B-AP-09Implement an artificial intelligence algorithm to play a game against a human opponent or solve a problem.
- 3B-AP-10Use and adapt classic algorithms to solve computational problems.
- 3B-AP-11Evaluate algorithms in terms of their efficiency, correctness, and clarity.
- 3B-AP-13Illustrate the flow of execution of a recursive algorithm.
- 3B-AP-14Construct solutions to problems using student-created components, such as procedures, modules and/or objects.
- 3B-AP-21Develop and use a series of test cases to verify that a program performs according to its design specifications.
2026 standards
- HS-ALG-PS-02Optimize the design of an algorithm using procedural abstraction and control structures.
- HS-ALG-PS-03Evaluate algorithms for efficiency, correctness, and clarity, using metrics or test cases.
- HS-ALG-PS-04Describe the differences between deterministic and probabilistic algorithms.
- HS-ALG-ML-06Justify the selection of a type of AI algorithm to accomplish a task.
- HS-PRO-PD-12Create a modular program that uses procedures, external libraries, or objects to improve reusability and readability.
- HS-PRO-RD-17Analyze how a segment of code works, including the role of parameters, return values, and data structures.
- HS-PRO-TR-19Evaluate a computing technology's alignment with design specifications and responsible design values, including its correctness, effectiveness, and user experience.
- S2-GMD-DD-03Construct in-game artificial intelligence to control NPC behavior.