reverse perft
Moderators: hgm, Rebel, chrisw
-
- Posts: 433
- Joined: Fri Jan 16, 2015 4:02 pm
reverse perft
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.
zurichess - http://www.zurichess.xyz
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: reverse perft
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.
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.
-
- Posts: 433
- Joined: Fri Jan 16, 2015 4:02 pm
Re: reverse perft
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 -
[d]rnbqkbnr/pppppppp/8/8/8/5N2/PPPPPPPP/RNBQKBnR w KQkq -
zurichess - http://www.zurichess.xyz
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: reverse perft
That position would be rejected on input as it has 17 black men.
-
- Posts: 10297
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: reverse perft
It is simple but there are things that are not so simplesje wrote:That position would be rejected on input as it has 17 black men.
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
-
- Posts: 859
- Joined: Mon Aug 10, 2009 10:05 pm
- Location: Italy
- Full name: Stefano Gemma
Re: reverse perft
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.
Finding a single legal path to the origin could be different, but this is not related to perft, direct or reverted.
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com
http://www.linformatica.com
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: reverse perft
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?Uri Blass wrote: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
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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: reverse perft
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.syzygy wrote: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?Uri Blass wrote: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
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.
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).
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: reverse perft
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:Sven Schüle wrote: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.syzygy wrote: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?Uri Blass wrote: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
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.
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).
(Maybe Ka8xb7(a8=bishop) would be a more intuitive notation for the reverse capture?)Uri wrote: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)
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.
-
- Posts: 433
- Joined: Fri Jan 16, 2015 4:02 pm
Re: reverse perft
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?
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?
zurichess - http://www.zurichess.xyz