1. Does split at root nodes bad? If I search the first root moves, and then splits the remaining root moves to run in parallel, what is the disadvantage of this?
2. Do we split in PV and nonPV nodes?
3. Normally, it is allowed to split after probing the hash AND searching the first move after hashmove. Is it better to split after good captures, or even after killers? i.e. only split in the phase of non-capture and losing capture.
Some questions on split points
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Some questions on split points
1. Splitting at the root is a great idea. So long as that is not where you START splitting. For example, if you do a 20 ply search, you might start at 16, then back up to 15, then 14, ... all the way back to 1. The young-brothers-wait (YBW) idea is that you want to search one move at any node before you search others in parallel, to convince yourself this is an ALL node and not a CUT node.edwardyu wrote:1. Does split at root nodes bad? If I search the first root moves, and then splits the remaining root moves to run in parallel, what is the disadvantage of this?
2. Do we split in PV and nonPV nodes?
3. Normally, it is allowed to split after probing the hash AND searching the first move after hashmove. Is it better to split after good captures, or even after killers? i.e. only split in the phase of non-capture and losing capture.
2. I split EVERYWHERE. Just so I satisfy the YBW criterion and have searched at least one node completely before starting a split.
3. See (2). The longer you wait, the safer the split is, as the more moves you search without failing high, the less likely it becomes that you will fail high. But while you are waiting, your extra processors are idle, and performance drops off. Faster than the gain from being more sure about the split point being correct.
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: Some questions on split points
Stockfish gained around +10 elo on 4 CPU when we started splitting at root. Do it if you can.edwardyu wrote:1. Does split at root nodes bad? If I search the first root moves, and then splits the remaining root moves to run in parallel, what is the disadvantage of this?
Sure. But it's good a idea to split immediately after the first move is searched (YBW) which means that most of the time there will be only a single split point in PV node (assuming number of threads <= 8).2. Do we split in PV and nonPV nodes?
I think at least not far from optimal recipe is always split() immediately when you can and use YBW. There exists slightly better recipes than YBW, but it's a lot of trouble (and crashes) for very little gain.3. Normally, it is allowed to split after probing the hash AND searching the first move after hashmove. Is it better to split after good captures, or even after killers? i.e. only split in the phase of non-capture and losing capture.
DISCLAIMER: Feel free to disagree, just personal opinions. I do not have data to backup these claims.
Joona Kiiski
-
- Posts: 2056
- Joined: Mon Mar 13, 2006 2:31 am
- Location: North Carolina, USA
Re: Some questions on split points
The reasons for not splitting at the root are quite theoretical and dependent on you method of load balancing the processors.
If you are using a manager/worker implementation with the manager doing all the splitting (handing out work), then this could be inefficient when one of the root nodes is still running and all the other processors are finished. If you used a more peer-to-peer request system, then this is not a problem. So, there are some implementation dependencies on which may be best.
Always split when YBW says. So, the second node and later. I've seen research on heuristics for splitting at the first node, but results weren't clearly positive.
If you are using a manager/worker implementation with the manager doing all the splitting (handing out work), then this could be inefficient when one of the root nodes is still running and all the other processors are finished. If you used a more peer-to-peer request system, then this is not a problem. So, there are some implementation dependencies on which may be best.
Always split when YBW says. So, the second node and later. I've seen research on heuristics for splitting at the first node, but results weren't clearly positive.
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Some questions on split points
Let's first note that obeying the YBW rule of splitting is a great idea removing most problems.edwardyu wrote:1. Does split at root nodes bad? If I search the first root moves, and then splits the remaining root moves to run in parallel, what is the disadvantage of this?
In many positions engines doubt, so odds for a fail high in root is much higher than in any other sort of position. So in Diep i don't split in root.
There is a psychological question about splitting in root. I sort the moves in the root well. So odds the 2nd move fails is bigger than that move 30 gives.
The real psychological question is whether you want from your 16 cores or so have 15 search nonsense moves and just 1 being busy to figure out if a fail high is possible, you ARE gonna time out. Throwing 16 cores at that 2nd move might give you a crucial fail high just before time out.
You really don't want to split there.
This might be less of a problem with todays beancounters that just check the mainline deep and basically prune the rest. Question there is usually whether your cpu has much of a time searching other moves than first move of the root, as they need like a few milloin nodes in total to cut the remaining moves.
The root position is a special case of a PV position.
With todays search depths and mainline checking it might be less dangerous splitting in root than it was in the past.
Obviously.2. Do we split in PV and nonPV nodes?
In Diep indeed i do something like that. If a node seems initially like a cutnode i don't split in parallel already the 2nd move etc. I wait until 3d move or don't split at all there.3. Normally, it is allowed to split after probing the hash AND searching the first move after hashmove. Is it better to split after good captures, or even after killers? i.e. only split in the phase of non-capture and losing capture.
This split decision depends however largely upon the number of cores you throw into battle. The game changes above 8 cores. Around 16 cores and upwards you can no longer afford the luxury of not splitting after the first move.
With 500 processors or so i used to already split after nullmove AND having indication it might be an all node here.
Don't forget that before the first move there is a nullmove. So in fact you always split already after the 2nd move, not so much first move in case of YBW as a minimum.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Some questions on split points
You can do both. You can certainly split at the root, and when you run out of root moves and have processors idle, they can still join in and help the thread working on that last root move.CRoberson wrote:The reasons for not splitting at the root are quite theoretical and dependent on you method of load balancing the processors.
If you are using a manager/worker implementation with the manager doing all the splitting (handing out work), then this could be inefficient when one of the root nodes is still running and all the other processors are finished. If you used a more peer-to-peer request system, then this is not a problem. So, there are some implementation dependencies on which may be best.
Always split when YBW says. So, the second node and later. I've seen research on heuristics for splitting at the first node, but results weren't clearly positive.
The advantage is search overhead. The root is the ONLY position in the tree that you can guarantee every move has to be searched, period. Splitting there offers no overhead at all, once the first move is found to establish alpha.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Some questions on split points
Crafty has always had an adaptive split-at-root algorithm. I can look at the node counts from the previous iteration, and pretty accurately determine if any of those moves have a chance of failing high. If so, I will search each of those, serially, using all processors on each move, until I exhaust the group that appear to have a chance of failing high. I then split the rest at the root and get it done in a hurry. This is not hard to do at all.diep wrote:Let's first note that obeying the YBW rule of splitting is a great idea removing most problems.edwardyu wrote:1. Does split at root nodes bad? If I search the first root moves, and then splits the remaining root moves to run in parallel, what is the disadvantage of this?
In many positions engines doubt, so odds for a fail high in root is much higher than in any other sort of position. So in Diep i don't split in root.
There is a psychological question about splitting in root. I sort the moves in the root well. So odds the 2nd move fails is bigger than that move 30 gives.
The real psychological question is whether you want from your 16 cores or so have 15 search nonsense moves and just 1 being busy to figure out if a fail high is possible, you ARE gonna time out. Throwing 16 cores at that 2nd move might give you a crucial fail high just before time out.
You really don't want to split there.
This might be less of a problem with todays beancounters that just check the mainline deep and basically prune the rest. Question there is usually whether your cpu has much of a time searching other moves than first move of the root, as they need like a few milloin nodes in total to cut the remaining moves.
The root position is a special case of a PV position.
With todays search depths and mainline checking it might be less dangerous splitting in root than it was in the past.
Obviously.2. Do we split in PV and nonPV nodes?
In Diep indeed i do something like that. If a node seems initially like a cutnode i don't split in parallel already the 2nd move etc. I wait until 3d move or don't split at all there.3. Normally, it is allowed to split after probing the hash AND searching the first move after hashmove. Is it better to split after good captures, or even after killers? i.e. only split in the phase of non-capture and losing capture.
This split decision depends however largely upon the number of cores you throw into battle. The game changes above 8 cores. Around 16 cores and upwards you can no longer afford the luxury of not splitting after the first move.
With 500 processors or so i used to already split after nullmove AND having indication it might be an all node here.
Don't forget that before the first move there is a nullmove. So in fact you always split already after the 2nd move, not so much first move in case of YBW as a minimum.
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: Some questions on split points
YBW+helpful master concept (which I assume is the standard way nowadays to do multiprocessing in computer chess) is solution to this (as Bob already said)CRoberson wrote:The reasons for not splitting at the root are quite theoretical and dependent on you method of load balancing the processors.
If you are using a manager/worker implementation with the manager doing all the splitting (handing out work), then this could be inefficient when one of the root nodes is still running and all the other processors are finished. If you used a more peer-to-peer request system, then this is not a problem. So, there are some implementation dependencies on which may be best.
Always split when YBW says. So, the second node and later. I've seen research on heuristics for splitting at the first node, but results weren't clearly positive.
Joona Kiiski
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: Some questions on split points
Exactly. Today's beancounters have a very low effective branching factor (for SF around 1.6). So when we start a new iteration, it's very very unlikely that the search is going to explode and we need to abort before finishing. And occasionally when this happens, it's often the case that we have seen something which completely turns the tables and we want to finish this no matter what.diep wrote: The real psychological question is whether you want from your 16 cores or so have 15 search nonsense moves and just 1 being busy to figure out if a fail high is possible, you ARE gonna time out. Throwing 16 cores at that 2nd move might give you a crucial fail high just before time out.
You really don't want to split there.
This might be less of a problem with todays beancounters that just check the mainline deep and basically prune the rest.
So because in around 96%-99% cases we are going to search all the moves anyway, it's just an optimazation to split in root.
Another point is that in your example, after 15 cores have quickly finished searching nonsense moves, they'll join in searching the promising move, so even here the lose of time is not untolerable.
Joona Kiiski