A Taxonomy of Parallel Game-Tree Search Algorithms

Abstract

In the last twenty years, a number of articles and theses have been written that contain innovative parallel game-tree search algorithms. The authors of the parallel algorithms have shown how their work is unique and interesting. In some cases, this has been shown by classifying other algorithms by listing implementation details (Bal and Van Renesse, 1986; Ciancarini, 1994). To the author’s knowledge, no attempt has been made to classify the algorithms based solely on their algorithmic properties. A taxonomy would make it easy to ascertain what has and has not been accomplished in parallel game-tree search. The presentation of this type of taxonomy is the main contribution of this paper.