Paper Info
Title
The efficiency of the alpha-beta search on trees with branch-dependent terminal node scores
Abstract
An analysis of the efficiency of the alpha-beta algorithm is carried out based on a probabilistic model in which terminal node scores depend on random branch values. Explicit expressions are derived for the expected number of terminal nodes scored for the cases of uniform trees of fanout N and of depths 2 and 3. For trees of depth 2, the expected number is of order O(NHN); for trees of depth 3, the expected number is of order O(N2). An upper bound on the expected number of terminal nodes scored for trees of depth 4 is shown to be no greater than O(N2HN2) and no less than O(N2).
Year
DOI
Venue
1977
10.1016/0004-3702(77)90017-0
Artificial Intelligence
Field
DocType
Volume
Discrete mathematics,Combinatorics,Expression (mathematics),Upper and lower bounds,Expected value,Statistical model,Mathematics,Alpha–beta pruning
Journal
8
Issue
ISSN
Citations 
2
0004-3702
25
PageRank 
References 
Authors
19.41
2
1
Name
Order
Citations
PageRank
Monroe M. Newborn117747.49