Computer Chess Club Archives




Subject: Re: MTD(f) (was Re: New(?) search idea.)

Author: Robert Hyatt

Date: 06:28:05 01/26/98

Go up one level in this thread

On January 26, 1998 at 07:05:23, Rickard Björklund wrote:

>On January 24, 1998 at 17:12:48, Don Dailey wrote:
>>The parallel algorithm is extremely simple, and completely recursive.
>>So parallelism can happen anywhere.  The cilk language was designed
>>around chess  and huge effort went into it to make it extremely
>>efficient and powerful at the same time.   The scheduling algorithm
>>is automatic and makes good decisions.  When a processor steals work
>>from another processor it steals the oldest work that was posted so
>>most of the "sharing" will get done near the root of the tree.
>>A lot of our parallel searches look at LESS nodes than a serial
>>search.  This can happen because if
>>you are looking at a bunch of sibling moves in parallel one may
>>just happen to give you a very fast cutoff (like a mate sequence)
>>and return quickly where the serial program may not get to that
>>move for a while.   In general of course any parallel program tends
>>to do more work on the average.   There are things we do to try to
>>avoid extra work, if we think a cutoff will happen we do not try
>>to search siblings in parallel, but wait for the result of the search.
>>I usually quote numbers like 20% more work than a serial job but in
>>fact this is nonsense.  The work climbs very gradually with number
>>of processors and drops with depth of search.   If we had 1 billion
>>processors we would have to search for a long time to get the full
>>Our program does not play speed chess well with a lot of slow processors
>>One intersting phenomemon we had with our 1800 processor Socrates
>>program is that the iteration times looked linear!  It took a second
>>per iteration until we were over 10 or something.  The branching
>>factor was so low.  But this was because the deeper we went, the
>>more parallelism we got.  Obviously, you cannot use 1836 processors
>>to efficiently do a 1 ply search!   It's like getting 1000 people
>>together to mow a small yard or garden!
>This concerns my initial question. Can't these searches be done be
>dividing the window among the processors. I know this has been done
>for the usual alphabeta search and that it's not efficient when using
>many processors. I think parallel window splitting is useful when
>you do a shallow search. I'm thinking of using the window split for the
>first plies in the iterative deepening and then resort to something YBW

this has already been done.  Baudet tried this approach at least 20
ago.  It was found to limit the speedup to around 5X, which is far worse
than splitting the tree itself into smaller slices that can be searched
in parallel.  In fact, if your initial "guess" of the score is dead on,
searching different "windows" in parallel would get you *no* speedup at

>>Most of this stuff is a bookkeeping nightmare.  But with Cilk they
>>are very high level commands and the language keeps up with all the
>>detail.   You can still control a lot of the details if you want
>>to and I have experiemented a lot with various scheduling algorithms
>>but this simple one get's almost all the benefit.
>>- Don
>I'm a writing a parallel chess program myself (right now, I'm
>all global variables in structs), but I'm the message-passing kind of
>guy, so
>I don't know much about Cilk. Does Cilk run on lously coupled system ?
>Does it
>require shared memory ? Is it portable ?
>Is the scheduler written as a part of the chess program or is it a part
>of Cilk ?

This page took 0.09 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.