Computer Chess Club Archives




Subject: Parallel search algorithms

Author: Scott Gasch

Date: 23:54:34 08/29/01


I've been reading about parallel search algorithms.  So far the only practical
ones I have run across are ABDADA and Youngest Brother Wait.  Others like APHID
and tree-splitting seem designed for distributed operation or operation with
more processors than I'm likely to use.

My first question is this: am I missing any important algorithm?  I'd like to
make sure I at least read an overview of the important ones before trying to
implement something.

What I have read leads me to conclude that ABDADA offers a good speedup with
fairly minor codebase changes.  Below is my understanding of the algorithm.  I
think I have an ok feel for what is happening but I would really appreciate
clarification.. I do not have a firm grip on this yet:

1. A count of "number of processors under this node" is maintained in the hash
table entry for each node.

2. Every node is searched with an extra flag: exclusive.  The recursive call to
search the subtree under the first move tried in a position is passed exclusive
as true.  All subsequent recursive calls (for moves 2..N) are passed exclusive
as false.

3. When the hash table is probed, the exclusive flag is passed in.  If a hash
cutoff is possible, it is returned no matter what.  If no cutoff is possible and
exclusive is true and there is another processor already under this node, return
"on evaluation" -- a special value.  Otherwise increment the numproc for this
node and return hash miss.

4. While searching save any moves that return the "on evaluation" value and go
on.  Having looped through all possible moves (1..N) once without a fail high,
retry any move that returned "on evaluation".  Repeat until all moves return a
real score.  This should be cheap because we hope the other processor(s) under
these moves have finished by now and it should simply be a matter of making the
move, making a recursive call, and getting a hash cutoff[?].

5. When exiting a node, in addition to storing its information in the hash table
also decrement numproc under the node.

6. Each thread (one for each cpu) starts at the root (with exclusive = false)
and searches the tree in parallel.  When the search terminates all threads
should return the same value.  Only one thread should change the PV structure.

This makes me wish i didn't have so many tricks in my search routine -- extended
transposition cutoff like tries to avoid avoiding a null move... don't store
stuff in the hash table if a lot of extended pruning was done at this node,
etc... In short this is going to be a mess to implement even when I do fully
understand it.

Thanks for any explaination / advice.

This page took 0.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.