YBWC details

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
nthom
Posts: 112
Joined: Thu Mar 09, 2006 5:15 am
Location: Australia
Contact:

YBWC details

Post by nthom » Thu Dec 31, 2009 2:43 am

I've gutted the horrible PVSplit implementation I had in LittleThought and want to put YBWC in its place. However, I'm having problems trying to find a decent description of the algorithm. I've founds bits and pieces but not really enough for me to get my head around all the little intricacies I run into when I try to design something.

Can someone please provide links to some good doco on it? I'm not interested in sample source code as that tends to confuse me more than help :)

Ferdy
Posts: 4110
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: YBWC details

Post by Ferdy » Thu Dec 31, 2009 6:13 am

nthom wrote:I've gutted the horrible PVSplit implementation I had in LittleThought and want to put YBWC in its place. However, I'm having problems trying to find a decent description of the algorithm. I've founds bits and pieces but not really enough for me to get my head around all the little intricacies I run into when I try to design something.

Can someone please provide links to some good doco on it? I'm not interested in sample source code as that tends to confuse me more than help :)

From Ed's site, check link below, chapter 3, might be helpful.

Code: Select all

http://www.top-5000.nl/ps/Parallel%20Alpha-Beta%20Search%20on%20Shared%20Memory%20Multiprocessors.pdf

jdart
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: YBWC details

Post by jdart » Thu Dec 31, 2009 3:58 pm

The canonical work on this was done by Rainer Feldmann in the early 1990s. His Ph.D. thesis at U. Paderborn is available, as are several publications.

See http://www2.cs.uni-paderborn.de/cs/ag-m ... tions.html/

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: YBWC details

Post by Tord Romstad » Thu Dec 31, 2009 5:12 pm

jdart wrote:The canonical work on this was done by Rainer Feldmann in the early 1990s. His Ph.D. thesis at U. Paderborn is available, as are several publications.

See http://www2.cs.uni-paderborn.de/cs/ag-m ... tions.html/
Canonical, perhaps -- but as is often the case, papers which are written a few years later, when the community has had some time to digest the ideas, are more readable. The historical importance of Feldmann's thesis is undeniable, but it is no longer the easiest place for a beginner to start learning.

My recommendation would be to read chapter 3 in Valavan Manohararajah's thesis:

http://www.valavan.net/mthesis.pdf

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: YBWC details

Post by bob » Thu Dec 31, 2009 8:58 pm

nthom wrote:I've gutted the horrible PVSplit implementation I had in LittleThought and want to put YBWC in its place. However, I'm having problems trying to find a decent description of the algorithm. I've founds bits and pieces but not really enough for me to get my head around all the little intricacies I run into when I try to design something.

Can someone please provide links to some good doco on it? I'm not interested in sample source code as that tends to confuse me more than help :)
It is simple. You will do a parallel split when the following conditions have been satisfied:

(1) you have searched at _least_ one move at this ply completely, and I do mean "searched". Making/Unmaking an illegal move does not count;

(2) you have at least one idle thread/processor to use.

It is a _very_ simple algorithm that is significantly better than PVsplit, because this can split anywhere, not just along PV nodes. And implemented properly, you never have a thread/cpu waiting, they are always jumping in to help whenever the YBW conditions described above are satisfied at any node.

The only issue is how do you split. In a recursive search, you can only split at the current ply, which means this ply must have satisfied the YB conditions above or you can't do a split, yet. If you use a non-recursive implementation, such as the pure iterative approach used in Cray Blitz, then whenever a processor goes idle, you can split at _any_ node where you can find that the YBW condition has been satisfied, which gives you a better chance to choose a better split point, rather than just being able to split at the current node in the tree.

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: YBWC details

Post by bob » Thu Dec 31, 2009 9:00 pm

jdart wrote:The canonical work on this was done by Rainer Feldmann in the early 1990s. His Ph.D. thesis at U. Paderborn is available, as are several publications.

