The solution for the branching factor of the alpha-beta pruning algorithm and its optimality

DOI10.1145/358589.358616zbMath0486.68056OpenAlexW2085081875WikidataQ56141858 ScholiaQ56141858MaRDI QIDQ3947131

Judea Pearl

Publication date: 1982

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/358589.358616

zbMATH Keywords

search depthaverage case analysisbranch and bound searchsearch timeminimax algorithmsaverage number of terminal nodesgame searching algorithmslower bound for the average complexityuniform game tree

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A generalization of alpha-beta and \(SSS^*\) search procedures, Eigen-distribution on random assignments for game trees, Improved lower bounds for the online bin stretching problem, Best-first fixed-depth minimax algorithms, Independent distributions on a multi-branching AND-OR tree of height 2, A randomized competitive algorithm for evaluating priced AND/OR trees, Equilibrium points of an AND-OR tree: under constraints on probability, Randomized vs. deterministic decision tree complexity for read-once Boolean functions, Optimistic minimax search for noncooperative switched control with or without dwell time, Non-depth-first search against independent distributions on an AND-OR tree, A minimax algorithm better than alpha-beta? Yes and no