ABDADA, (Alpha-Bêta Distribué avec Droit d'Aînesse = Distributed Alpha-Beta Search with Eldest Son Right)
a loosely synchronized, 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) ^{[1]}^{[2]} and αβ* (Vincent David 1993) ^{[3]} . 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's algorithm (1988) ^{[4]} which both rely on a Shared Hash Table and all processors start the search simultaneously at the root, ABDADA retains the simple recursive control structure similar to a serial algorithm. With the help of additional transposition table information, i.e. the number of processors searching this node, it is possible to control speculative parallelism.

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 and beta must at least be kept in arrays indexed by 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 algorithm. In his paper ^{[6]} , 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 ^{[7]} . It can be explained by the fact that within high-level languages and their compilers for certain target platforms, the use of procedure stacks is much more optimized than the use of indexed arrays, also observed by Niklaus Wirth concerning the Quicksort algorithm ^{[8]} .

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

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 value range need to be defined (ON_EVALUATION), and retrieveAsk returns this score if probed in exclusive move, and other processors evaluating this node.

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;}elseif( value > best ){
best = value;if( best > β )goto endsearch;}
m = nextMove( position );}}
endsearch:
storeHash( position, α, β, depth, best );return best;}

Home * Search * Parallel Search * ABDADAABDADA, (Alpha-Bêta Distribué avec Droit d'Aînesse = Distributed Alpha-Beta Search with Eldest Son Right)a loosely synchronized, 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)

^{[1]}^{[2]}and αβ* (Vincent David 1993)^{[3]}. 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's algorithm (1988)^{[4]}which both rely on a Shared Hash Table and all processors start the search simultaneously at the root, ABDADA retains the simple recursive control structure similar to a serial algorithm. With the help of additional transposition table information, i.e. the number of processors searching this node, it is possible to control speculative parallelism.^{[5]}## Table of Contents

## Recursion

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 and beta must at least be kept in arrays indexed by 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 algorithm. In his paper^{[6]}, 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^{[7]}. It can be explained by the fact that within high-level languages and their compilers for certain target platforms, the use of procedure stacks is much more optimized than the use of indexed arrays, also observed by Niklaus Wirth concerning the Quicksort algorithm^{[8]}.## Algorithm

The ABDADA algorithm is described in five steps:entry.nproccontaining the number of processors currently searching the associated nodeentry.nprocentry.nproc## 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 parameterexclusivePindicates whether the node should be searched exclusively and is passed to the TT-probing code via the procedureretrieveAsk. A new value outside the usual value range need to be defined (ON_EVALUATION), andretrieveAskreturns this score if probed in exclusive move, and other processors evaluating this node.## Implementations

## Frenchess

ABDADA was implemented in Frenchess on a Cray T3D with 128 DEC Alpha 21064 processors. Frenchess participated at the WCCC 1995 finishing fourth, tied with Deep Blue Prototype^{[9]}, as well inside an Othello program calledBUGS^{[10]}.## Smash

The GPL open source chess engine Smash by Maurizio Sambati demonstrates an ABDADA implementation in C++^{[11]}^{[12]}.## See also

## Publications

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, zipped ps (French)1995).Frenchess: A Cray T3D at the 8th World Computer Chess Championship. zipped ps1996).The ABDADA Distributed Minimax Search Agorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal, Vol. 19, No. 1, zipped postscript## Forum Posts

## 1997 ...

Re:Parallel searching by Mark Brockington, rgcc, March 22, 1997

## 2000 ...

## 2010 ...

## External Links

## Algorithm

^{[13]}Cutoff Checks from Parallel Search by Tom Kerrigan

## Misc

feat. Allan Zavod, Jamie Glaser, Rayford Griffin and Keith Jones

## References

1986).A Local Area Network Used as a Parallel Architecture. Technical Report 31, University of Paderborn1993).Game Tree Search on Massively Parallel Systems. Ph.D. Thesis, pdf1993).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, École nationale supérieure de l'aéronautique et de l'espace, Toulouse, France1988).Chess on a Hypercube. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications (ed. G. Fox), pp. 1329-13411996).The ABDADA Distributed Minimax Search Agorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal, Vol. 19, No. 1, zipped postscript1994).An Implementation of the Young Brothers Wait Concept. Internal report, University of Alberta1976).Algorithms + Data Structures = Programs. pp 1001995).Frenchess: A Cray T3D at the 8th World Computer Chess Championship. zipped ps1996).The ABDADA Distributed Minimax Search Agorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal, Vol. 19, No. 1, zipped postscript## What links here?

Up one level