See http://www2.cs.uni-paderborn.de/cs/ag-m ... tions.html/
The _name_ was coined by Feldman, the idea was in use long before that. My PhD dissertatoin was published in 1988, based on the same underlying principle used in YBW,

User avatar
nthom
Posts: 112
Joined: Thu Mar 09, 2006 5:15 am
Location: Australia
Contact:

Re: YBWC details

Post by nthom » Fri Jan 01, 2010 1:29 am

jdart wrote:The canonical work on this was done by Rainer Feldmann in the early 1990s. His Ph.D. thesis at U. Paderborn is available, as are several publications.

See http://www2.cs.uni-paderborn.de/cs/ag-m ... tions.html/
Thanks, this looks good to me.

User avatar
nthom
Posts: 112
Joined: Thu Mar 09, 2006 5:15 am
Location: Australia
Contact:

Re: YBWC details

Post by nthom » Fri Jan 01, 2010 1:32 am

bob wrote:
nthom wrote:I've gutted the horrible PVSplit implementation I had in LittleThought and want to put YBWC in its place. However, I'm having problems trying to find a decent description of the algorithm. I've founds bits and pieces but not really enough for me to get my head around all the little intricacies I run into when I try to design something.

Can someone please provide links to some good doco on it? I'm not interested in sample source code as that tends to confuse me more than help :)
It is simple. You will do a parallel split when the following conditions have been satisfied:

(1) you have searched at _least_ one move at this ply completely, and I do mean "searched". Making/Unmaking an illegal move does not count;

(2) you have at least one idle thread/processor to use.

It is a _very_ simple algorithm that is significantly better than PVsplit, because this can split anywhere, not just along PV nodes. And implemented properly, you never have a thread/cpu waiting, they are always jumping in to help whenever the YBW conditions described above are satisfied at any node.

The only issue is how do you split. In a recursive search, you can only split at the current ply, which means this ply must have satisfied the YB conditions above or you can't do a split, yet. If you use a non-recursive implementation, such as the pure iterative approach used in Cray Blitz, then whenever a processor goes idle, you can split at _any_ node where you can find that the YBW condition has been satisfied, which gives you a better chance to choose a better split point, rather than just being able to split at the current node in the tree.
And you make it sound very simple, which makes me feel very stupid for struggling with these concepts :)

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: YBWC details

Post by bob » Fri Jan 01, 2010 5:30 pm

nthom wrote:
bob wrote:
nthom wrote:I've gutted the horrible PVSplit implementation I had in LittleThought and want to put YBWC in its place. However, I'm having problems trying to find a decent description of the algorithm. I've founds bits and pieces but not really enough for me to get my head around all the little intricacies I run into when I try to design something.

Can someone please provide links to some good doco on it? I'm not interested in sample source code as that tends to confuse me more than help :)
It is simple. You will do a parallel split when the following conditions have been satisfied:

(1) you have searched at _least_ one move at this ply completely, and I do mean "searched". Making/Unmaking an illegal move does not count;

(2) you have at least one idle thread/processor to use.

It is a _very_ simple algorithm that is significantly better than PVsplit, because this can split anywhere, not just along PV nodes. And implemented properly, you never have a thread/cpu waiting, they are always jumping in to help whenever the YBW conditions described above are satisfied at any node.

The only issue is how do you split. In a recursive search, you can only split at the current ply, which means this ply must have satisfied the YB conditions above or you can't do a split, yet. If you use a non-recursive implementation, such as the pure iterative approach used in Cray Blitz, then whenever a processor goes idle, you can split at _any_ node where you can find that the YBW condition has been satisfied, which gives you a better chance to choose a better split point, rather than just being able to split at the current node in the tree.
And you make it sound very simple, which makes me feel very stupid for struggling with these concepts :)
The _idea_ is about as simple as it gets, in the world of parallel programming. however, the devil is in the details of the data structures to make this work in a really unsynchronized way to produce good performance.

Post Reply