Tic Tac Toe

Build an unbeatable Tic-Tac-Toe AI with minimax

CS Room originalPython4-5 class periods27 graded tests

README.md

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:

StepFunctionFileTest it with
0factorial(n)warmup_factorial.pypython test_warmup.py
1check_winner(board)main.pypython test_game.py
2is_board_full(board)main.pypython test_game.py
3minimax(board, is_ai_turn)main.pypython test_game.py
4get_best_move(board)main.pypython 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. Check check_winner and is_board_full first.
  • The AI makes strange moves. Check that the AI is PLAYER_O and the human is PLAYER_X everywhere, and that the AI's wins score +10.
  • get_best_move fails 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 minimax call 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 depth through minimax and score a win as 10 - depth so 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

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

  1. Ask: can Tic-Tac-Toe be solved? What would "unbeatable" mean? (Perfect play from both sides always ends in a draw.) (5 min)

  2. 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 | _
    _ | _ | O
    

    O has to block at the bottom-left square, and the game ends in a draw (score 0).

  3. Tour the files: README.md, warmup_factorial.py, main.py and the two test files. (5 min)

  4. Students write check_winner and is_board_full. They should reach 10 of 22 on test_game.py. (20 min)

Day 2: recursion

  1. 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)
  2. Students write factorial and get 5 of 5 on test_warmup.py. Pair up anyone who can't: a student who can't write factorial won't get through minimax. (15 min)
  3. Bridge: factorial has one base case and one recursive call. Minimax has three base cases and one recursive call per empty square. (5 min)
  4. Write the three base cases of minimax together. (15 min)

Day 3: minimax

  1. Students write the recursive case of minimax. Walk the room; the common mistakes are in the table below. (35 min)
  2. Students who finish start get_best_move. (10 min)

Day 4: best move and play

  1. Students write get_best_move and reach 22 of 22. Anyone still on minimax keeps going. (20 min)
  2. Students play their AI with python main.py and try to beat it. (10 min)
  3. 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

  1. 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)
  2. 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)
  3. Compare the counts as a class. (10 min)

Where students get stuck

SymptomCause
check_winner says " " wonThey didn't check that the line isn't empty: board[a] != EMPTY and board[a] == board[b] == board[c]
RecursionErrorA base case never fires, usually because check_winner or is_board_full is wrong
The AI plays badlyScore signs are flipped, or is_ai_turn isn't flipped on the recursive call
get_best_move fails its testsIt 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.