On Parallel Evaluation of Game Trees
Title | On Parallel Evaluation of Game Trees |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Karp, R. M., & Zhang Y. |
Other Numbers | 524 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-89-25.pdf |
Bibliographic Notes | ICSI Technical Report TR-89-025 |
Abbreviated Authors | R. M. Karp and Yangun Zhang |
ICSI Publication Type | Technical Report |