Parallel searches of game trees

A two‐person perfect‐information game is represented by a minimax game tree and, by solving the tree, we can obtain the result of the game when both players choose perfect moves at all the positions. To this end, various search procedures have been proposed. In this paper, these procedures are modified to implement them on a parallel computer consisting of m processors, and variations of the computation time are investigated with m being a parameter. As a theoretical result, we point out that the speedup ratio of the computation time of solving a game tree by m processors to that by 1 processor may become larger than m (acceleration anomaly) or smaller than 1 (detrimental anomaly) in general. Also, we show that the detrimental anomaly does not occur as long as the five search procedures investigated in this paper are used. Next, through simulation experiments, it is shown that the speedup ratio is considerably smaller than m, and its cause is discussed. The eligible search is considered to be the best among the search procedure investigated.