YBWC details

[nthom]

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]

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]

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]

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]

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]

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,

[nthom]

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.

[nthom]

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]

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.