Some questions on split points

[edwardyu]

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.

[bob]

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.

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.

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.

[zamar]

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?

Stockfish gained around +10 elo on 4 CPU when we started splitting at root. Do it if you can.

2. Do we split in PV and nonPV nodes?

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).

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.

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.

DISCLAIMER: Feel free to disagree, just personal opinions. I do not have data to backup these claims.

[CRoberson]

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.

[diep]

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?

Let's first note that obeying the YBW rule of splitting is a great idea removing most problems.

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.

2. Do we split in PV and nonPV nodes?

Obviously.

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.

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.

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.

[bob]

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.

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.

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.

[bob]

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?

Let's first note that obeying the YBW rule of splitting is a great idea removing most problems.

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.

2. Do we split in PV and nonPV nodes?

Obviously.

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.

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.

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.

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.

[zamar]

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.

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)

[zamar]

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.

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.

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.