Game-Playing AI: From Minimax to AlphaZero
How machines learned to beat world champions: game trees, minimax, evaluation functions, alpha–beta pruning, Deep Blue, Monte Carlo tree search, UCT, and AlphaGo and AlphaZero’s marriage of search and learning.
📄 Illustrated notes · every chapter as a picture · printable
Quick quiz
5 questions to check your understanding.
Go deeper
University-level written lectures in The AI Lecture Hall:
Transcript
Introduction. Games have been a proving ground for artificial intelligence since the field began. They have clear rules and a clear winner, yet they demand planning, judgement and anticipating an opponent. In this deep dive we trace how game playing AI went from exhaustive search to systems that teach themselves.
Milestones. The milestones are famous. In 1997 IBM’s Deep Blue defeated world chess champion Garry Kasparov. In 2016 AlphaGo beat Lee Sedol at Go, four games to one. AlphaZero mastered three board games from scratch in 2017, and in 2019 AI systems reached the top level in multiplayer poker and StarCraft two.
Adversarial search. Game playing is adversarial search: planning when another agent is working against you. The classic setting has two players taking turns, perfect information, where both see the whole board, and zero sum outcomes, where one player’s win is the other’s loss. Chess, checkers and Go all fit.
Game trees. We can represent a game as a tree. Each node is a position and each edge a move, with levels alternating between us, the MAX player, and the opponent, the MIN player. Leaves are finished games scored by utility. Tic tac toe has fewer than three hundred and sixty three thousand move sequences.
Minimax. Watch the values rise up the tree. Each MIN node takes the smallest value below it, assuming the opponent plays their best: three, two and two. Then MAX at the top takes the largest of those, three. So MAX should choose the left move, which guarantees at least three whatever MIN does.
The minimax rule. Formally, the minimax value of a finished position is its utility. On MAX’s turn it is the maximum over the children, and on MIN’s turn the minimum. Computing it from the bottom of the tree up gives the best achievable result against a perfect opponent.
Pause and think. Pause and think. Minimax assumes the opponent always plays perfectly. Is that a weakness? It is a cautious assumption. It guarantees a result against the strongest opponent, but may miss chances to exploit a weak one. Against an unknown opponent, that safety is usually worth it.
The size problem. For real games, the tree is astronomically large. A chess position offers about thirty five legal moves on average, and games last dozens of moves. Go offers about two hundred and fifty moves per position, and has around ten to the one hundred and seventy legal positions. We can never search to the end.
Evaluation functions. The classic solution is to search a fixed number of moves ahead, then score the positions reached with an evaluation function. Early chess programs counted material: a pawn is one point, knights and bishops three, rooks five and the queen nine, plus terms for mobility and king safety.
Alpha–beta pruning. Searching deeper needs efficiency, and alpha beta pruning provides it. After the left branch, MAX knows it can get at least three. In the middle branch, MIN finds a two straight away, so this branch can never beat three. The remaining leaves are skipped. Same answer, less work.
How much does pruning save?. How much does pruning save? Alpha tracks the best value MAX can already guarantee, and beta the best MIN can guarantee. When they cross, the branch is cut. With perfect move ordering, the work falls from b to the d to roughly b to the d over two, letting the program search about twice as deep.
Pause and think. Pause and think. To get the most pruning, in which order should moves be examined? Best moves first. A strong move found early sets tight bounds, so weaker alternatives are cut off quickly. Chess programs order moves using captures, previous searches and learned heuristics.
Alpha–beta in code. Here is alpha beta in Python. At the depth limit, return the evaluation. On MAX’s turn, take the best child value and raise alpha. As soon as alpha reaches beta, stop: the opponent would never allow this line, so its remaining moves need no examination. MIN’s case is symmetric.
Transposition tables. Another classic speed up is the transposition table. The same position can arise from different move orders, for example pawn to e four then d four, or d four then e four. Programs store each searched position’s value in a hash table and reuse it, avoiding a great deal of repeated work.
Playing against the clock. Real games are played against a clock. Iterative deepening searches to depth one, then two, then three, and so on until time runs out, always keeping the best move from the last completed search. The shallow searches are cheap, and they supply excellent move ordering for the deeper ones.
The horizon effect. Fixed depth search has a blind spot called the horizon effect. If a loss is unavoidable but can be delayed, the search may play pointless delaying moves that push it just beyond its horizon. Quiescence search helps by continuing to search noisy positions, such as pending captures, until they settle.
Deep Blue. Deep Blue was the triumph of this approach. Custom chess chips evaluated about two hundred million positions per second, running deep alpha beta searches with an evaluation function hand tuned with the help of grandmasters. It was brute force guided by expert knowledge, and it beat the world champion.
Why Go was harder. Go resisted this approach for two more decades. Its branching factor is about seven times larger, and, crucially, there is no simple evaluation function: counting stones says little about who is winning. Strong Go play depends on subtle, long range judgement that is hard to write down by hand.
Monte Carlo evaluation. A new idea changed Go programming: evaluate a position by playing many random games from it to the very end, and counting how often each side wins. No hand written evaluation function is needed. Random games are poor individually, but on average they reveal which positions are promising.
Monte Carlo tree search. Monte Carlo tree search builds a tree gradually, in four phases. Selection walks down the tree choosing promising children. Expansion adds a new position. Simulation plays a random game from it. Backpropagation updates the win and visit counts along the path. After thousands of iterations, play the most visited move.
The UCT rule. Selection uses the UCT rule: a move’s win rate plus a bonus that is large when the move has been tried rarely compared with its parent. It is exactly the upper confidence bound from multi armed bandits, applied at every node of the tree, balancing exploiting good moves against exploring uncertain ones.
Every node is a bandit. Here is UCB on a simple bandit. Each arm, like each candidate move, keeps getting occasional pulls while its uncertainty bonus is large, and the best arm is chosen more and more often. Inside Monte Carlo tree search, this happens at every position in the tree simultaneously.
Pause and think. Pause and think. Why can Monte Carlo tree search play reasonable Go without a hand written evaluation? Because averaging many random playouts estimates win probabilities, and UCT concentrates playouts on the most promising lines, so the estimates get sharper exactly where the decision is made.
AlphaGo. AlphaGo combined Monte Carlo tree search with deep neural networks. A policy network, first trained on human expert games, suggested promising moves, and a value network judged positions, replacing many random playouts. Reinforcement learning through self play then made both networks stronger than their human teachers.
The AlphaZero loop. AlphaZero went further, starting from nothing but the rules. A single network outputs move probabilities and a position value. Search guided by the network plays games against itself. Every position becomes a training example: the network learns to match the stronger search, which in turn makes the next search stronger.
AlphaZero. AlphaZero used no human games at all, only the rules. The same algorithm mastered chess, shogi and Go, defeating the strongest existing programs in each. It did require enormous compute: about five thousand first generation TPUs generated its self play games.
MuZero. MuZero removed another ingredient: the rules. It learns its own internal model of how the game evolves, and plans inside that learned model. It matched AlphaZero at board games and also mastered Atari video games, a striking example of model based reinforcement learning.
Imperfect information. Poker is different: you cannot see your opponents’ cards, so simple tree search over positions breaks down. Programs such as Libratus and Pluribus used counterfactual regret minimisation to approximate game theoretic equilibrium strategies. Remarkably, bluffing emerges naturally from the mathematics.
Techniques at a glance. To summarise: minimax assumes a perfect opponent, and alpha beta makes it efficient, powering programs from Deep Blue to Stockfish. Monte Carlo tree search with UCT cracked Go at amateur level. Neural networks guiding search produced AlphaGo and AlphaZero, and regret minimisation handles hidden information.
Pause and think. Pause and think. Why is self play such a powerful way to learn? It provides an endless curriculum: your opponent improves exactly as fast as you do, so the challenge always fits, and every game produces fresh training data without any human labelling.
Beyond games. The ideas did not stay in games. The same combination of search and learning discovered faster algorithms for matrix multiplication, in AlphaTensor in 2022, and for sorting, in AlphaDev in 2023, and it is used for planning in chemistry and robotics. Games were the training ground; real problems are the goal.
Recap. To recap. Game trees alternate MAX and MIN, and minimax assumes perfect play. Depth limits and evaluation functions make search practical, and alpha beta pruning makes it deep. Monte Carlo tree search uses random playouts with bandit style selection, and AlphaZero combines neural intuition, search and self play.