Pruning Game Trees with Alpha-Beta Techniques, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 4.7 Free with a free account

Pruning Game Trees with Alpha-Beta Techniques

Introduction to Artificial Intelligence · Chapter 4: Search, Heuristics, and Game StrategySection 4.7 · lesson 29 of 6913 min · free with a free account

← Climbing Toward Solutions: Local Search MethodsNext lesson: Working with Constraint Satisfaction Problems →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

Alpha-beta pruning, move ordering, and evaluation functions for deeper game search.

  • Explain how alpha and beta bounds let a search skip branches without changing the minimax result
  • Trace alpha and beta cut-offs on a game tree
  • Describe how move ordering affects pruning and why the best case searches about twice as deep
  • Design a simple evaluation function and explain the horizon effect and quiescence search

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,829 words). Read along, or search it.

Opening Question

1.8 Billion Chess Positions

A typical chess position offers about 35 legal moves. Looking six half-moves ahead means checking 35 times 35, six times over: about 1.8 billion positions. A program that examines every one of them is far too slow for a real game. Yet strong programs search that deep, and deeper. A big part of their secret is alpha-beta pruning: skipping whole branches of the game tree that can't change the final decision. And the best part? It gives exactly the same answer as examining everything. How can skipping work be that safe?

Review

How Minimax Passes Values Upward

A quick reminder of minimax. MAX tries to make the score as high as possible, and MIN tries to make it as low as possible. Scores at the leaves are passed upward. A MAX node takes the largest value of its children, and a MIN node takes the smallest. The value at the top tells MAX how well it can do against a perfect opponent. Plain minimax visits every node. Our goal is to visit fewer, and get the same value.

Analogy

Skipping a Road Already Worse

Here's the idea, with roads. On road one, you've checked everything: the worst that can happen is arriving in 3 hours. You start checking road two, and the very first thing you find is a closure. At best, you'll arrive in 5 hours. Do you need to check the rest of road two? No. It's already worse than road one, and more news can only make it worse, or leave it the same.

First Example

The Leaf That Is Never Examined

The same idea, on a tiny game tree. MAX moves first, then MIN. The left MIN node looks at 3 and 5, and picks 3. So MAX already knows it can get at least 3. On the right, MIN sees the leaf 2 first. So MIN can hold this branch to 2 or less. Whatever the remaining leaf is, the right branch can't beat 3. If it's 9, MIN still picks 2. So the 9 is never examined.

Key Terms

Alpha, Beta, and the Search Window

To make this precise, the search carries two numbers down the tree, called alpha and beta. Alpha is the best value MAX is already sure of, on the path to this node. It starts at minus infinity, and only ever rises. Beta is the best value MIN is already sure of: the lowest. It starts at plus infinity, and only ever falls. Together they form a window. Only values inside the window can still change the decision at the top.

Pruning Rule

Alpha Cut-Offs and Beta Cut-Offs

The pruning rule: as soon as alpha is greater than or equal to beta at a node, stop examining its remaining children. The window has closed. One player already has a better option elsewhere, so they'd never let play reach this node. That gives two kinds of cut-off. An alpha cut-off happens at a MIN node, when its value falls to alpha or below: MAX already has that much elsewhere. A beta cut-off happens at a MAX node, when its value rises to beta or above: MIN already has a lower option higher up. Bounds travel down to the children. Values travel up to the parents. And because a cut-off only skips children that can't change the top, the root's value and move are exactly what plain minimax gives.

Worked Example

Alpha-Beta Examines 7 of 9 Leaves

Now a real trace. MAX can choose B, C or D, each a MIN node with three leaves, searched left to right. Visit B: its leaves are 6, 9 and 7, so B takes 6. Back at the root, alpha becomes 6. Visit C, carrying alpha 6. Its first leaf is 4, so C is worth at most 4. That's an alpha cut-off. Skip 11 and 8. Visit D. Its first leaves are 10 and 8, both above alpha, so the search continues. Only the last leaf, 3, shows that D is poor. Root takes the largest of 6, at most 4, and 3. MAX moves to B. Plain minimax examines 9 leaves, and alpha-beta examines 7.

