A PARALLEL GAME TREE-SEARCH ALGORITHM WITH A LINEAR SPEEDUP

In the theoretical analysis of the average run time of game tree search algorithms it is assumed for simplicity that in every elementary unit of time each processor can reveal the value of one leaf node. Until now there exists only one nontrivial stochastic game tree model for which the optimal sequential (= 1-processor) algorithm is known. For this model the author presents a parallel algorithm which involves n processors and achieves a linear speedup of better than 201/n in binary trees of depth 6n[log n] for all natural numbers n. This result can be generalized in two directions: (1) (1/k)nk processors can achieve a speedup of (201)kk/nk in binary trees of depth 6n[log n]. (2) Similar algorithms with a linear speedup exist for "all" recursion trees in which directional search is optimal. © 1993 Academic Press, Inc.