Parallel Search of Strongly Ordered Game Trees

... This paper draws upon experiences gained during the development of programs which search chess game trees. Over the past decade major enhancements to the alpha-beta algorithm have been developed by people building game-playing programs, and many of these methods will be surveyed and compared here. The balance of the paper contains a study of contemporary methods for searching chess game trees in parallel, using an arbitrary number of independent processors. To make efficient use of these processors, one must have a clear understanding of the basic properties of the trees actually traversed when alpha-beta cutoffs occur. This paper provides such insights and concludes with a brief description of our own refinement to a standard parallel search algorithm for this problem.