To recapitulate.
If white's DTZ goes from even to even, DTZ is lowered by at least 2 ply.
From odd to odd, the same applies.
From odd to even, DTZ is lowered by at least 1.
From even to odd, DTZ is lowered by at least 3.
You can't have two odd to even transitions without an even to odd transition in between.
So in aggregate, at most 1 ply can be lost.
Syzygy probing code: DTZ in some cursed endgames off by one?
Moderators: hgm, Rebel, chrisw
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Syzygy probing code: DTZ in some cursed endgames off by
Thanks a lot. That is really clever!! I had not noticed the switch from dtz=odd to dtz=even if the winning player makes a sub-optimal move.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Syzygy probing code: DTZ in some cursed endgames off by
Code: Select all
// This means that if dtz > 0 is returned, the position is certainly
// a win if dtz + 50-move-counter <= 99. Care must be taken that the engine
// picks moves that preserve dtz + 50-move-counter <= 99.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Syzygy probing code: DTZ in some cursed endgames off by
True, it should have said that if there are moves for which the sum is <= 99, then one of those movers should be picked. If there are none (but there were in the past), then the moves that have the sum = 100 will preserve the win (but the engine will not be aware of that (unless it remembers it was winning earlier in the game), so will probably have to display a draw score).
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Syzygy probing code: DTZ in some cursed endgames off by
In fact I am not sure if my own comment is correct. It seems sum=99 and real-dtz=odd may be fatal. It means that 50-move-counter+real-dtz=100 so the winning player cannot afford to make a move that does not lower real-dtz but he does not know how to do this (except by doing a 2-ply search).
I am worried that the situation sum=99 and real-dtz=odd may occur if the engine played suboptimally (in the dtz sense) before (e.g by using heuristic search to get more natural play).
I am worried that the situation sum=99 and real-dtz=odd may occur if the engine played suboptimally (in the dtz sense) before (e.g by using heuristic search to get more natural play).
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Syzygy probing code: DTZ in some cursed endgames off by
A reported DTZ of n might correspond to an actual value of n+1, so if a calculated sum dtz + cnt50 of 99 really means 100 AND the situation corresponds to what I described as the odd case, then it would appear to be possible to slip to an actual sum of 101.
I suspect this situation would correspond to the even case, though. But I will have a better look at this later.
I suspect this situation would correspond to the even case, though. But I will have a better look at this later.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Syzygy probing code: DTZ in some cursed endgames off by
Don't worry, I'll check it myself. You are probably correct that odd-even have been exchanged in the prior discussion (which solves the problem). Thanks for explaining.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Syzygy probing code: DTZ in some cursed endgames off by
Not unrelated to this discussion is the fact that the DTZ tables store information only for one side to move. This table encodes 0/1/2 as 0, 3/4 as 1, 5/6 as 2, 7/8 as 3, ..., 99/100 as 49. The values for the other side to move are determined by a 1-ply search.
Suppose the table stores information for white to move and that white is winning.
An example of a critical situation is cnt50 = 94, real-dtz = 6, reported-dtz = 5. Is white guaranteed to find a move with real-dtz = 5? (If it plays a move with real-dtz=6, the next position will be a cursed win since 95 + 6 > 100.)
White's best move leads to a position with black to move and real-dtz = 5. Since a DTZ probe for a position with black to move requires a 1-ply search, the reported-dtz of the position will correspond to the position with white to move after black's best move. Black's best move leads to a position with real-dtz=4 and reported-dtz = 3. Backing this up leads to a reported-dtz=4 for the position of black after white's best move (the one that has real-dtz=5).
If white has a dangerous suboptimal move leading to a position with real-dtz=6, probing that position for black corresponds to probing a position with real-dtz=5 and reported-dtz=5 for white. So the position after the suboptimal move will have reported-dtz = 6.
In other words, the engine is indeed able to detect the best move in the critical situation.
In the other case, where white is winning and the DTZ table stores information for black to move, the reasoning will be similar.
Suppose the table stores information for white to move and that white is winning.
An example of a critical situation is cnt50 = 94, real-dtz = 6, reported-dtz = 5. Is white guaranteed to find a move with real-dtz = 5? (If it plays a move with real-dtz=6, the next position will be a cursed win since 95 + 6 > 100.)
White's best move leads to a position with black to move and real-dtz = 5. Since a DTZ probe for a position with black to move requires a 1-ply search, the reported-dtz of the position will correspond to the position with white to move after black's best move. Black's best move leads to a position with real-dtz=4 and reported-dtz = 3. Backing this up leads to a reported-dtz=4 for the position of black after white's best move (the one that has real-dtz=5).
If white has a dangerous suboptimal move leading to a position with real-dtz=6, probing that position for black corresponds to probing a position with real-dtz=5 and reported-dtz=5 for white. So the position after the suboptimal move will have reported-dtz = 6.
In other words, the engine is indeed able to detect the best move in the critical situation.
In the other case, where white is winning and the DTZ table stores information for black to move, the reasoning will be similar.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Syzygy probing code: DTZ in some cursed endgames off by
Thanks. So it seems that in the end it is still a 2-ply search (which is needed anyway since only half the positions are stored) that saves the day... So maybe the clever reasoning that we lose only one ply is not necessary after all...
It would be nice is this were better documented. Perhaps I'll give it a shot...
It would be nice is this were better documented. Perhaps I'll give it a shot...
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Syzygy probing code: DTZ in some cursed endgames off by
All this craziness just to save 1 bit?
Probably you have measured the saved space and probably we are talking of some tens or hundred of MB..otherwise I really can't understand this design choice...
Probably you have measured the saved space and probably we are talking of some tens or hundred of MB..otherwise I really can't understand this design choice...