Null-moves and zugzwang

[metax]

Hello,

What is the best way to deal with zugzwang positions in your opinion? I read many ideas now, like double null-move (which doesn't seem to work for me?) and verified null-move pruning (which I have not tried, but there are many negative statements on it). What do you do in your engines?

At the moment I simply do not use null-move pruning in endgames at all, which I do not consider a good solution because it misses much performance and there might be zugzwangs in middlegame positions, too (although they are not that frequent).

[mcostalba]

Hello,

What is the best way to deal with zugzwang positions in your opinion? I read many ideas now, like double null-move (which doesn't seem to work for me?) and verified null-move pruning (which I have not tried, but there are many negative statements on it). What do you do in your engines?

At the moment I simply do not use null-move pruning in endgames at all, which I do not consider a good solution because it misses much performance and there might be zugzwangs in middlegame positions, too (although they are not that frequent).

In Glaurung is done a verification re-search for nodes at high depths:

Code: Select all

       if (nullValue >= beta)
        {
            if &#40;depth < 6 * OnePly&#41;
                return beta;

            // Do zugzwang verification search
            Value v = search&#40;pos, ss, beta, depth-5*OnePly, ply, false, threadID&#41;;
            if &#40;v >= beta&#41;
                return beta;
        &#125; 

This code is from Stockfish that has kept the same behaviour.

[bob]

Hello,

What is the best way to deal with zugzwang positions in your opinion? I read many ideas now, like double null-move (which doesn't seem to work for me?) and verified null-move pruning (which I have not tried, but there are many negative statements on it). What do you do in your engines?

At the moment I simply do not use null-move pruning in endgames at all, which I do not consider a good solution because it misses much performance and there might be zugzwangs in middlegame positions, too (although they are not that frequent).

In Glaurung is done a verification re-search for nodes at high depths:

Code: Select all

       if (nullValue >= beta)
        {
            if &#40;depth < 6 * OnePly&#41;
                return beta;

            // Do zugzwang verification search
            Value v = search&#40;pos, ss, beta, depth-5*OnePly, ply, false, threadID&#41;;
            if &#40;v >= beta&#41;
                return beta;
        &#125; 

This code is from Stockfish that has kept the same behaviour.

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.

[mcostalba]

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 ?

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

[jwes]

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.

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

[Eelco de Groot]

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

[mcostalba]

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

[Tord Romstad]

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.