Alpha–beta pruning makes minimax game search more efficient by avoiding analysis of branches that cannot affect the final choice. This lesson introduces the game-tree setting, the roles of the maximizing and minimizing players, and the meanings of alpha and beta.
A game tree represents possible sequences of moves. Each node is a game situation, and each edge represents a legal move. A path from the root to a terminal node represents one possible continuation of play. Terminal positions, or positions where a depth-limited search stops, are assigned numeric values that estimate how favorable they are for a player.
All flashcards
What is a game tree?
A representation of possible game situations and moves. Nodes represent positions, and paths through the tree represent possible sequences of play.
How does minimax treat the two players?
It assumes the maximizing player chooses the highest-valued child and the minimizing player chooses the lowest-valued child.
What does alpha mean?
Alpha is the best score the maximizing player can guarantee based on the search so far; it acts as a lower bound.
What does beta mean?
Beta is the best score the minimizing player can guarantee based on the search so far; it acts as an upper bound on the score available to the maximizing player.
When is a branch eligible for an alpha–beta cutoff?
When the bounds meet or cross, α≥β. At that point, further descendants cannot alter the minimax choice.
Quiz questions
What may a fail-soft alpha–beta search return when its result lies outside the input window?Answer: The search value outside the input bounds.
With optimal move ordering, how many leaf evaluations can alpha–beta search require for branching factor b and depth d?Answer: Approximately O(bd/2) leaf evaluations.
Why can iterative deepening be useful if a search is interrupted?Answer: A completed shallower search has already produced a usable move.
What does the killer heuristic prioritize during move ordering?Answer: Moves that caused beta cutoffs at the same depth elsewhere.
What should a search do if an aspiration-window search fails high or fails low?Answer: Adjust the window and search again.
Based on the Wikipedia article Alpha–beta pruning, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.