Minimax and Alpha–Beta Pruning
How game-playing AI thinks ahead: MAX and MIN take turns, values flow up the tree, and alpha–beta pruning skips branches that cannot matter.
📄 Illustrated notes · every chapter as a picture · printable
Quick quiz
3 questions to check your understanding.
Go deeper
University-level written lectures in The AI Lecture Hall:
Transcript
Introduction. How does a computer play chess or tic-tac-toe? It imagines future moves for both players and assumes the opponent plays their best. That idea is called minimax.
The idea. We call our AI MAX, because it wants the highest score. The opponent is MIN, who wants the lowest. We score the final positions at the bottom of the tree, then pass values upwards, each player choosing their best option.
Minimax. Watch the values rise. Each MIN node takes the smallest value below it: 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.
Alpha–beta pruning. Now alpha beta pruning. 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.
Why it matters. Game trees grow exponentially. Alpha beta pruning always gives exactly the same answer as minimax, but with good move ordering it can search roughly twice as deep in the same time. That is a huge advantage in games like chess.
Recap. Remember: MAX maximises, MIN minimises. Values flow up from the leaves. Alpha beta pruning skips hopeless branches and gets the same answer much faster.