"CUT" vs "ALL" nodes

[lkaufman]

How important or useful is it to make this distinction? Stockfish doesn't seem to make it at all, whereas Rybka and the Ippo derivatives all make extensive use of it. What programs other than the Ippo derivatives are known to make this distinction?

[michiguel]

How important or useful is it to make this distinction? Stockfish doesn't seem to make it at all, whereas Rybka and the Ippo derivatives all make extensive use of it. What programs other than the Ippo derivatives are known to make this distinction?

Could you elaborate more? What do you mean by making a distinction? They predict whether a node will be cut or all at the beginning of it and make decisions based on that?

Miguel
PS: Could we move this thread to the programming section?

[lkaufman]

How important or useful is it to make this distinction? Stockfish doesn't seem to make it at all, whereas Rybka and the Ippo derivatives all make extensive use of it. What programs other than the Ippo derivatives are known to make this distinction?

Could you elaborate more? What do you mean by making a distinction? They predict whether a node will be cut or all at the beginning of it and make decisions based on that?

Yes, exactly so.

Miguel
PS: Could we move this thread to the programming section?

Sure, if a mod will move it there, that's fine with me.

[bob]

How important or useful is it to make this distinction? Stockfish doesn't seem to make it at all, whereas Rybka and the Ippo derivatives all make extensive use of it. What programs other than the Ippo derivatives are known to make this distinction?

From past experience, I don't think it that important. However, StockFish does do this, just in a subtle way. A "PV" node is guaranteed to be an ALL node. The only problem is it is impossible to say that "this node is the one and only PV node at this ply" because move ordering is not perfect...

Knuth/Moore give a good definition for PV, ALL and CUT. But the definitions don't mean a thing without perfect move ordering. And perfect move ordering is impossible. So we might name these as PPV, PALL and PCUT where "P" means possibly or probably but not certainly...

[lkaufman]

Yes, the term should be "expected" or "predicted" CUT or ALL node. Most top programs do distinguish between PV and non-PV nodes; I'm only interested in the question of which ones distinguish between the two sub-categories of non-PV nodes, and whether this helps or not.

[Eelco de Groot]

I think Stockfish distinguishes between these types of nodes more by what is stored in the Transposition Table. If the entry is a lower limit, I think this means it was a CUT node at least when this entry was stored. Only these entries are candidates for singular extensions. I assumed that it would be the same in Rybka or at least the Rybka clones but Marco Costalba and others posted that this distinction, "soft singular extensions" I believe someome called it, is exclusive for Stockfish. If Rybka determines CUT nodes in another way I do not know how it is done, you can assume that most nodes where it is the opponent's move in nullwindow searches should be CUT nodes, but for the PV move at the root in all null window branches upward from this main rootmove it should be the opposite. But this is only true for "stable" nullwindow branches.

Doing singular extensions in CUT nodes with exclusion searches makes sense because, if the TT move is good, you need not look at other moves, but if it is not singular, or not singular anymore, or not a CUT node anymore, you probably have branches/siblings growing/descending from that node that are underresearched and could use some IID. That is the dual purpose of the exclusion search in CUT modes, at least that is how I see it.

Regards, Eelco

[jwes]

In the general case, predicting node types is straightforward. If the current node is a CUT or ALL node, child nodes will be ALL or CUT respectively. If the first node is a PV node, the first child node will be a PV node and all other child nodes will be CUT nodes. One question is that if the first move fails low at a CUT or PV node, should you then treat the node as an ALL node (or perhaps after n moves fail low). Someone could (or has) run statistics to find out.

[lkaufman]

I think Stockfish distinguishes between these types of nodes more by what is stored in the Transposition Table. If the entry is a lower limit, I think this means it was a CUT node at least when this entry was stored. Only these entries are candidates for singular extensions. I assumed that it would be the same in Rybka or at least the Rybka clones but Marco Costalba and others posted that this distinction, "soft singular extensions" I believe someome called it, is exclusive for Stockfish. If Rybka determines CUT nodes in another way I do not know how it is done, you can assume that most nodes where it is the opponent's move in nullwindow searches should be CUT nodes, but for the PV move at the root in all null window branches upward from this main rootmove it should be the opposite. But this is only true for "stable" nullwindow branches.

