Parallel searches of game trees

Hiromoto Usui, Masafumi Yamashita, Masaharu Imai, Toshihide Ibaraki

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)97-109
Number of pages13
JournalSystems and Computers in Japan
Issue number8
Publication statusPublished - Jan 1 1987

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Parallel searches of game trees'. Together they form a unique fingerprint.

Cite this