alpha–beta pruning
E748469
Alpha–beta pruning is a search algorithm optimization that reduces the number of nodes evaluated in minimax-based game tree searches by eliminating branches that cannot affect the final decision.
Statements (45)
| Predicate | Object |
|---|---|
| instanceOf |
adversarial search algorithm
ⓘ
game tree search technique ⓘ search algorithm optimization ⓘ |
| alphaRepresents | best value that maximizer can guarantee so far ⓘ |
| alsoKnownAs | alpha-beta search NERFINISHED ⓘ |
| assumes |
deterministic game transitions
ⓘ
no hidden information ⓘ optimal play by both players ⓘ |
| basedOn | minimax algorithm ⓘ |
| belongsTo |
algorithm design
ⓘ
artificial intelligence ⓘ |
| benefitsFrom | good move ordering ⓘ |
| bestCaseComplexity | O(b^(d/2)) ⓘ |
| betaRepresents | best value that minimizer can guarantee so far ⓘ |
| canBeCombinedWith |
heuristic evaluation functions
ⓘ
iterative deepening search ⓘ transposition tables ⓘ |
| category | depth-first search enhancement ⓘ |
| commonlyAppliedIn |
computer Go variants with minimax search
ⓘ
computer Othello ⓘ computer checkers ⓘ computer chess ⓘ |
| doesNotChange | final minimax value with perfect play ⓘ |
| eliminates | branches that cannot affect final decision ⓘ |
| enables | deeper search within same time limit ⓘ |
| ensures | same decision as full minimax search if implemented correctly ⓘ |
| formalizedBy | John McCarthy NERFINISHED ⓘ |
| goal | reduce number of nodes evaluated in game tree search ⓘ |
| improves | search efficiency ⓘ |
| influenced | design of modern game-playing engines ⓘ |
| introducedInContextOf | game-playing programs ⓘ |
| mathematicallyRelatedTo | branch and bound ⓘ |
| optimizes | minimax-based game tree search ⓘ |
| prunes | subtrees that cannot improve current best outcome ⓘ |
| prunesWhen | alpha is greater than or equal to beta ⓘ |
| reduces | time complexity constant factor ⓘ |
| requires | two bounds alpha and beta ⓘ |
| typicallyUsedWith | depth-first minimax search ⓘ |
| typicalUseCase | searching game trees to a fixed depth with evaluation at leaves ⓘ |
| usedIn |
perfect-information games
ⓘ
turn-based games ⓘ two-player zero-sum games ⓘ |
| where |
b is branching factor
ⓘ
d is search depth ⓘ |
| worstCaseComplexity | O(b^d) ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.