Apha-Beta Pruning
AIMA 5.2.3
CMPSC 442
Week 4, Meeting 12, Two Segments
Outline
● Defining Alpha and Beta
● Alpha Beta Pruning Algorithm
2Outline, Wk 4, Mtg 12
Apha-Beta Pruning
AIMA 5.2.3
CMPSC 442
Week 4, Meeting 12, Segment 1 of 2: Defining Alpha and
Beta
Motivation for Alpha-Beta Pruning
● Patrick Winston, computer scientist who succeeded Marvin Minsky as
director of the MIT AI Lab for the years 1972 to 1997
● Characterized alpha-beta pruning this way:
If you have an idea which is surely bad, don’t take the time to
see how truly awful it is
4Defining Alpha and Beta
● Consider this tree
○ Why is it unnecessary to compute
the value of the green node?
Motivation for Alpha-Beta Pruning
● Consider this tree
○ Why is it unnecessary to compute the green node?
● Among the possible actions at a given MIN node, MIN will
always choose the one that results in MAX’s lowest score
○ For the left node, MIN has two possible actions, and will
choose the one resulting in 2 points for MAX; 2 is the
current upper bound (best case) for MIN
○ For the right node, MIN has two possible actions, but
MIN’s upper bound will still be 2; MAX will never
choose the action that gives MAX ≤ 1 instead of 2
5Defining Alpha and Beta
Defining Alpha and Beta
α: lower bound on MAX’s outcome
β: upper bound on MIN’s outcome
Do not evaluate a branch
● From a MAX node, given a value v ≥ β
○ MIN will never select that MAX node
● From a MIN node, given a value v ≤ α
○ MAX will never select that MIN node
6Defining Alpha and Beta
Pruning the
Minimax Search
Tree
7Defining Alpha and Beta
Illustrating Alpha and Beta
Minimax(root)
= max(min(3,12,8),
min(2,x,y),
min(14,5,2))
● No need to know values of x, y
8
x y
Defining Alpha and Beta
Illustrating Alpha and Beta
Minimax(root)
= max(3,
min(2,x,y),
2)
● No need to know values of x, y
9
x y
Defining Alpha and Beta
Schematic Summary of Pruning
● If opponent’s actions from node m or
m’ are better for Player than those
from node n, the Player will never
allow the game to proceed to n
10Defining Alpha and Beta
Apha-Beta Pruning
AIMA 5.2.3
CMPSC 442
Week 4, Meeting 12, Segment 2 of 2: Alpha Beta Algorithm
When to Prune: Whenever Alpha ≥ Beta
● Reminder: alpha is lower bound on MAX, beta is upper bound on MIN
● Prune below a MAX node when alpha ≥ beta of its (MIN) ancestors
○ MAX nodes update alpha based on children’s returned values
○ MIN at MAX’s parent node will choose the action leading to beta
● Prune below a MIN node when beta ≤ alpha of its (MAX) ancestors
○ MIN nodes update beta based on children’s returned values
○ MAX at MIN’s parent node will chose the action leading to alpha
12Alpha-Beta Algorithm
Alpha-Beta Algorithm Description
α = current lower bound on MAX’s outcome (α
0
= − ∞)
β = current upper bound on MIN’s outcome (β
0
= + ∞)
● DFS
● Pass current values of α, β down to children during search
● Update values of α and β during search:
○ Update α at MAX nodes
○ Update β at MIN nodes
● Prune remaining branches at a node whenever α ≥ β
13Alpha-Beta Algorithm
Alpha-Beta Pruning Pseudo Code – 1
14Alpha-Beta Algorithmg
Alpha-Beta Pruning Pseudo Code – 2
15Alpha-Beta Algorithm
Performance of Alpha-Beta Pruning
● Guaranteed to compute same root value as Minimax
○ Recall: the root value tells MAX which action to take
● Worst case complexity: no pruning, same as Minimax O(bd)
● Best case complexity: when each player’s best move is the first option
examined, examines only O(bd/2) nodes, allowing to search twice as
deep!
16Alpha-Beta Algorithm
Using Alpha-Beta Pruning
● Use Iterative Deepening search, sort by value last iteration
● Expand captures first, then threats, then forward moves
● O(b(d/2)) is the same as having a branching factor of sqrt(b),
○ sqrt(b)d = b(d/2)
○ Chess goes from b ≈ 35 to b ≈ 6
○ For example, IBM’s Deep Blue used alpha-beta pruning, going from an
average branching factor of 35-40 to 6, doubling the search depth
17Alpha-Beta Algorithm
Summary
● Alpha-Beta pruning improves minimax efficiency
○ Alpha at every node: the lower bound on MAX’s outcome
○ Beta at every node: the upper bound on MIN’s outcome
18Wk 4, Mtg 12 Summary