Access Restriction

Author Karp, Richard M. ♦ Zhang, Yangun
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1998
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword &agr;-&bgr; pruning ♦ AND/OR tree ♦ Parallel speedup
Abstract A class of parallel algorithms for evaluating game trees is presented. These algorithms parallelize a standard sequential algorithm for evaluating AND/OR trees and the α-β pruning procedure for evaluating MIN/MAX trees. It is shown that, uniformly on all instances of uniform AND/OR trees, the parallel AND/OR tree algorithm achieves an asymptotic linear speedup using a polynomial number of processors in the height of the tree. The analysis of linear speedup using more than a linear number of processors is due to J. Harting. A numerical lower bound rigorously establishes a good speedup for the uniform AND/OR trees with parameters that are typical in practice. The performance of the parallel α-β algorithm on best-ordered MIN/MAX trees is analyzed.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1998-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 45
Issue Number 6
Page Count 26
Starting Page 1050
Ending Page 1075

Open content in new tab

   Open content in new tab
Source: ACM Digital Library