Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD is a big win.

Author: Dave Gomboc

Date: 19:51:22 07/20/99

Go up one level in this thread


On July 20, 1999 at 22:04:42, Don Dailey wrote:

>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
>>>>time?
>>>
>>>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
>>
>>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

I've tried using Cilk, I think it's pretty good.  I wish it would work with g++
though.

Dave



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