A terminal puzzle: follow clues through a folder tree with cd, ls and cat, and find the treasure hidden among decoys
First day on CS Room: use the terminal, run Python, and publish a live web page
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
By the end, students can:
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 | _
_ | _ | O
O 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.py and the two test files. (5 min)
Students write check_winner and is_board_full. They should reach 10 of 22 on test_game.py. (20 min)
Day 2: recursion
factorial(3) calls down and returns back up. (10 min)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)minimax together. (15 min)Day 3: minimax
minimax. Walk the room; the common mistakes are in the table below. (35 min)get_best_move. (10 min)Day 4: best move and play
get_best_move and reach 22 of 22. Anyone still on minimax keeps going. (20 min)python main.py and try to beat it. (10 min)Day 5 (optional): speed
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)| 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 |
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.
Our own mapping. CSTA has not reviewed it.