Alpha-beta pruning
- Algorithms course
- Expert
- Lesson 32/41
- 4 min
Speed up search with alpha-beta pruning.
Alpha-beta pruning
Alpha-beta pruning is a faster version of minimax. It prunes branches that cannot affect the final decision; the result is unchanged.
Alpha is the lowest value the max player can secure; beta is the highest value the min player can secure.
When alpha >= beta at a node, the remaining children are skipped. With good ordering, complexity drops to O(b^(d/2)).
Pruning condition
In the max branch, after evaluating each child, alpha is updated with alpha = max(alpha, value). If alpha >= beta, the loop breaks and remaining children are skipped.
In the min branch, beta is updated with beta = min(beta, value) and pruning occurs when beta <= alpha.
Pruning never changes the final minimax value; it only avoids unnecessary computation.
Practice alphabeta function
Write alphabeta(node, alpha, beta, is_max). Return the minimax value with pruning. Print 3 with print(alphabeta([[3, 5], [2, 9]], float('-inf'), float('inf'), True)).
Starter code
def alphabeta(node, alpha, beta, is_max):
# Minimax with alpha-beta pruningSample solution
def alphabeta(node, alpha, beta, is_max):
# Minimax with alpha-beta pruning
if not isinstance(node, list):
return node
if is_max:
value = float('-inf')
for child in node:
value = max(value, alphabeta(child, alpha, beta, False))
alpha = max(alpha, value)
if alpha >= beta:
break
return value
value = float('inf')
for child in node:
value = min(value, alphabeta(child, alpha, beta, True))
beta = min(beta, value)
if beta <= alpha:
break
return value
print(alphabeta([[3, 5], [2, 9]], float('-inf'), float('inf'), True))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 alpha update
alpha = max(alpha, ____)alpha = max(alpha, value)Explanation: alpha is compared against value.
2 When is pruning done in the max branch?
if alpha >= beta:
break- When alpha is greater than or equal to beta Correct answer
- When alpha is zero
- When beta is zero
- When all children are scanned
Explanation: When alpha >= beta, remaining children are pruned.
3 Alpha-beta concepts
| Term | Meaning |
|---|---|
alpha |
Max lower bound |
beta |
Min upper bound |
pruning |
Cut unnecessary branches |
O(b^(d/2)) |
Good ordering |