Publication Details
Title: On Parallel Evaluation of Game Trees
Author: R. M. Karp and Y. Zhang
Group: ICSI Technical Reports
Date: May 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-25.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-025
Bibliographic Reference:
R. M. Karp and Y. Zhang. On Parallel Evaluation of Game Trees. ICSI Technical Report TR-89-025, May 1989
Author: R. M. Karp and Y. Zhang
Group: ICSI Technical Reports
Date: May 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-25.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-025
Bibliographic Reference:
R. M. Karp and Y. Zhang. On Parallel Evaluation of Game Trees. ICSI Technical Report TR-89-025, May 1989