"CUT" vs "ALL" nodes

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: "CUT" vs "ALL" nodes

Post by bob » Tue Mar 08, 2011 4:06 am

lkaufman wrote: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.
In CB, I used this extensively, because you never want to split at a CUT node, and want to prefer an ALL node. YBW tries to recognize an ALL node by requiring that at least one move be searched before splitting, since > 90% of CUT nodes are discovered on the first move searched. But waiting on that first move introduces some wait time, and if you knew it was an ALL node from the get-go, you could split before the first move is completed. That was the basic premise behind the iterated search and DTS algorithm in Cray Blitz...

I don't do that in Crafty however, because I did not want to give up the simple elegance of the recursive negamax search which would be necessary to do to implement a full DTS-like search.

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: "CUT" vs "ALL" nodes

Post by bob » Tue Mar 08, 2011 4:08 am

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.
You can do that, and we did it in Cray Blitz. But it is not without errors. Since perfect move ordering is impossible, node types can always change. 90+% of the time they don't, but that is still a long way from 100%

Post Reply