Asynchronous parallel game-tree search
Brockington, Mark Gordon. · Library and Archives Canada (Government of Canada) · 1998
Tree searching is a fundamental and computationally intensive problem in artificial intelligence. Parallelization of tree-searching algorithms is one method of improving the speed of these algorithms. However, a high-performance parallel two-player game-tree search algorithm has eluded researchers. Most parallel game-tree search approaches follow synchronous methods, where the work is concentrated within a specific part of the tree, or a given search depth. This thesis shows that asynchronous gametree search algorithms can be as efficient as synchronous methods in determining the minimax value. A taxonomy of previous work in parallel game-tree search is presented. A theoretical model is developed for comparing the efficiency of synchronous and asynchronous search algorithms under realistic assumptions. APHID, a portable parallel game-tree search library, has been built based on the asynchronous parallel game-tree search algorithm proposed in the comparison. The library is easy to imple...