Given a legal chess position, is there an algorithm that generates a series of moves that lead to it?

Question

Given a FEN board position, is there an algorithm that can return a PGN move list that evaluates to it from the standard initial position?

Answer 1

The task you are considered is usually called a proof game, named such because the task is to prove that the position is legal. As a genre of puzzles, there are various aesthetic constraints, most commonly that the resulting game be unique. However, this is not necessary in general, and there is even a genre of counting the number of solutions.

There are several programs available that perform this task of solving proof games:

1. Natch is often considered the fastest. You can see it in use in this answer to another question on this site: "Can it be proven that 11. 0-0-0+ is legal in this position?"

2. Euclide is apparently most useful when the sequence of moves is unique.

3. Popeye can solve many chess problems, including fairy chess problems. Apparently it is not the most performant for proof games.

4. Jacobi is a program to solve (fairy) chess proof game problems. It is written in JavaScript and run from browser, which makes it easy to try.

I have used Natch most successfully myself.

Answer 2

If you are familiar with mathematical induction then it should be clear to you that the answer is trivially "Yes".

Just as for any position (legal or otherwise) it is possible to use the laws of chess to calculate all the legal moves in that position (this is what computer engines do) so given any position (legal or otherwise), P(n), other than the start position and a side, S(n), either black or white, it is possible to calculate all the possible previous legal moves for player S(n). This will likely give many new positions (some may be illegal), P(n-1).

If P(n-1) is the empty set then we know that P(n) was an illegal position. If P(n-1) is not the empty set then set S(n-1) to the opposite of S(n) and repeat the previous step for all elements of P(n-1) for player S(n-1).

If the original position was legal then this induction process will terminate with the initial position. If the original position was not legal then it will terminate with some other position.

Answer 3

The natural approach to this problem is a tablebase-like approach like outlined by Brian. But doing something similar to that for just 7 pieces (namely, 7 men tablebases) with current algorithms already takes many months of calculation and 1 Tera Byte of RAM, doing that and trying to get to the starting position sounds pretty impossible. (otherwise one may just as well try to solve chess by building a 32 men TB)

In general I strongly suspect this problem is NP hard. However in practice the following human-like approach should work for most positions: Determine which pieces are missing from either side and evaluate how many captures are necessary to form the given pawn structure. (e.g. you need at least one capture to create a doubled pawn) Based on that, create "paths" that the pawns might have taken to reach the current pawn structure. Then try to move the to be captured pieces on that path to be captured by pawns if necessary. Move the remaining pieces on their squares.

The reason why this will work most of the time is that the only irreversible moves are captures and pawn moves (this is not quite true, but close enough for this explanation). Therefore, the shuffling of other pieces does not need to be exact, there are many ways to bring some piece to some other square. (but there may only be one way to get a pawn to a certain square)

For most "real life" examples this should work well enough. Things will get more complicated, once you require promotions or specific move orders (for instance because some piece is locked in by pawns and the piece and pawn movements must be coordinated to achieve that position). Also, if 50 moves rule becomes a factor because in that case it might matter which path pieces choose. Nonetheless for most practical positions that is not an issue.

Even for those difficult positions I still think human like approaches might be useful. The following is very vague, but I think what could work is trying to determine certain scenarios that must have happened. For a contrived example, consider a position white Bf8, black Pg7 Pe7. The bishop can not have moved there since the pawns are on g7 and e7 still. So it must have come from a promotion of the f pawn.

Accumulate all relevant scenarios, determine which are dependent and try to put them in some order that makes it work. In practice you will fail here for some positions but such is the nature of NP hard problems. More specifically, I suspect that for every algorithm you devise, there will be some position that you can't solve with current computing power.