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

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?

• There is Jacobi, a program that does what you ask, but requires more than just the FEN and you will have to read the documentation to use it properly. wismuth.com/jacobi Commented Dec 13, 2020 at 10:53
• Judging by this question, I'm guessing you would be most interested in Raymond Smullyan's "The Chess Mysteries of Sherlock Holmes" book, which is mostly a collection of problems about finding the history of a position, eg proving that a pawn has been promoted, finding the correct orientation of a board, etc.
– Stef
Commented Dec 15, 2020 at 16:07

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.

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.

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.

Chess is a finite graph whose vertices are called “positions” linked to one another by directed edges called “legal moves”. Those positions which can be reached from the game array by a sequence of legal moves are termed “legal positions”.

Since a priori we don’t know whether a given position is legal, it’s still useful conceptually to reason about the bigger graph which also includes the illegal positions, however it’s worth excluding the “ill-formed” positions where one side has the wrong number of kings, a pawn is on the first or last rank, or the player to move is already delivering check.

We could in principle simply pursue a depth-first search of all positions reachable from the game array until we encounter the desired position, or exhaust the graph. So at some level an algorithm does exist, but this is not practical.

There are numerous problems where there is a unique shortest proof game, and engines have been constructed which allow the unique proof game to be determined. The most powerful general purpose engine today is Stelvio, but others like Natch, Jacobi & Euclide are also competitive because they allow for constraints to be added by the user. Those constraints (e.g. wRa1 has never moved) are in the nature of heuristics so are not algorithmic, but given enough resources any of these engines would in principle solve any unique proof game.

However it’s not widely recognised that there is a huge hole in proof game engine capabilities. These engines are basically “good at solving jigsaws” but the mass of naturally occurring positions are much looser: they are more like arrangements of cornflakes in a box.

There is a real interest in validating automatically the legality of chess problem positions (usually where there is are no retro features) but paradoxically none of the engines today even Stelvio can handle them. This isn’t my opinion: I’ve discuss it with Reto Aschwenden, the Stelvio developer.

A practical approach with a new engine might be to determine the pawn captures and promotions. Then one could start with a game array from which all extraneous pieces had already been removed. Then one could attempt to move all the pawns to their final squares, and finally shift all the remaining pieces to their destinations. This would probably be effective but it’s not algorithmic.