Computer Chess Club Archives




Subject: Re: MTD is a big win.

Author: Don Dailey

Date: 19:04:42 07/20/99

Go up one level in this thread

On July 20, 1999 at 17:31:44, Dan Homan wrote:

>On July 20, 1999 at 15:19:52, Don Dailey wrote:
>>On July 20, 1999 at 00:45:58, hgkjhg wrote:
>>>Don, is Cilkchess going to be released as a commersial or freeware program some
>>I thought about releasing Occam when it gets good.  But I don't want
>>to see 10000 occams on the chess server or at tournaments!   I may release
>>a version before it gets too strong perhaps just an executable for linux
>>and windows.
>>Probably there will be a parallel version of Occam that will be released
>>with the Cilk distribution as an example with source code.  Cilk is free
>>and so would this be.  But I don't know if I would release a really
>>advanced version.  You will be surprised how simple it is to write a
>>parallel chess program when you see this.
>>- Don
>I was looking over the Cilk Pousse web page and it was pretty clear from
>this how to use Cilk to write a parallel chess program with minimal
>effort, but I had a question:  Do you need to have local data structures
>(position, move list) at each node?  It seemed to me (as I read the
>web page) that you would.  My assumption is that this would create
>substantial overhead that would be a problem for non-parallel versions
>of the program.
>Second question: Can cilk be compiled and used with C++ or does it require
>pure ANSI C?
> - Dan

This is a question everyone asks.  We do it this way because it works
very well and is clean.  But it's not necessary.   In any parallel
program you will have to create separate state in order to perform
your parallelism.  Obviously you cannot have 256 processors updating
the same exact data structure right?   But how you accomplish this
is solely up to you.

In Cilkchess I choose to make it part of the search to simply make
a move by creating a brand new board and search state.  This is
simple and fast.  No one ever believes me when I tell them it's
fast but modern processors do memory block copies very rapidly,
it's just not a problem.  Believe me when I say it's dwarfed by
the other complexities of making a move.  If this is a problem
for you, you can always simply do the end nodes in place like in
a serial chess program and not do the state copy.  But I'm telling
you that this is not necessary.  Even in a serial chess program you
have to carry some state around, for instance all the undo information.
I don't carry any undo information because I don't ever unmake moves,
each position is sitting on the stack.   Also I don't have any other
undo overheads either.

Occam uses the same state copy and update technique all the way through
the quies search.  Occam is my new chess program which is doing over
400,000 nodes per second on a pentium 500 in middlegame positions.
State copy is simply  not expensive.  It makes the whole chess program
a whole lot cleaner too, so it should appeal to meticulous programmers.

If you read the web page about our cilk-pousse program we competed
and beat every other pousse program using these techniques.  Every
cilk program is also a serial program and in private tests against
one of the other top 4 finishers we beat them with our serial version,
which is superfast.

The move list I also put on the stack, declared as an array at the
top of the search function.  If you wanted to, you could easily make
this a list but again,  you have to solve the problem of different
processors accessing the same stack.  It would be a simple matter
to do it differently depending on whether you are compiling the
serial or parallel versions, your move list is a pointer and an
ifdef determines whether to declare it or to point it to the right
place on your global list.

As for your second question, cilk actually requires gcc right now.
It uses special features of gcc so you have no other options.  You
can link in from other compilers as long as you do the searh part
in gcc.   We are looking at making cilk more compiler portable but
this is a way off.  Sorry.  But there is nothing wrong with Gcc,
there are some great versions with strong pentium optimizations
that are as good as any compiler (please no holy wars over this)
as far as performance.

- Don

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