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

[niklasf]

An example KPPvKP position:

[d]8/8/1k2P2K/6P1/8/3p4/8/8 b - - 0 1

Generating works fine. In the statistics:

Code: Select all

[...]
Longest cursed win for white: 105 ply; 8/8/1k2P2K/6P1/8/3p4/8/8 b - -
[...]

The ply 105 (that is 100 for the blessed loss + 5) is correct.

However the probing code is one ply short. For example output from fathom:

Code: Select all

[...]
[WDL "BlessedLoss"]
[DTZ "104"]
[WinningMoves ""]
[DrawingMoves "Kc6, Kc7"]
[LosingMoves "Ka5, Kb5, Kc5, Ka6, Ka7, Kb7, d2"]

1... Kc6 2. Kg6 Kd6 3. Kf7 d2 4. e7 d1=Q 5. e8=Q Qd5 6. Kg6 [...]

Following the DTZ mainline the error is corrected (and also has no impact on practical play): 104, 103, 102, 101, 101, Zeroing move

Is it possible that the probing code in tbprobe.cpp l. 497

Code: Select all

dtz = 1 + probe_dtz_table(pos, wdl, success);
if (*success >= 0) {
  if (wdl & 1) dtz += 100;  // XXX
  return wdl >= 0 ? dtz : -dtz;
}

should add 101 instead of 100?

Best,
Niklas

More positions courtesy of Guy Haworth:
8/8/8/1B6/8/8/K1p5/B2k4 w - - 0 1
8/8/3B4/K7/8/8/1pk3B1/8 b - - 0 1
8/8/1k2P2K/6P1/8/3p4/8/8 b - - 0 1

[syzygy]

Code: Select all

// Probe the DTZ table for a particular position.
// If *success != 0, the probe was successful.
// The return value is from the point of view of the side to move:
//         n < -100 &#58; loss, but draw under 50-move rule
// -100 <= n < -1   &#58; loss in n ply &#40;assuming 50-move counter == 0&#41;
//         0	     &#58; draw
//     1 < n <= 100 &#58; win in n ply &#40;assuming 50-move counter == 0&#41;
//   100 < n        &#58; win, but draw under 50-move rule
//
// The return value n can be off by 1&#58; a return value -n can mean a loss
// in n+1 ply and a return value +n can mean a win in n+1 ply. This
// cannot happen for tables with positions exactly on the "edge" of
// the 50-move rule.

If -100 <= n <= 100, then n can be off by one unless the table has a position exactly 100 ply away from a win or loss.

If n < -100 or n > 100, then the position is a draw under the 50-move rule and a loss or win without the 50-move rule. The precise meaning of n is complicated, so not mentioned. So strictly speaking in those ranges n cannot be "off by one" from anything promised.

The complicated meaning of n > 100 is that the position is either n ply away from a winning zeroing move (capture or pawn move) or n - 100 ply away from a zeroing move into a cursed win. And indeed n can be off by one. Similar for n < -100.

This is by design. Throwing away the least significant bit whenever possible improves compression of the DTZ tables.

Theoretically it may lead to the engine taking 1 ply more than optimal to reach the next winning zeroing move. If the last zeroing move led to a winning position, then this cannot lead to a 50-move draw (because there is no "off by one" for winning positions if at least one position has dtz=100). But if the last zeroing move led to a "cursed win" and the opponent does not play optimally, there is a theoretical possibility that the engine at some point reaches a position exactly on the edge and then takes 1 ply too many. (Between two zeroing moves, at most 1 ply can be lost.)

[niklasf]

Thank you for the prompt reply.

[jshriver]

What is a cursed endgame position? Curious never heard the phrase before.

[hgm]

A cursed win is a win if it were not for the 50-move rule.

[jshriver]

A cursed win is a win if it were not for the 50-move rule.

Ah, thank you very much. Makes sense.

Glad to see you're still running the monthly tournaments. Going to try and watch it tomorrow.

[Michel]

Code: Select all

// Probe the DTZ table for a particular position.
// If *success != 0, the probe was successful.
// The return value is from the point of view of the side to move:
//         n < -100 &#58; loss, but draw under 50-move rule
// -100 <= n < -1   &#58; loss in n ply &#40;assuming 50-move counter == 0&#41;
//         0	     &#58; draw
//     1 < n <= 100 &#58; win in n ply &#40;assuming 50-move counter == 0&#41;
//   100 < n        &#58; win, but draw under 50-move rule
//
// The return value n can be off by 1&#58; a return value -n can mean a loss
// in n+1 ply and a return value +n can mean a win in n+1 ply. This
// cannot happen for tables with positions exactly on the "edge" of
// the 50-move rule.

