All and Cut nodes

[bob]

For example, does it work to have a different min depth and reduction for IID between 'All' and 'Cut' nodes

In 'All' nodes you can omit IID entirely since all moves are expected to fail low.

Only problem is, you really don't know a node is an ALL node until you search all the moves without improving alpha. You can assume that if you get a fail high at depth D, then depth D-1 is likely to be an ALL node, but in DTS I found this to be prone to significant error, because move ordering is anything but perfect.

Komodo uses a simple definition which seems to work extremely well. We count the number of nodes since the last PV node and go by the odd/even parity.

Doesn't work so well in my testing. This was a MAJOR problem when I was working on DTS. If you try your trick, you will be astounded at how many times you say "ALL" when it is really "CUT". I found a better way was working back, as you back up. You know what the CURRENT node is, better than anything else. Which means that the previous node is the opposite, in general, except when move ordering back there is wrong, of course.

So the when you are in the PV nodes and do a zero window PVS search, that is a cut node and it usually will cut off. The node after it is always an ALL node and every other node swaps back and forth.

For PERFECTLY ordered trees, yes. But a good program gets that wrong something like 10% of the time (wrong ordering). And that simply wrecks trying to categorize things forward from the root.

This definition is always "correct" until a cut node does not fail or an all node does fail. When that happens, the search will unwind to some point and correct itself.

For example if an all node fails high, the parent node which is a cut node will simply have to try more moves. One of them will either produce the cut node that it should, or else none of them will. In that case the parent did not produce a cutoff and it's parent now gets involved - which is an all node. Eventually it will reset itself perfectly, or else it actually back up all the way back to a PV node and get researched as a PV node.

This "correct itself" implies too much. While you are in the middle of this mess, EVERYTHING is wrong, and any decisions you make are based on incorrect information.

I agree that nulls at ALL nodes are worthless. Only NULLS at CUT nodes make any sense. But identifying which is which is error-prone. I fiddled with this "identify node types" for a year in DTS, because I REALLY want to split at ALL nodes, NEVER at CUT nodes, which is what YBW tries to do in a very simplistic way. And it, too (YBW) is wrong far more than I would like.

But here is the beauty of that. If it gets back to PV node some of the same moves may get searched, but they will switch roles! The very same node that was considered a CUT becomes an ALL node and vice versa.

We only partially understand the repercussion of that but it seems to be a very nice quality for the search to have, especially if you want to treat the nodes differently. It essentially allows you to cheat move on some nodes by speculatively throwing t hem out or reducing them. If a research is triggered you are saved, if not you saved time.

My objection is doing something different based on the projected type, because I REALLY want those ALL nodes to fail high when I am walking down some tactical path that I do not yet grasp. Cut/reduce/prune/etc the wrong move or moves and that ALL node won't reveal its true nature until it is too late and you are committed to a path that is going to get you killed.

[lucasart]

OK, now with my corrected code, I did some counting:
- 81% of my predicted All nodes fail low. So 19% error there.
- Also to be noted that 81% of my null searches fail high, and the child of a null search is a predicted All node (so coincidently the %age of All failing low overall or restricted to null children is the same). From that number it is clear that DiscoCheck spends most of its time in the null search.

You guys have more experience that me on that, so what do you reckon ? Do these numbers sound reasonable ? Or should the prediction be much more accurate (indicating that my move ordering sucks) ?

[asanjuan]

I do the folowing: I assign the expected node type depending on the position in the tree, as is defined in the wiki (and other papers):

- expected ALL nodes: LMR
- expected CUT nodes: IID
- both ALL and CUT nodes: null-move pruning, usually solves the classification when an ALL node is really a CUT node.

it seems to add stability to the search. At least for me. It seems to be TT-friendly.
:S
just my two cents.

[PK]

Am I correct in stating that Fruit 2.1 does determine node type, but in its search makes no distinction between all and cut nodes? If not, what did I miss?

[lucasart]

Am I correct in stating that Fruit 2.1 does determine node type, but in its search makes no distinction between all and cut nodes? If not, what did I miss?

You are correct. Only thing is "predict" rather than "determine".

[Don]

Am I correct in stating that Fruit 2.1 does determine node type, but in its search makes no distinction between all and cut nodes? If not, what did I miss?

You are correct. Only thing is "predict" rather than "determine".

No matter what you do, it's arbitrary. You don't know what type of node it is until the last move is searched, which could be a cutoff making this a cut node all of a sudden.

In the chessprogramming wiki the definition is pretty arbitrary, not because there is anything wrong with it but just because to know how to treat a node you have to be pretty flexible, even to the point of changing the node type in mid-stream.

Since it's going to be screwed up anyway, we choose in Komodo to have a very precise and predictable definition which is an engineering decision. Our definition would actually be perfect if the tree was ordered perfectly. But the real point of how we do it is that it is self-correcting due to PVS search. If a node is of the incorrect type it will become irrelevant. It took us some time to come up with this - we experimented and tried various things so this was not arbitrary for us. I think I even opened a thread on this forum to get some ideas.

The proof is in the pudding as they say. Komodo is stronger as a result of making this distinction. That doesn't necessarily mean our way is right, but it works. I don't know what the other top programs do wiith respect to this but it seems like in view of the name of the thread there should be a survey. What we know is:

