On Parallel Evaluation of Game Trees

TitleOn Parallel Evaluation of Game Trees
Publication TypeTechnical Report
Year of Publication1989
AuthorsKarp, R. M., & Zhang Y.
Other Numbers524

We present parallel algorithms for evaluating game trees. These algorithms parallelize the "left-to-right" sequential algorithm for evaluating AND/OR trees and the alpha-beta pruningn procedure for evaluating MIN/MAX trees. We show that, on every instance of a uniform tree, these parallel algorithms achieve a linear speed-up over their corresponding sequential algorithms, if number of processors used is close to the height of the input tree. These are the first non-trivial deterministic speed-up bounds known for the "left-to-right" algorithm and the alpha-beta pruning procedure.

Bibliographic Notes

ICSI Technical Report TR-89-025

Abbreviated Authors

R. M. Karp and Yangun Zhang

ICSI Publication Type

Technical Report