Quick Check

Which Leaves Get Skipped

Quick check, on a new tree. The root is MAX, with three MIN children, searched left to right. P has leaves 4 and 9. Q has 7, 6 and 5. And R has 3, 8 and 2. Which leaves does alpha-beta skip? Pause, and predict. R's last two. P is worth 4, so alpha is 4. Every leaf of Q is above 4, so Q is searched in full, and alpha rises to 5. Then R's first leaf, 3, is at or below alpha. Cut off: 8 and 2 are skipped, and the root is worth 5. Q is the tempting answer, but its leaves never fall to alpha, so nothing there can be cut.

Worked Example

Both Cut-Offs in a Deeper Tree

Now a deeper tree, with both kinds of cut-off: MAX at the top, then MIN, then MAX, then the leaves. On the left, the first MAX child sees 3 and 5, and returns 5. So beta at the left MIN node becomes 5. The second MAX child sees 6 first. Six is at least beta, 5: a beta cut-off. Skip the 9. The left MIN node returns 5, so the root now has alpha 5. Right side: the first MAX child sees 2 and 1, and returns 2. That's at most alpha: an alpha cut-off. So the whole second child, with leaves 7 and 8, disappears at once. Only 5 of the 8 leaves were examined. Pruning higher in the tree is worth more than pruning near the leaves.

Move Ordering

Best-First Ordering Examines Under 1 Percent

Those cut-offs came because a good move was found early. Reverse the children, and the bounds tighten later, so less is skipped. To measure it, picture 100 random game trees, each with 6 moves at every position and 6 levels: 46,656 leaves each. In a simulation, worst-first ordering still examined nearly all the leaves. Random ordering examined only about a ninth. And best-first ordering examined just 431 leaves: less than 1 percent. Every method returned the same value, only the work differed.

Best-Case Savings

Square Root of the Leaves, Twice as Deep

There's a pattern behind those numbers. With b moves per position and d levels, plain minimax examines about b to the d leaves. With perfect ordering, alpha-beta examines about b to the d over 2: roughly the square root. For our trees, 6 cubed plus 6 cubed, minus 1, is exactly 431. At chess-like branching, 35 moves, depth 4 costs plain minimax about 1.5 million leaves. Best-case alpha-beta reaches depth 8 for about 3 million. Same effort, twice as far ahead. And deeper search means stronger play.

Ordering Techniques

Killer Moves, History Tables, Iterative Deepening

Nobody can order moves perfectly, since that would mean already knowing their values. So programs use cheap guesses. Domain knowledge: in chess, try captures, checks and central moves first. Killer moves: a move that caused a cut-off in a sibling branch is probably good here too. A history table counts how often each move has caused cut-offs, and tries the high scorers first. Iterative deepening searches to depth 1, then 2, then 3, and uses each round's best move to order the next. And stored positions reuse the score of a position reached by a different move order.

Evaluation Functions

Depth Limits and Weighted Features

Even best-case pruning can't reach the end of a complex game. So programs stop at a depth limit, measured in plies, where one ply is one move by one player. At the limit, an evaluation function guesses how good the position is: a quick formula, from MAX's point of view. The test, is this a leaf, becomes: is the game over, or have we reached the limit? Most evaluation functions add up weighted features: weight one times feature one, plus weight two times feature two, and so on. In chess, material is the classic feature, with common values: pawn 1, knight 3, bishop 3, rook 5, queen 9. Mobility, king safety and pawn structure count too.

Worked Example

Counting Open Lines in Tic-Tac-Toe

Here's a worked example in tic-tac-toe. There are 8 winning lines: 3 rows, 3 columns and 2 diagonals. A line is open for a player if the opponent has no mark on it. Score the position as X's open lines minus O's open lines. X holds the center, and O holds a corner. O's corner lies on 3 lines, so X has 8 minus 3: 5 open lines. X's center lies on 4 lines, so O has 8 minus 4: 4 open lines. The score is 5 minus 4, plus 1: slightly better for X.

