When a Node Type Changes...

[Cheney]

Hi,

I decided to study a little bit more into Knuth's node types to measure the frequency in which a type does not do what it was expected to do and I am now trying to wrap my mind around the basic data.

I've read a few dozen posts, thought I read at one time what it means when a node type changes, but just cannot seem to find it.

My implementation:
* The root position is a PVNode. I am performing the PVS zero window search at the root.
* The first move is searched as a PV node, however, all following moves made are flagged as cut nodes when searched in a zero window.
* In the case of a research, the move is flagged as a PV node.
* All children of cut nodes are all nodes.
* All children of all nodes are cut nodes.
* If an expected cut node does not cut in the first move then it becomes an all node and continues searching moves.
* If an expected all node cuts then the node is done searching.

At the end of each node, I am tallying some counters. At the end of searching a position for a few seconds, I will see something like this:

All Nodes encountered: 3112
All Nodes that Failed High: 1261
All Nodes First Move Fail High: 839
Cut Nodes encountered: 15807
Cut Nodes that Failed Low: 177
Cut Nodes First Move Fail High: 9570

Here's what I feel I can conclude:
* My cut nodes are successfully cutting, percentage could be better.
* The all nodes are cutting at a high rate, but I did not expect this to happen.

From what I read about node types, in perfect move ordering, we search all moves in an all node but in a cut node we'll only end up searching the first move. Also, it is mentioned that move ordering in an all node can be insignificant.

But, since move ordering is not perfect, I believe what I am seeing is expected - there will be some cut nodes that do not cut, some all nodes that do cut.

My question here is how to treat this? Can an all node's move ordering not be improved? Maybe I am doing something wrong - maybe the count of fail highs for the all nodes should be reduced while the count of fail lows for cut nodes should also be reduced?

Ty
-Cheney

[odomobo]

So if I understand the matter correctly, here's a conclusion:

If every PV node and cut node has perfect ordering (i.e. the PV move or a cut move is evaluated first), then you will see that every expected cut node will be a cut node, and every expected all node will be an all node. However, if a cut node first evaluates a position that fails low, that means the cut node's first child is another cut node, and its child is an all-node (when it was predicted to be a cut node).

As you said, there's no amount of ordering that will improve an all node. For a true all node, you have to evaluate every child, and all of them will fail low (which means every child is a cut node). The only point for ordering an all node is to apply optimizations like LMR/LMP. However, you don't know that a predicted all-node is actually an all-node until you've fully searched it. It could potentially turn into a cut node.

I think a more useful statistic than what you are gathering is move ordering within cut/PV nodes. Something like number of incorrect moves searched before the correct move was found. IMO, that would be representing the same statistic you are gathering, just in a way that's easier to interpret.

[Cheney]

Thank you

That statistic has been used and what lead me to wanting to measure each node type.

I have collected data on fail highs, first move fail highs, and fail highs within the first 5 moves. I have also collected this data per move type - hash, capture, promotions, etc. I have not collected this based on the expected node type.

I feel that the move ordering is good; I know it changes positively or negatively if I take a type of move and sort it differently. This change in sorting is reflected in the counters of fail highs.

Here is some data and why I think my move ordering is good:

First Move Fail Highs: 93%
Top5 Fail Highs: 5%
Hash: 58% of fail highs
Captures: 32% of fail highs

I guess where I am going with this is how to predict a node type, use that to an advantage, and understand how to react when an expected node type changes.

For example, I have added some pruning and reduction features - extended futility pruning, LMR. I have definitely gained some speed and ELO. I was trying to add IID for PV Nodes only, and it works, but not gaining speed or ELO.

Upon reading more on IID, I read comments how it may not help well if move ordering is good. Also, that IID works better in cut nodes. I have seen similar comments for LMR, use it in all nodes. This lead me to here - determine an expected node type, test these features based on node type, but when I saw the node type change, I started to collect these stats and wondered if I was on the right path.