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.

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.

That's why I spent so much time optimizing Quiesce(). Regular search code is insignificant compared to that... There are so many more qsearch nodes to deal with.

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

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.

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

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

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.

[Pablo Vazquez]

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.

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

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

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

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

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

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.

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