1. How Komodo does it.
2. That Houdini does something in this regard
3. Crafty does not make a distinction.
4. Stockfish does not make a distinction.

Others? Maybe Robert will say what he does and hopefully others.

I'm not sure Crafty even distinguishes PV nodes from other nodes, but I might be wrong.

[lucasart]

I already pushed two patches in DiscoCheck (validated in testing, bothing giving a small but measurable gain accounting for error bar):
1/ IID: Only do IID at All nodes when eval+pawn>=beta. Of course there is a min depth condition too (4 for PV nodes and 7 for non PV nodes, whether All or Cut).
2/ Lazy move ordering at All nodes (captures by MVV/LVA instead of SEE, not bothering to distinguish good and bad captures as this means calling the costly SEE function)

[bob]

Am I correct in stating that Fruit 2.1 does determine node type, but in its search makes no distinction between all and cut nodes? If not, what did I miss?

You are correct. Only thing is "predict" rather than "determine".

No matter what you do, it's arbitrary. You don't know what type of node it is until the last move is searched, which could be a cutoff making this a cut node all of a sudden.

In the chessprogramming wiki the definition is pretty arbitrary, not because there is anything wrong with it but just because to know how to treat a node you have to be pretty flexible, even to the point of changing the node type in mid-stream.

Since it's going to be screwed up anyway, we choose in Komodo to have a very precise and predictable definition which is an engineering decision. Our definition would actually be perfect if the tree was ordered perfectly. But the real point of how we do it is that it is self-correcting due to PVS search. If a node is of the incorrect type it will become irrelevant. It took us some time to come up with this - we experimented and tried various things so this was not arbitrary for us. I think I even opened a thread on this forum to get some ideas.

The proof is in the pudding as they say. Komodo is stronger as a result of making this distinction. That doesn't necessarily mean our way is right, but it works. I don't know what the other top programs do wiith respect to this but it seems like in view of the name of the thread there should be a survey. What we know is:

1. How Komodo does it.
2. That Houdini does something in this regard
3. Crafty does not make a distinction.
4. Stockfish does not make a distinction.

Others? Maybe Robert will say what he does and hopefully others.

I'm not sure Crafty even distinguishes PV nodes from other nodes, but I might be wrong.

Crafty does distinguish PV from Non-PV, because doing a null-move search on a PV node is a waste of time 99% of the time. On that rare occasion where the PV is suddenly badly wrong, a null-search might fail high, obviously. But that's rare. That's really all I remember doing specifically, just turning off null.

Oops, forgot about IID. I ONLY allow that on PV nodes and only when there is no hash move, which is incredibly rare in Crafty at the moment (I have a fix in progress to address this a bit, but it is behind another set of changes dealing with LMR that is taking some time to tune.)

[bob]

OK, now with my corrected code, I did some counting:
- 81% of my predicted All nodes fail low. So 19% error there.
- Also to be noted that 81% of my null searches fail high, and the child of a null search is a predicted All node (so coincidently the %age of All failing low overall or restricted to null children is the same). From that number it is clear that DiscoCheck spends most of its time in the null search.

You guys have more experience that me on that, so what do you reckon ? Do these numbers sound reasonable ? Or should the prediction be much more accurate (indicating that my move ordering sucks) ?

Here is the common metric to see how your ordering works. At any node in the tree where you fail high, at any point in time, first move or not, increment a counter failed_high. At those positions where you increment that counter, if you have just searched one move, increment a second counter failed_high_1st_move.

After the search is done, print this:

percentage = 100 * failed_high_1st_move / failed_high.

You want to be at 90% or above, otherwise your basic move ordering needs work...

[lucasart]

OK, now with my corrected code, I did some counting:
- 81% of my predicted All nodes fail low. So 19% error there.
- Also to be noted that 81% of my null searches fail high, and the child of a null search is a predicted All node (so coincidently the %age of All failing low overall or restricted to null children is the same). From that number it is clear that DiscoCheck spends most of its time in the null search.

You guys have more experience that me on that, so what do you reckon ? Do these numbers sound reasonable ? Or should the prediction be much more accurate (indicating that my move ordering sucks) ?

Here is the common metric to see how your ordering works. At any node in the tree where you fail high, at any point in time, first move or not, increment a counter failed_high. At those positions where you increment that counter, if you have just searched one move, increment a second counter failed_high_1st_move.

After the search is done, print this:

percentage = 100 * failed_high_1st_move / failed_high.

You want to be at 90% or above, otherwise your basic move ordering needs work...

But what if I fail high, or fail low, *before* searching the first move ? Reasons for this are:
- TT pruning
- eval pruning (when eval is significantly above beta, at low depth, and under certain stability conditions, I return a fail high score = eval + tempo_bonus)
- razoring
- null move pruning: don't forget that 81% of the time my null move searh fails high, and I return without searching anything.

So, because of the above, my search typically exits in the vast majority of cases without even generating any moves or searching any...

Of course I could do the counting you suggest on the subpopulation of nodes that actually *reach* the move loop. But that subpopulation is relatively small, and could introduce a selection biais, no ?

That's why the only thing I can reliably measure is the %age of nodes that fail low or fail high, by predicted node type (I have to increment my counters at every possible exit point of the search, and there are quite a few).