Dual core musings

[GeoffW]

Hi

Having just put together my first dual core PC, I am well impressed by the performance for the cost (My new £50 E2140 C2D is smoking my 3.4 GHz £180 P4 ) Now i have the PC to do the job I thought I would start reading up on some multithreaded Chess program techniques. Surprisingly I found it really difficult to find some simple introductory articles on YBWC for example. Its a rather catchy title but I have no idea what it means.

Any links to good articles would be appreciated. Preferably not too academic and not *.ps format as that is fiddly to read. Thanks.

Regards Geoff

[jswaff]

Ok, this is an academic paper, but it's really very good and not hard to read.

http://valavan.net/mthesis.pdf

Skip ahead to page 25 for the YBWC section, or page 27 for DTS.

Tord Romstad's "Viper" is a nice program designed to illustrate YBWC.
http://www.glaurungchess.com/viper/

Crafty is another example, although more complex.

--
James

[Dan Andersson]

If you want to get the concept from the horses mouth then:
http://wwwcs.uni-paderborn.de/fachberei ... ation.html
In lieu of converting Postscript yourself you could go to citeseer and find them already converted to PDF. For example:
http://citeseer.ist.psu.edu/feldmann94studying.html
Reading the citations and similar documents section will yield a lot of other sources. Citeseer is a treasure trove of knowledge. Like arxiv but for older fact checked and peer reviewed papers.

MvH Dan Andersson

[GeoffW]

Thanks for the links guys.

As a regular reader here I know about a fair few of the Engines with Src available like Crafty and Viper, but the chance of me every learning how the threading code works from just reading source is less than nil. I first really need to understand the principles of how the alpha beta search is split across threads.

Although an academic paper the http://valavan.net/mthesis.pdf document looks very nicely written and easy to understand, at least as far as I have read up to now.

Trying to make a multi-core capable Chess engine is quite a daunting prospect however. It does seem to require a high level of programming ability, not to mention chess knowledge and no small measure of hard work and tenacity.

I would be interested to hear of any author's experience in trying to come up with an SMP chess program. Was it easier or more difficult than you had originally anticipated ? Did you start from an existing non threaded version ? How impossible was debugging ? How did you cope with all those nasty globals you knew you shouldnt have used in the first place ? etc, etc .

Regards Geoff

[Tord Romstad]

Ok, this is an academic paper, but it's really very good and not hard to read.

http://valavan.net/mthesis.pdf

Seconded. Valavan's thesis is the best place to start.

Tord Romstad's "Viper" is a nice program designed to illustrate YBWC.
http://www.glaurungchess.com/viper/

Viper is in bad need of an update. It is too big and too complex, and poorly commented. There are also many things I dislike about the programming style. I wish I had time to clean up the mess, but I'm afraid I have too much else to do right now...

Tord

[Tord Romstad]

Trying to make a multi-core capable Chess engine is quite a daunting prospect however.

It isn't as bad as you think.

It does seem to require a high level of programming ability,

I don't think it does, at least as long as a decent speedup on 2-4 CPUs is good enough for you. My programming abilities in C/C++ are abysmal, but adapting my engine to dual-core CPUs wasn't all that difficult.

Of course, if you want to write the most efficient parallel search in the world, and/or write a parallel search which works well even on a very big number of CPUs, you will need a very high level of programming ability.

not to mention chess knowledge

It requires hardly any chess knowledge at all. The techniques used are completely game-independent. Implementing parallel search in chess does not differ much from implementing parallel search in games like checkers or othello.

and no small measure of hard work and tenacity.

I don't think it requires so much hard work and tenacity: It's more a matter of mental dicipline. You probably can't expect to be able to just start writing the code and hack away happily until it works. It is necessary to understand the problem well and design a reasonably comlete solution on paper before writing the actual code. Unlike the other parts of a chess program, parallel search cannot easily be broken down into small and independent pieces of code which can be tested in isolation.

I would be interested to hear of any author's experience in trying to come up with an SMP chess program. Was it easier or more difficult than you had originally anticipated ?

Implementing my first dual-threaded search was much easier than anticipated. Going from two to four threads was somewhat harder than anticipated. I expected the second problem to be much easier than the first, but I think I ended up spending a similar amount of work on both problems.

Did you start from an existing non threaded version ?

Yes.

How impossible was debugging ?

I usually don't debug C/C++ code at all. If it doesn't work as intended, and it is not immediately obvious why it doesn't work, the code is too messy and complicated, and needs to be simplified or completely rewritten.

How did you cope with all those nasty globals you knew you shouldnt have used in the first place ?

This usually isn't a big problem in practise. Most of the global variables in a chess program are what I call "pseudo-constants": Big arrays which are computed during program initialization (or before the start of a new search from the root), and which stay constant during the search. Such global data does not cause problems in a multithreaded program.

If you have a global board (as I did), you have some work to do, but although it is tedious and time-consuming, it is not technically difficult. Just pass a board as a parameter to the search, evaluation, and related functions, and modify the relevant parts of the code to use this parameter instead of the global board.

Good luck! Parallel search is great fun.

Tord