Lesson plan

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.

4 chapters, 7 lessons, about 6 hours, on the Raspberry Pi 4 Model B. Every lesson runs in the browser, with nothing to install.

The unit

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.

Chapter 1. About 2 h

Perfect play

Tic-tac-toe as a tree, solved outright by minimax.

LessonTimeWhat 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
  1. Run it: a board is a list
  2. Who won?
  3. Count the tree
  4. Who wins, if nobody thinks?
  5. Why trees explode
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
  1. Run it: a score for a position
  2. Pick the best move
  3. Win fast, lose slow
  4. Solve the whole game
  5. Play it
  6. Why it cannot lose

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".

Chapter 2. About 1 h 50 min

Search smarter

Cut the tree with alpha-beta, then stop early and guess with an evaluation.

LessonTimeWhat 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
  1. Run it: count the work
  2. Alpha and beta
  3. Best moves first
  4. The whole game, no memo
  5. How cutoffs grow
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
  1. Run it: a Connect Four board
  2. Four in a row
  3. An evaluation function
  4. A one-move player
  5. The horizon

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".

Chapter 3. About 1 h 20 min

Budgets

A clock that decides the depth, and random games that need no evaluation at all.

LessonTimeWhat 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
  1. Run it: negamax
  2. Deeper costs more
  3. Iterative deepening
  4. Seeing a trap
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
  1. Run it: random games
  2. Flat Monte Carlo
  3. More games, less noise
  4. UCB1: spend games wisely

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".

Chapter 4. About 55 min

Boss

Connect Four against the Pi, typed on the Serial Monitor.

LessonTimeWhat 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
  1. Run it: a game loop and a monkey
  2. Give it a brain
  3. The traffic light
  4. A clock instead of a depth
  5. Unbeatable?

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?".

Your class

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.