reverse perft

[Robert Pope]

2) Corollary. We can have positions with more than 32 pieces.

I don't think that's a reasonable conclusion, since piece organization is highly dependent on the internal structures of the chess program. Not every program can handle having 40 pawns on one side, nor should they be expected to, since a position like that is clearly not chess.

[syzygy]

(includes uncastling)

Getting uncastling right needs a bit of thought.

For example, if there are white rooks on a1 and on h1, there are four legal unmoves Ke2-e1.

[syzygy]

2) Corollary. We can have positions with more than 32 pieces.

I don't think that's a reasonable conclusion, since piece organization is highly dependent on the internal structures of the chess program. Not every program can handle having 40 pawns on one side, nor should they be expected to, since a position like that is clearly not chess.

But most programs cannot handle reverse perft anyway

[Luis Babboni]

It is nearly impossible to compute all positions from a final one to the start... 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...

Not understood.
For me, if for example you have a black Knight in A1, there are 3 previous possible conditions for that piece: as a Knight in B3, as a Knight in C2 or as a pawn in A2.
What I´m understanding wrongly?

[yurikvelo]

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?

filter EGTB (of DTM-metric kind) by distance N?

SELECT COUNT(fen) FROM Nalimov WHERE DTM=n?

[Sven]

It is nearly impossible to compute all positions from a final one to the start... 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...

Not understood.
For me, if for example you have a black Knight in A1, there are 3 previous possible conditions for that piece: as a Knight in B3, as a Knight in C2 or as a pawn in A2.
What I´m understanding wrongly?

I can't speak for Stefano of course but it seems he was thinking about the complexity of the task, not whether it would be doable in theory.

As to your example, please don't forget captures. Possible previous moves to the square a1 when the current position has a black knight on a1 are:

Nb3-a1
Nb3xa1 (capturing either of QRBN)
Nc2-a1
Nc2xa1 (capturing either of QRBN)
a2-a1N
b2xa1N (capturing either of QRBN)

So there are 15 unmoves with target square a1 in that case, which is a lot more than in the classical "forward perft" with two legal moves of a black knight from a1 (to b3 or c2). More unmoves per square means higher branching factor and therefore higher computational complexity. This might arise from allowing arbitrary positions which need not be reachable from the initial chess position.

For target squares on rank 2..7 there are no "unpromotions" (also not for the first rank of each color) but additional "uncaptures" (capturing a pawn) so the computational effort is not really lower.

[syzygy]

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?

Not requiring that a position be reachable from the start position has further interesting consequences. For example, one unmove from this position:
[d]2k5/8/4P3/8/8/8/3K4/8 b - - 0 1
leads to this position:
[d]2k5/8/8/8/4P3/8/3K4/8 w - - 0 1
From this position, the pawn cannot be further unmoved. The double pawn push is legal only on the pawn's first move:

a. The pawn may move forward to the square immediately in front of it on the same file, provided that this square is unoccupied, or
b. on its first move the pawn may move as in 3.7.a or alternatively it may advance two squares along the same file, provided that both squares are unoccupied, or
c. (...)

There is also no reason to unmove a white pawn from a2 to a1 (unless it has previously been unmoved from a4 to a2) or from a3 to a1 (unless it has previously been unmoved from a5 to a3).

Another series of legal unmoves:
[d]2k5/4p3/8/8/8/8/3K4/8 w - - 0 1
[d]2k1Qp2/8/8/8/8/8/3K4/8 b - - 0 1
[d]2k2p2/8/4P3/8/8/8/3K4/8 w - - 0 1

[syzygy]

So I'm afraid that it does make sense to limit reverse perft to "legal positions" and, at least according to the Laws of Chess, a "legal position" is one that is reachable from the initial position. (This means that reverse perft numbers of a position can be different depending on which (Chess960) initial position is taken.)

Alternatively, one could take a more pragmatic approach to defining "legal position". The following seems to make sense (together with a slight redefinition of the Laws of Chess):
- pawns must be on ranks 2-7; white pawns may move 2 squares only from rank 2, black pawns only from rank 7;
- for each color, the numbers of pawns, knights, bishops, queens, rooks and king must be "compatible" with the numbers in the initial position and the rules on promotion (writing out the equations is a bit of a hassle);
- the side to move may not attack the opponent's king.