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

reportActive / Technical Report | Accession Number: ADA046746 | Open PDF

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.

Author(s):
Baudet, Gerard M.
Author Organization(s):
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Descriptive Note:
Interim rept.,
Pagination:
0040

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Contract/Grant Number(s):
N00014-76-C-0370, NSF-MCS-75-22255
 Subject Terms
Joint Capability Areas:
JCA_5_Command and Control; JCA_5.3_Planning; JCA_1_Force Support; JCA_1.3_Human Capital Management; JCA_1.3.2_Personnel Management
Communities of Interest:
Advanced Electronics
Descriptor(s):
*ALGORITHMS, *COMPUTER LOGIC, PROBABILITY DISTRIBUTION FUNCTIONS, RANDOM VARIABLES, PROBLEM SOLVING, NODES, TREES, SEARCHING, COMBINATORIAL ANALYSIS, GAME THEORY, TERMINALS, MINIMAX TECHNIQUE, SEARCH THEORY
Field(s)/Group(s):
Statistics and Probability
Keyword(s):
WUNR044422
Report Date:
1977 Sep 01