reverse perft

[brtzsnr]

Does anyone have results for reverse perft? I.e. a perft for which the moves the moves are done in reverse. For pawns it should handle unpromoting, and for king uncastling.

[sje]

It would be fairly straightforward to write one. Everyone who has written a tablebase generator has written a reverse move generator, and that's the only thing needed to make a perft program a retroperft program.

Much more interesting would be to use a reverse move generator as part of a program which would accept a chess position and then use various search techniques to find a path from the initial array to the given position. Note that not all positions have a solution.

[brtzsnr]

I don't think it's easy. Captures are very hard since it needs at least to look at if it's possible to reach the position from that capture. E.g. from the following invalid position you can reach the start position:

[d]rnbqkbnr/pppppppp/8/8/8/5N2/PPPPPPPP/RNBQKBnR w KQkq -

[sje]

That position would be rejected on input as it has 17 black men.

[Uri Blass]

That position would be rejected on input as it has 17 black men.

It is simple but there are things that are not so simple

For example the second position is invalid because the bishop has no way to get to a8 in the previous move so the reverse perft should not produce
Kb7xa8(a8=bishop)

[D]K7/8/8/3k4/8/8/8/8 b - - 14 1

[D]b7/1K6/8/3k4/8/8/8/8 w - - 14 1

Unlike this example
the following position is clearly legal when black last move was simply underpromotion to bishop.

[D]8/8/8/3k4/8/8/1K6/b7 w - - 14 1

[stegemma]

It is nearly impossible to compute all positions from a final one to the start. The two kings position is a sample of this: you can reach that position almost in any legal way. Anytime that you have a QRBN on the 8th (or first) rank you cannot know if it is a "genuine" piece or a promoted pawn, to revert its last move.

Finding a single legal path to the origin could be different, but this is not related to perft, direct or reverted.

[syzygy]

For example the second position is invalid because the bishop has no way to get to a8 in the previous move so the reverse perft should not produce

I don't see why reverse perft should not produce the second position, even though that position is impossible to reach from the starting position. What has the starting position to do with perft / reverse perft?

Perft is well-defined for any position where the side to move cannot immediately capture the opponent king, including for positions that cannot be reached from the starting position. So perft 1 from your second position should produce your first position. And so reverse perft 1 from your first position should produce your second position.

[Sven]

For example the second position is invalid because the bishop has no way to get to a8 in the previous move so the reverse perft should not produce

I don't see why reverse perft should not produce the second position, even though that position is impossible to reach from the starting position. What has the starting position to do with perft / reverse perft?

Perft is well-defined for any position where the side to move cannot immediately capture the opponent king, including for positions that cannot be reached from the starting position. So perft 1 from your second position should produce your first position. And so reverse perft 1 from your first position should produce your second position.

I think Uri means that there is no legal predecessor position for the second position since no legal move can lead to a position where a black bishop on a8 gives check to a white king on b7. So the second position has reverse_perft(N) = 0 for any depth N.

The first position has the second as a legal predecessor (even though it is unreachable from the initial position) so reverse_perft(1) for the first position would include counting the second position. But reverse_perft(N) with N>1 for the first position would not include counting the second, for the reason given above (similar to perft(N) you would only count ancestors at the distance of exactly N).

[syzygy]

For example the second position is invalid because the bishop has no way to get to a8 in the previous move so the reverse perft should not produce

I don't see why reverse perft should not produce the second position, even though that position is impossible to reach from the starting position. What has the starting position to do with perft / reverse perft?

Perft is well-defined for any position where the side to move cannot immediately capture the opponent king, including for positions that cannot be reached from the starting position. So perft 1 from your second position should produce your first position. And so reverse perft 1 from your first position should produce your second position.

I think Uri means that there is no legal predecessor position for the second position since no legal move can lead to a position where a black bishop on a8 gives check to a white king on b7. So the second position has reverse_perft(N) = 0 for any depth N.

The first position has the second as a legal predecessor (even though it is unreachable from the initial position) so reverse_perft(1) for the first position would include counting the second position. But reverse_perft(N) with N>1 for the first position would not include counting the second, for the reason given above (similar to perft(N) you would only count ancestors at the distance of exactly N).

According to Uri (but also according to Alexandru and Steven, if I understand them correctly), Uri's second position should not be counted for reverse perft 1 of his first position:

For example the second position is invalid because the bishop has no way to get to a8 in the previous move so the reverse perft should not produce
Kb7xa8(a8=bishop)

(Maybe Ka8xb7(a8=bishop) would be a more intuitive notation for the reverse capture?)

I understand the point, which is that the 2nd position is not reachable from the start position, but I don't see why the start position is relevant at all for perft and reverse perft. Certainly the normal definition of the regular perft need not mention the start position at all.

[brtzsnr]

To sum it up:

1) It's very hard to detect whether a position can be reached from the start position (which start position? chess960 has many start positions). Regular perft doesn't care about start position.
2) Corollary. We can have positions with more than 32 pieces.
3) The only thing we care is that king cannot be captured (includes uncastling).


Now given these rules, does anyone have reverse perft results?