If -100 <= n <= 100, then n can be off by one unless the table has a position exactly 100 ply away from a win or loss.

If n < -100 or n > 100, then the position is a draw under the 50-move rule and a loss or win without the 50-move rule. The precise meaning of n is complicated, so not mentioned. So strictly speaking in those ranges n cannot be "off by one" from anything promised.

The complicated meaning of n > 100 is that the position is either n ply away from a winning zeroing move (capture or pawn move) or n - 100 ply away from a zeroing move into a cursed win. And indeed n can be off by one. Similar for n < -100.

This is by design. Throwing away the least significant bit whenever possible improves compression of the DTZ tables.

Theoretically it may lead to the engine taking 1 ply more than optimal to reach the next winning zeroing move. If the last zeroing move led to a winning position, then this cannot lead to a 50-move draw (because there is no "off by one" for winning positions if at least one position has dtz=100). But if the last zeroing move led to a "cursed win" and the opponent does not play optimally, there is a theoretical possibility that the engine at some point reaches a position exactly on the edge and then takes 1 ply too many. (Between two zeroing moves, at most 1 ply can be lost.)

I am sorry for bumping this very old thread. I am trying to understand a bit better the syzygy file format (perhaps for writing some notes about it).

I have a question for Ronald. If you only store int(dtz/2) how does DTZ optimal play work ? Assume we are in a winning position. So we have at least one move that reduces dtz by 1. However if dtz is odd then int((dtz-1)/2)=int(dtz/2). So how can we recognize the dtz optimal moves? Clearly I am misunderstanding something

[syzygy]

The short answer: the moves come in pairs: winning, losing. Moves by the losing side are always optimal (or worse!). So the engine is guaranteed to get DTZ/2 lower by at least 1 on each move (2 ply).

This is not a fully developed argument but it can be made to work. I might work out the full proof later.

[Michel]

The short answer: the moves come in pairs: winning, losing. Moves by the losing side are always optimal (or worse!). So the engine is guaranteed to get DTZ/2 lower by at least 1 on each move (2 ply).

This is not a fully developed argument but it can be made to work. I might work out the full proof later.

Ok! This I had also worked out. But this seems to require a 2-ply search to make it work. Is that correct?

[syzygy]

The short answer: the moves come in pairs: winning, losing. Moves by the losing side are always optimal (or worse!). So the engine is guaranteed to get DTZ/2 lower by at least 1 on each move (2 ply).

This is not a fully developed argument but it can be made to work. I might work out the full proof later.

Ok! This I had also worked out. But this seems to require a 2-ply search to make it work. Is that correct?

Yes, the argument I gave is probably not the best.

I try again. Let's say white is winning and the table stores DTZ/2 (rounded down).

If white is to move and DTZ=2n, then white's best move has DTZ=2n-1, which will be the move in the table with DTZ/2 = n-1. So white is sure to pick the best move, black will lower DTZ by at least another ply, and after 2 ply we are in DTZ<=2n-2. If equal to 2n-2, we are back in the even case which is great. If smaller than 2n-2 we might be in the odd case, but we win at least 1 ply compared to perfect play by black.

If white is to move and DTZ=2n+1, then white's best move has DTZ=2n. In the table this is indistinguishable from moves with DTZ=2n+1. So white might be unlucky and pick a move to a position with DTZ=2n+1. Now black will decrease DTZ by at least 1 ply. In the worst case, we lose a ply compared to perfect play, but then we end up in the even case DTZ=2n.

So starting from the even case, we always keep up with perfect play. Starting from the odd case, we may lose 1 ply the first time we slip into the even case. But slipping back into the odd case wins at least 1 ply, which compensates for any later slipping to the even case. In other words, over the whole sequence of moves to the next zeroing move at most 1 ply is lost.

(If the table has a DTZ=100 position, this inaccuracy is not present. The only way to lose half a point is if there is an amount of inaccurate play after entering a TB that does not have a DTZ=100 position. Everything is possible, but this is such a minor case that I decided to take the compression gain).