25,161
edits
Changes
Created page with "'''Home * Search * Parallel Search * ABDADA''' FILE:hannah-hoche_da-dandy-1919.jpg|border|right|thumb|link=http://littlemissartypants.tumblr.com/post/..."
'''[[Main Page|Home]] * [[Search]] * [[Parallel Search]] * ABDADA'''
[[FILE:hannah-hoche_da-dandy-1919.jpg|border|right|thumb|link=http://littlemissartypants.tumblr.com/post/12081930289/hannah-h%C3%B6ch-da-dandy-1919-the-photomontage-da|[[Arts#Hoech|Hannah Höch]] - Da Dandy <ref>[[Arts#Hoech|Hannah Höch]] - Da Dandy, 1919, [http://littlemissartypants.tumblr.com/post/12081930289/hannah-h%C3%B6ch-da-dandy-1919-the-photomontage-da Hannah Höch | Da-Dandy (1919)]</ref> ]]
'''ABDADA''', (Alpha-Bêta Distribué avec Droit d'Aînesse = Distributed Alpha-Beta Search with Eldest Son Right)<br/>
a loosely synchronized, [[Parallel Search|distributed search algorithm]] developed by [[Jean-Christophe Weill]]. The ABDADA search algorithm is based on [[Young Brothers Wait Concept]] (YBWC) ([[Rainer Feldmann]] et al. 1986, 1993) <ref>[[Rainer Feldmann]], [[Peter Mysliwietz]], [[Oliver Vornberger]] ('''1986'''). ''A Local Area Network Used as a Parallel Architecture''. Technical Report 31, [[University of Paderborn]]</ref> <ref>[[Rainer Feldmann]] ('''1993'''). ''Game Tree Search on Massively Parallel Systems''. Ph.D. Thesis, [http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/POSTSCRIPTS/feldmann_phd.pdf pdf]</ref> and αβ* ([[Vincent David]] 1993) <ref>[[Vincent David]] ('''1993'''). ''[http://cat.inist.fr/?aModele=afficheN&cpsidt=161774 Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint. Etude et application au Minimax]'' = Parallel algorithm for heuristic tree searching and real-time reasoning. Study and application to the Minimax, Ph.D. Thesis, [https://en.wikipedia.org/wiki/%C3%89cole_nationale_sup%C3%A9rieure_de_l%27a%C3%A9ronautique_et_de_l%27espace École nationale supérieure de l'aéronautique et de l'espace], [https://en.wikipedia.org/wiki/Toulouse Toulouse], [https://en.wikipedia.org/wiki/France France]</ref> . From YBWC it retains the basic concept to allow parallel search only if the eldest son has been fully evaluated. From αβ* as well as [[Steve Otto]] and [[Ed Felten|Ed Felten's]] algorithm (1988) <ref>[[Ed Felten]], [[Steve Otto]] ('''1988'''). ''[http://portal.acm.org/citation.cfm?id=63088 Chess on a Hypercube]''. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications (ed. [http://portal.acm.org/author_page.cfm?id=81100501616&coll=GUIDE&dl=GUIDE&trk=0&CFID=90098691&CFTOKEN=72738297 G. Fox]), pp. 1329-1341</ref> which both rely on a [[Shared Hash Table]] and all processors start the search simultaneously at the [[Root|root]], ABDADA retains the simple [[Recursion|recursive]] control structure similar to a serial algorithm. With the help of additional [[Transposition Table|transposition table]] information, i.e. the number of processors searching this node, it is possible to control [https://en.wikipedia.org/wiki/Speculative_multithreading speculative parallelism].
=Recursion=
<span id="Recursion"></span>While YBWC is difficult to implement recursively, ABDADA is not. In YBWC, when a processor receives an evaluation answer from one of its slaves, it must be able to produce a jump in the search depth if this evaluation produces a pruning of the current master node. So the values of [[Alpha|alpha]] and [[Beta|beta]] must at least be kept in [[Array|arrays]] indexed by [[Ply|ply]] distance from root, and special arrangements must be made to counteract the disruption that might occur from confusing depths. Therefor YBWC needs a hugely modified [[Iterative Search|iterative search]] algorithm. In his paper <ref>[[Jean-Christophe Weill]] ('''1996'''). ''[http://portal.acm.org/citation.cfm?id=228345 The ABDADA Distributed Minimax Search Agorithm]''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped postscript]</ref> , Weill states that using ABDADA within a recursive [[NegaScout]] framework was 30% faster than a none-recursive search, which was observed independently by [[Mark Brockington]] in 1994 <ref>[[Mark Brockington]] ('''1994'''). ''An Implementation of the Young Brothers Wait Concept''. Internal report, [[University of Alberta]]</ref> . It can be explained by the fact that within high-level languages and their compilers for certain target platforms, the use of procedure [[Stack|stacks]] is much more optimized than the use of indexed arrays, also observed by [https://en.wikipedia.org/wiki/Niklaus_Wirth Niklaus Wirth] concerning the [https://en.wikipedia.org/wiki/Quicksort Quicksort] algorithm <ref>[https://en.wikipedia.org/wiki/Niklaus_Wirth Niklaus Wirth] ('''1976'''). ''[https://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs Algorithms + Data Structures = Programs]''. pp 100</ref> .
=Algorithm=
The ABDADA algorithm is described in five steps:
# A TT-Entry has a field ''entry.nproc'' containing the number of processors currently searching the associated node
# All processors start the search simultaneously at the root of the [[Search Tree|search tree]]
# When a processor enters a node, it increments ''entry.nproc''
# When a processor leaves a node, it decrements ''entry.nproc''
# The analysis of a position is done in three phases:
## The eldest son is analyzed, regardless of the activities of other processors
## Next, all other sons not currently being analyzed by other processors are analyzed
## In the final phase, any remaining sons not yet analyzed are searched, i.e. the corresponding entry in the TT indicates this node and its siblings have not been searched to the required depth
=Pseudo Code=
The C-like pseudo code below (adopted from the Pascal like pseudo code from Weill's paper), demonstrates the mentioned three phases controlled by an iteration counter. The boolean parameter ''exclusiveP'' indicates whether the node should be searched exclusively and is passed to the TT-probing code via the procedure ''retrieveAsk''. A new value outside the usual [[Score#ValueRange|value range]] need to be defined (ON_EVALUATION), and ''retrieveAsk'' returns this score if probed in exclusive move, and other processors evaluating this node.
<pre>
int abdada(const CNode &position, int α, int β, int depth, bool exclusiveP) {
if (depth == 0) return evaluate( position );
int best = -oo;
retrieveAsk(position, α, β, depth, exclusiveP);
/* generate moves while waiting for the answer ... */
GenerateMoves(position);
retrieveAnswer(&α, &β, &best);
/* The current move is not searched if causing a cutoff or */
/* in exclusive mode and another processor is currently searching it */
if ( α >= β || best == ON_EVALUATION )
return best; /* entry.nproc not incremented */
bool alldone = false;
for ( int iteration = 0; iteration < 2 && α < β && !alldone; iteration++) {
alldone = true;
Move m = firstMove( position );
while ( (m != 0) && (α < β) ) {
exclusive = (iteration == 0) && !isFirstMove( m );
/* On the first iteration, only one processor should search young sons exclusively */
value = -abdada( position * m, -β, -max(α, best), depth-1, exclusive );
if ( value == -ON_EVALUATION) {
alldone = false;
} else if ( value > best ) {
best = value;
if ( best > β ) goto endsearch;
}
m = nextMove( position );
}
}
endsearch:
storeHash( position, α, β, depth, best );
return best;
}
</pre>
=Implementations=
==Frenchess==
ABDADA was implemented in [[Frenchess]] on a [[Cray T3D]] with 128 [[DEC Alpha|DEC Alpha 21064]] processors. Frenchess participated at the [[WCCC 1995]] finishing fourth, tied with [[Deep Blue|Deep Blue Prototype]] <ref>[[Marc-François Baudot]], [[Jean-Christophe Weill]], [[Jean-Luc Seret]], [[Michel Gondran]] ('''1995'''). ''[https://www.researchgate.net/publication/228386252_Frenchess_A_Cray_T3D_at_the_8th_World_Computer_Chess_Championship Frenchess: A Cray T3D at the 8th World Computer Chess Championship]''. [http://www.recherche.enac.fr/%7Eweill/publications/papier.ps.gz zipped ps]</ref>, as well inside an [[Othello]] program called ''BUGS'' <ref>[[Jean-Christophe Weill]] ('''1996'''). ''[http://portal.acm.org/citation.cfm?id=228345 The ABDADA Distributed Minimax Search Agorithm]''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped postscript]</ref> .
==Smash==
The [[Free Software Foundation#GPL|GPL]] [[Open Source Engines|open source chess engine]] [[Smash]] by [[Maurizio Sambati]] demonstrates an ABDADA implementation in [[Cpp|C++]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=165470&t=18611 Re: interested in making single procesor program multi] by [[Alessandro Scotti]], [[CCC]], December 29, 2007</ref> <ref>[http://www.cli.di.unipi.it/~sambati/prog/smash.tar.bz2 smash.tar.bz2 search.cpp]</ref> .
=See also=
* [[Dynamic Tree Splitting]]
* [[Jamboree]]
* [[Lazy SMP]]
* [[Cilk#ParallelAlphaBeta|Parallel Alpha-Beta]] in [[Cilk]]
* [[Shared Hash Table]]
* [[Young Brothers Wait Concept]]
=Publications=
* [[Jean-Christophe Weill]] ('''1995'''). ''Programmes d'Échecs de Championnat: Architecture Logicielle Synthèse de Fonctions d'Évaluations, Parallélisme de Recherche''. Ph.D. Thesis. Université Paris 8, Saint-Denis, [http://www.recherche.enac.fr/%7Eweill/publications/phdJCW.ps.gz zipped ps] (French)
* [[Marc-François Baudot]], [[Jean-Christophe Weill]], [[Jean-Luc Seret]], [[Michel Gondran]] ('''1995'''). ''[https://www.researchgate.net/publication/228386252_Frenchess_A_Cray_T3D_at_the_8th_World_Computer_Chess_Championship Frenchess: A Cray T3D at the 8th World Computer Chess Championship]''. [http://www.recherche.enac.fr/%7Eweill/publications/papier.ps.gz zipped ps]
* [[Jean-Christophe Weill]] ('''1996'''). ''[http://portal.acm.org/citation.cfm?id=228345 The ABDADA Distributed Minimax Search Agorithm]''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped postscript]
=Forum Posts=
==1997 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/Wl7A-v-gWYQ/QLuvAp0l4_gJ Parallel searching] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], March 22, 1997
: [https://groups.google.com/d/msg/rec.games.chess.computer/Wl7A-v-gWYQ/w-Ky1kkvfeYJ Re:Parallel searching] by [[Mark Brockington]], [[Computer Chess Forums|rgcc]], March 22, 1997
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=112849 tip for "simulating" an MP computer & performance of ABDADA] by [[Tom Kerrigan]], [[CCC]], May 28, 2000
* [https://www.stmintz.com/ccc/index.php?id=112884 A couple of Questions re ABDADA] by [[Steve Maughan]], [[CCC]], May 29, 2000
* [https://www.stmintz.com/ccc/index.php?id=163888 Parallel algorithms in chess programming] by [[Dieter Bürssner|Dieter Buerssner]], [[CCC]], April 16, 2001
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=42986 Parallelization questions, ABDADA or DTS?] by Benjamin Rosseaux, [[CCC]], March 23, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=47887 ABDADA speedup results] by [[Daniel Shawul]], [[CCC]], May 01, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47951 IID and move sorting] by [[Daniel Shawul]], [[CCC]], May 09, 2013 » [[Internal Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=56936 Possible improvement to ABDADA -- checking for cutoffs] by [[Tom Kerrigan]], [[CCC]], July 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56937 Actual speedups from YBWC and ABDADA on 8+ core machines?] by [[Tom Kerrigan]], [[CCC]], July 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=63023 Good parallel speedup with ABDADA and cutoff checks] by [[Tom Kerrigan]], [[CCC]], February 03, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=43 Approximate ABDADA] by [[Peter Österlund]], [[CCC]], August 23, 2017 » [[Lazy SMP#LazyCluster|Lazy SMP - Lazy Cluster]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65011 "How To" guide to parallel-izing an engine] by [[Tom Kerrigan]], [[CCC]], August 27, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65025 "Simplified ABDADA" updated] by [[Tom Kerrigan]], [[CCC]], August 29, 2017
=External Links=
==Algorithm==
* [http://www.tckerrigan.com/Chess/Parallel_Search/Simplified_ABDADA/ Simplified ABDADA] from [http://www.tckerrigan.com/Chess/Parallel_Search/ Parallel Search] by [[Tom Kerrigan]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65011 "How To" guide to parallel-izing an engine] by [[Tom Kerrigan]], [[CCC]], August 27, 2017</ref>
: [http://www.tckerrigan.com/Chess/Parallel_Search/Cutoff_Checks/ Cutoff Checks] from [http://www.tckerrigan.com/Chess/Parallel_Search/ Parallel Search] by [[Tom Kerrigan]]
==Misc==
* [https://en.wikipedia.org/wiki/AB AB from Wikipedia]
* [https://en.wiktionary.org/wiki/ab ab - Wiktionary]
* [https://en.wiktionary.org/wiki/ab_initio ab initio - Wiktionary]
* [https://en.wiktionary.org/wiki/%D8%A8%D8%AF بد - Wiktionary]
* [https://en.wikipedia.org/wiki/Dada Dada from Wikipedia]
* [[Videos#JeanLucPonty|Jean luc Ponty]] - Final Truth (Part 2), [https://en.wikipedia.org/wiki/Montreal_International_Jazz_Festival Montreal Jazz Festival], 1982, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: feat. [http://wiki.killuglyradio.com/wiki/Allan_Zavod Allan Zavod], [https://en.wikipedia.org/wiki/Jamie_Glaser Jamie Glaser], [http://www.drumsoloartist.com/Site/Drummers3/Rayford_Griffin.html Rayford Griffin] and [http://deanguitars.com/keith_jones.php Keith Jones]
: {{#evu:https://www.youtube.com/watch?v=TSLGrDJqaAI|alignment=left|valignment=top}}
=References=
<references />
'''[[Parallel Search|Up one level]]'''
[[FILE:hannah-hoche_da-dandy-1919.jpg|border|right|thumb|link=http://littlemissartypants.tumblr.com/post/12081930289/hannah-h%C3%B6ch-da-dandy-1919-the-photomontage-da|[[Arts#Hoech|Hannah Höch]] - Da Dandy <ref>[[Arts#Hoech|Hannah Höch]] - Da Dandy, 1919, [http://littlemissartypants.tumblr.com/post/12081930289/hannah-h%C3%B6ch-da-dandy-1919-the-photomontage-da Hannah Höch | Da-Dandy (1919)]</ref> ]]
'''ABDADA''', (Alpha-Bêta Distribué avec Droit d'Aînesse = Distributed Alpha-Beta Search with Eldest Son Right)<br/>
a loosely synchronized, [[Parallel Search|distributed search algorithm]] developed by [[Jean-Christophe Weill]]. The ABDADA search algorithm is based on [[Young Brothers Wait Concept]] (YBWC) ([[Rainer Feldmann]] et al. 1986, 1993) <ref>[[Rainer Feldmann]], [[Peter Mysliwietz]], [[Oliver Vornberger]] ('''1986'''). ''A Local Area Network Used as a Parallel Architecture''. Technical Report 31, [[University of Paderborn]]</ref> <ref>[[Rainer Feldmann]] ('''1993'''). ''Game Tree Search on Massively Parallel Systems''. Ph.D. Thesis, [http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/POSTSCRIPTS/feldmann_phd.pdf pdf]</ref> and αβ* ([[Vincent David]] 1993) <ref>[[Vincent David]] ('''1993'''). ''[http://cat.inist.fr/?aModele=afficheN&cpsidt=161774 Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint. Etude et application au Minimax]'' = Parallel algorithm for heuristic tree searching and real-time reasoning. Study and application to the Minimax, Ph.D. Thesis, [https://en.wikipedia.org/wiki/%C3%89cole_nationale_sup%C3%A9rieure_de_l%27a%C3%A9ronautique_et_de_l%27espace École nationale supérieure de l'aéronautique et de l'espace], [https://en.wikipedia.org/wiki/Toulouse Toulouse], [https://en.wikipedia.org/wiki/France France]</ref> . From YBWC it retains the basic concept to allow parallel search only if the eldest son has been fully evaluated. From αβ* as well as [[Steve Otto]] and [[Ed Felten|Ed Felten's]] algorithm (1988) <ref>[[Ed Felten]], [[Steve Otto]] ('''1988'''). ''[http://portal.acm.org/citation.cfm?id=63088 Chess on a Hypercube]''. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications (ed. [http://portal.acm.org/author_page.cfm?id=81100501616&coll=GUIDE&dl=GUIDE&trk=0&CFID=90098691&CFTOKEN=72738297 G. Fox]), pp. 1329-1341</ref> which both rely on a [[Shared Hash Table]] and all processors start the search simultaneously at the [[Root|root]], ABDADA retains the simple [[Recursion|recursive]] control structure similar to a serial algorithm. With the help of additional [[Transposition Table|transposition table]] information, i.e. the number of processors searching this node, it is possible to control [https://en.wikipedia.org/wiki/Speculative_multithreading speculative parallelism].
=Recursion=
<span id="Recursion"></span>While YBWC is difficult to implement recursively, ABDADA is not. In YBWC, when a processor receives an evaluation answer from one of its slaves, it must be able to produce a jump in the search depth if this evaluation produces a pruning of the current master node. So the values of [[Alpha|alpha]] and [[Beta|beta]] must at least be kept in [[Array|arrays]] indexed by [[Ply|ply]] distance from root, and special arrangements must be made to counteract the disruption that might occur from confusing depths. Therefor YBWC needs a hugely modified [[Iterative Search|iterative search]] algorithm. In his paper <ref>[[Jean-Christophe Weill]] ('''1996'''). ''[http://portal.acm.org/citation.cfm?id=228345 The ABDADA Distributed Minimax Search Agorithm]''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped postscript]</ref> , Weill states that using ABDADA within a recursive [[NegaScout]] framework was 30% faster than a none-recursive search, which was observed independently by [[Mark Brockington]] in 1994 <ref>[[Mark Brockington]] ('''1994'''). ''An Implementation of the Young Brothers Wait Concept''. Internal report, [[University of Alberta]]</ref> . It can be explained by the fact that within high-level languages and their compilers for certain target platforms, the use of procedure [[Stack|stacks]] is much more optimized than the use of indexed arrays, also observed by [https://en.wikipedia.org/wiki/Niklaus_Wirth Niklaus Wirth] concerning the [https://en.wikipedia.org/wiki/Quicksort Quicksort] algorithm <ref>[https://en.wikipedia.org/wiki/Niklaus_Wirth Niklaus Wirth] ('''1976'''). ''[https://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs Algorithms + Data Structures = Programs]''. pp 100</ref> .
=Algorithm=
The ABDADA algorithm is described in five steps:
# A TT-Entry has a field ''entry.nproc'' containing the number of processors currently searching the associated node
# All processors start the search simultaneously at the root of the [[Search Tree|search tree]]
# When a processor enters a node, it increments ''entry.nproc''
# When a processor leaves a node, it decrements ''entry.nproc''
# The analysis of a position is done in three phases:
## The eldest son is analyzed, regardless of the activities of other processors
## Next, all other sons not currently being analyzed by other processors are analyzed
## In the final phase, any remaining sons not yet analyzed are searched, i.e. the corresponding entry in the TT indicates this node and its siblings have not been searched to the required depth
=Pseudo Code=
The C-like pseudo code below (adopted from the Pascal like pseudo code from Weill's paper), demonstrates the mentioned three phases controlled by an iteration counter. The boolean parameter ''exclusiveP'' indicates whether the node should be searched exclusively and is passed to the TT-probing code via the procedure ''retrieveAsk''. A new value outside the usual [[Score#ValueRange|value range]] need to be defined (ON_EVALUATION), and ''retrieveAsk'' returns this score if probed in exclusive move, and other processors evaluating this node.
<pre>
int abdada(const CNode &position, int α, int β, int depth, bool exclusiveP) {
if (depth == 0) return evaluate( position );
int best = -oo;
retrieveAsk(position, α, β, depth, exclusiveP);
/* generate moves while waiting for the answer ... */
GenerateMoves(position);
retrieveAnswer(&α, &β, &best);
/* The current move is not searched if causing a cutoff or */
/* in exclusive mode and another processor is currently searching it */
if ( α >= β || best == ON_EVALUATION )
return best; /* entry.nproc not incremented */
bool alldone = false;
for ( int iteration = 0; iteration < 2 && α < β && !alldone; iteration++) {
alldone = true;
Move m = firstMove( position );
while ( (m != 0) && (α < β) ) {
exclusive = (iteration == 0) && !isFirstMove( m );
/* On the first iteration, only one processor should search young sons exclusively */
value = -abdada( position * m, -β, -max(α, best), depth-1, exclusive );
if ( value == -ON_EVALUATION) {
alldone = false;
} else if ( value > best ) {
best = value;
if ( best > β ) goto endsearch;
}
m = nextMove( position );
}
}
endsearch:
storeHash( position, α, β, depth, best );
return best;
}
</pre>
=Implementations=
==Frenchess==
ABDADA was implemented in [[Frenchess]] on a [[Cray T3D]] with 128 [[DEC Alpha|DEC Alpha 21064]] processors. Frenchess participated at the [[WCCC 1995]] finishing fourth, tied with [[Deep Blue|Deep Blue Prototype]] <ref>[[Marc-François Baudot]], [[Jean-Christophe Weill]], [[Jean-Luc Seret]], [[Michel Gondran]] ('''1995'''). ''[https://www.researchgate.net/publication/228386252_Frenchess_A_Cray_T3D_at_the_8th_World_Computer_Chess_Championship Frenchess: A Cray T3D at the 8th World Computer Chess Championship]''. [http://www.recherche.enac.fr/%7Eweill/publications/papier.ps.gz zipped ps]</ref>, as well inside an [[Othello]] program called ''BUGS'' <ref>[[Jean-Christophe Weill]] ('''1996'''). ''[http://portal.acm.org/citation.cfm?id=228345 The ABDADA Distributed Minimax Search Agorithm]''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped postscript]</ref> .
==Smash==
The [[Free Software Foundation#GPL|GPL]] [[Open Source Engines|open source chess engine]] [[Smash]] by [[Maurizio Sambati]] demonstrates an ABDADA implementation in [[Cpp|C++]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=165470&t=18611 Re: interested in making single procesor program multi] by [[Alessandro Scotti]], [[CCC]], December 29, 2007</ref> <ref>[http://www.cli.di.unipi.it/~sambati/prog/smash.tar.bz2 smash.tar.bz2 search.cpp]</ref> .
=See also=
* [[Dynamic Tree Splitting]]
* [[Jamboree]]
* [[Lazy SMP]]
* [[Cilk#ParallelAlphaBeta|Parallel Alpha-Beta]] in [[Cilk]]
* [[Shared Hash Table]]
* [[Young Brothers Wait Concept]]
=Publications=
* [[Jean-Christophe Weill]] ('''1995'''). ''Programmes d'Échecs de Championnat: Architecture Logicielle Synthèse de Fonctions d'Évaluations, Parallélisme de Recherche''. Ph.D. Thesis. Université Paris 8, Saint-Denis, [http://www.recherche.enac.fr/%7Eweill/publications/phdJCW.ps.gz zipped ps] (French)
* [[Marc-François Baudot]], [[Jean-Christophe Weill]], [[Jean-Luc Seret]], [[Michel Gondran]] ('''1995'''). ''[https://www.researchgate.net/publication/228386252_Frenchess_A_Cray_T3D_at_the_8th_World_Computer_Chess_Championship Frenchess: A Cray T3D at the 8th World Computer Chess Championship]''. [http://www.recherche.enac.fr/%7Eweill/publications/papier.ps.gz zipped ps]
* [[Jean-Christophe Weill]] ('''1996'''). ''[http://portal.acm.org/citation.cfm?id=228345 The ABDADA Distributed Minimax Search Agorithm]''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped postscript]
=Forum Posts=
==1997 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/Wl7A-v-gWYQ/QLuvAp0l4_gJ Parallel searching] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], March 22, 1997
: [https://groups.google.com/d/msg/rec.games.chess.computer/Wl7A-v-gWYQ/w-Ky1kkvfeYJ Re:Parallel searching] by [[Mark Brockington]], [[Computer Chess Forums|rgcc]], March 22, 1997
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=112849 tip for "simulating" an MP computer & performance of ABDADA] by [[Tom Kerrigan]], [[CCC]], May 28, 2000
* [https://www.stmintz.com/ccc/index.php?id=112884 A couple of Questions re ABDADA] by [[Steve Maughan]], [[CCC]], May 29, 2000
* [https://www.stmintz.com/ccc/index.php?id=163888 Parallel algorithms in chess programming] by [[Dieter Bürssner|Dieter Buerssner]], [[CCC]], April 16, 2001
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=42986 Parallelization questions, ABDADA or DTS?] by Benjamin Rosseaux, [[CCC]], March 23, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=47887 ABDADA speedup results] by [[Daniel Shawul]], [[CCC]], May 01, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47951 IID and move sorting] by [[Daniel Shawul]], [[CCC]], May 09, 2013 » [[Internal Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=56936 Possible improvement to ABDADA -- checking for cutoffs] by [[Tom Kerrigan]], [[CCC]], July 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56937 Actual speedups from YBWC and ABDADA on 8+ core machines?] by [[Tom Kerrigan]], [[CCC]], July 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=63023 Good parallel speedup with ABDADA and cutoff checks] by [[Tom Kerrigan]], [[CCC]], February 03, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=43 Approximate ABDADA] by [[Peter Österlund]], [[CCC]], August 23, 2017 » [[Lazy SMP#LazyCluster|Lazy SMP - Lazy Cluster]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65011 "How To" guide to parallel-izing an engine] by [[Tom Kerrigan]], [[CCC]], August 27, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65025 "Simplified ABDADA" updated] by [[Tom Kerrigan]], [[CCC]], August 29, 2017
=External Links=
==Algorithm==
* [http://www.tckerrigan.com/Chess/Parallel_Search/Simplified_ABDADA/ Simplified ABDADA] from [http://www.tckerrigan.com/Chess/Parallel_Search/ Parallel Search] by [[Tom Kerrigan]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65011 "How To" guide to parallel-izing an engine] by [[Tom Kerrigan]], [[CCC]], August 27, 2017</ref>
: [http://www.tckerrigan.com/Chess/Parallel_Search/Cutoff_Checks/ Cutoff Checks] from [http://www.tckerrigan.com/Chess/Parallel_Search/ Parallel Search] by [[Tom Kerrigan]]
==Misc==
* [https://en.wikipedia.org/wiki/AB AB from Wikipedia]
* [https://en.wiktionary.org/wiki/ab ab - Wiktionary]
* [https://en.wiktionary.org/wiki/ab_initio ab initio - Wiktionary]
* [https://en.wiktionary.org/wiki/%D8%A8%D8%AF بد - Wiktionary]
* [https://en.wikipedia.org/wiki/Dada Dada from Wikipedia]
* [[Videos#JeanLucPonty|Jean luc Ponty]] - Final Truth (Part 2), [https://en.wikipedia.org/wiki/Montreal_International_Jazz_Festival Montreal Jazz Festival], 1982, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: feat. [http://wiki.killuglyradio.com/wiki/Allan_Zavod Allan Zavod], [https://en.wikipedia.org/wiki/Jamie_Glaser Jamie Glaser], [http://www.drumsoloartist.com/Site/Drummers3/Rayford_Griffin.html Rayford Griffin] and [http://deanguitars.com/keith_jones.php Keith Jones]
: {{#evu:https://www.youtube.com/watch?v=TSLGrDJqaAI|alignment=left|valignment=top}}
=References=
<references />
'''[[Parallel Search|Up one level]]'''
