Game-playing AI – minimax and alpha-beta pruning on tic-tac-toe
Computer ScienceData, AI & Machine LearningAges 17–18
How do you mainly use this simulation?
Use it with your class: students open it from a link or a QR code, with no account needed.
Play tic-tac-toe against an AI that searches the game tree with minimax. The tree view shows every move the AI considered, the score minimax gave it and how many positions lie below it; open a branch to follow the search down. Switch on alpha-beta pruning to see branches cut off without changing the move, compare the positions searched, and lower the depth limit to make the AI play weakly enough to beat.
Lesson: Artificial intelligence in games: game trees, minimax, depth-limited search, evaluation functions and alpha-beta pruning
What it shows
A game-playing program can look ahead: it tries every move, every reply and so on, building a game tree. Minimax scores finished positions (win, loss or draw) and passes the scores up the tree: the player to move picks the best score for them, assuming the opponent does the same. Tic-tac-toe is small enough to search to the end, so a full-depth AI never loses. Real games are not, so programs stop at a depth limit and estimate the position. Alpha-beta pruning skips branches that cannot change the choice, giving the same move with far fewer positions searched.
How to use
Tap a square to move; the AI replies. The tree shows the AI's choices and their scores: tap one to open its branch, and use ▲ Up or ⤒ Top of tree to go back. Tick Alpha-beta pruning to compare. Lower Depth limit, or choose Score at the depth limit, to weaken the AI. Search this position shows your own options.
Parameters you can change
- You play X (first), O (second)
- Depth limit (moves ahead) 1–9
- Score at the depth limit 0 (unknown), Open lines
- Alpha-beta pruning
Questions to explore
- At depth limit 9, why does the AI never lose, whichever square you start in?
- Which squares does alpha-beta prune first, and why can it skip them?
- Below which depth limit can you beat the AI, and how did you do it?