Artificial IntelligenceIntermediate1:34 video6 chapters

Minimax and Alpha–Beta Pruning — lecture notes

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.

▶ Watch the animated lecture

0:001. Introduction

Introduction — Minimax and Alpha–Beta Pruning

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.

0:122. The idea

The idea — Minimax and Alpha–Beta Pruning

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.

0:293. Minimax

Minimax — Minimax and Alpha–Beta Pruning

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.

0:474. Alpha–beta pruning

Alpha–beta pruning — Minimax and 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.

1:065. Why it matters

Why it matters — Minimax and Alpha–Beta Pruning

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.

1:236. 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.

Key takeaways

Minimax assumes both players play optimally: MAX maximises, MIN minimises.
Values are computed at the leaves and passed up the tree.
Alpha–beta pruning skips branches that cannot affect the final decision.
Pruning returns exactly the same move as full minimax.

Check yourself

In our tree the MIN nodes had values 3, 2 and 2. What value does MAX choose?
Show answer
3 — MAX takes the largest of its children’s values: 3.
What does alpha–beta pruning change?
Show answer
How many positions must be evaluated — It skips irrelevant branches but returns the same decision.
Why could the middle branch be pruned after seeing a 2?
Show answer
MIN would never let MAX get more than 2 there, and MAX already has 3 — That branch can be worth at most 2 to MAX, which is worse than the 3 already guaranteed.

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