Testing retrograde move generation

[Dave Gomboc]

Does anyone know of a test suite (perhaps something similar to https://www.chessprogramming.org/Perft_Results) that is available for retrograde move generation? For example, KiwiPete's (Peter McKenzie's) position #2 there exposes a lot of potential bugs, and it would be great if we had a few such positions for vetting retrograde move generation too.

(I guess if you have very little material on board, you can cobble something together using endgame tables.)

[hgm]

Why would that be useful? I only ever used retrograde moving in EGT generation. And then positions are so simple that it is hard to do anything wrong. Furthermore, the problem seems ill-defined. In retrograde moving you have uncaptures instead of captures, but which piece types you can uncapture depends on the EGT you are generating.

[Dave Gomboc]

I am inquiring about a general capability, not one limited to generating some specific subset of any particular endgame, so the intent would be for all legal unmoves (including uncaptures and unpromotions) to be identified. (Of course, someone who is focussed specifically upon endgame table construction might want the option to generate only those unmoves that would retain the same material balance, which would exclude many interesting unmoves.)

Regarding utility, well, one could ask the same about playing a board game to begin with!

[petero2]

I am inquiring about a general capability, not one limited to generating some specific subset of any particular endgame, so the intent would be for all legal unmoves (including uncaptures and unpromotions) to be identified.

That is a very difficult problem, at least if you define "legal unmove" as a move causing the position after the unmove to be legal, i.e. reachable from the starting position through a sequence of legal moves. This is related to the fact that the "retrograde analysis problem" is PSPACE-hard on arbitrarily large chess boards. On an 8x8 board the problem can of course be solved in constant time, but for the best known algorithms the constant is far too large to always find a solution.

The best you can hope for is to create an algorithm that can produce a set of unmoves that contains all legal unmoves and possibly also some illegal unmoves, but the algorithm will not be able to tell which unmoves are legal. The "texelutil" program contains such an algorithm.

If you define "legal unmove" in some other way, you first have to decide exactly what the definition is.

[Dave Gomboc]

That is a very difficult problem, at least if you define "legal unmove" as a move causing the position after the unmove to be legal, i.e. reachable from the starting position through a sequence of legal moves. This is related to the fact that the "retrograde analysis problem" is PSPACE-hard on arbitrarily large chess boards. On an 8x8 board the problem can of course be solved in constant time, but for the best known algorithms the constant is far too large to always find a solution.

The best you can hope for is to create an algorithm that can produce a set of unmoves that contains all legal unmoves and possibly also some illegal unmoves, but the algorithm will not be able to tell which unmoves are legal. The "texelutil" program contains such an algorithm.

If you define "legal unmove" in some other way, you first have to decide exactly what the definition is.

It was my intention to keep the notion of legal unmove generation distinct from the notion of board states that are in fact reachable from the traditional starting position. The commit message you pointed to gives the sorts of moves that I would like to exclude when determining legal unmoves:

* Moves that are invalid because the resulting piece counts (taking promotions and captures into account) are impossible.
* Moves that are invalid because king capture was possible before the move.
* Moves that are invalid because the en passant square does not match a double pawn push.

I would add to that list things like that a retrograde castling move from the successor position should not be generated whenever immediately castling from the predecessor position reached via such a pseudo-legal unmove to reach the successor position would not actually be legal.

I realize that it is also possible to prove in many more special cases that some predecessor position could not actually have been reached from the starting position. For instance, analysis of the combination of pawn structure and piece count could reveal that too many captures would have occurred for the pawns to be where they are while so many pieces remain on the board. However, I consider that to be a separate concern that I am not currently interested in addressing.

Thank you very much for the pointer to your code! I can at least use it to check which legal unmoves your code generates versus what mine generates, and investigate any discrepancies to resolve implementation bugs versus differences of interpretation regarding what constitutes a legal unmove.