Game AI: minimax and beyond lesson plan
Teach a Raspberry Pi to play: game trees and perfect tic-tac-toe with minimax, then Connect Four with alpha-beta, evaluation, iterative deepening and Monte Carlo search, ending in an opponent on the Serial Monitor.
Objectives and materials
By the end, students can
- Tic-tac-toe as a tree, solved outright by minimax.
- Cut the tree with alpha-beta, then stop early and guess with an evaluation.
- A clock that decides the depth, and random games that need no evaluation at all.
- Connect Four against the Pi, typed on the Serial Monitor.
Materials for the whole unit
- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module
Every part is already on the simulator’s bench, so there is nothing to buy or hand out. The counts are the most any one lesson uses, if you build it on real breadboards too.
Perfect play
Tic-tac-toe as a tree, solved outright by minimax.
| Lesson | Time | What students do |
|---|---|---|
| Game treesEvery game AI starts with the same picture: a tree of positions. Model tic-tac-toe in Python, find the winner, and count every game that can follow a position, then see why the tree for a real game is too big to draw. | 55 min |
|
| MinimaxScore a position by assuming both players play perfectly: minimax, a best-move picker, a fix that makes it win fast instead of toying with you, a memo that solves the whole game in 5,478 positions, and a tic-tac-toe opponent you cannot beat. | 65 min |
|
Materials
- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module
Check for understanding
Each student finishes "Minimax" on their own, without opening the hints. The simulator checks 6 of its 6 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Why it cannot lose".
Search smarter
Cut the tree with alpha-beta, then stop early and guess with an evaluation.
| Lesson | Time | What students do |
|---|---|---|
| Alpha-betaPrune the tree without changing the answer: count the positions minimax visits, add alpha and beta to skip branches that cannot matter, order moves best first, and solve all of tic-tac-toe in 7,865 positions with no memo at all. | 55 min |
|
| EvaluationMove to Connect Four, where the tree is far too big to finish: a board and a four-in-a-row check, then an evaluation function that scores a position by counting the lines each player could still complete, and a one-move player built on it. | 55 min |
|
Materials
- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module
Check for understanding
Each student finishes "Evaluation" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "The horizon".
Budgets
A clock that decides the depth, and random games that need no evaluation at all.
| Lesson | Time | What students do |
|---|---|---|
| Depth vs timeAlpha-beta with a depth limit on Connect Four, written as negamax: measure how nodes and milliseconds grow with every move of lookahead, then let a clock decide the depth with iterative deepening, and watch a deeper search spot a forced win. | 40 min |
|
| Monte Carlo searchA different road: no evaluation function at all, just random games played to the end and counted. Playouts, flat Monte Carlo move choice, why more samples beat noise, and the UCB1 rule at the heart of Monte Carlo tree search, the method that cracked Go. | 40 min |
|
Materials
- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module
Check for understanding
Each student finishes "Monte Carlo search" on their own, without opening the hints. The simulator checks 4 of its 4 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "UCB1: spend games wisely".
Boss
Connect Four against the Pi, typed on the Serial Monitor.
| Lesson | Time | What students do |
|---|---|---|
| Boss: an unbeatable Connect FourPut it all together: a Connect Four game on the Serial Monitor against the Pi, the board drawn as text and your moves typed in, an alpha-beta engine with iterative deepening behind it, and the traffic light showing your turn, the Pi thinking and the Pi winning. | 55 min |
|
Materials
- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module
Check for understanding
Each student finishes "Boss: an unbeatable Connect Four" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Unbeatable?".
Teach this unit as a class
Start a class from this course and its 7 lessons are assigned in one go, in order. Students join with a six-character code or printed login cards, and each one’s work comes back to you.
The class tools are free for 30 days for one class of up to 20 students, with no card. The lessons themselves are free either way.