The APHID Parallel alpha-beta Search Algorithm
Jonathan Schaeffer, M.G. Brockington · PubMed · 1996
This paper introduces the APHID (Asynchronous Parallel Hierarchical Iterative Deepening) gametree search algorithm. An APHID search is a hierarchical search with a master controlling the top of the tree (d 0 ply), and the slaves searching the rest of the tree (d \\Gamma d 0 ply). The slaves asynchronously read work lists from the master and return score information to the master. The master uses the returned score information to generate approximate minimax values, until all of the required score information is available. APHID has been programmed as an easy to implement, game-independent fffi library. This has been demonstrated by parallelizing three programs (chess, checkers and Othello) on a network of workstations, each with less than a day's worth of effort.