Smooth scaling stockfish

[Michael Sherwin]

There is no chance this is even a 20 ELO improvement at reasonable time controls.

This is very possible, although I am asking myself what is the meaning of a null search at very high depths ?

I mean, if, for instance, I am at depth 7 and do a null search at depth 3 I can see a meaning, but if I am at depth 20 and I do a null search at depth 16 what is the meaning ?

How is possible that a missed tempo can have an influece 16 plies later ? For what I have understood of null move, I think null search is something that can give the clue if a position is under threat, but a threat at 5-10 plies later.

I don't understand how null move can give you a clue position is under threath at a 20 plies search.

At such big depths null search it becomes a kind of LMR....

My thinking is this:

There are deep tactics including mating attacks that are not limited in anyway by depth. A deeper Null Move Search can find the deep tactics that a too shallow NMS will not find. An R in the range of 2 to 3 makes for a 'really fast look-see' that does not sacrifice tactical depth as the ply that are gained to the search make up for that. When R starts to get larger than 3 the additional time saved is less important and the tactics missed are more important as it becomes harder to get extra ply out of the search. If there is some value in Dann's idea it is most likely to be found in the delta term. There will just simply be more moves on average to defend a position with a high delta and less moves to bust it making the reduction safer.

The basic idea is that if you give the opponent two moves in a row, and he can't damage your position with a shallower-than-normal search, then your position is good enough to not search any further. The depth of the search below the null-move is most likely not that significant, and it might be interested to try a fixed-depth search below the null and vary that depth. Once I skip a move, everything changes anyway, and very deep searches are not so useful since the resulting positions are not going to occur anyway. I have for years thought about this idea, since the concept of "R" doesn't really make a lot of sense to me (why accept a 4 ply null-search result in one spot in the tree, and do a 14 ply null-search somewhere else?

This is, among other ideas, on my to-do list. I had planned on doing this for the 23.0 release but we stopped making significant changes to get ready for a tournament, leaving this as a future test. The idea of the reduction is to expend less effort since you are giving your opponent a huge advantage by not making a move. There are still several null-move ideas to be tried, since the depths today are so much deeper than when null-move was first developed.

Search is not yet deep enough to take us beyond not seeing the effects of tactics. Take as an example the simple rook for a knight exchange sacrifice that leads to mate (or winning of material to stop mate) after 20 moves (40 ply). No program can see these kinds of sacrifices and much shallower ones as well. If Null depth is reduced too much then a program may win some games against stronger opponents based on searching more iterations and then turn around and loose more often to weaker programs due to the missed tactics. However, if the R values are picked carefully (i.e. 2,3,5,8) so that an extra ply of search is gained for every increase in R and maybe limit the recursiveness then a real improvement in strength may be achieved.

I consider that to be irrelevant here. You are "skipping" a move. Something impossible in a real game. So you introduce a huge error there, and simply use the so-called "null-move observation" that says "if I give my opponent two moves in a row, but search his second move to a significantly shallower depth than normal, and he is still unable to wreck my position, I am effectively winning.

Most of the null-move fail highs occur due to material imbalance, where you have already won something (or your opponent has simply dropped something, which is extremely common in full-width search). It doesn't take a deep search to convince you that if you give your opponent two moves in a row and he _still_ can't recover whatever advantage he has previously lost, then you are doing well. You don't need a deep search beyond null-move, because the positions beyond null-move are already _all_ broken since a null is not legal.

My comment was made because null-move is being incorrectly explained in what it is doing. Not that I don't believe that a variable value might work better. It is possible. It is not a +50 Elo change however, if it does work. It will be much less.

It really doesn't matter what kind of tactics you see below a null-move, since this is already an inaccurate (but useful) approach to searching. I'm not convinced that it makes sense to do 15 ply searches below some null moves and 3 ply searches below others.

Okay, then this is what I do not understand. It is my move and my opponent if it were his move has an 18 ply mating attack. I only credit him a 14 ply search which says to me that he has no mate and that I am winning. I play into that line and discover the mate threat. I see two possibilities at that point. One, I have a move to save myself or two, there is no saving move. Seems like blind luck to me.

If your opponent has a deep mating attack, you shouldn't be doing null-move. If you do, you are foolish to expect it to detect that. It is not so common to be way ahead in material and still losing. yes it happens, but it is not the "norm" which is why null-move works.

Note that what you describe is a problem for _any_ pruning or reduction algorithm, not just null-move. This is an issue with LMR, with any sort of forward pruning such as futility,etc.

Okay! However, an engine that at iteration depth 18 uses an R of 8 as opposed to an engine that at iteration depth 16 uses an R of 3 will miss lots of really shallow tactics and get eaten alive. Or is this wrong?

[Uri Blass]

I find this _really_ hard to swallow myself. If I turn null-move completely off, it is an 80 Elo reduction over 40,000 games. I find it difficult to imagine how any scaling is going to make the idea 2x _more_ efficient.

IMHO the correct question is "how much theoretical ELO gain could I obtain if null move search returns the value in zero time ?" IOW it takes no time to do a null search.

Of course this is only a theoretical extrapolation to get the theoretical (and never reachable) maximum gain we could have from speeding up null search.

So it could be that null move as is gives 80 ELO _and_ a way to make null search "for free" could give more, say 100 ELO. In reality that number is not reachable but if we find a way to speed up without loosing too much precision could be realistic to think to get at least a part of that 100 ELO points.

Apart from numbers, the thing that I would like to say is that the ELO we gain from null search as a function and the elo we lose due to null search because it costs precious computing time are two independent numbers and is not said that one must be bigger then the other.

For instance I can say that the evaluation gives me 100 ELO points, and that if that evaluation would come free I would (theoretical) gain another 200 ELO points.

I don't know if I have expressed clearly this concept.

In theory if you increase R you may earn more than the theoretical ELO gain from the case that null move search returns the value in zero time.

The reason is that you may save time by pruning some bad moves that have deep threats but have no threat at small depth(you may also lose time by not pruning some bad moves that have threats but not deep threats but it is possible to solve this problem by research,see the end of this post below ***).

I guess that the demage from pruning good moves that have deep threats
is bigger but it is only a guess and not a proved fact and it may be dependent on the game.

I can imagine that there may be a game when moves that have only deep threats(and not threats based on small depth search) are usually bad
but I do not think that chess is a game like that.

***
if you use bigger R you may detect threats that you do not detect with smaller R because moves may have a threat at small depth but not at bigger depth so practically you can try starting with big R but research with smaller R if you find a threat because maybe the threat is going to disappear(and in this case you do not need to search).

Today program use search to depth n-R-1 after null move(when n is the remaining depth before making the null move).

If you want to test more pruning then it is possible to replace it by searching to depth n-R-2 and researching to depth n-R-1 in case that you found a threat.

Uri

[Uri Blass]

There is no chance this is even a 20 ELO improvement at reasonable time controls.

This is very possible, although I am asking myself what is the meaning of a null search at very high depths ?

I mean, if, for instance, I am at depth 7 and do a null search at depth 3 I can see a meaning, but if I am at depth 20 and I do a null search at depth 16 what is the meaning ?

How is possible that a missed tempo can have an influece 16 plies later ? For what I have understood of null move, I think null search is something that can give the clue if a position is under threat, but a threat at 5-10 plies later.

I don't understand how null move can give you a clue position is under threath at a 20 plies search.

At such big depths null search it becomes a kind of LMR....

My thinking is this:

There are deep tactics including mating attacks that are not limited in anyway by depth. A deeper Null Move Search can find the deep tactics that a too shallow NMS will not find. An R in the range of 2 to 3 makes for a 'really fast look-see' that does not sacrifice tactical depth as the ply that are gained to the search make up for that. When R starts to get larger than 3 the additional time saved is less important and the tactics missed are more important as it becomes harder to get extra ply out of the search. If there is some value in Dann's idea it is most likely to be found in the delta term. There will just simply be more moves on average to defend a position with a high delta and less moves to bust it making the reduction safer.

The basic idea is that if you give the opponent two moves in a row, and he can't damage your position with a shallower-than-normal search, then your position is good enough to not search any further. The depth of the search below the null-move is most likely not that significant, and it might be interested to try a fixed-depth search below the null and vary that depth. Once I skip a move, everything changes anyway, and very deep searches are not so useful since the resulting positions are not going to occur anyway. I have for years thought about this idea, since the concept of "R" doesn't really make a lot of sense to me (why accept a 4 ply null-search result in one spot in the tree, and do a 14 ply null-search somewhere else?

This is, among other ideas, on my to-do list. I had planned on doing this for the 23.0 release but we stopped making significant changes to get ready for a tournament, leaving this as a future test. The idea of the reduction is to expend less effort since you are giving your opponent a huge advantage by not making a move. There are still several null-move ideas to be tried, since the depths today are so much deeper than when null-move was first developed.

Search is not yet deep enough to take us beyond not seeing the effects of tactics. Take as an example the simple rook for a knight exchange sacrifice that leads to mate (or winning of material to stop mate) after 20 moves (40 ply). No program can see these kinds of sacrifices and much shallower ones as well. If Null depth is reduced too much then a program may win some games against stronger opponents based on searching more iterations and then turn around and loose more often to weaker programs due to the missed tactics. However, if the R values are picked carefully (i.e. 2,3,5,8) so that an extra ply of search is gained for every increase in R and maybe limit the recursiveness then a real improvement in strength may be achieved.

I consider that to be irrelevant here. You are "skipping" a move. Something impossible in a real game. So you introduce a huge error there, and simply use the so-called "null-move observation" that says "if I give my opponent two moves in a row, but search his second move to a significantly shallower depth than normal, and he is still unable to wreck my position, I am effectively winning.

Most of the null-move fail highs occur due to material imbalance, where you have already won something (or your opponent has simply dropped something, which is extremely common in full-width search). It doesn't take a deep search to convince you that if you give your opponent two moves in a row and he _still_ can't recover whatever advantage he has previously lost, then you are doing well. You don't need a deep search beyond null-move, because the positions beyond null-move are already _all_ broken since a null is not legal.

My comment was made because null-move is being incorrectly explained in what it is doing. Not that I don't believe that a variable value might work better. It is possible. It is not a +50 Elo change however, if it does work. It will be much less.

It really doesn't matter what kind of tactics you see below a null-move, since this is already an inaccurate (but useful) approach to searching. I'm not convinced that it makes sense to do 15 ply searches below some null moves and 3 ply searches below others.

Okay, then this is what I do not understand. It is my move and my opponent if it were his move has an 18 ply mating attack. I only credit him a 14 ply search which says to me that he has no mate and that I am winning. I play into that line and discover the mate threat. I see two possibilities at that point. One, I have a move to save myself or two, there is no saving move. Seems like blind luck to me.

If your opponent has a deep mating attack, you shouldn't be doing null-move. If you do, you are foolish to expect it to detect that. It is not so common to be way ahead in material and still losing. yes it happens, but it is not the "norm" which is why null-move works.

Note that what you describe is a problem for _any_ pruning or reduction algorithm, not just null-move. This is an issue with LMR, with any sort of forward pruning such as futility,etc.

Okay! However, an engine that at iteration depth 18 uses an R of 8 as opposed to an engine that at iteration depth 16 uses an R of 3 will miss lots of really shallow tactics and get eaten alive. Or is this wrong?

I do not know but I do not like the solution of null move pruning at high depth.

It may make the program blind to zugzwang.

I wonder if it is not better to use some multi-cut pruning at high depth when the idea is to reduce the move if you find many refutations at small depth(usually moves that are refuted by null move also have many refutation at small depth)

Instead of searching null move and after it searching to depth n-R-1 it may be better or not better to search if the move has at least K refutations at depth n-R-T for some values of K and T)

Uri

[jwes]

Has anyone tried comparing this stockfish to a regular stockfish on a tactical test set? I know that generally test sets are not a good way to compare engine strengths, but for the specific purpose of seeing how much reductions or pruning hurt you tactically, they can be useful.

[bob]

There is no chance this is even a 20 ELO improvement at reasonable time controls.

This is very possible, although I am asking myself what is the meaning of a null search at very high depths ?

I mean, if, for instance, I am at depth 7 and do a null search at depth 3 I can see a meaning, but if I am at depth 20 and I do a null search at depth 16 what is the meaning ?

How is possible that a missed tempo can have an influece 16 plies later ? For what I have understood of null move, I think null search is something that can give the clue if a position is under threat, but a threat at 5-10 plies later.

I don't understand how null move can give you a clue position is under threath at a 20 plies search.

At such big depths null search it becomes a kind of LMR....

My thinking is this:

There are deep tactics including mating attacks that are not limited in anyway by depth. A deeper Null Move Search can find the deep tactics that a too shallow NMS will not find. An R in the range of 2 to 3 makes for a 'really fast look-see' that does not sacrifice tactical depth as the ply that are gained to the search make up for that. When R starts to get larger than 3 the additional time saved is less important and the tactics missed are more important as it becomes harder to get extra ply out of the search. If there is some value in Dann's idea it is most likely to be found in the delta term. There will just simply be more moves on average to defend a position with a high delta and less moves to bust it making the reduction safer.

The basic idea is that if you give the opponent two moves in a row, and he can't damage your position with a shallower-than-normal search, then your position is good enough to not search any further. The depth of the search below the null-move is most likely not that significant, and it might be interested to try a fixed-depth search below the null and vary that depth. Once I skip a move, everything changes anyway, and very deep searches are not so useful since the resulting positions are not going to occur anyway. I have for years thought about this idea, since the concept of "R" doesn't really make a lot of sense to me (why accept a 4 ply null-search result in one spot in the tree, and do a 14 ply null-search somewhere else?

This is, among other ideas, on my to-do list. I had planned on doing this for the 23.0 release but we stopped making significant changes to get ready for a tournament, leaving this as a future test. The idea of the reduction is to expend less effort since you are giving your opponent a huge advantage by not making a move. There are still several null-move ideas to be tried, since the depths today are so much deeper than when null-move was first developed.

Search is not yet deep enough to take us beyond not seeing the effects of tactics. Take as an example the simple rook for a knight exchange sacrifice that leads to mate (or winning of material to stop mate) after 20 moves (40 ply). No program can see these kinds of sacrifices and much shallower ones as well. If Null depth is reduced too much then a program may win some games against stronger opponents based on searching more iterations and then turn around and loose more often to weaker programs due to the missed tactics. However, if the R values are picked carefully (i.e. 2,3,5,8) so that an extra ply of search is gained for every increase in R and maybe limit the recursiveness then a real improvement in strength may be achieved.

I consider that to be irrelevant here. You are "skipping" a move. Something impossible in a real game. So you introduce a huge error there, and simply use the so-called "null-move observation" that says "if I give my opponent two moves in a row, but search his second move to a significantly shallower depth than normal, and he is still unable to wreck my position, I am effectively winning.

Most of the null-move fail highs occur due to material imbalance, where you have already won something (or your opponent has simply dropped something, which is extremely common in full-width search). It doesn't take a deep search to convince you that if you give your opponent two moves in a row and he _still_ can't recover whatever advantage he has previously lost, then you are doing well. You don't need a deep search beyond null-move, because the positions beyond null-move are already _all_ broken since a null is not legal.

My comment was made because null-move is being incorrectly explained in what it is doing. Not that I don't believe that a variable value might work better. It is possible. It is not a +50 Elo change however, if it does work. It will be much less.

It really doesn't matter what kind of tactics you see below a null-move, since this is already an inaccurate (but useful) approach to searching. I'm not convinced that it makes sense to do 15 ply searches below some null moves and 3 ply searches below others.

Okay, then this is what I do not understand. It is my move and my opponent if it were his move has an 18 ply mating attack. I only credit him a 14 ply search which says to me that he has no mate and that I am winning. I play into that line and discover the mate threat. I see two possibilities at that point. One, I have a move to save myself or two, there is no saving move. Seems like blind luck to me.

If your opponent has a deep mating attack, you shouldn't be doing null-move. If you do, you are foolish to expect it to detect that. It is not so common to be way ahead in material and still losing. yes it happens, but it is not the "norm" which is why null-move works.

Note that what you describe is a problem for _any_ pruning or reduction algorithm, not just null-move. This is an issue with LMR, with any sort of forward pruning such as futility,etc.

Okay! However, an engine that at iteration depth 18 uses an R of 8 as opposed to an engine that at iteration depth 16 uses an R of 3 will miss lots of really shallow tactics and get eaten alive. Or is this wrong?

No idea. I have always found that R > 3 worsens results when I have done testing on the idea...

[Greg Strong]

So did this idea ever get tested enough to actually make a determination?

[Dann Corbit]

So did this idea ever get tested enough to actually make a determination?

I think that the answer is no.

Some people have tested and shown a significant improvement with enough games for statistical significance. Other people have tested and show little or no improvment, also with a large number of games. I am not sure what to think about it.

I made a version that allows the parameters to be tested as UCI values and I also plan to make a self-calibrating version. Eventually, I will test the spots off of it, but I don't have the time right now.

[Eelco de Groot]

So did this idea ever get tested enough to actually make a determination?

The last CCRL result I saw with Dann's version was a while back, I think it was from Graham but not sure, it showed a difference of exactly one elopoint at that time. So it seems neither a big improvement nor a big loss, just a good alternative to investigate or do something different. Dann's changes from his last version are still in my copy of Rainbow Serpent. I don't know if that will be out soon, maybe there will be new patches from Marco and Joona in the near future if the UCI handling is not yet bugfree as it seems Pascal still had problems with SCID Stockfish, not yet specified. I do not know.

There is still a fundamental problem how sensitive Stockfish's new search is to Zugzwang in general, compared to Stockfish 1.5. I don't have any data on that myself, but it is related I think to Dann's changes, to how large R can be made to still function well. Also the general search is very sensitive to small changes in the null window search. Much more so than the PV-search which after all only deals with a very small percentage of all nodes. Tuning is very important.

Eelco

[Eelco de Groot]

I think I just saw someone from the CCRL passing by here, I just wanted to add my thanks to this post, to the CCRL and to the CEGT for testing all the Stockfish versions. That is invaluable data for making some progress.

A Big thanks to all the men and women testing out there !!

Regards,
Eelco