25,161
edits
Changes
Created page with "'''Home * Search * Parallel Search * APHID''' FILE:Aphidoidea puceron Luc Viatour.jpg|border|right|thumb|Two adult aphids <ref>[https://en.wikipedia.o..."
'''[[Main Page|Home]] * [[Search]] * [[Parallel Search]] * APHID'''
[[FILE:Aphidoidea puceron Luc Viatour.jpg|border|right|thumb|Two adult aphids <ref>[https://en.wikipedia.org/wiki/Aphid Aphidoidea] in [https://en.wikipedia.org/wiki/Belgium Belgium], [https://commons.wikimedia.org/wiki/File:Aphidoidea_puceron_Luc_Viatour.jpg Image] by [https://commons.wikimedia.org/wiki/User:Lviatour Luc Viatour], 2008, [https://creativecommons.org/licenses/by-sa/2.5/deed.en CC BY-SA 2.5], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''APHID''', (Asynchronous Parallel Hierarchical Iterative Deepening)<br/>
an asynchronous parallel [[Alpha-Beta|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]] <ref>[[Mark Brockington]] ('''1998'''). ''Asynchronous Parallel Game-Tree Search''. Ph.D. thesis, [[University of Alberta]], [http://www.collectionscanada.gc.ca/obj/s4/f2/dsk2/ftp02/NQ29023.pdf pdf]</ref>, along with his thesis advisor [[Jonathan Schaeffer]]. APHID uses repeated depth-limited searches of the top of the [[Search Tree|search tree]] to instantiate, update and [https://en.wikipedia.org/wiki/Load_balancing_(computing) load balance] work lists for other processors. APHID can be seen as a [https://en.wikipedia.org/wiki/Master/slave_(technology) master/slave] model, but can be generalized to a hierarchical processor tree.
=Library=
APHID has been programmed as an easy-to-implement, game-independent library <ref>[http://webdocs.cs.ualberta.ca/~games/aphid/index.html APHID Parallel Game-Tree Search Library]</ref>, and was implemented into the chess program [[The Turk]] with less than one day of programming effort <ref>[[Mark Brockington]], [[Jonathan Schaeffer]] ('''1997'''). ''APHID Game-Tree Search''. [[Advances in Computer Chess 8]], 4. Experiments pp. 83</ref>. It was further tested in [[Crafty]] in chess, in [https://en.wikipedia.org/wiki/Chinook_(draughts_player) Chinook] in the domain of [[Checkers]], and in Brockington's [[Othello]] program ''Keyano'' <ref>[https://webdocs.cs.ualberta.ca/~games/keyano/ Keyano (Othello) Home Page]</ref>. APHID yields reasonable performance on a [https://en.wikipedia.org/wiki/Computer_network network] of [https://en.wikipedia.org/wiki/Workstation workstations], an architecture where it is extremely difficult to use a [[Shared Hash Table|shared transposition table]] effectively. More recently, APHID was used within the [[ChessBrain]] project of over 2000 [https://en.wikipedia.org/wiki/Internet internet] connected machines running [[Beowulf]] <ref>[[Colin Frayn]], [[Carlos Justiniano]], [[Kevin Lew]] ('''2006'''). ''ChessBrain II – A Hierarchical Infrastructure for Distributed Inhomogeneous Speed-Critical Computation''. [http://www.chessbrain.net/docs/chessbrainII.pdf pdf]</ref>.
=How it works=
The master is responsible for searching the top d' [[Ply|plies]] of the d-ply [[Search Tree|tree]] inside its [[Iterative Deepening|iterative deepening]] frame. When the master reaches a [[Leaf Node|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|node types]], the master decides which child-nodes are searched sequentially or in parallel.
[[FILE:aphidybw.jpg|none|border|text-bottom]]
Location of Parallelism in typical APHID and [[Young Brothers Wait Concept|YBW]] [[Search Tree|search trees]] <ref>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]], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8215&rep=rep1&type=pdf pdf] from [https://en.wikipedia.org/wiki/CiteSeerX CiteSeerX]</ref>
The slave process essentially executes the same code that a sequential [[Alpha-Beta|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=
* [[ChessBrain]]
* [[Crafty]]
* [[The Turk]]
* [[Young Brothers Wait Concept]]
=Publications=
* [[Mark Brockington]], [[Jonathan Schaeffer]] ('''1996'''). ''The APHID Parallel αβ Search Algorithm''. Technical Report 96-07, Department of Computing Science, [[University of Alberta]], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8215&rep=rep1&type=pdf pdf] from [https://en.wikipedia.org/wiki/CiteSeerX 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]], [http://www.collectionscanada.gc.ca/obj/s4/f2/dsk2/ftp02/NQ29023.pdf pdf]
* [[Mark Brockington]], [[Jonathan Schaeffer]] ('''1999'''). ''APHID: Asynchronous Parallel Game-Tree Search''. Department of Computing Science, [[University of Alberta]], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.9870&rep=rep1&type=pdf pdf] from [https://en.wikipedia.org/wiki/CiteSeerX CiteSeerX]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=189126 Chess over LAN revisited - APHID] by [[Gian-Carlo Pascutto]], [[CCC]], September 17, 2001
: [https://www.stmintz.com/ccc/index.php?id=189259 APHID , advances in ICCA #8] by [[Vincent Diepeveen]], [[CCC]], September 18, 2001
* [https://groups.google.com/d/msg/rec.games.chess.computer/3Z5eCrUmA5U/x_eLJS4kELEJ Deep Crafty] by Donald O. Davis, [[Computer Chess Forums|rgcc]], October 29, 2001
* [http://www.talkchess.com/forum/viewtopic.php?t=33652 asynchronous search] by [[Daniel Shawul]], [[CCC]], April 06, 2010
: [http://www.talkchess.com/forum/viewtopic.php?t=33652&start=8 Re: asynchronous search] by [[Daniel Shawul]], [[CCC]], April 07, 2010
: [http://www.talkchess.com/forum/viewtopic.php?t=33652&start=11 Re: asynchronous search] by [[Dann Corbit]], [[CCC]], April 08, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=57343 scorpio can run on 8192 cores] by [[Daniel Shawul]], [[CCC]], August 22, 2015 » [[Scorpio]]
: [http://www.talkchess.com/forum/viewtopic.php?t=57343&start=8 Re: scorpio can run on 8192 cores] by [[Daniel Shawul]], [[CCC]], August 30, 2015
=External Links=
==Game Tree Search==
* [http://webdocs.cs.ualberta.ca/~games/aphid/index.html APHID Parallel Game-Tree Search Library]
==Misc==
* [https://en.wikipedia.org/wiki/Aphid Aphid from Wikipedia]
* [https://en.wiktionary.org/wiki/aphid aphid - Wiktionary]
* [https://en.wikipedia.org/wiki/Aphid_(disambiguation) Aphid (disambiguation) from Wikipedia]
=References=
<references />
'''[[Parallel Search|Up one level]]'''
[[FILE:Aphidoidea puceron Luc Viatour.jpg|border|right|thumb|Two adult aphids <ref>[https://en.wikipedia.org/wiki/Aphid Aphidoidea] in [https://en.wikipedia.org/wiki/Belgium Belgium], [https://commons.wikimedia.org/wiki/File:Aphidoidea_puceron_Luc_Viatour.jpg Image] by [https://commons.wikimedia.org/wiki/User:Lviatour Luc Viatour], 2008, [https://creativecommons.org/licenses/by-sa/2.5/deed.en CC BY-SA 2.5], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''APHID''', (Asynchronous Parallel Hierarchical Iterative Deepening)<br/>
an asynchronous parallel [[Alpha-Beta|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]] <ref>[[Mark Brockington]] ('''1998'''). ''Asynchronous Parallel Game-Tree Search''. Ph.D. thesis, [[University of Alberta]], [http://www.collectionscanada.gc.ca/obj/s4/f2/dsk2/ftp02/NQ29023.pdf pdf]</ref>, along with his thesis advisor [[Jonathan Schaeffer]]. APHID uses repeated depth-limited searches of the top of the [[Search Tree|search tree]] to instantiate, update and [https://en.wikipedia.org/wiki/Load_balancing_(computing) load balance] work lists for other processors. APHID can be seen as a [https://en.wikipedia.org/wiki/Master/slave_(technology) master/slave] model, but can be generalized to a hierarchical processor tree.
=Library=
APHID has been programmed as an easy-to-implement, game-independent library <ref>[http://webdocs.cs.ualberta.ca/~games/aphid/index.html APHID Parallel Game-Tree Search Library]</ref>, and was implemented into the chess program [[The Turk]] with less than one day of programming effort <ref>[[Mark Brockington]], [[Jonathan Schaeffer]] ('''1997'''). ''APHID Game-Tree Search''. [[Advances in Computer Chess 8]], 4. Experiments pp. 83</ref>. It was further tested in [[Crafty]] in chess, in [https://en.wikipedia.org/wiki/Chinook_(draughts_player) Chinook] in the domain of [[Checkers]], and in Brockington's [[Othello]] program ''Keyano'' <ref>[https://webdocs.cs.ualberta.ca/~games/keyano/ Keyano (Othello) Home Page]</ref>. APHID yields reasonable performance on a [https://en.wikipedia.org/wiki/Computer_network network] of [https://en.wikipedia.org/wiki/Workstation workstations], an architecture where it is extremely difficult to use a [[Shared Hash Table|shared transposition table]] effectively. More recently, APHID was used within the [[ChessBrain]] project of over 2000 [https://en.wikipedia.org/wiki/Internet internet] connected machines running [[Beowulf]] <ref>[[Colin Frayn]], [[Carlos Justiniano]], [[Kevin Lew]] ('''2006'''). ''ChessBrain II – A Hierarchical Infrastructure for Distributed Inhomogeneous Speed-Critical Computation''. [http://www.chessbrain.net/docs/chessbrainII.pdf pdf]</ref>.
=How it works=
The master is responsible for searching the top d' [[Ply|plies]] of the d-ply [[Search Tree|tree]] inside its [[Iterative Deepening|iterative deepening]] frame. When the master reaches a [[Leaf Node|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|node types]], the master decides which child-nodes are searched sequentially or in parallel.
[[FILE:aphidybw.jpg|none|border|text-bottom]]
Location of Parallelism in typical APHID and [[Young Brothers Wait Concept|YBW]] [[Search Tree|search trees]] <ref>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]], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8215&rep=rep1&type=pdf pdf] from [https://en.wikipedia.org/wiki/CiteSeerX CiteSeerX]</ref>
The slave process essentially executes the same code that a sequential [[Alpha-Beta|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=
* [[ChessBrain]]
* [[Crafty]]
* [[The Turk]]
* [[Young Brothers Wait Concept]]
=Publications=
* [[Mark Brockington]], [[Jonathan Schaeffer]] ('''1996'''). ''The APHID Parallel αβ Search Algorithm''. Technical Report 96-07, Department of Computing Science, [[University of Alberta]], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8215&rep=rep1&type=pdf pdf] from [https://en.wikipedia.org/wiki/CiteSeerX 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]], [http://www.collectionscanada.gc.ca/obj/s4/f2/dsk2/ftp02/NQ29023.pdf pdf]
* [[Mark Brockington]], [[Jonathan Schaeffer]] ('''1999'''). ''APHID: Asynchronous Parallel Game-Tree Search''. Department of Computing Science, [[University of Alberta]], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.9870&rep=rep1&type=pdf pdf] from [https://en.wikipedia.org/wiki/CiteSeerX CiteSeerX]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=189126 Chess over LAN revisited - APHID] by [[Gian-Carlo Pascutto]], [[CCC]], September 17, 2001
: [https://www.stmintz.com/ccc/index.php?id=189259 APHID , advances in ICCA #8] by [[Vincent Diepeveen]], [[CCC]], September 18, 2001
* [https://groups.google.com/d/msg/rec.games.chess.computer/3Z5eCrUmA5U/x_eLJS4kELEJ Deep Crafty] by Donald O. Davis, [[Computer Chess Forums|rgcc]], October 29, 2001
* [http://www.talkchess.com/forum/viewtopic.php?t=33652 asynchronous search] by [[Daniel Shawul]], [[CCC]], April 06, 2010
: [http://www.talkchess.com/forum/viewtopic.php?t=33652&start=8 Re: asynchronous search] by [[Daniel Shawul]], [[CCC]], April 07, 2010
: [http://www.talkchess.com/forum/viewtopic.php?t=33652&start=11 Re: asynchronous search] by [[Dann Corbit]], [[CCC]], April 08, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=57343 scorpio can run on 8192 cores] by [[Daniel Shawul]], [[CCC]], August 22, 2015 » [[Scorpio]]
: [http://www.talkchess.com/forum/viewtopic.php?t=57343&start=8 Re: scorpio can run on 8192 cores] by [[Daniel Shawul]], [[CCC]], August 30, 2015
=External Links=
==Game Tree Search==
* [http://webdocs.cs.ualberta.ca/~games/aphid/index.html APHID Parallel Game-Tree Search Library]
==Misc==
* [https://en.wikipedia.org/wiki/Aphid Aphid from Wikipedia]
* [https://en.wiktionary.org/wiki/aphid aphid - Wiktionary]
* [https://en.wikipedia.org/wiki/Aphid_(disambiguation) Aphid (disambiguation) from Wikipedia]
=References=
<references />
'''[[Parallel Search|Up one level]]'''
