Which strategy reduces the number of branches explored and the number of…
2012
Which strategy reduces the number of branches explored and the number of static evaluations performed in a game tree?
Answer: B. Alpha-beta pruning strategy — ConceptIn adversarial search, minimax evaluates a game tree by alternating MAX and MIN choices. Alpha-beta pruning keeps lower and upper bounds on values…
- A.
Minimax strategy
- B.
Alpha-beta pruning strategy
- C.
Constraint satisfaction strategy
- D.
Static max strategy
Attempted by 50 students.
Show answer & explanation
Correct answer: B
Concept
In adversarial search, minimax evaluates a game tree by alternating MAX and MIN choices.
Alpha-beta pruning keeps lower and upper bounds on values already established, so a branch can be omitted when it cannot change the final minimax choice.
Application
Suppose MAX has already found a move worth 5, so α = 5.
While examining another branch, MIN finds a reply worth 3, so β = 3 for that branch.
Because beta is now less than or equal to alpha, MAX already has a better alternative. The remaining successors of that branch cannot affect the selected move, so they are not expanded or statically evaluated.
With ideal move ordering, this optimization can reduce the effective search from O(bd) toward O(bd/2), while returning the same minimax decision.
Cross-check
Minimax determines backed-up values through alternating MAX and MIN levels.
Constraint satisfaction solves variable-domain restrictions.
Static evaluation assigns a heuristic score to a position.
The bound-based pruning mechanism is specifically alpha-beta pruning.
Therefore, the required strategy is alpha-beta pruning.