Michel wrote:syzygy wrote: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).