Page 1 of 1
YBWC details
Posted: Thu Dec 31, 2009 3:43 am
by 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
Re: YBWC details
Posted: Thu Dec 31, 2009 7:13 am
by Ferdy
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
Re: YBWC details
Posted: Thu Dec 31, 2009 4:58 pm
by 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/
Re: YBWC details
Posted: Thu Dec 31, 2009 6:12 pm
by Tord Romstad
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
Re: YBWC details
Posted: Thu Dec 31, 2009 9:58 pm
by bob
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.
Re: YBWC details
Posted: Thu Dec 31, 2009 10:00 pm
by bob
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,
Re: YBWC details
Posted: Fri Jan 01, 2010 2:29 am
by nthom
Thanks, this looks good to me.
Re: YBWC details
Posted: Fri Jan 01, 2010 2:32 am
by nthom
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
Re: YBWC details
Posted: Fri Jan 01, 2010 6:30 pm
by bob
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.