Leapfrog: Retrograde Analysis

Retrograde Analysis

Building a tablebase starts by identifying the positions that are 'immediately' lost, i.e. lost(0) positions. Positions where black is checkmated definitely belong in this class. With the DTM metric, they are the only lost(0) positions. With other metrics, like DTC or DTZ, other events are considered immediate wins as well (namely capturing a piece in a way that wins, or pushing a pawn in a way that wins, respectively).

After identifying the lost(0) positions we iterate a number of 'cycles', deriving lost(N+1) from lost(N) positions for N=0, 1, ..., until we find no lost(N+1) positions anymore. This cycle consists of two steps: first we derive newly-won positions from the lost(N). Every parent of a lost(N) position is a won position, as white wins even if he has only one move that wins. But it could be that some or all of the parents of a lost(N) position are won in a smaller number of moves, through another move than the one leading to the lost(N) position of which it is the parent. In that case we would have already declared that position won in an earlier cycle. SO to get the newly-won positions, we only have to consider the parents of a lost(N) that were not yet won.

In the second step, we derive the lost(N+1) positions from the newly-won positions found in the previous step. This is more complicated. The parents of the newly-won positions are not automatically lost(N+1). They are only 'potentially-lost(N+1)', meaning that black has at least one move that loses (namely the one leading to the newly-won position of which it was the parent). But usually black has other moves from this position, and even if there is only one move that leads to a position that is not won (or won in a larger number of moves, so that we do not know it is won yet), then the parent position is not lost(N+1). We thus have to 'verify' the potehtially-lost(N+1) positions (third step), to make sure all black's moves lead to won or newly-won positions.

We thus see that a cycle requires the building of a 3-ply tree: one white unmove, one black unmove, and then a black forward move. The first two levels of this tree have to consider all moves always. The third level can have a cut-off: as soon as we find one black move that saves black, by reaching a position that was not won (for white!), we know the position is not lost(N+1), and we do not have to consider any other black moves.

Fig. 4 - Three-ply retrograde tree, folded back onto the same won set. The won info serves both to block branches after ply 1, and to probe for escapes in ply 3.