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).
Null-moves and zugzwang
Moderators: hgm, Rebel, chrisw
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Null-moves and zugzwang
In Glaurung is done a verification re-search for nodes at high depths: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).
Code: Select all
if (nullValue >= beta)
{
if (depth < 6 * OnePly)
return beta;
// Do zugzwang verification search
Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
if (v >= beta)
return beta;
}
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Null-moves and zugzwang
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).mcostalba wrote:In Glaurung is done a verification re-search for nodes at high depths: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).
This code is from Stockfish that has kept the same behaviour.Code: Select all
if (nullValue >= beta) { if (depth < 6 * OnePly) return beta; // Do zugzwang verification search Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID); if (v >= beta) return beta; }
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.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Null-moves and zugzwang
Thanks for the testing, I am curious to read final results.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.
What is the verification research depth you are using ? depth-5*OnePly ?
Do you vary also that ?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Null-moves and zugzwang
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.mcostalba wrote:Thanks for the testing, I am curious to read final results.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.
What is the verification research depth you are using ? depth-5*OnePly ?
Do you vary also that ?
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Null-moves and zugzwang
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 wrote: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.mcostalba wrote:Thanks for the testing, I am curious to read final results.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.
What is the verification research depth you are using ? depth-5*OnePly ?
Do you vary also that ?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Null-moves and zugzwang
I am testing that as well. Without that change, verified null-move was a complete waste and was worse by 15-20 Elo.jwes wrote: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 wrote: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.mcostalba wrote:Thanks for the testing, I am curious to read final results.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.
What is the verification research depth you are using ? depth-5*OnePly ?
Do you vary also that ?
-
- Posts: 4567
- Joined: Sun Mar 12, 2006 2:40 am
- Full name:
Re: Null-moves and zugzwang
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.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.jwes wrote: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 wrote: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.mcostalba wrote:Thanks for the testing, I am curious to read final results.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.
What is the verification research depth you are using ? depth-5*OnePly ?
Do you vary also that ?
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
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Null-moves and zugzwang
!!!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....
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: Null-moves and zugzwang
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.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.
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.