Simplified ABDADA - Tom Kerrigan's Home Page

Tom Kerrigan's Home Page

Simplified AB...

Simplified ABDADA

ABDADA is a self-synchronizing version of the Young Brothers Wait Concept algorithm for doing parallel alpha-beta searches.

Here's a summary:

ABDADA

Each thread searches the entire tree as if it was doing a single-threaded search.
When a thread visits a position, it searches the first move no matter what.
Before searching each subsequent move, it checks to see if another thread is already searching that move.
If so, the move is reordered so it's searched last.
(I call this a deferred move.)

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.)

Files

simplified_abdada.html

Pseudocode for Simplified ABDADA, with implementation notes