Null-moves and zugzwang

[metax]

That depends on what you try to achieve: I am sure you are right that it does not help one bit from the perspective of practical playing strength. It does help in the sense that many simple positions which are never solved without zugzwang verification are solved reasonably fast with zugzwang verification. This is the whole point. I don't like having a program which is unable to find simple wins even when given an infinite amount of time. Given infinite time, a chess program should be able to play perfectly from any position, with no other code changes than increasing a few arrays.

Maybe for that reason, Vincent Diepeeven's double null-move idea would be better because it allows to use null-moves almost everywhere and thus should give an increase in playing strength AND from any position, the engine plays "perfectly" given infinite time because zugzwang positions are seen, even if they're found a few plies later?

[bob]

Based on testing I have done, and am right now repeating, you can throw this idea out. It does not help one bit. More when the test finishes and I can post data. It isYAITDWAA. (Yet Another Idea That Doesn't Work As Advertised).

I'm running the usual test, and am varying the "depth limit" from 2 plies to 9 (in the above snippet the 6*OnePly test becomes N * OnePly where N is varied from 2 to 9 by 1 for 40K games. So far, as N increases, Elo rises. I am also going to test the reduced depth value of 5*OnePly, but suspect that as N goes up again Elo will rise as well as this will reduce the verification search overhead to the point where it is ineffectual.

Thanks for the testing, I am curious to read final results.

What is the verification research depth you are using ? depth-5*OnePly ?

Do you vary also that ?

I first am testing the cutoff depth where this search is not done (6 plies in Stockfish). Second test will vary the depth reduction. So far nothing is better than normal null-move with no verification, as the depth limit gets larger it obviously gets closer, as the two programs are exactly the same except for the addition of the verification code. A value of 99 completely disables it.

One advantage of this is that, while it may not help in games, it will solve some of the zugzwang positions it currently does not solve. Something you could try is using verified null move where you do not now use null move now because of low material, using it for all material except perhaps K+P.

I am testing that as well. Without that change, verified null-move was a complete waste and was worse by 15-20 Elo.

Robert does this mean that in your testing verified null move is somehow doing worse in Stockfish than in Crafty? Because as far as I can see in the last thread about this, you wrote that verified null move was neither a gain nor a loss, and I thought you tested all that in Crafty. Now you measure 15-20 elo worse for verified nullmove.

http://www.talkchess.com/forum/viewtopi ... t=zugzwang

Was this not just about the same test that you are testing now, so the only difference is that it is Stockfish?

Regards, Eelco

OK. Testing is done. Here is what I tried.

First, in Crafty, I added the simple verification search. I then tried varying two parameters. The minimum depth remaining before a verification search is done (glaurung/stockfish use 6 plies I believe) and the reduction used on the search. I started with a minimum depth of 2 plies and worked my way up. That started off at -30 Elo, and as the minimum depth was increased, the Elo asymptotically approached the non-verification-search level. If I set it to 99, then they match within the error bar as expected. Bottom line, it hurts unless you only do it so close to the root that it is infrequently done.

I then tried 5, 6 and 7 in the above test, and for each I then tried reduced-depth searches that varied. The smaller the reduction, the worse the play, the higher the reduction, the better, but again no case was better than non-verified search, and most were worse.

Second, I just commented the code out in Glaurung and Stockfish (I currently use both but am going to just use stockfish in the future if I can find a replacement for Glaurung that doesn't have time loss issues and such.) In both cases, there was very little change, although I could see perhaps +1 to +2 Elo by removing the test, but it would take more games to have a lot of confidence in that number.

My conclusion is that this is just an idea that doesn 't work. The attempt to avoid zugzwang issues is flawed in a basic way so far as I am concerned. If I lop off 5 plies from the verification search, I am going to miss a lot, enough so that I might not recognize the zugzwang at all since I can't see deep enough to spot the "stinger" at the end.

Yes, this might be of some benefit in test positions, if you look at tree sizes for positions where zugzwang is critical. But so far as I can tell, it is an idea that helps in a few positions, hurts in far more positions, so that the overall loss is simply a function of how restrictively it is applied. Stockfish using a remaining depth of at least 6 plies before doing a verification search, along with a depth reduction of 5 plies, seems to have tuned out the bad. And most likely any "good" as well, to make this a benign addition that loses very little, but which clearly gains nothing either.

This is not the first time I have seen this kind of result. Remember my history counter tests with fruit, glaurung, etc as with Crafty. (history counter for LMR decisions).

[bob]

I am testing that as well. Without that change, verified null-move was a complete waste and was worse by 15-20 Elo.

!!!

This is a lot !

I have started a verification of this, actually it seems to much to me, my profiling shows that the time spent in verification is almost zero, the only reason to have that elo difference is not the speed but the bigger tree that is searched with verification (because fewer nodes are pruned by null search).

Anyhow that number 15-20 seems way too much....

Depends on how you limit the verification search. Glaurung does it in the first N plies, leaving the last 5 unverified. If you change 5 to 2, you will lose 30+ elo. If you change to 3, 4, ... the elo loss drops. But then you are verifying less and if the verification search is significantly shallower than the null-move search, if the null-fails high the verification will also and you just waste effort.

So that "30 elo" was based on starting at not verifying only in the last 2 plies, as I worked my way up to the stockfish limit and higher. My measurement on just commenting out the code in stockfish was a +2 Elo gain. But if you change the 5 ply limit to something bigger, you slowly get back that +2 elo until you make it big enough that the verification is never done at all, where you get it all back.

[bob]

Based on testing I have done, and am right now repeating, you can throw this idea out. It does not help one bit.

That depends on what you try to achieve: I am sure you are right that it does not help one bit from the perspective of practical playing strength. It does help in the sense that many simple positions which are never solved without zugzwang verification are solved reasonably fast with zugzwang verification. This is the whole point. I don't like having a program which is unable to find simple wins even when given an infinite amount of time. Given infinite time, a chess program should be able to play perfectly from any position, with no other code changes than increasing a few arrays.

Zugzwang verification is very cheap, both in terms of code complexity and playing strength. I wouldn't want to remove it even if it turned out to cost 5--10 Elo points, and in practice I believe the cost is much smaller. If it does turn out to be more expensive than I think, I would increase the depth reduction and/or the depth limit for zugzwang verification rather than removing it altogether.

But here's the question. Are you willing to give up a couple of Elo in real games, to get this effect in test positions? I'm not. Yet that is exactly what the current implementation of verification costs. And note that my testing is on fairly fast games. It might be worse at deeper time controls depending on how it is tuned. I only ran one long test case, just to see if it was better at longer time controls (ran with and without) and the answer was "no". Whether it can be tuned better is unknown as long games require too much time when trying to adjust a parameter over a signficant range of values.

My goal is max elo. Nothing more, nothing less. If I were worried about test positions, I would have left the various extensions in (mate threat, one legal move, passed pawn pushes) as they clearly made Crafty faster in the WAC-type positions. But in real games they hurt. Some not much, others quite a bit. Anything that doesn't help goes unless there is some reason to keep the code in place. If it hurts, it goes, period.

[bob]

Based on testing I have done, and am right now repeating, you can throw this idea out. It does not help one bit.

That depends on what you try to achieve: I am sure you are right that it does not help one bit from the perspective of practical playing strength. It does help in the sense that many simple positions which are never solved without zugzwang verification are solved reasonably fast with zugzwang verification. This is the whole point. I don't like having a program which is unable to find simple wins even when given an infinite amount of time. Given infinite time, a chess program should be able to play perfectly from any position, with no other code changes than increasing a few arrays.

Zugzwang verification is very cheap, both in terms of code complexity and playing strength. I wouldn't want to remove it even if it turned out to cost 5--10 Elo points, and in practice I believe the cost is much smaller. If it does turn out to be more expensive than I think, I would increase the depth reduction and/or the depth limit for zugzwang verification rather than removing it altogether.

But here's the question. Are you willing to give up a couple of Elo in real games, to get this effect in test positions? I'm not. Yet that is exactly what the current implementation of verification costs. And note that my testing is on fairly fast games. It might be worse at deeper time controls depending on how it is tuned. I only ran one long test case, just to see if it was better at longer time controls (ran with and without) and the answer was "no". Whether it can be tuned better is unknown as long games require too much time when trying to adjust a parameter over a signficant range of values.

My goal is max elo. Nothing more, nothing less. If I were worried about test positions, I would have left the various extensions in (mate threat, one legal move, passed pawn pushes) as they clearly made Crafty faster in the WAC-type positions. But in real games they hurt. Some not much, others quite a bit. Anything that doesn't help goes unless there is some reason to keep the code in place. If it hurts, it goes, period.

Note, I did find a nice +10 Elo change to Crafty's timing that I will explain. I used to have the "time overflow mode" that the Deep Blue guys referred to as "panic time". This was variable extra time allowed depending on the score dropping and how far. I was using a .25 pawn threshold to trigger extra time in Crafty, where it the current score is .25 pawns or more worse than the score for the previous iteration, I would allow 2x longer in an effort to find a better move. Often there is none, but the iteration ends very quickly in those cases, and I do not start a new iteration once I pass the target time anyway. The change was simply setting that threshold to zero. If the current score is worse than the score from the previous iteration, by _any_ amount, I allow extra time.

Here's why it works after I studied it a bit. If you use that .25 cutoff, you are basically saying "I consider any score within .25 of the last score to be acceptable and equivalent." I had carefully gone through a few games and found one example that stood out was a series of moves where the score dropped by .2, then by .1, then by .2, and now I am a half-pawn down and still using the normal target time.

I made this simple change (change the threshold to zero) and tried cluster tests to see what happened. It was a clear +10 elo benefit whether the games were zero-increment or not, whether the games were longer or shorter. I will try to look at the code, but I believe that I now allow 5x the time to improve the score if it drops _any_.

I know what you are thinking "Wait, won't this burn a lot of time?" The answer is "no". Because if the score drops and you can't prevent it, once you have searched the first move to get that score, the rest go by in a flash and you use almost no extra time anyway. The current version (23.1) is now at +25 over 23.0, this represents +10, there is some forward pruning stuff and other changes that account for the rest...

And remember, of course, this +25 is not a guess. It is based on millions of games. Ditto for the +10 for the time overflow change.

[bob]

That depends on what you try to achieve: I am sure you are right that it does not help one bit from the perspective of practical playing strength. It does help in the sense that many simple positions which are never solved without zugzwang verification are solved reasonably fast with zugzwang verification. This is the whole point. I don't like having a program which is unable to find simple wins even when given an infinite amount of time. Given infinite time, a chess program should be able to play perfectly from any position, with no other code changes than increasing a few arrays.

Maybe for that reason, Vincent Diepeeven's double null-move idea would be better because it allows to use null-moves almost everywhere and thus should give an increase in playing strength AND from any position, the engine plays "perfectly" given infinite time because zugzwang positions are seen, even if they're found a few plies later?

More on this topic later. It is on my "to test list"

[zamar]

Second, I just commented the code out in Glaurung and Stockfish (I currently use both but am going to just use stockfish in the future if I can find a replacement for Glaurung that doesn't have time loss issues and such.)

AFAIK the only difference in time management between glaurung and stockfish is related to aspiration window. When Stockfish faces aspiration fail-high/low, it allocates much extra time. With extra short time controls this can result in loss of time (often in already lost position). If this is the only problem you have with the Stockfish I suggest you to disable the aspiration search (it loses 10 - 20 elo points in strength, but should still be much stronger than old glaurung.). This can be done by single line change in search.cpp: (line 661)

- if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN)
+ if (false)

(If this fixes things for you, we could also easily make this ucioption)

In both cases, there was very little change, although I could see perhaps +1 to +2 Elo by removing the test, but it would take more games to have a lot of confidence in that number.

1-2 elo points seems like acceptable trade-off for me. We want engine also to be useful analysis tool.

[bob]

Second, I just commented the code out in Glaurung and Stockfish (I currently use both but am going to just use stockfish in the future if I can find a replacement for Glaurung that doesn't have time loss issues and such.)

AFAIK the only difference in time management between glaurung and stockfish is related to aspiration window. When Stockfish faces aspiration fail-high/low, it allocates much extra time. With extra short time controls this can result in loss of time (often in already lost position). If this is the only problem you have with the Stockfish I suggest you to disable the aspiration search (it loses 10 - 20 elo points in strength, but should still be much stronger than old glaurung.). This can be done by single line change in search.cpp: (line 661)

- if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN)
+ if (false)

(If this fixes things for you, we could also easily make this ucioption)

In both cases, there was very little change, although I could see perhaps +1 to +2 Elo by removing the test, but it would take more games to have a lot of confidence in that number.

1-2 elo points seems like acceptable trade-off for me. We want engine also to be useful analysis tool.

I do not keep engines that lose on time in any of my tests. I might accept 1-2 time losses out of 8,000 games, but more than that and out they go. I am not seeing this problem with any of the programs I currently use.

If I wanted something useful for analysis, I would likely add it in _only_ for analysis. I would not weaken playing mode to improve analysis or vice-versa.

[mcostalba]

Second, I just commented the code out in Glaurung and Stockfish (I currently use both but am going to just use stockfish in the future if I can find a replacement for Glaurung that doesn't have time loss issues and such.)

Please set UCI option "LSN filtering" to false if you don't want Stockfish to lose on time when in big disadvantage and few seconds remain.

In both cases, there was very little change, although I could see perhaps +1 to +2 Elo by removing the test, but it would take more games to have a lot of confidence in that number.

I am still doing the test now, after around 500 games at 1'+0" the version WITH zugzwang verification is ahead of about 6 ELO points.


BTW thanks a lot for testing with Stockfish. If you have any problem with SF setup (as the tendency to lose on time) please tell us, I will do my best to fix it. In this case is easy because is an intended behaviour

[Tord Romstad]

But here's the question. Are you willing to give up a couple of Elo in real games, to get this effect in test positions?

It depends. I don't care any more than you do about solving test positions fast, but I do consider it a serious issue if my program is never able to solve a simple test position, even if given an infinite amount of time.

My goal is max elo. Nothing more, nothing less.

I'm a little bit more nuanced. I wouldn't want to sacrifice 50 Elo points in order to detect all zugzwangs, but I wouldn't hesitate to sacrifice 5 Elo points. It's easy to compensate by doing some improvement elsewhere in the program.

If I were worried about test positions, I would have left the various extensions in (mate threat, one legal move, passed pawn pushes) as they clearly made Crafty faster in the WAC-type positions.

But these are fundamentally different: Extensions are about solving some test positions a little faster, and not about solving positions which wouldn't otherwise have been solvable in any finite amount of time.

But in real games they hurt. Some not much, others quite a bit. Anything that doesn't help goes unless there is some reason to keep the code in place. If it hurts, it goes, period.

I mostly agree, but with some reservations. "If it hurts" right now doesn't mean quite the same as "if it hurts" in some future descendant of the current program. This is an important point, which I'll try to explain in more detail some day when I'm not quite as tired as right now.