APHID Parallel Game-Tree Search Library

APHID is an acronym for Asycnhronous Parallel Hierarchical Iterative Deepening. The APHID game-tree search algorithm attempts to accomplish many goals:

to test out the viability of asynchronous search methods for parallel alpha-beta based search.
to develop an algorithm that works well across all hardware platforms and applications.
to implement a tool that can be easily inserted into legacy sequential search algorithms.

Synchronous game-tree search methods have been employed throughout the literature. A synchronous algorithm is one where all processors must synchronize at a node within the tree before proceeding. For example, Young Brothers Wait synchronizes at every PV node. However, APHID is an asynchronous algorithm; it does not synchronize at the root of the game tree.

The library is written in C, using PVM as the underlying communication manager, and is available for beta-testers here. Included at the FTP site is a version of Crafty that was used for my thesis experiments. Please e-mail if you have any further questions.

The algorithm has been tested in many applications, including:

Chinook (checkers)
Keyano (Othello)
Crafty (chess, ftp site)
TheTurk (chess)

Publications

Asynchronous Parallel Game-Tree Search

Ph.D. Thesis, Department of Computing Science, University of Alberta, November 1997.

Mark G. Brockington and Jonathan Schaeffer.

The APHID Parallel alpha-beta Search Algorithm.

Accepted at Eighth IEEE Symposium of Parallel and Distributed Processing (SPDP'96), New Orleans, Oct. 23-26 1996.

Expanded version available as Technical Report 96-07, Department of Computing Science, University of Alberta, August 1996.

Mark G. Brockington and Jonathan Schaeffer.

APHID Game-Tree Search.

Presented at Advances in Computer Chess 8, Maastricht, June 1996.

April 18, 1998