Game-Playing AI: From Minimax to AlphaZero — lecture notes
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.
0:001. 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.
0:202. 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.
0:423. 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.
1:024. 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.
1:245. 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.
1:466. 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.
2:067. 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.
2:258. 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.
2:489. 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.
3:0810. 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.
3:2911. 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.
3:5212. 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.
4:1113. 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.
4:3214. 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.
4:5415. 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.
5:1516. 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.
5:3617. 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.
5:5718. 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.
6:1819. 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.
6:3820. 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.
6:5921. 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.
7:2122. 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.
7:4123. 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.
8:0124. 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.
8:2025. 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.
8:4126. 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.
8:5927. 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.
9:1828. 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.
9:3529. 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.
9:5430. 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.
10:1331. 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.
10:3432. 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.
Key takeaways
- Two-player, zero-sum, perfect-information games can be solved in principle with minimax over the game tree.
- Real games are too large, so programs search to a depth limit and use evaluation functions.
- Alpha–beta pruning gives the same answer as minimax while skipping branches; good move ordering roughly doubles search depth.
- Monte Carlo tree search estimates values from random playouts and selects moves with the UCT bandit rule.
- AlphaGo and AlphaZero guide MCTS with policy and value networks trained through self-play reinforcement learning.
- Hidden-information games such as poker need different tools, such as counterfactual regret minimisation.
Check yourself
- In minimax, what value does a MIN node take?
Show answer
The smallest child value — MIN assumes the opponent picks what is worst for MAX.
- What does alpha–beta pruning change?
Show answer
Only the amount of work — the decision is the same as minimax — Pruned branches cannot affect the result.
- Which phase of MCTS plays a random game to the end?
Show answer
Simulation — Playouts estimate win rates.
- The UCT selection rule is borrowed from…
Show answer
Multi-armed bandits (UCB) — Win rate plus an exploration bonus.
- What did AlphaZero learn from?
Show answer
Only the rules and self-play — No human game records were used.
Go deeper
- Adversarial Search: Minimax and Alpha–Beta Pruning · The AI Lecture Hall
- Monte Carlo Tree Search: The Algorithm Behind Superhuman Go · The AI Lecture Hall
- AlphaGo, AlphaZero and MuZero: Search Meets Deep Learning · The AI Lecture Hall
© 2026 Janin A Apurba, CSE, AUST · Advanced ICT Officer, CNRS-UNHCR. All rights reserved. Notes for the animated lecture at https://ai-in-motion.vercel.app/watch/game-playing-ai-deep-dive.html