Syzygy probing code: DTZ in some cursed endgames off by one?

[syzygy]

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.

[Michel]

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.

[Michel]

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.

But is this comment correct then? If the real dtz is odd then there is no move that strictly lowers the stored dtz. So it seems stored-dtz+50-move-counter may in fact become 100 temporarily.

[syzygy]

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

[Michel]

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

[syzygy]

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.

[Michel]

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.

[syzygy]

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.

[Michel]

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

[mcostalba]

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