expensive null move searches

[Jan Brouwer]

I added some code to count the number of nodes contained in null-move searches in my program,
and to my surprise this turns out to be about 50% of all nodes! This seems rather high to me.
Can anyone confirm these numbers?

Jan

[adieguez]

hi, nullmove nodes here in early middlegame is 19-20% when using reductions. And 29-30% not using reductions. I have mainly 2 restrictions to avoid doing nullmove, having eval>=beta, and not having hash upper value<=beta with depth diff<=2. Also when depth remaining is 2 I restrict even more. Note that I actually "cheat", I evaluate at every node and see the enemy captures too when depth is 2 and often cut there. If I don't do that and let the nullmove go, the nullmove nodes off course would increment more, but with actually little impact in search performance.

[Jan Brouwer]

Hi Antonio,

hi, nullmove nodes here in early middlegame is 19-20% when using reductions. And 29-30% not using reductions. I have mainly 2 restrictions to avoid doing nullmove, having eval>=beta, and not having hash upper value<=beta with depth diff<=2. Also when depth remaining is 2 I restrict even more. Note that I actually "cheat", I evaluate at every node and see the enemy captures too when depth is 2 and often cut there. If I don't do that and let the nullmove go, the nullmove nodes off course would increment more, but with actually little impact in search performance.

Your numbers are quite a bit lower, more what I would expect.
I don't use any restrictions other than not being in check and a minimal amount of material on the board, so perhaps that explains the difference.
I'll try adding some conditions and some more statistics.

[jwes]

I tried this with crafty and was also surprised to find that most nodes searched were null move nodes and that most null move tries fail high.

[bob]

I tried this with crafty and was also surprised to find that most nodes searched were null move nodes and that most null move tries fail high.

This is not surprising to me. A ton of moves lose material. Null-move is the cheapest way possible to recognize those positions and dismiss them as quickly as possible.

[Jan Brouwer]

I tried this with crafty and was also surprised to find that most nodes searched were null move nodes and that most null move tries fail high.

Good to hear that others are getting similar results. Still a bit of an eye-opener how expensive null move searches can be, I have seen it peek at about 80%!

[bob]

I tried this with crafty and was also surprised to find that most nodes searched were null move nodes and that most null move tries fail high.

Good to hear that others are getting similar results. Still a bit of an eye-opener how expensive null move searches can be, I have seen it peek at about 80%!

You are thinking about it backward. Without the null-move search fail highs. the regular search would be _far_ larger.

[Jan Brouwer]

I tried this with crafty and was also surprised to find that most nodes searched were null move nodes and that most null move tries fail high.

Good to hear that others are getting similar results. Still a bit of an eye-opener how expensive null move searches can be, I have seen it peek at about 80%!

You are thinking about it backward. Without the null-move search fail highs. the regular search would be _far_ larger.

Of course. But it indicates opportunity for savings there, such as skipping null move searches with low probability of fail high, or replacing null move searches near the leaves with static methods.

[bob]

I tried this with crafty and was also surprised to find that most nodes searched were null move nodes and that most null move tries fail high.

Good to hear that others are getting similar results. Still a bit of an eye-opener how expensive null move searches can be, I have seen it peek at about 80%!

You are thinking about it backward. Without the null-move search fail highs. the regular search would be _far_ larger.

Of course. But it indicates opportunity for savings there, such as skipping null move searches with low probability of fail high, or replacing null move searches near the leaves with static methods.

That wasn't my point. If you make the percentage of null-move searches lower, you must, by definition, be making the non-null-move searches bigger. Which will reduce overall depth.

percentages in an alpha/beta search don't mean a lot in this kind of context. Which would you rather see, 22 ply search with 60% null-move searches, or 12 ply searches with no null-move searches?

[jwes]

I tried this with crafty and was also surprised to find that most nodes searched were null move nodes and that most null move tries fail high.

Good to hear that others are getting similar results. Still a bit of an eye-opener how expensive null move searches can be, I have seen it peek at about 80%!

You are thinking about it backward. Without the null-move search fail highs. the regular search would be _far_ larger.

Of course. But it indicates opportunity for savings there, such as skipping null move searches with low probability of fail high, or replacing null move searches near the leaves with static methods.

That wasn't my point. If you make the percentage of null-move searches lower, you must, by definition, be making the non-null-move searches bigger. Which will reduce overall depth.

percentages in an alpha/beta search don't mean a lot in this kind of context. Which would you rather see, 22 ply search with 60% null-move searches, or 12 ply searches with no null-move searches?

I would rather see 23 ply with 20% null-move searches. The idea is to make null-move more efficient, not to stop using it, e.g. making R larger would reduce the number of null-move nodes and search deeper (though it might cause it to miss tactical shots). I did not realize that the percentage of null-move nodes was anywhere near that large, and so did not think that optimizing null-move could gain much.