Doing singular extensions in CUT nodes with exclusion searches makes sense because, if the TT move is good, you need not look at other moves, but if it is not singular, or not singular anymore, or not a CUT node anymore, you probably have branches/siblings growing/descending from that node that are underresearched and could use some IID. That is the dual purpose of the exclusion search in CUT modes, at least that is how I see it.

Regards, Eelco

Thanks. Do you have any comment on the distinction between "CUT" and "ALL" nodes in places other than singular extension, for example for futility margins and other such search restrictions? Rybka and the Ippo derivatives make this distinction, SF apparently does not.

[Eelco de Groot]

I think Stockfish distinguishes between these types of nodes more by what is stored in the Transposition Table. If the entry is a lower limit, I think this means it was a CUT node at least when this entry was stored. Only these entries are candidates for singular extensions. I assumed that it would be the same in Rybka or at least the Rybka clones but Marco Costalba and others posted that this distinction, "soft singular extensions" I believe someome called it, is exclusive for Stockfish. If Rybka determines CUT nodes in another way I do not know how it is done, you can assume that most nodes where it is the opponent's move in nullwindow searches should be CUT nodes, but for the PV move at the root in all null window branches upward from this main rootmove it should be the opposite. But this is only true for "stable" nullwindow branches.

Doing singular extensions in CUT nodes with exclusion searches makes sense because, if the TT move is good, you need not look at other moves, but if it is not singular, or not singular anymore, or not a CUT node anymore, you probably have branches/siblings growing/descending from that node that are underresearched and could use some IID. That is the dual purpose of the exclusion search in CUT modes, at least that is how I see it.

Regards, Eelco

Thanks. Do you have any comment on the distinction between "CUT" and "ALL" nodes in places other than singular extension, for example for futility margins and other such search restrictions? Rybka and the Ippo derivatives make this distinction, SF apparently does not.

Hello Larry, I don't think I could say much about that that would be of any use. Bob may have made some measurements which is what you would need. And I don't know anything about the Ippo code, for Stockfish a consideration is I think that that the team does not want too complicated code, only if there is measurable benefit of added code, and any asymmetry that you build in can turn against itself because CUT nodes can allways turn into ALL nodes in principle, and vice versa. Maybe I'm seeing this wrong but is it not that you only can be sure of an ALL node if you have tested all the moves and none of them fail high? By then you have already searched all the siblings so any distinction does not matter any more, only when you return here for the next iteration. Bob will argue that any value returned from a null window search is for a large part only an upper limit, if you are lucky a lower limit, but nothing more. So you cannot really use these values to determine singularity, and the exclusion value can also not be used to determine a second best move. This is of course true, but for the very undeep searches I think the values are still of some use, e.g if they are static values they are also "exact"!

Only for deeper nullwindow searches you will have to find something better, because they are very imprecise in the moves and values they return. If you want better "second best" moves for instance you could do your exclusion search in such a way that you don't stop at the first move that is better than "b"', b being the value of the TT move minus some margin. All the moves that are better than b are at least a little bit better than moves that do not cause a beta cutoff in the node. These you could search a bit deeper if the TT move fails for instance. But I have not any statistics on this.

My best, Eelco

[michiguel]

In the general case, predicting node types is straightforward. If the current node is a CUT or ALL node, child nodes will be ALL or CUT respectively. If the first node is a PV node, the first child node will be a PV node and all other child nodes will be CUT nodes. One question is that if the first move fails low at a CUT or PV node, should you then treat the node as an ALL node (or perhaps after n moves fail low). Someone could (or has) run statistics to find out.

But the accuracy of predicting it this way is very bad (_relatively_ speaking for what is needed). I measured it.
The problem is you really need better accuracy to make certain decisions (whenever you fail it is very costly). I have not given up to explore this path, but I am not sure you can use the word 'straightforward'.

Miguel