KEMBAR78
Alpha Beta Pruning Example | PDF
Scribd
Upload
23 views5 pages

Alpha Beta Pruning Example

Alpha-Beta Pruning is an optimization technique for the Minimax algorithm used in game theory that reduces the number of nodes evaluated in a game tree. In a given example, the final value selected by the maximizer is 6, with certain leaf nodes evaluated and others pruned for efficiency. This method enhances performance by allowing deeper exploration of game trees while maintaining correctness.

Uploaded by

Arunprakash
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
23 views5 pages

Alpha Beta Pruning Example

Alpha-Beta Pruning is an optimization technique for the Minimax algorithm used in game theory that reduces the number of nodes evaluated in a game tree. In a given example, the final value selected by the maximizer is 6, with certain leaf nodes evaluated and others pruned for efficiency. This method enhances performance by allowing deeper exploration of game trees while maintaining correctness.

Uploaded by

Arunprakash
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Alpha-Beta Pruning - Game Tree

Example
Optimizing Minimax Algorithm in
Game Trees
What is Alpha-Beta Pruning?
• Alpha-Beta Pruning is an optimization for the
Minimax algorithm used in decision-making and
game theory.

• - Alpha (α): Best value that the maximizer can


guarantee.
• - Beta (β): Best value that the minimizer can
guarantee.
• - It reduces the number of nodes evaluated in the
search tree.
Game Tree Example
• Tree structure:

• A (MAX)
• / | \
• B C D (MIN nodes)
• /\ /\ /\
• 3 5 6 9 1 2 (leaf nodes)

• We'll apply Alpha-Beta Pruning to this tree.


Step-by-Step Alpha-Beta Evaluation
• 1. Start at A (MAX): α = -∞, β = +∞
• 2. Go to B (MIN): evaluates 3 and 5 → returns 3
• → A updates α = max(-∞, 3) = 3
• 3. Go to C (MIN): evaluates 6 → β = 6
• Since 6 > α (3), prune 9
• → C returns 6, A updates α = max(3, 6) = 6
• 4. Go to D (MIN): evaluates 1 → β = 1
• Since β (1) < α (6), prune 2
• → D returns 1, A final value = 6
Summary of Alpha-Beta Pruning
• - Final value selected by MAX: 6
• - Leaf nodes evaluated: 3, 5, 6, 1
• - Leaf nodes pruned(skipped): 9, 2

• Benefits:
• - Reduces time complexity
• - Allows deeper game tree exploration
• - Improves efficiency without sacrificing
correctness

You might also like