|Tom Kerrigan's Home Page|
ABDADA is a self-synchronizing version of the Young Brothers Wait Concept algorithm for doing parallel alpha-beta searches.
Here's a summary:
The idea is that, by the time a thread returns to a deferred move, another thread has already finished searching the move and wrote the result to the hash table. Searching it again results in a hash table hit and no duplicated effort. (And if the move isn't done yet, the thread recurses and helps finish the search.)
When implementing ABDADA, the hard part is checking to see if another thread is already searching a move. There's a simple, straightforward way to do this: maintain a hash table of the moves that are currently being searched. I call this idea "Simplified ABDADA." Here's the pseudocode, with implementation notes:
Pseudocode for Simplified ABDADA
If you decide to use Simplified ABDADA, I would appreciate an e-mail!
Compared to "regular" ABDADA
The original implementation of ABDADA (from Jean-Christophe Weill's paper) was designed to minimize the number of accesses to shared memory, so it folded the "is this move being searched?" check into the code that probed the shared transposition table. This is fine, but more complicated.
Simplified ABDADA also makes it easy to do a novel optimization: if a move fails a null-window search, it's removed from the hash table of moves that are currently being searched. This makes it more likely that other threads will search the move sooner. (Note 5.2 in the pseudocode.)