APHID
Home * Search * Parallel Search * APHID
APHID, (Asynchronous Parallel Hierarchical Iterative Deepening)
an asynchronous parallel alpha-beta based search algorithm developed and elaborated by Mark Brockington as topic of his Ph.D. thesis at the Department of Computing Science, University of Alberta [2], along with his thesis advisor Jonathan Schaeffer. APHID uses repeated depth-limited searches of the top of the search tree to instantiate, update and load balance work lists for other processors. APHID can be seen as a master/slave model, but can be generalized to a hierarchical processor tree.
Contents
Library
APHID has been programmed as an easy-to-implement, game-independent library [3], and was implemented into the chess program The Turk with less than one day of programming effort [4]. It was further tested in Crafty in chess, in Chinook in the domain of Checkers, and in Brockington's Othello program Keyano [5]. APHID yields reasonable performance on a network of workstations, an architecture where it is extremely difficult to use a shared transposition table effectively. More recently, APHID was used within the ChessBrain project of over 2000 internet connected machines running Beowulf [6].
How it works
The master is responsible for searching the top d' plies of the d-ply tree inside its iterative deepening frame. When the master reaches a leaf of the d'-ply tree, it uses either a (d-d')-ply search result already available from the slave, or the "best available" i.e. using guessed scores from shallower previous searches marked as uncertain. As values get backed up the tree, the master maintains a count of how many uncertain nodes have been visited in a pass of the tree, and has to repeat the root search until all contributing leaves have reliable, certain results. By using the guessed score and expected node types, the master decides which child-nodes are searched sequentially or in parallel.
Location of Parallelism in typical APHID and YBW search trees [7]
The slave process essentially executes the same code that a sequential alpha-beta searcher would. It looks in the local copy of the so called APHID table, initially allocated and supplied by the master, to find the highest priority node to search. After finishing the search, it reports the result back to the master, getting an update to its APHID table entry in return.
See also
Publications
- Mark Brockington, Jonathan Schaeffer (1996). The APHID Parallel αβ Search Algorithm. Technical Report 96-07, Department of Computing Science, University of Alberta, pdf from CiteSeerX
- Mark Brockington, Jonathan Schaeffer (1997). APHID Game-Tree Search. Advances in Computer Chess 8
- Mark Brockington (1998). Asynchronous Parallel Game-Tree Search. Ph.D. thesis, University of Alberta, pdf
- Mark Brockington, Jonathan Schaeffer (1999). APHID: Asynchronous Parallel Game-Tree Search. Department of Computing Science, University of Alberta, pdf from CiteSeerX
- Mark Brockington, Jonathan Schaeffer (2000). APHID: Asynchronous Parallel Game-Tree Search. Journal of Parallel and Distributed Computing, Vol. 60, No. 2
Forum Posts
- Chess over LAN revisited - APHID by Gian-Carlo Pascutto, CCC, September 17, 2001
- APHID , advances in ICCA #8 by Vincent Diepeveen, CCC, September 18, 2001
- Deep Crafty by Donald O. Davis, rgcc, October 29, 2001
- asynchronous search by Daniel Shawul, CCC, April 06, 2010
- Re: asynchronous search by Daniel Shawul, CCC, April 07, 2010
- Re: asynchronous search by Dann Corbit, CCC, April 08, 2010
- scorpio can run on 8192 cores by Daniel Shawul, CCC, August 22, 2015 » Scorpio
- Re: scorpio can run on 8192 cores by Daniel Shawul, CCC, August 30, 2015
External Links
Game Tree Search
Misc
References
- ↑ Aphidoidea in Belgium, Image by Luc Viatour, 2008, CC BY-SA 2.5, Wikimedia Commons
- ↑ Mark Brockington (1998). Asynchronous Parallel Game-Tree Search. Ph.D. thesis, University of Alberta, pdf
- ↑ APHID Parallel Game-Tree Search Library
- ↑ Mark Brockington, Jonathan Schaeffer (1997). APHID Game-Tree Search. Advances in Computer Chess 8, 4. Experiments pp. 83
- ↑ Keyano (Othello) Home Page
- ↑ Colin Frayn, Carlos Justiniano, Kevin Lew (2006). ChessBrain II – A Hierarchical Infrastructure for Distributed Inhomogeneous Speed-Critical Computation. pdf
- ↑ Image cropped from Figure 4, pp. 6 in Mark Brockington, Jonathan Schaeffer (1996). The APHID Parallel αβ Search Algorithm. Technical Report 96-07, Department of Computing Science, University of Alberta, pdf from CiteSeerX