All paths

Game AI: minimax and beyond

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.

Raspberry Pi 4 Model BFree7 lessons6 h4 chapters3,040 XPCoding · Expert+400 XP

0 of 7 done

What you will build

3 projects, built step by step

7 lessons in 4 chapters, about 6 hours on a simulated Raspberry Pi 4 Model B. Free, in your browser, every step checked by the simulator.

Chapter 1 project

Minimax

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

Open it in the simulator
Chapter 2 project

Evaluation

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

Open it in the simulator
Chapter 3 project

Monte Carlo search

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

Open it in the simulator
The map

Chapter by chapter

Each lesson opens when the one before it is done, and each chapter ends in a project.

Chapter 1

Perfect play

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

  1. Open300 XP

    Game trees

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

    0 of 5 steps

  2. ProjectLocked700 XP

    Minimax

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

    0 of 6 steps

4 questions, graded as you go.
Chapter 2

Search smarter

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

  1. Locked300 XP

    Alpha-beta

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

    0 of 5 steps

  2. ProjectLocked600 XP

    Evaluation

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

    0 of 5 steps

4 questions, graded as you go.
Chapter 3

Budgets

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

  1. Locked280 XP

    Depth vs time

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

    0 of 4 steps

  2. ProjectLocked560 XP

    Monte Carlo search

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

    0 of 4 steps

4 questions, graded as you go.
Chapter 4

Boss

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

  1. Locked300 XP

    Boss: an unbeatable Connect Four

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

    0 of 5 steps

3 questions, graded as you go.
Syllabus

Every lesson in the course

All 7 lessons, in order, each with what it covers. Any of them opens in the editor right away.

Chapter 1

Perfect play

  1. 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.
  2. 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.
Chapter 2

Search smarter

  1. 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.
  2. 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.
Chapter 3

Budgets

  1. 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.
  2. 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.
Chapter 4

Boss

  1. 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.
Kits

Build it on your bench too

Every lesson runs in the simulator with nothing to buy. When you want the real thing, these kits have the parts.

Have a kit already?

Find your kit

Pick the starter kit you own and run every lesson in its manual with the same parts on the same pins.

See every kit
Questions

About Game AI: minimax and beyond

Is Game AI: minimax and beyond free?

Yes. All 7 lessons of Game AI: minimax and beyond are free and run in your browser, with nothing to install and no parts to buy before you start.

Do I need a real Raspberry Pi 4 Model B?

No. Every lesson runs on a simulated Raspberry Pi 4 Model B with its parts on the canvas, and the simulator checks each step as you go. When you want to build it for real, the same wiring and code work on a real board.

How long does Game AI: minimax and beyond take?

About 6 hours: 7 lessons in 4 chapters, each one a few short steps. Your progress is kept, so you can stop after any lesson and pick up where you left off.

What will I build?

Each chapter ends in a project that puts it together: Minimax, Evaluation and Monte Carlo search.

Where do I start?

With "Game trees", and each lesson builds on the one before it. New to circuits? Electronics basics is the course that starts from zero.