TwiddleLab / Artificial Intelligence / Search, Games and Plans
Alpha-Beta: Skip What Doesn't Matter
What you will learn
- Alpha-beta pruning searches the tree like minimax, left to right, and skips any branch that can't beat what is already guaranteed.
- It always picks the same move as minimax, while looking at fewer positions.
- Move ordering matters: try the best moves first and more gets skipped.
- With perfect ordering it looks at roughly b^(d/2) positions instead of b^d, so it can search about twice as deep in the same time.
How the lesson goes
You already found a move that guarantees you 5. The next move lets your opponent force 2. Do you need to see the rest of that branch?
Tap the hidden leaves you still need to look at. If none, just press Check.
Search the tree left to right and skip what can't matter.
Step through it. Count the leaves it looks at.
Your turn. Cut the branches this search never needs.
Read the leaves from left to right. Swipe across an edge to cut it.
After the left branch you have 3 for sure. In the middle the opponent can already force 2, so this branch is worth at most 2: worse than 3 whatever 4 and 6 are. On the right, 14 and 5 don't settle it; only the last leaf, 2, does, and nothing is left after it.
This trick is called alpha-beta pruning.
Alpha is the best score you are already sure of; beta is the best the opponent is sure of. When a branch can't beat them, it is pruned: skipped. The answer is always the same as minimax. Which moves you try first is the move ordering.
Three levels now. Cut everything alpha-beta skips.
A whole branch can be cut, not just a leaf.
On the left, the opponent can hold you to 5. The second purple node shows 6 at once, so it is worth at least 6, and the opponent will never choose it: skip 9. On the right, the opponent can already hold you to 2 after the first purple node, worse than your 5, so the rest of that side is skipped.
Game: reorder the moves so alpha-beta looks at 5 leaves or fewer.
Drag a branch onto another to swap them. You can swap leaves inside a branch too.
A chess bot with plain minimax reaches 6 moves deep in a second. With alpha-beta and good ordering, how deep?
Minimax looks at about b^d positions, alpha-beta at best about b^(d/2). Put your pin on the depth.
With the best possible ordering alpha-beta looks at about b^(d/2) leaves (more exactly b^ceil(d/2) + b^floor(d/2) - 1). Setting d/2 = 6 gives d = 12: roughly double the depth for the same work. Real bots get close to this by trying the most promising moves first.
Which leaves will alpha-beta skip in this tree?
Tap each leaf it never looks at.
Left branch: the opponent picks 4, so you have 4. Middle: after 7 comes 3, which is less than 4: the branch is worth at most 3, skip 9. Right: after 8 comes 2: skip 1.
Speed round: three trees. Mark the leaves alpha-beta skips.
Three lives. Some trees skip more than others.
Previous lesson: Scoring Positions: Evaluation Functions · Next lesson: Monte Carlo: Play Random Games · Part of the course: Search, Games and Plans
Lessons are interactive and need JavaScript. Turn it on to play them.
