Distributed Game Tree Search

We present a distributed algorithm for searching game trees. A general strategy for distributed computing is used that can be applied also to other search algorithms. Two new concepts are introduced in order to reduce search overhead and communication overhead: the “Young Brothers Wait Concept” and the “Helpful Master Concept”. We describe some properties of our distributed algorithm including optimal speedup on best ordered game trees.An implementation of this algorithm in a distributed chess program is studied and experimental data showing surprisingly good performance are presented. Since the performance of our algorithm increases with a better move ordering, this algorithm promises to outperform other known algorithms, especially when combined with state-of-the-art chess programs.