Uri Blass wrote:
Considering the fact that null move is recursive
Yes Uri, but you have to be careful here.
LMR is recursive, but null move is getting worst after each call.
At the beginning I give the move to my opponent then I do the search, after a while I _again_ give the move to my opponent, and so on.
After null move the possibility that the null search fails low increases because I always give away free moves, so although is recursive it is also much more easier to break the recursion because after a 2-3 "gifts" to my opponent is easy that null search starts to fail low.
So it is true that is recursive, but is getting harder and harder to recurse, this, for instance, doesn't happens with LMR that is _really_ recursive 100%.
Don wrote:
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.
Don wrote:
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.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Don wrote:
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.
Dann Corbit wrote:
I doubt that 150 Elo will hold, but I guess at least 100 Elo will. Then again, my test was not very extensive.
For me it seems 15 ELO worse than regular nullmove.
Maybe that's because latest deepsjeng is one of the strongest engines on the planet, so just getting a bigger search depth then isn't everything as that's not its strongest point compared to the competition.
On other hand versus all the rybka type clones i guess Stockfish can do better by trying to get similar search depth or getting deeper, is worth more elo than trying to get a tad more stable evaluated lines; it already lost based upon evaluation there anyway, so a bit more stable evaluation doesn't really give the same amount of points then than a small increase of search depth does.
double r = 0.18 * ddepth + 3.1 + log(delta)/5.0;
Balancing this equation is perhaps the next challenge? I need to think about this...
I think that it may be interesting to balance this equation also with
replacing approximateEval = quick_evaluate(pos) by something that is closer to the real evaluation or the real evaluation.
Even if evaluate(pos) is too expensive to calculate then it is not expensive to calculate average difference between quick_evaluate() and evaluate()
for the cases that evaluate() is being calculated and later use the average value for better approximation.
Uri
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.
Unfortunately, I am still waiting on the A/C repairs to happen and can't test this, but once the cluster comes up I can discover exactly what effect this has on Stockfish since I already use it in my cluster testing.
Well Bob, look these engines are just mainline checkers.
If something is a pawn away or something from current PV score, then there's already a reduction by a ply or 8 by default with these engines.
Didn't check latest crafty but i'd guess non mainline, other than reduction factor of nullmove, doesn't get forward pruned *that many plies*.
The way to beat them is to build an engine that doesn't do pure mainline checking, but which also smells other opportunities.
Don wrote:
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 you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
bob wrote:
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.
Don wrote:
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.
bob wrote:
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.
This would be difficult to measure since NM is recursive. One could not count nodes below a NM search of any kind, but that would overlook the recursive computations that are done when NM happens a second time in a single path, etc. I consider NM search to be a normal part of the search, except that it is searching to prove something rather than to find a best move, and save me time overall by avoiding the _real_ search that would be significantly more expensive.