NMP on ALL nodes

[Onno Garms]

As most of you might know, Toga uses three different node types, namely NodePV, NodeAll, and NodeCut.

While the search acts differently on NodePV, the search acts absolutely identical on NodeAll and NodeCut. I was surprised that Toga e.g. does null move pruning on NodeAll. I believed that that is wasted time and also that occasional wrong pruning reduces the quality.

Therefore I changed Toga's behaviour not do do NMP on ALL nodes. I thought that this should increase the playing strength. However, the score after 120 games is within the usual range. Any ideas why one should do NMP on ALL nodes?

PS: I also tried to adapt node type handling in full_no_null to that in search_full. Handling node types differently there seems to be a bug that mixes up NodeAll and NodeCut - which of course currently has no effect on the playing due to identical handling of these types.

I also know that 120 games are too few. But I don't have the computational ressources to run more. Any ideas how to test with other methods?

[H.G.Muller]

How does Toga decide if something is an all-node or a cut-node? In general, all nodes will have eval<alpha. So if the NMP is done only when eval>=beta, as is the usual condition, effectively you will not be doing NMP in most all-nodes.

Another answer could be that the classification of node types is not perfect, and that null move is a much cheaper way to spot the mistakes than doing a full search. I guess it would be simple enough to build in code that counts the number of all-nodes searched, the number of null-move searches attempted from there, and the number of prunings in which this resulted.

Finally, it seems that for some people even doing chanceless null-move searches (e.g. when eval << alpha) is not a waste of time at all, but on the contrary speeds things up. This because even a low-failing search does fill hash, killer and history tables, from which the full-wdth search profits later.

If you really suspect that searching certain branches is a waste of time, you could simply compare the number of nodes to search a certain collection of possitions to various depths with or without pruning the stuff you think is useless. If searching the extra branches lead to other moves at the same depth then they are apparently not a waste of time. If you get the same moves, but faster, you could say the same. Only if you get different moves, but slower, you have to deal with the question if this was worth it.

[Onno Garms]

How does Toga decide if something is an all-node or a cut-node? In general, all nodes will have eval<alpha. So if the NMP is done only when eval>=beta, as is the usual condition, effectively you will not be doing NMP in most all-nodes.

There is an option UseNullEval (controlled by UCI option NullMove Pruning). If set to true, NMP is only done when eval>=beta. However, the default is false. Can you tell what's the idea behind UseNullEval? Up to now I thought that eval does not give an adequate information on a position's value for larger search depths. So I thought that Toga's authors were right to disable the option by default.

Toga's node types can be defined the following way (after the bugfix in full_no_null):
- initial node is PV
- first child of PV is PV
- other children of PV are Cut
- first child of Cut is All
- other children of Cut are Cut
- children of All are Cut

I think this amounts to:
- PV is when both players only played first children
- node type is All iff player to move was the last one who did not play the first child
- node Cut is when the opponent was the last who did not play the first child

On a minimal search tree I think this is the only resonable way to define node types recursively. Maybe the extension to the rest of the search tree is not so good. At least I conceived a different extension. Maybe the best way is to leave node type undefined when off the minimal search tree (cf http://citeseer.ist.psu.edu/hopp95parallel.html)

However, above node types are not so bad: On All nodes, the number of children generated is more than 20 on an average. On Cut nodes, the number of children generated is less then 2.

I will try undefined node types after I've fixed my computer. (I'm recently experiencing crashes under heavy load and have ordered a new CPU fan and power supply.)

Another answer could be that the classification of node types is not perfect, and that null move is a much cheaper way to spot the mistakes than doing a full search. I guess it would be simple enough to build in code that counts the number of all-nodes searched, the number of null-move searches attempted from there, and the number of prunings in which this resulted.

I had implemented most of above counting before posting. Results follow.

Finally, it seems that for some people even doing chanceless null-move searches (e.g. when eval << alpha) is not a waste of time at all, but on the contrary speeds things up. This because even a low-failing search does fill hash, killer and history tables, from which the full-wdth search profits later.

