expensive null move searches

[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.

I ran some statistics with crafty and estimate that a full search takes 10x as many nodes as a null search, but with depth remaining of 1, the null search takes as many nodes as a full search. With some thought, I understood why this is. Obviously, you don't want to do null move unless both the null search and the full search will fail high. So, the null move drops into qsearch while the full search tries moves until one fails high (virtually always the first tried), and goes into qsearch (which also generally fails high on the stand pat score). The difference is one node plus any difference between the two qsearches, which I believe would favor the full search.

Recommendations:
1. Don't try null move if depth remaining is 1.
2. Don't try null move if material is more than about 1.4 pawns below beta, this is where the odds of a null move fail high is less than 1 in 10.

These results are for crafty 23.0, so as always YMMV.

You should test #1. You will be surprised how much it will slow things down. You are not quite right in how you explain it. Assume a null-move search fails high, which means no good captures when you drop right into the q-search. Very fast. Otherwise, you have to actually go to the next ply, and search more than one move. 1/2 of the time you search 'em all, the other half you search just 1 (fail high). It does make a big difference.

I just did try it and it is slightly faster. The null-move fail high does not necessarily mean no good captures, it means that no sequences of captures will drop the evaluation below beta, e.g if the side making the null move had dropped its queen, there may well be captures that win a rook, a knight, or a pawn, and the null move will still fail high. Also it is more like 1 time in 1000 that the null move will fail high and the full search will fail low. If it were 1/2 the time, you would really not want to do the null-move search, because it would be causing search errors 1/2 the time.

To recapitulate:
1. if the null-move search will fail low, you don't want to do it because it is a waste of time.
2. if the null-move search will fail high and the full search will fail low, you really don't to do it because this is a search error.
3. if both searches will fail high, then you want to do the null-move search if you save nodes.

Overall, you want to do null-move searches if the nodes saved in case 3 are more than the nodes wasted in case 1 and case 2 is rare enough not to adversely affect the search.

If the depth remaining is 1, you do not save enough nodes in case 3 to make null-move worthwhile.

I agree, now that I think of it, it doesn't make much sense to try a null move when depth = 1 because you will get no reduction from it (you will fall right into quiescence either with a null move or a normal move) and you can try another move first with a higher probability of failing high.

There is an advantage for using the null-move. You don't have to generate any moves. And if it happens that the first move you search at depth=1 is a check, then the search gets much more expensive than the null-move search since Crafty extends when it gives check.

I ran a test with crafty searching a test suite to a fixed depth of 13 and got these results which is a 15% improvement:

901088189 total nodes searched
773575166 total nodes searched with no nullmove at depth 1

It is pretty easy to reduce the number of nodes searched to fixed depth. The question, however, is "is this better"? I have it set up to run on the cluster when 8 current runs complete. Probably have some data tomorrow.

In general I agree, but when not doing null-move searches in some cases actually reduces the number of nodes searched, I would find it hard to believe that it made the program weaker, even if testing showed that.
Also, I was wondering if there is some interaction between futility pruning and null-move, which is why you did not see this before.

Not sure. And "futility pruning" has changed dramatically in version 23.1 anyway. I'm trying to finish final testing so we can release it. We are now about +40 Elo over 23.0...

Got some results, and you were absolutely correct. Avoiding nulls at depth=1 is worth about +10 Elo. I am still testing (I try to repeat each test just to make sure I don't get one of those 2-3-4 sigma events that occasionally happen. Currently, with this plus some other changes, 23.1 is now at almost +50 over 23.0...

[Uri Blass]

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.

I ran some statistics with crafty and estimate that a full search takes 10x as many nodes as a null search, but with depth remaining of 1, the null search takes as many nodes as a full search. With some thought, I understood why this is. Obviously, you don't want to do null move unless both the null search and the full search will fail high. So, the null move drops into qsearch while the full search tries moves until one fails high (virtually always the first tried), and goes into qsearch (which also generally fails high on the stand pat score). The difference is one node plus any difference between the two qsearches, which I believe would favor the full search.

Recommendations:
1. Don't try null move if depth remaining is 1.
2. Don't try null move if material is more than about 1.4 pawns below beta, this is where the odds of a null move fail high is less than 1 in 10.

These results are for crafty 23.0, so as always YMMV.

You should test #1. You will be surprised how much it will slow things down. You are not quite right in how you explain it. Assume a null-move search fails high, which means no good captures when you drop right into the q-search. Very fast. Otherwise, you have to actually go to the next ply, and search more than one move. 1/2 of the time you search 'em all, the other half you search just 1 (fail high). It does make a big difference.

I just did try it and it is slightly faster. The null-move fail high does not necessarily mean no good captures, it means that no sequences of captures will drop the evaluation below beta, e.g if the side making the null move had dropped its queen, there may well be captures that win a rook, a knight, or a pawn, and the null move will still fail high. Also it is more like 1 time in 1000 that the null move will fail high and the full search will fail low. If it were 1/2 the time, you would really not want to do the null-move search, because it would be causing search errors 1/2 the time.

To recapitulate:
1. if the null-move search will fail low, you don't want to do it because it is a waste of time.
2. if the null-move search will fail high and the full search will fail low, you really don't to do it because this is a search error.
3. if both searches will fail high, then you want to do the null-move search if you save nodes.

Overall, you want to do null-move searches if the nodes saved in case 3 are more than the nodes wasted in case 1 and case 2 is rare enough not to adversely affect the search.

If the depth remaining is 1, you do not save enough nodes in case 3 to make null-move worthwhile.

I agree, now that I think of it, it doesn't make much sense to try a null move when depth = 1 because you will get no reduction from it (you will fall right into quiescence either with a null move or a normal move) and you can try another move first with a higher probability of failing high.

There is an advantage for using the null-move. You don't have to generate any moves. And if it happens that the first move you search at depth=1 is a check, then the search gets much more expensive than the null-move search since Crafty extends when it gives check.

I ran a test with crafty searching a test suite to a fixed depth of 13 and got these results which is a 15% improvement:

901088189 total nodes searched
773575166 total nodes searched with no nullmove at depth 1

It is pretty easy to reduce the number of nodes searched to fixed depth. The question, however, is "is this better"? I have it set up to run on the cluster when 8 current runs complete. Probably have some data tomorrow.

In general I agree, but when not doing null-move searches in some cases actually reduces the number of nodes searched, I would find it hard to believe that it made the program weaker, even if testing showed that.
Also, I was wondering if there is some interaction between futility pruning and null-move, which is why you did not see this before.

Not sure. And "futility pruning" has changed dramatically in version 23.1 anyway. I'm trying to finish final testing so we can release it. We are now about +40 Elo over 23.0...

Got some results, and you were absolutely correct. Avoiding nulls at depth=1 is worth about +10 Elo. I am still testing (I try to repeat each test just to make sure I don't get one of those 2-3-4 sigma events that occasionally happen. Currently, with this plus some other changes, 23.1 is now at almost +50 over 23.0...

Note that other programs already avoid null move pruning at depth=1

Here are stockfish's conditions for allowing null move pruning

allowNullmove
&& depth > OnePly
&& !isCheck
&& !value_is_mate(beta)
&& ok_to_do_nullmove(pos)
&& approximateEval >= beta - NullMoveMargin)

Uri

[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.

I ran some statistics with crafty and estimate that a full search takes 10x as many nodes as a null search, but with depth remaining of 1, the null search takes as many nodes as a full search. With some thought, I understood why this is. Obviously, you don't want to do null move unless both the null search and the full search will fail high. So, the null move drops into qsearch while the full search tries moves until one fails high (virtually always the first tried), and goes into qsearch (which also generally fails high on the stand pat score). The difference is one node plus any difference between the two qsearches, which I believe would favor the full search.

Recommendations:
1. Don't try null move if depth remaining is 1.
2. Don't try null move if material is more than about 1.4 pawns below beta, this is where the odds of a null move fail high is less than 1 in 10.

These results are for crafty 23.0, so as always YMMV.

You should test #1. You will be surprised how much it will slow things down. You are not quite right in how you explain it. Assume a null-move search fails high, which means no good captures when you drop right into the q-search. Very fast. Otherwise, you have to actually go to the next ply, and search more than one move. 1/2 of the time you search 'em all, the other half you search just 1 (fail high). It does make a big difference.

I just did try it and it is slightly faster. The null-move fail high does not necessarily mean no good captures, it means that no sequences of captures will drop the evaluation below beta, e.g if the side making the null move had dropped its queen, there may well be captures that win a rook, a knight, or a pawn, and the null move will still fail high. Also it is more like 1 time in 1000 that the null move will fail high and the full search will fail low. If it were 1/2 the time, you would really not want to do the null-move search, because it would be causing search errors 1/2 the time.

To recapitulate:
1. if the null-move search will fail low, you don't want to do it because it is a waste of time.
2. if the null-move search will fail high and the full search will fail low, you really don't to do it because this is a search error.
3. if both searches will fail high, then you want to do the null-move search if you save nodes.

Overall, you want to do null-move searches if the nodes saved in case 3 are more than the nodes wasted in case 1 and case 2 is rare enough not to adversely affect the search.

If the depth remaining is 1, you do not save enough nodes in case 3 to make null-move worthwhile.

I agree, now that I think of it, it doesn't make much sense to try a null move when depth = 1 because you will get no reduction from it (you will fall right into quiescence either with a null move or a normal move) and you can try another move first with a higher probability of failing high.

There is an advantage for using the null-move. You don't have to generate any moves. And if it happens that the first move you search at depth=1 is a check, then the search gets much more expensive than the null-move search since Crafty extends when it gives check.

I ran a test with crafty searching a test suite to a fixed depth of 13 and got these results which is a 15% improvement:

901088189 total nodes searched
773575166 total nodes searched with no nullmove at depth 1

It is pretty easy to reduce the number of nodes searched to fixed depth. The question, however, is "is this better"? I have it set up to run on the cluster when 8 current runs complete. Probably have some data tomorrow.

In general I agree, but when not doing null-move searches in some cases actually reduces the number of nodes searched, I would find it hard to believe that it made the program weaker, even if testing showed that.
Also, I was wondering if there is some interaction between futility pruning and null-move, which is why you did not see this before.

Not sure. And "futility pruning" has changed dramatically in version 23.1 anyway. I'm trying to finish final testing so we can release it. We are now about +40 Elo over 23.0...

Got some results, and you were absolutely correct. Avoiding nulls at depth=1 is worth about +10 Elo. I am still testing (I try to repeat each test just to make sure I don't get one of those 2-3-4 sigma events that occasionally happen. Currently, with this plus some other changes, 23.1 is now at almost +50 over 23.0...

Note that other programs already avoid null move pruning at depth=1

Here are stockfish's conditions for allowing null move pruning

allowNullmove
&& depth > OnePly
&& !isCheck
&& !value_is_mate(beta)
&& ok_to_do_nullmove(pos)
&& approximateEval >= beta - NullMoveMargin)

Uri

Not sure what that should imply. "other programs" are using history counters to limit LMR. "other programs" are using what are probably excessive extensions in their search. I know of several people that have jumped off a bridge into a river and drowned.

Should I do the same as all of those?

What we are doing doesn't have to pass the " Areother people doing it?" test. It has to pass the "does it work on the cluster testing?" test. Sometimes those two tests give significantly different answers. I go with the cluster test _every_ time, due to its inherent accuracy.

[Jan Brouwer]

In general I agree, but when not doing null-move searches in some cases actually reduces the number of nodes searched, I would find it hard to believe that it made the program weaker, even if testing showed that.
Also, I was wondering if there is some interaction between futility pruning and null-move, which is why you did not see this before.

Not sure. And "futility pruning" has changed dramatically in version 23.1 anyway. I'm trying to finish final testing so we can release it. We are now about +40 Elo over 23.0...

Got some results, and you were absolutely correct. Avoiding nulls at depth=1 is worth about +10 Elo. I am still testing (I try to repeat each test just to make sure I don't get one of those 2-3-4 sigma events that occasionally happen. Currently, with this plus some other changes, 23.1 is now at almost +50 over 23.0...

How are we ever going to catch up with Crafty if you keep improving it at this pace?

[bob]

In general I agree, but when not doing null-move searches in some cases actually reduces the number of nodes searched, I would find it hard to believe that it made the program weaker, even if testing showed that.
Also, I was wondering if there is some interaction between futility pruning and null-move, which is why you did not see this before.

Not sure. And "futility pruning" has changed dramatically in version 23.1 anyway. I'm trying to finish final testing so we can release it. We are now about +40 Elo over 23.0...

Got some results, and you were absolutely correct. Avoiding nulls at depth=1 is worth about +10 Elo. I am still testing (I try to repeat each test just to make sure I don't get one of those 2-3-4 sigma events that occasionally happen. Currently, with this plus some other changes, 23.1 is now at almost +50 over 23.0...

How are we ever going to catch up with Crafty if you keep improving it at this pace?

Shoot. there are several _I_ am chasing.