"CUT" vs "ALL" nodes

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
lkaufman
Posts: 3647
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

"CUT" vs "ALL" nodes

Post by lkaufman » Mon Mar 07, 2011 3:28 pm

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?

User avatar
michiguel
Posts: 6387
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: "CUT" vs "ALL" nodes

Post by michiguel » Mon Mar 07, 2011 3:44 pm

lkaufman wrote: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
Posts: 3647
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: "CUT" vs "ALL" nodes

Post by lkaufman » Mon Mar 07, 2011 4:06 pm

michiguel wrote:
lkaufman wrote: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
Posts: 20408
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: "CUT" vs "ALL" nodes

Post by bob » Mon Mar 07, 2011 4:18 pm

lkaufman wrote: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
Posts: 3647
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: "CUT" vs "ALL" nodes

Post by lkaufman » Mon Mar 07, 2011 5:01 pm

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.

User avatar
Eelco de Groot
Posts: 4136
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: "CUT" vs "ALL" nodes

Post by Eelco de Groot » Mon Mar 07, 2011 5:32 pm

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
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: "CUT" vs "ALL" nodes

Post by jwes » Mon Mar 07, 2011 6:41 pm

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
Posts: 3647
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: "CUT" vs "ALL" nodes

Post by lkaufman » Mon Mar 07, 2011 6:47 pm

Eelco de Groot wrote: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.

User avatar
Eelco de Groot
Posts: 4136
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: "CUT" vs "ALL" nodes

Post by Eelco de Groot » Mon Mar 07, 2011 7:40 pm

lkaufman wrote:
Eelco de Groot wrote: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
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

User avatar
michiguel
Posts: 6387
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: "CUT" vs "ALL" nodes

Post by michiguel » Mon Mar 07, 2011 8:27 pm

jwes wrote: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

Post Reply