Parallel alpha-beta search on shared memory multiprocessors
Valavan Manohararajah · Library and Archives Canada (Government of Canada) · 2001
The alpha-beta algorithm is a well known method for the sequential search of game trees. Two methods, young brothers wait concept and dynamic tree splitting, have been used successfully in parallel game tree search. First, this work introduces the notion of an exponentially ordered game tree as a model for the game trees encountered in practice. Second, exponentially ordered trees are used in the study of the tree splitting methods used by young brothers wait concept and dynamic tree splitting. Finally, a new tree splitting method based on neural networks is introduced and is found to outperform the other two methods on certain types of trees.