On the Branching Factor of the Alpha-Beta Pruning Algorithm.

Abstract

An analysis of the alpha-beta pruning algorithm is presented which takes into account both shallow and deep cut-offs. A formula is first developed to measure the average number of terminal nodes examined by the algorithm in a uniform tree of degree n and depth d when ties are allowed among the bottom positions: specifically, all bottom values are assumed to be independent identically distributed random variables drawn from a discrete probability distribution.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1977
Accession Number
ADA046746

Entities

People

  • Gerard M. Baudet

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Cartesian Coordinates
  • Computer Science
  • Computers
  • Distribution Functions
  • Equations
  • Inequalities
  • Integrals
  • Intervals
  • Notation
  • Probability
  • Probability Distributions
  • Random Variables
  • Sequences
  • Simulations
  • Terminals
  • Test And Evaluation

Fields of Study

  • Computer science

Readers

  • Atmospheric Science / Meteorology, specifically Wind Wave Turbulence.
  • Game Theory.
  • Graph Algorithms and Convex Optimization.