An analysis of alpha-beta pruning

DOI10.1016/0004-3702(75)90019-3zbMath0358.68143OpenAlexW2157803532WikidataQ55894546 ScholiaQ55894546MaRDI QIDQ1238442

Publication date: 1975

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(75)90019-3

Mathematics Subject Classification ID

2-person games (91A05) Pattern recognition, speech recognition (68T10) Other game-theoretic models (91A40) Multistage and repeated games (91A20) Algorithms in computer science (68W99)

Related Items (85)

A generalization of alpha-beta and \(SSS^*\) search procedures ⋮ Nagging: A scalable fault-tolerant paradigm for distributed search ⋮ Error analysis in minimax trees ⋮ An effective two-level proof-number search algorithm ⋮ Uniqueness of optimal randomized algorithms for balanced AND-OR trees ⋮ A general framework for minimax search in game trees ⋮ Optimal depth-first algorithms and equilibria of independent distributions on multi-branching trees ⋮ Using evaluation functions in Monte-Carlo tree search ⋮ LinUCB applied to Monte Carlo tree search ⋮ Conspiracy number search with relative sibling scores ⋮ Polymerization and crystallization of snowflake molecules in Domineering ⋮ Game tree searching by min/max approximation ⋮ Eigen-distribution on random assignments for game trees ⋮ Proof-Number Search and Its Variants ⋮ Asymptotic properties of level-regular decision trees with randomly evaluated leaves ⋮ Integrating formal specifications into applications: the ProB Java API ⋮ Statistical heuristic search ⋮ Searching minimax game trees under memory space constraint ⋮ Conspiracy numbers for min-max search ⋮ Error propagation in game trees ⋮ Pattern knowledge and search: The SUPREM architecture ⋮ Best-first minimax search ⋮ Benefits of using multivalued functions for minimaxing ⋮ Pruning algorithms for multi-model adversary search ⋮ Multistage robust discrete optimization via quantified integer programming ⋮ A minimax algorithm better than alpha-beta? ⋮ The eigen-distribution for multi-branching weighted trees on independent distributions ⋮ Pruning with improving sequences in lazy functional programs ⋮ Searching game trees under a partial order ⋮ Best-first fixed-depth minimax algorithms ⋮ When is it better not to look ahead? ⋮ Asymptotic properties of minimax trees and game-searching procedures ⋮ Independent distributions on a multi-branching AND-OR tree of height 2 ⋮ Solving multistage quantified linear optimization problems with the alpha-beta nested Benders decomposition ⋮ The last player theorem ⋮ The complexity of a simple stochastic OR-tree model in which ``directional search is bad ⋮ Parallelism in alpha-beta search ⋮ Information capture and reuse strategies in Monte Carlo Tree Search, with applications to games of hidden information ⋮ An investigation of the causes of pathology in games ⋮ A randomized competitive algorithm for evaluating priced AND/OR trees ⋮ Is real-valued minimax pathological? ⋮ Optimistic Monte Carlo Tree Search with Sampled Information Relaxation Dual Bounds ⋮ Equilibrium points of an AND-OR tree: under constraints on probability ⋮ Solving \(8\times 8\) Domineering ⋮ Computational ability in games: individual difference and dynamics ⋮ New results for Domineering from combinatorial game theory endgame databases ⋮ A game tree with distinct leaf values which is easy for the alpha-beta algorithm ⋮ On pruning search trees of impartial games ⋮ A faster alternative to \(SSS^*\) with extension to variable memory ⋮ Autonomous Evolution of Topographic Regularities in Artificial Neural Networks ⋮ On game graph structure and its influence on pathology ⋮ The \(PN^{*}\)-search algorithm: Application to tsume-shogi ⋮ Partial order bounding: A new approach to evaluation in game tree search ⋮ AWT: Aspiration with Timer Search Algorithm in Siguo ⋮ Two-agent IDA* ⋮ The efficiency of the alpha-beta search on trees with branch-dependent terminal node scores ⋮ Deep Blue ⋮ Computer Go: An AI oriented survey ⋮ On the branching factor of the alpha-beta pruning algorithm ⋮ Optimistic minimax search for noncooperative switched control with or without dwell time ⋮ Non-depth-first search against independent distributions on an AND-OR tree ⋮ Multi-player alpha-beta pruning ⋮ From State-of-the-Art Static Fleet Assignment to Flexible Stochastic Planning of the Future ⋮ Linguistic geometry approach for solving the cops and robber problem in grid environments ⋮ Is SSS* better than alpha-beta? ⋮ A general branch and bound formulation for understanding and synthesizing And/Or tree search procedures ⋮ A minimax algorithm better than alpha-beta? Yes and no ⋮ Pathology on game trees revisited, and an alternative to minimaxing ⋮ A comparison of minimax tree search algorithms ⋮ On the nature of pathology in game searching ⋮ The *-minimax search procedure for trees containing chance nodes ⋮ ENHANCED REALIZATION PROBABILITY SEARCH ⋮ MONTE CARLO GO CAPTURING TACTIC SEARCH ⋮ General branch and bound, and its relation to \(A^*\) and \(AO^*\) ⋮ Strategies anticipating a difference in search depth using opponent-model search ⋮ Multi-cut \(\alpha \beta\)-pruning in game-tree search ⋮ Game tree algorithms and solution trees ⋮ A quantitative analysis of the alpha-beta pruning algorithm ⋮ The multi-player version of minimax displays game-tree pathology ⋮ Probabilistic opponent-model search ⋮ Asymmetric Action Abstractions for Planning in Real-Time Strategy Games ⋮ Parallel randomized best-first minimax search. ⋮ Proof-number search ⋮ Special issue: Heuristic search and computer game playing ⋮ An analysis of the conspiracy numbers algorithm

Cites Work

This page was built for publication: An analysis of alpha-beta pruning