Computer Chess Club Archives


Search

Terms

Messages

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

Author: Don Dailey

Date: 14:12:48 01/24/98

Go up one level in this thread


Hi Rickard,

MTD(f) is identical on the serial, parallel with 1 processor or
parallel with more than 1, the implementation has nothing to do
with parallelism although I'm sure it interacts.    A 1 processor
parallel search is about 5% slower but searches the exact same tree
(right to the node) as a serial search.

MTD(f) in a nutshell:  Essentially MTD(f) is a sequence of zero width
window probes done to the whole search.   Many searches return extremely
quickly because most of tree is already known to the search (via the
hash table.)   Each search gains more information about the true score
but
a search is never returned that does not fail either high or low.

The way you determine the "goal" of each probe  determines what type
of search it is.  Essentially it's best to do your test searches with
scores as close to the correct score as possible.  That's why a binary
search of this space is a poor attempt.   I have my own driver that's
based on MTD(f) but with my own enhancements.

I am discouraging most people from using MTD(f).  Look at the posts
on the problems with it.   I hate MTD(f) and there is only 1 reason
I am forced to keep it in my program, its far better than nega-scout
in terms of speed.  I never thought anything would ever prove to be
significantly better than nega-scout but at least for me it was.
As I discussed with Bob and others,  my program may be one of the
few that can benefit from it,  it's benefit is very much tied to the
kind of program you have and all the ugly hacks you use in the name
of speed!

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
benefit.
Our program does not play speed chess well with a lot of slow processors
etc.
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!

Move ordering may be even more important for a parallel program than
for a serial program for this reason.  One algorithm we use is to
always search the first move at any node and get back a result before
we search the rest in parallel.  This is a big benefit for us.  The
processors are not wasted because the algorithm is recursive and
all the processors will quickly get activated further up the tree.

  score = search the first_move;
  if cutoff then return
  search rest of moves at same time.
  if any one of these is a cutoff then abort all work in progress

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





On January 24, 1998 at 02:29:19, Rickard Björklund wrote:

>On January 22, 1998 at 21:59:57, Don Dailey wrote:
>
>>
>>I have problems with PV's.  In Cilkchess 1, I implemented MTD(f) and
>>Aske Plaat improved the driver (I was doing it wrong and still getting
>>a small speedup over PVS.)
>
>In Cilkchess, how is MTD(f) used when running on a parallel machine ?
>
>Is the root searched with different windows in order to cut down the
>number
>of re-searches or is parallelism used at interior nodes ?
>
>/Rickard



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.