19

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

4
  • 5
    No, because there are positions for which there is no unique list, simple e.g.: 1 e4 c5 2 d4 and 1 d4 c5 2 e4 . If you change it to "gets a series of moves" I don't know the answer, but I still suspect no practical one exists
    – Ian Bush
    Dec 13 '20 at 9:04
  • 9
    I just want a single possible move list, not all. And if the board position is not possible (or legal), then it doesn't matter.
    – 2080
    Dec 13 '20 at 9:07
  • 6
    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
    – B.Swan
    Dec 13 '20 at 10:53
  • 1
    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
    Dec 15 '20 at 16:07
25

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.

8

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.

10
  • 2
    Nice! I didn't consider doing it backwards. But still, is there a fast enough algorithm for this, either way? Because this general problem seems to be NP-hard.
    – 2080
    Dec 13 '20 at 11:02
  • 3
    @HagenvonEitzen I mean, what you describe is basically what a tablebase does. However even a 7 men tablebase generated by Ronald de Men's algorithm needs about 1 tera byte of RAM. That is 7 pieces. If you could simply run an algorithm like yours you might just as well solve chess. I suspect that finding a shortest solution is in NP-hard however finding any solution might not be. (at least if you exclude things like 50 moves rule) And likely finding any solution is easy for most positions. However I'm not sure what the worst case is.
    – koedem
    Dec 13 '20 at 14:49
  • 1
    @DM Anything less than a few months, subsecond would be great
    – 2080
    Dec 13 '20 at 18:04
  • 1
    There is a finite number t that is the maximum number of turns that a game can last, and a finite number t that is the maximum number of legal moves that there can be, so there is a finite number of games < m^t. All you have to do is look through each legal game and see whether any of them contain the desired position. Dec 14 '20 at 1:00
  • 2
    @2080: yes, the naive algorithm proposed here is completely impractical without major cleverness to prune the search space to favour likely candidates. (e.g. trying to get pawns moved backwards). The exponential explosion of possibilities is even worse than forward chess, because every position could be the result of a capture (unless there are already 16 pieces+pawns of that colour on the board). Limits like 2 rook can't be assumed either, unless you can prove that a missing pawn couldn't have been promoted to another rook and then moved out to be captured at any current piece location. Dec 14 '20 at 15:06
5

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.

13
  • 8
    If you're going to bandy about terms like NP-hard, you need to specify how your problem size grows. On a 64-square board, solving this problem takes a number of steps bounded by a finite limit which we can calculate, so it can't be NP-hard as it stands.
    – TonyK
    Dec 13 '20 at 18:24
  • 4
    @TonyK It does technically need to be specified, but in this case there's a 'canonical' answer (positions of all the pieces, which 'automatically' means problem length polynomial in board size) that everyone agrees on; that's the standard meaning behind statements like 'Go is NP-hard' etc. Dec 13 '20 at 18:31
  • 5
    In this case, given the nature of the structures at play, I would guess that this particular question is EXPTIME complete ignoring the 50-move rule, and PSPACE complete with that in place; that's the 'generic' result for board games with potentially unbounded (Chess without the 50-move rule) vs. polynomially-bounded (e.g. Checkers, or chess with the 50-move rule) move counts. Dec 13 '20 at 18:34
  • 1
    @TonyK for chess I'd naturally have it be the board size, while chess is played on 8x8 usually, there is no reason it couldn't be played on a bigger board. Solving chess then of course is an Exp problem, however just finding a path is in NP since a path can easily be verified.
    – koedem
    Dec 13 '20 at 22:11
  • 4
    @StevenStadnicki is it PSPACE complete? Given that we don't look for a shortest path or anything, but just any path, can't a path be verified in polynomial time?
    – koedem
    Dec 13 '20 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.