Good idea, I've not thought of that. But can the null move search itsself help to fill the tables? Isn't it the wrong players turn? Or is it the verification search that fills the tables?

If you really suspect that searching certain branches is a waste of time, you could simply compare the number of nodes to search a certain collection of possitions to various depths with or without pruning the stuff you think is useless. If searching the extra branches lead to other moves at the same depth then they are apparently not a waste of time. If you get the same moves, but faster, you could say the same. Only if you get different moves, but slower, you have to deal with the question if this was worth it.

I tried a few positions manually. Without NMP on All nodes, total node count differs, but it's sometimes more and sometimes less. The values of the positions also differed. (Moves did not on the few positions I've tested.) So I thought that the modification might be an even deal w.r.t. the total node count, but give better moves because of less pruning.

[Onno Garms]

I had implemented most of above counting before posting. Results follow.

With Toga's node types, the number of All nodes that are pruned away by NMP is less then 0.5% on the few positions that I tested.

Even with undefined nodes, occasional pruning by null move on All nodes occurs, but that's less then 0.1%.

[bob]

As most of you might know, Toga uses three different node types, namely NodePV, NodeAll, and NodeCut.

While the search acts differently on NodePV, the search acts absolutely identical on NodeAll and NodeCut. I was surprised that Toga e.g. does null move pruning on NodeAll. I believed that that is wasted time and also that occasional wrong pruning reduces the quality.

Therefore I changed Toga's behaviour not do do NMP on ALL nodes. I thought that this should increase the playing strength. However, the score after 120 games is within the usual range. Any ideas why one should do NMP on ALL nodes?

PS: I also tried to adapt node type handling in full_no_null to that in search_full. Handling node types differently there seems to be a bug that mixes up NodeAll and NodeCut - which of course currently has no effect on the playing due to identical handling of these types.

I also know that 120 games are too few. But I don't have the computational ressources to run more. Any ideas how to test with other methods?

The issue is that it is impossible to be accurate in labeling a node as ALL or CUT. Sometimes a node appears to be an ALL node but because of poor move ordering at the previous CUT node, this node becomes a CUT node itself. And null-move helps there.

I do null-move _everywhere_ even on PV nodes, because there is no way to accurately determine that a node is a PV node until after it is searched...

[H.G.Muller]

Good idea, I've not thought of that. But can the null move search itsself help to fill the tables? Isn't it the wrong players turn? Or is it the verification search that fills the tables?

Well, things like history tables do not realy pay attention to the exact board position, so if one side does null move, and the other some non-essential move, you might have many moves that have similar scores as from the position before null move.

Also, if one side does null move, and the other side wastes a tempo by playing the same piece twice, you are back to the same position, but at lower remaining depth. This would be a form of implicit internal iterative deepening, providing a later full-depth search of that same position with a hash move.

For Killers the null move is usually included in the depth count, so the killer entries would be filled by moves for the proper side. In the absense of IID the fact that a low-failing null move sets the killer at the reply level to its refutation, which might be very benificial for refuting the first move you try at full depth.

[Ron Murawski]

Good idea, I've not thought of that. But can the null move search itsself help to fill the tables? Isn't it the wrong players turn? Or is it the verification search that fills the tables?

I store null-move verification searches that fail high in the hash. I can't store a pure null-move fail-high move because there's no move to store! But it's possible for other nodes in a null move search that does not fail high to get stored in the hash.

Ron

[Onno Garms]

I will try undefined node types after I've fixed my computer. (I'm recently experiencing crashes under heavy load and have ordered a new CPU fan and power supply.)

This also gives results within the usual range.

Btw. it was the hardware's fault that running chess engine(s) on both cores did not work. The recent abortion of engine tournaments seems to have been caused by too large logfiles written by the Shredder GUI. I will file a report to Stefan Meyer-Kahlen.