Null-moves and zugzwang

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Null-moves and zugzwang

Post by metax » Fri Sep 25, 2009 8:58 pm

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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Null-moves and zugzwang

Post by mcostalba » Fri Sep 25, 2009 9:08 pm

metax wrote: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
Posts: 20475
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null-moves and zugzwang

Post by bob » Sat Sep 26, 2009 5:35 pm

mcostalba wrote:
metax wrote: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 &#40;nullValue >= beta&#41;
        &#123;
            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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Null-moves and zugzwang

Post by mcostalba » Sat Sep 26, 2009 5:52 pm

bob wrote: 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
Posts: 20475
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null-moves and zugzwang

Post by bob » Sat Sep 26, 2009 6:36 pm

mcostalba wrote:
bob wrote: 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
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: Null-moves and zugzwang

Post by jwes » Sat Sep 26, 2009 8:37 pm

bob wrote:
mcostalba wrote:
bob wrote: 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
Posts: 20475
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null-moves and zugzwang

Post by bob » Sun Sep 27, 2009 12:08 am

jwes wrote:
bob wrote:
mcostalba wrote:
bob wrote: 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.

User avatar
Eelco de Groot
Posts: 4148
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Null-moves and zugzwang

Post by Eelco de Groot » Sun Sep 27, 2009 1:51 am

bob wrote:
jwes wrote:
bob wrote:
mcostalba wrote:
bob wrote: 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
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Null-moves and zugzwang

Post by mcostalba » Sun Sep 27, 2009 6:36 am

bob wrote: 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
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Null-moves and zugzwang

Post by Tord Romstad » Sun Sep 27, 2009 10:53 am

bob wrote: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.

Post Reply