Quick Check

X on an Edge, O in the Center

Quick check. A different position: X is on an edge square, the middle of the top row. O holds the center. Using X's open lines minus O's open lines, what's the score? Pause, and predict. Minus 2. O's center lies on 4 lines, so X keeps only 4 open lines. X's edge square lies on just 2 lines, so O keeps 6. Four minus six is minus 2. Plus 2 gets the subtraction backwards. The center is the strongest square, because it sits on the most lines.

Design Criteria

Fast, Correct, Predictive, and Stable

A good evaluation function is fast, because it runs at every leaf, possibly millions of times a second. It's correct at the end: a won position scores very high, a lost one very low, and a draw in between. It's predictive: higher scores really mean better chances. And it's stable: it doesn't swing wildly when a capture is about to happen.

Common Pitfall

Horizon Effect and Quiescence Search

Depth limits bring a problem called the horizon effect. The program can't see past its limit. Suppose a loss is unavoidable, but would happen just past the horizon. The program may play useless delaying moves, like giving up a piece, that push the loss one step further away. It believes it has avoided the problem, when it has only hidden it. Quiescence search reduces the risk. Instead of evaluating right at the limit, it keeps searching through unsettled positions, such as pending captures, and evaluates once the position is quiet.

Putting It Together

Deep Blue and Kasparov in 1997

So a typical game program runs alpha-beta to a depth limit, scores the positions there with an evaluation function, and tries moves in a good order, so pruning removes as much as possible. In 1997, IBM's Deep Blue beat the world champion, Garry Kasparov, with this combination of search and evaluation, plus powerful special hardware. Back to that 1.8 billion. Skipping is safe because alpha-beta only skips branches that can't change the decision, and good ordering lets it skip almost everything.

Key Takeaways

Alpha-Beta Pruning Summed Up

To sum up. Alpha-beta skips branches that can't change the decision, and returns the same value and move as plain minimax. Alpha is the best MAX is sure of, and beta the best MIN is sure of. Prune when alpha reaches beta: MIN nodes give alpha cut-offs, and MAX nodes give beta cut-offs. Move ordering decides the savings. The best case examines about the square root of the leaves, so a program can search about twice as deep. Real programs add a depth limit with an evaluation function, and quiescence search against the horizon effect.

Reflection

Better Evaluation or Better Ordering

Here's something to think about. Your program gets exactly one second per move. Would you rather give it a better evaluation function that runs twice as slowly, or better move ordering that searches deeper in the same time? What would you measure to decide?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Pruning Game Trees with Alpha-Beta Techniques

What is alpha-beta pruning?
Alpha-beta pruning is a way to speed up minimax by skipping branches of a game tree that cannot change the final decision. It returns exactly the same value and move as plain minimax. For example, if MAX can already get 6 from one move and another MIN node's first leaf is 4, that node is worth at most 4, so its remaining leaves are skipped.
What do alpha and beta mean in alpha-beta pruning?
Alpha is the best value MAX is already sure of along the current path, starting at minus infinity, and beta is the best (lowest) value MIN is already sure of, starting at plus infinity. When alpha becomes greater than or equal to beta at a node, its remaining children are skipped. Cut-offs at MIN nodes are alpha cut-offs; cut-offs at MAX nodes are beta cut-offs.
Why does move ordering matter in alpha-beta pruning?
Move ordering decides how much alpha-beta can skip, because good moves found early tighten the bounds sooner. With perfect ordering it examines about b to the d/2 leaves instead of b to the d, roughly the square root, so a program can search about twice as deep in the same time. Programs approximate good ordering with captures first, killer moves, history tables, and iterative deepening.
What is the horizon effect in game-playing AI?
The horizon effect happens when a depth-limited search cannot see past its limit, so it plays useless delaying moves that push an unavoidable loss just beyond the horizon. The program believes it avoided the problem when it only hid it. Quiescence search reduces the risk by continuing through unsettled positions, such as pending captures, and evaluating only once the position is quiet.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →