Evaluating a Game Tree with Alpha-Beta Pruning

Last updated

Problem Setup

Scenario:MAX must choose between two moves, A and B, in a turn-based game. The opponent controls the next move and will always choose the outcome that gives MAX the lower score.

Given:A game tree with terminal scores at the leaf nodes. The root is a MAX node, A and B are MIN nodes, and C through G are MAX nodes. The tree is evaluated from left to right.

Task:Evaluate the tree using Alpha-Beta Pruning, find the optimal move and final value at the root, and identify the branches that can be pruned.

Need a quick refresher? Review Alpha-Beta theory

Game Tree

Each leaf shows a possible utility score for MAX. The tree illustrates the choices available to both players, with higher scores favoring MAX and lower scores favoring MIN.

Root
A
B
C
D
E
F
G
8
3
9
-2
5
7
2
4
6
8
1
Want to edit this data in the live solver?

Step-by-Step Resolution

Watch the full global tree update as the depth-first search traverses back up. The active node being evaluated is highlighted with a glowing blue ring.

1

Evaluating Node: C

Position:Level 2 (Bottom-most evaluating layer)Layer Type:MAX

Received α\alpha: −∞\small-∞Received β\beta: ∞\small∞
Child Node Evaluations
Evaluated child 8 (returns 8)
Update: α=8,β=∞\alpha = 8,\quad \beta = ∞max(−∞,8)=8max(-∞, 8) = 8
Evaluated child 3 (returns 3)
Update: α=8,β=∞\alpha = 8,\quad \beta = ∞max(8,3)=8max(8, 3) = 8
Result: Node C locks in a value of 8.
Global Tree State (Step 1)
α:-∞
β:∞
Root
α:-∞
β:∞
A
B
α:-∞→8
β:∞
C [8]
D
E
F
G
8
3
9
-2
5
7
2
4
6
8
1
2

Evaluating Node: D

Position:Level 2 (Bottom-most evaluating layer)Layer Type:MAX

Received α\alpha: −∞\small-∞Received β\beta: 8\small8
Child Node Evaluations
Evaluated child 9 (returns 9)
Update: α=9,β=8\alpha = 9,\quad \beta = 8max(−∞,9)=9max(-∞, 9) = 9
✂️Pruning triggered! α\alpha (9) >= β\beta (8)
Result: Node D locks in a value of 9.
Global Tree State (Step 2)
α:-∞
β:∞
Root
α:-∞
β:∞→8
A
B
C [8]
α:-∞→9
β:8
D [9]
E
F
G
8
3
9
-2 [PRUNED]
5
7
2
4
6
8
1
3

Evaluating Node: E

Position:Level 2 (Bottom-most evaluating layer)Layer Type:MAX

Received α\alpha: −∞\small-∞Received β\beta: 8\small8
Child Node Evaluations
Evaluated child 5 (returns 5)
Update: α=5,β=8\alpha = 5,\quad \beta = 8max(−∞,5)=5max(-∞, 5) = 5
Evaluated child 7 (returns 7)
Update: α=7,β=8\alpha = 7,\quad \beta = 8max(5,7)=7max(5, 7) = 7
Result: Node E locks in a value of 7.
Global Tree State (Step 3)
α:-∞
β:∞
Root
α:-∞
β:∞→8
A
B
C [8]
D [9]
α:-∞→5→7
β:8
E [7]
F
G
8
3
9
-2 [PRUNED]
5
7
2
4
6
8
1
4

Evaluating Node: A

Position:Level 1 (Intermediate Layer)Layer Type:MIN

Received α\alpha: −∞\small-∞Received β\beta: ∞\small∞
Child Node Evaluations
Evaluated child C (returns 8)
Update: α=−∞,β=8\alpha = -∞,\quad \beta = 8min(∞,8)=8min(∞, 8) = 8
Evaluated child D (returns 9)
Update: α=−∞,β=8\alpha = -∞,\quad \beta = 8min(8,9)=8min(8, 9) = 8
Evaluated child E (returns 7)
Update: α=−∞,β=7\alpha = -∞,\quad \beta = 7min(8,7)=7min(8, 7) = 7
Result: Node A locks in a value of 7.
Global Tree State (Step 4)
α:-∞
β:∞
Root
α:-∞
β:∞→8→7
A [7]
B
C [8]
D [9]
E [7]
F
G
8
3
9
-2 [PRUNED]
5
7
2
4
6
8
1
5

Evaluating Node: F

Position:Level 2 (Bottom-most evaluating layer)Layer Type:MAX

Received α\alpha: 7\small7Received β\beta: ∞\small∞
Child Node Evaluations
Evaluated child 2 (returns 2)
Update: α=7,β=∞\alpha = 7,\quad \beta = ∞max(−∞,2)=2max(-∞, 2) = 2
Evaluated child 4 (returns 4)
Update: α=7,β=∞\alpha = 7,\quad \beta = ∞max(2,4)=4max(2, 4) = 4
Evaluated child 6 (returns 6)
Update: α=7,β=∞\alpha = 7,\quad \beta = ∞max(4,6)=6max(4, 6) = 6
Result: Node F locks in a value of 6.
Global Tree State (Step 5)
α:-∞→7
β:∞
Root
A [7]
α:7
β:∞
B
C [8]
D [9]
E [7]
α:7
β:∞
F [6]
G
8
3
9
-2 [PRUNED]
5
7
2
4
6
8
1
6

Evaluating Node: B

Position:Level 1 (Intermediate Layer)Layer Type:MIN

Received α\alpha: 7\small7Received β\beta: ∞\small∞
Child Node Evaluations
Evaluated child F (returns 6)
Update: α=7,β=6\alpha = 7,\quad \beta = 6min(∞,6)=6min(∞, 6) = 6
✂️Pruning triggered! α\alpha (7) >= β\beta (6)
Result: Node B locks in a value of 6.
Global Tree State (Step 6)
α:-∞→7
β:∞
Root
A [7]
α:7
β:∞→6
B [6]
C [8]
D [9]
E [7]
F [6]
G [PRUNED]
8
3
9
-2 [PRUNED]
5
7
2
4
6
8 [PRUNED]
1 [PRUNED]
7

Evaluating Node: Root

Position:Level 0 (Root Node)Layer Type:MAX

Received α\alpha: −∞\small-∞Received β\beta: ∞\small∞
Child Node Evaluations
Evaluated child A (returns 7)
Update: α=7,β=∞\alpha = 7,\quad \beta = ∞max(−∞,7)=7max(-∞, 7) = 7
Evaluated child B (returns 6)
Update: α=7,β=∞\alpha = 7,\quad \beta = ∞max(7,6)=7max(7, 6) = 7
Result: Node Root locks in a value of 7.
Global Tree State (Step 7)
α:-∞→7
β:∞
Root [7]
A [7]
B [6]
C [8]
D [9]
E [7]
F [6]
G [PRUNED]
8
3
9
-2 [PRUNED]
5
7
2
4
6
8 [PRUNED]
1 [PRUNED]

Final Answer

The root compares the final values from branches A and B:

max⁡(7,6)=7\max(7, 6) = 7

Optimal move:A

Optimal utility value:7

Branch A returns 7 after evaluating C, D, and E. At branch B, node F returns 6, establishing an upper bound of 6 for B. Since this cannot improve the root's current value of 7, the remaining G branch is pruned. The root therefore selects A with an optimal utility value of 7.

Exam Takeaway

  • Carry bounds down the tree: A MAX node updates α\alpha, while a MIN node updates β\beta. The bounds inherited from ancestors are essential because they determine when pruning becomes possible.
  • A pruned node's reported value may be only a bound: At D, observing 9 is enough to establish a value of at least 9. At B, observing 6 establishes a value of at most 6. Neither node needs to evaluate its remaining children.
  • Traversal order affects pruning, not the optimal result: Exploring stronger moves earlier can tighten α\alpha and β\beta sooner, allowing more branches to be skipped. With correct Alpha-Beta Pruning, the root still obtains the same optimal minimax value.