Answers.Body: <p>Basically, the answer is "no", and that will probably never change.</p>
  
  <p>I am going to compare this to tablebases since it seems relevant due to how they are made compared to what you ask in your question. I realize they are different in certain other aspects.</p>
  
  <p>Tablebases, which are databases of perfect endgame play, are computed in exactly that way that you are asking: They start at the final position, and work back to the possible original position. Of course, they start from the end of the game when there are only currently 7 pieces, or less, left on the board, including kings. You can see how this is actually is MUCH easier than your question, yet it is still a HUGE undertaking for computing power as we currently know it.</p>
  
  <p>With only 7 pieces, it not only takes an incredible amount of time to solve even one position, and it takes a WHOPPING 140+ terabytes to store all 7-man tablebases. It took years to do this. You can see how adding even a few more pieces, this grows exponentially. Due to the extreme computing-power cost, we are not even close to starting 8-man tablebases, and it is estimated that they would take over 10 petabytes to store in their entirety. Even though you are not trying to solve every position with 32 pieces, you can see how trying to go from the end of a game back to the original 32-piece starting position is not feasible.</p>
  
  <p>The only question is if could they program in the human tendency to play in various ways to prune the search, but I doubt that very much, as even then, the numbers are huge.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T12:28:26.803Z
Answers.LastActivityDate: 2019-11-28T12:28:26.803Z
Answers.UserDisplayName: PhishMaster
Answers.Body: <p>I’ve decided to expand this to a more general survey of the applicability of engines to various retro sub-genres.</p>
  
  <p>Chess engines (e.g. Stockfish) are good at trying out all the moves going forward in a position but famously bad at abstracting general features such as fortresses.</p>
  
  <p>In the same way you can easily try retracting possible least moves just by making pieces move backwards, hatch opposing pieces instead of capturing them, and run away from opposing kings that are “checking” them. The difficulty is in abstracting general
  features to find out whether the position can be derived from the starting position. The distinction between legal moves and legal positions is the key here and is a distinction made in the FIDE Laws as well.</p>
  
  <p><strong>Proof games</strong> One retro domain that has enjoyed great success with engines is proof games. These are like retro problems except that you’ve been given the additional information of the expect number of moves. This notion of clock simplifies the retro process enormously, in a similar way that Othello games can be deduced because one knows the exact number of moves. Some people regard them as forward stipulations because you do start from the game array and can play forwards, but they are generally viewed as retros. Leading engines in this space are Natch, Euclide, Popeye and for fairy problems Jacobi.</p>
  
  <p><strong>General retros</strong> There are fewer engines for general retro problems. These work by allowing the solver to specify constraints that are deduced by a human solver. Jacobi does this within the envelope of some notional number of moves, but the best I know is the enigmatic Rawbats, a tool only used by its maker Mario Richter, and known only by its results in augmenting its developer’s skills.</p>
  
  <p><strong>Helpmate retractors</strong> There is a big opportunity for someone computerate to build a simple retraction engine which just tries retracting recent moves, without worrying about global legality, and then plays forwards like a regular problem engine. Such an engine, combined with a little human common sense, would be able to validate the hundreds of helpmate retractor compositions which are currently untestable.</p>
  
  <p>I want to finish by mentioning two retros areas which are less amenable to engine assault.</p>
  
  <p><strong>Problems based on conventions</strong> One is the domain of retro conventions: castling, en passant and other related rules. Combining a logical reasoning system with a chess engine has not been done, and in some cases there are deep ambiguities in the conventions themselves. This work is normally left for the human to solve, but in principle if the conventions could be grounded logically, it would be an interesting research topic.</p>
  
  <p><strong>Defensive retractors</strong> The other difficult genre of retro composition contains the highly technical defensive detractors of various kinds. These essentially involve playing chess backwards in a competitive way, and questions of position legality are normally the key without which the problems compositions make little sense.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T12:26:34.303Z
Answers.LastActivityDate: 2019-11-29T08:12:21.410Z
Answers.LastEditDate: 2019-11-29T08:12:21.410Z
Answers.UserDisplayName: Laska
Answers.Body: <p>Current engines can't do this at all. Calculating backwards is quite different from calculating forward. Pieces come into existence instead of being taken. </p>
  
  <p>But you could certainly adapt engines to be able to perform well on this task.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T08:27:04.973Z
Answers.Text: I disagree with the second statement - to date there is no engine even able to list fully all possible retractions (legal or illegal) from a position. And determining whether a retraction is legal is EXTREMELY difficult in retro problems - there is no neat way to encapsulate all that logic into a computer program.
Answers.UserDisplayName: Remellion
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T08:34:47.827Z
Answers.Text: Yes, legality is difficult. I assume you'd have to find the whole game. But retractions should be relatively easily doable. And then it's just tree search.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T08:46:22.383Z
Answers.Text: Tree search is horrible if only one 15-ply retraction line is legal out of many, many, many possible lines. And it doesn't even get back to the starting position. See the problem linked to in my answer for a taste of a moderately difficult retrograde problem.
Answers.UserDisplayName: Remellion
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T09:05:38.577Z
Answers.Text: Sure, tree search requires pruning. But I concede that such an engine probably does not do well on Troitzky-problems, where there is only one legal 15-ply line. I was thinking more of the general task of recontructing the most likely line that lead to a position. I think that would be a very interesting and also tractable problem.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T09:11:36.303Z
Answers.Text: Even for the general task, it is hard to say. To have an engine of some sort, we must tell it what a "legal" move/retraction is. This is indeed the hard part for regular engines (move validation), and the nearly impossible part for a retraction engine - how do you define a legal retraction in a verifiable way?
Answers.UserDisplayName: Remellion
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T09:19:11.920Z
Answers.Text: For actual games I would try to machine learn legal / likely retractions. The final proof of legality could only be a complete game.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T05:18:16.370Z
Answers.Text: @MilesRout Legal moves are defined by the rules of chess, and it is thus "easy" to check a move is legal - you just need to refer to the rules of chess. A legal retraction is defined (one possible definition) as one which starts from and results in a legal position (reachable from the starting array by legal moves). But how do you tell if a position is legal? There is no easy way to do so.
Answers.UserDisplayName: Remellion
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T08:18:12.527Z
Answers.LastActivityDate: 2019-11-28T08:18:12.527Z
Answers.UserDisplayName: BlindKungFuMaster
Answers.Body: <p>No.</p>
  
  <p>First and foremost, engines (and everybody) play against some other also (an human player, another engine, even themselves with the opposing color). They may <em>guess</em> the probable move(s) of the other actor, but they do not get too far. They pick a good move and the other actor's move helps them to narrow the range of possibilities.</p>
  
  <p>Reversing a game position is a different problem, as you need to <em>know</em> both players moves to solve it. You do not know if the moves were good or bad, or even if they made sense, you only know that they were legal. In that sense, rebuilding the game would be more akin to "solving" chess (getting all possible solutions of a game from the start position).</p>
  
  <p>Additionally, even if you strengthen the requirements ("let's guess that each player always played the move with the best analisis by the current engine") you have lots of situations where several possible predecessor states do appear. Just guess</p>
  
  <pre><code>rnbqkbnr/pp1p1ppp/8/8/3p/N7/PPP1PPPP/R1B1KBNR w - - 1 13
  </code></pre>
  
  <p>Does this come from?</p>
  
  <pre><code>[fen ""]
  
  1. d3 c5 2. d4 e5 3. Na3 exd4 4. Qxd4 cxd4
  </code></pre>
  
  <p>Or from? </p>
  
  <pre><code>[fen ""]
  
  1. d3 c5 2. d4 e5 3. Na3 cxd4 4. Qxd4 exd4
  </code></pre>
  
  <p>In both cases black's last move is its the strongest one, yet it does not serve you to decide which was the previous board situation. As the analysis expands backwards, the possibilities multiply.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T02:37:10.683Z
Answers.Text: Thanks for your answer and welcome. When engaging in retrograde analysis we do jettison in almost all cases consideration of the quality of the move. Hard enough just to consider legality. I think the engine referred to in the question was a hypothetical one designed for retro purposes rather than one of the familiar forward engines like Stockfish
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T18:20:14.237Z
Answers.Text: @Laska As I see it, the idea of the quality of the move is that, as a strengthening of the conditions, it would make retrograde analysis easier, as it would limit the number of possible previous boards. My point is that even with a stronger criteria uncertainty will appear.
Answers.UserDisplayName: user20689
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T18:35:18.073Z
Answers.Text: Thanks again for your response, user20689. How to be absolutely objective about the quality of the move? It can't depend upon an engine at a given moment in time. One futuristic idea I heard from top retro composer Nicolas Dupont is to link with the reflexmate condition, so any mate in 1 is mandatory. Under reflexmate-2, any mate in 2 is mandatory etc. So we can converge towards a world where retrograde analysis assumes perfect play. But remember the primary goal is chess composition is an artistic one: to achieve cool effects, it's not necessarily to make retroanalysis easier.
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T00:31:00.437Z
Answers.LastActivityDate: 2019-11-29T00:31:00.437Z
Answers.UserDisplayName: user20689
Answers.Body: <p>As others have said, current engines are not meant to do that. But from a theoretical computer science perspective, it is "possible", although likely unfeasible.</p>
  
  <p>Just like a "forward" chess engine can search at most a few (dozens?) moves in the future (because the possibilities explodes exponentially), a backwards engine would suffer from the exact same limitation.</p>
  
  <p>I think enumerating all legal backwards move from a given board state is relatively simple (contrary to what others have said), but the number of possibilities explodes exponentially the farther back we go.</p>
  
  <p>Anyway, since the number of board states is finite, it is theoretically "possible" to write such a program: given enough time, a computer will analyze every possible state and eventually concludes with a valid game up to that point (it is non-unique; many games can lead to the same state), or conclude that such position is impossible (even if it takes many times the age of the universe to get there, hence the quotes on "possible"). This is what we computer scientists call a <a href="https://en.wikipedia.org/wiki/Undecidable_problem" rel="nofollow noreferrer">decidable problem</a>. Such approach is probably not feasible (as it is certainly not feasible for "forward chess").</p>
  
  <p>But modern chess engines does not blindly enumerates every possibility. Instead they use very advanced heuristics to decide the likelihood of a movement, and they perform very well against humans. It seems to me that similar heuristics and techniques can be used to create a backwards game of chess in a software that works at least sometimes.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-30T10:14:48.983Z
Answers.Text: I don't doubt we could build a game that leads to a legal position in acceptable time in most cases. However, that result would almost positively be meaningless, as we'd have to drop the implicit assumption that the game 'makes sense'. We'd most likely get a game where first only the pawns move in position, then all missing pieces get cooperatively sacrificed, with finally each piece moving into position like clockwork.
Answers.UserDisplayName: Sudix
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-02T13:54:07.993Z
Answers.Text: It may be that the reconstructed legal game is "illogical", but I highly doubt that are so many "illogical" legal paths that leads to a logical board state, specially if positional analysis is used to help with the reconstruction. In fact, the "logical" possibilities is what might help a backwards engine to filter out the unlikely paths.
Answers.UserDisplayName: lvella
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T18:33:11.220Z
Answers.LastActivityDate: 2019-11-29T18:38:25.580Z
Answers.LastEditDate: 2019-11-29T18:38:25.580Z
Answers.UserDisplayName: lvella
Answers.Body: <p>It's true that starting from the target position, searching for possible previous moves will probably be infeasible. However, there is an approach that could yield a reasonable game that hits the target position.</p>
  
  <p>In normal chess engines, the computer scores each position with some criteria, such as how many pieces it has remaining. The purpose of the score is to decide how likely it is to win from that position.</p>
  
  <p>One could instead use a different set of scoring criteria, such as how many pieces are in correct places, and whether the set of remaining pieces matches the target.</p>
  
  <p>Placing two such engines playing a normal forwards-game against each other could probably generate a game that ends up in the target position.</p>
  
  <p><strong>Extra:</strong> A fun extension would be to use the normal scoring for predicting opponent's moves and the target scoring for chess engine's own moves. This way the plays-for-target chess engine would try to force a plays-for-win opponent to end up in the specific position. Of course this would only be possible for a small subset of positions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-30T07:23:33.517Z
Answers.LastActivityDate: 2019-11-30T07:28:51.440Z
Answers.LastEditDate: 2019-11-30T07:28:51.440Z
Answers.UserDisplayName: jpa
Answers.Body: <p>While it might not be currently possible to write an AI that does better than humans, there are some relevant programs under the "retro, programy, úlohy" subheading <a href="http://members.chello.cz/chessproblems/links0.htm" rel="nofollow noreferrer">here</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-01T13:25:27.067Z
Answers.LastActivityDate: 2019-12-01T13:55:23.370Z
Answers.LastEditDate: 2019-12-01T13:55:23.370Z
Answers.UserDisplayName: alphacapture
Answers.Body: <p>From the pure theoretical point of view: Yes, it is possible.</p>
  
  <p>You just need to play forward all possible games until you find at least one game that contains the current position. Then you use the moves it played forward to do your retro analysis.</p>
  
  <p>But you cannot <strong>just</strong> do it, as the amount of possible games is huge. So this point is only a proof, that it is possible in theory. In practice, the question is if it is tractable in a reasonable time.</p>
  
  <p>I suppose it is tractable by extending some of the current planning methods, but the details are not straightforward. I would recommend asking the question if an AI can achieve this at <a href="https://ai.stackexchange.com">https://ai.stackexchange.com</a>, as it is an interesting question about game AIs and may spark some quite interesting answers on that site.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-30T18:31:19.267Z
Answers.LastActivityDate: 2019-11-30T18:31:19.267Z
Answers.UserDisplayName: allo
Answers.Body: <p>Engines like Stockfish and Komodo are not able to work out the previous moves, because that is not what they are programmed for.</p>
  
  <p>However, it is vanishingly unlikely that anybody can ever program an engine that works out legal previous moves. The logic of working out whether a possible previous move is legal or not is extremely difficult.</p>
  
  <p>To start with, <strong>how do we list possible previous moves?</strong></p>
  
  <p>Possible previous moves, called retractions (if we ignore legality for a second) are easily found algorithmically - every piece retracts as it moves in forward chess (except pawns), and they could also "uncapture" an enemy unit - pawn, knight, bishop, rook or queen. e.g. wBc4 takes pawn on f7 in reverse looks like the bishop moving from f7 to c4, with a black pawn appearing on f7.</p>
  
  <p>Pawns move 1 square backwards, and uncapture one square diagonally backwards. (You can figure out what the double step looks like.)</p>
  
  <p>With regard to checks, one can retract into what looks like "check" in regular chess, and one must always retract to never leave the opponent in "check". (So if the previous example of wBc4xbPf7 checks the black king on e8, it required white to retract the bishop to remove the "check".)</p>
  
  <p>Uncastling is easy to visualise (and adds the constraint that the king or rook cannot retract again). Un-en-passant is hard to describe and forms the basis of many classic retro problems. Unpromotion is again easy to visualise.</p>
  
  <p>So listing all potential retractions is not difficult, from a programming standpoint. <strong>The incredibly difficult part is determining which retractions are legal.</strong> There are many reasons why a retraction cannot be legal, ranging from simple (retracting an uncapture to leave 9 black pawns on the board, for instance) to highly convoluted (cf. most retrograde analysis problems, see <a href="https://www.janko.at/Retros/index.htm" rel="noreferrer">the Retro corner</a>.)</p>
  
  <p>See for instance <a href="https://chess.stackexchange.com/questions/19973/beautiful-retrograde-analysis-problem-by-alexsey-a-troitsky">this problem by Troitsky</a> on Chess.SE, and my accompanying answer to it. A lot of logic goes into proving that there is in fact only one legal retraction by black, and this is not obvious, involving counting pawn captures, considering their order, and tempo constraints.</p>
  
  <p>To write an engine to perform such a task, one must be able to elucidate the human logic behind it in such a way that a computer can execute the logic. This simply does not seem possible at all, given that "legality of retractions" is far more nebulous than "legality of forward chess moves".</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T08:49:10.420Z
Answers.Text: That's interesting. One thing that humans can do better!
Answers.UserDisplayName: Snack_Food_Termite
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T22:58:28.137Z
Answers.Text: proving that a position is reachable from start position is in general about as hard as solving chess. Humans can only do so for a small subset of positions. For computers it's infeasible.
Answers.UserDisplayName: Sopel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T08:02:14.857Z
Answers.Text: @Sopel *Humans can only do so for a small subset of positions.* This is incorrect. Given a random position, in most case humans can say pretty whether it is legal or not. Some are obviously unreachable because of the pawn structure, others are trivially legal because "nothing special is going on". Retrograde analysts concentrate on the thin border zone, building sophisticated puzzles with positions than are or are not legal because of multiple subtleties.
Answers.UserDisplayName: Evargalo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T08:51:32.837Z
Answers.Text: *Un-en-passant is hard to describe and forms the basis of many classic retro problems.* – I fail to see this. Whenever an en-passant could have happened, you could instead have the normal capture of a singly advancing pawn. Both the setup and the outcome are indistinguishable. So, one could ignore en-passant during the entire retro analysis, and simply add it at the end as an additional, trivial one-move branch whenever a singly advancing pawn was directly captured (and wasn’t blocked from advancing two fields).
Answers.UserDisplayName: Wrzlprmft
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T09:16:00.160Z
Answers.Text: @Wrzlprmft It is not trivial and the setup is indeed distinguishable: https://chess.stackexchange.com/a/23541/15989
Answers.UserDisplayName: Remellion
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T09:34:24.510Z
Answers.Text: @Remellion: Ah, I see. So the only reason why it is difficult is that the captured pawn may have blocked a check?
Answers.UserDisplayName: Wrzlprmft
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T09:53:54.180Z
Answers.Text: @Wrzlprmft That's one of the reasons. Another one (quite a broad topic) is how en passant retractions interact with castling rights. See https://www.janko.at/Retros/Glossary/Castling-and-En-passant.htm for a sampling, namely the last 8 problems (9-16). There are other, even more subtle interactions (e.g. with threefold repetition/50-move/Dead Reckoning) - retrograde analysis is a much deeper field than the first impression it makes.
Answers.UserDisplayName: Remellion
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T14:21:15.133Z
Answers.Text: Retrograde-analysis of castling and en passant is going to be interesting as well. After 40 moves, there are a lot of options to pick from to go back to starting position.
Answers.UserDisplayName: Mast
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T08:44:03.793Z
Answers.LastActivityDate: 2019-11-28T08:44:03.793Z
Answers.UserDisplayName: Remellion
Body: <p>If I took a legal chess position, to what extent could an engine work out the previous moves? [in some other board games such as Othello such game reconstruction is done easily with an engine.] </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-28T17:12:47.707Z
Comments.Text: I don't have any real data to go with, but your question makes me ponder whether an engine like Alpha-Zero could be taught to play chess in reverse, striving to reach the initial state.  Given that Alpha-Go has won at Go, where the positions get more complicated as you go along, I wonder if their algorithms might overcome the limits brought up in the answers.
Comments.UserDisplayName: Cort Ammon
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-29T07:56:37.000Z
Comments.Text: I asked a similar question some time ago: https://chess.stackexchange.com/questions/15146/calculate-the-first-n-unknown-moves-of-a-chess-game
Comments.UserDisplayName: Adrenaxus
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-29T17:20:10.297Z
Comments.Text: I think you could probably trick the people over at the Code Golf SE into writing a solver for this for you :-D
Comments.UserDisplayName: Aaron F
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-01T07:25:51.967Z
Comments.Text: @AaronF: And then they would give you a Jelly program and leave you to make your input into jelly format, or worse still Hexagony.
Comments.UserDisplayName: user21820
Tags: <engines><retrograde-analysis>
Title: Could a chess engine do retro analysis?
ThreadText: # Could a chess engine do retro analysis?
  
  (Asked by: username_0 on 2019-11-28)
  
  If I took a legal chess position, to what extent could an engine work out the previous moves? [in some other board games such as Othello such game reconstruction is done easily with an engine.]
  
  **Tags:** engines, retrograde-analysis
  
  > **Comments:**
  > **username_1**: I don't have any real data to go with, but your question makes me ponder whether an engine like Alpha-Zero could be taught to play chess in reverse, striving to reach the initial state.  Given that Alpha-Go has won at Go, where the positions get more complicated as you go along, I wonder if their algorithms might overcome the limits brought up in the answers.  
  > **username_2**: I asked a similar question some time ago: https://chess.stackexchange.com/questions/15146/calculate-the-first-n-unknown-moves-of-a-chess-game  
  > **username_3**: I think you could probably trick the people over at the Code Golf SE into writing a solver for this for you :-D  
  > **username_4**: @username_3: And then they would give you a Jelly program and leave you to make your input into jelly format, or worse still Hexagony.  
  
  ---
  
  ## 9 answers
  
  ### Answer by username_8 on 2019-11-28. Score: 16 | Accepted answer
  
  Engines like Stockfish and Komodo are not able to work out the previous moves, because that is not what they are programmed for.
  
  However, it is vanishingly unlikely that anybody can ever program an engine that works out legal previous moves. The logic of working out whether a possible previous move is legal or not is extremely difficult.
  
  To start with, **how do we list possible previous moves?**
  
  Possible previous moves, called retractions (if we ignore legality for a second) are easily found algorithmically - every piece retracts as it moves in forward chess (except pawns), and they could also "uncapture" an enemy unit - pawn, knight, bishop, rook or queen. e.g. wBc4 takes pawn on f7 in reverse looks like the bishop moving from f7 to c4, with a black pawn appearing on f7.
  
  Pawns move 1 square backwards, and uncapture one square diagonally backwards. (You can figure out what the double step looks like.)
  
  With regard to checks, one can retract into what looks like "check" in regular chess, and one must always retract to never leave the opponent in "check". (So if the previous example of wBc4xbPf7 checks the black king on e8, it required white to retract the bishop to remove the "check".)
  
  Uncastling is easy to visualise (and adds the constraint that the king or rook cannot retract again). Un-en-passant is hard to describe and forms the basis of many classic retro problems. Unpromotion is again easy to visualise.
  
  So listing all potential retractions is not difficult, from a programming standpoint. **The incredibly difficult part is determining which retractions are legal.** There are many reasons why a retraction cannot be legal, ranging from simple (retracting an uncapture to leave 9 black pawns on the board, for instance) to highly convoluted (cf. most retrograde analysis problems, see [the Retro corner](https://www.janko.at/Retros/index.htm).)
  
  See for instance [this problem by Troitsky](https://chess.stackexchange.com/questions/19973/beautiful-retrograde-analysis-problem-by-alexsey-a-troitsky) on Chess.SE, and my accompanying answer to it. A lot of logic goes into proving that there is in fact only one legal retraction by black, and this is not obvious, involving counting pawn captures, considering their order, and tempo constraints.
  
  To write an engine to perform such a task, one must be able to elucidate the human logic behind it in such a way that a computer can execute the logic. This simply does not seem possible at all, given that "legality of retractions" is far more nebulous than "legality of forward chess moves".
  
  > **Comments:**
  > **username_0**: That's interesting. One thing that humans can do better!  
  > **username_15**: proving that a position is reachable from start position is in general about as hard as solving chess. Humans can only do so for a small subset of positions. For computers it's infeasible.  
  > **username_16**: @username_15 *Humans can only do so for a small subset of positions.* This is incorrect. Given a random position, in most case humans can say pretty whether it is legal or not. Some are obviously unreachable because of the pawn structure, others are trivially legal because "nothing special is going on". Retrograde analysts concentrate on the thin border zone, building sophisticated puzzles with positions than are or are not legal because of multiple subtleties.  
  > **username_17**: *Un-en-passant is hard to describe and forms the basis of many classic retro problems.* – I fail to see this. Whenever an en-passant could have happened, you could instead have the normal capture of a singly advancing pawn. Both the setup and the outcome are indistinguishable. So, one could ignore en-passant during the entire retro analysis, and simply add it at the end as an additional, trivial one-move branch whenever a singly advancing pawn was directly captured (and wasn’t blocked from advancing two fields).  
  > **username_8**: @username_17 It is not trivial and the setup is indeed distinguishable: https://chess.stackexchange.com/a/23541/15989  
  > **username_17**: @username_8: Ah, I see. So the only reason why it is difficult is that the captured pawn may have blocked a check?  
  > **username_8**: @username_17 That's one of the reasons. Another one (quite a broad topic) is how en passant retractions interact with castling rights. See https://www.janko.at/Retros/Glossary/Castling-and-En-passant.htm for a sampling, namely the last 8 problems (9-16). There are other, even more subtle interactions (e.g. with threefold repetition/50-move/Dead Reckoning) - retrograde analysis is a much deeper field than the first impression it makes.  
  > **username_18**: Retrograde-analysis of castling and en passant is going to be interesting as well. After 40 moves, there are a lot of options to pick from to go back to starting position.  
  
  ---
  
  ### Answer by username_5 on 2019-11-28. Score: 6
  
  Basically, the answer is "no", and that will probably never change.
  
  I am going to compare this to tablebases since it seems relevant due to how they are made compared to what you ask in your question. I realize they are different in certain other aspects.
  
  Tablebases, which are databases of perfect endgame play, are computed in exactly that way that you are asking: They start at the final position, and work back to the possible original position. Of course, they start from the end of the game when there are only currently 7 pieces, or less, left on the board, including kings. You can see how this is actually is MUCH easier than your question, yet it is still a HUGE undertaking for computing power as we currently know it.
  
  With only 7 pieces, it not only takes an incredible amount of time to solve even one position, and it takes a WHOPPING 140+ terabytes to store all 7-man tablebases. It took years to do this. You can see how adding even a few more pieces, this grows exponentially. Due to the extreme computing-power cost, we are not even close to starting 8-man tablebases, and it is estimated that they would take over 10 petabytes to store in their entirety. Even though you are not trying to solve every position with 32 pieces, you can see how trying to go from the end of a game back to the original 32-piece starting position is not feasible.
  
  The only question is if could they program in the human tendency to play in various ways to prune the search, but I doubt that very much, as even then, the numbers are huge.
  
  
  ---
  
  ### Answer by username_6 on 2019-11-28. Score: 6
  
  I’ve decided to expand this to a more general survey of the applicability of engines to various retro sub-genres.
  
  Chess engines (e.g. Stockfish) are good at trying out all the moves going forward in a position but famously bad at abstracting general features such as fortresses.
  
  In the same way you can easily try retracting possible least moves just by making pieces move backwards, hatch opposing pieces instead of capturing them, and run away from opposing kings that are “checking” them. The difficulty is in abstracting general
  features to find out whether the position can be derived from the starting position. The distinction between legal moves and legal positions is the key here and is a distinction made in the FIDE Laws as well.
  
  **Proof games** One retro domain that has enjoyed great success with engines is proof games. These are like retro problems except that you’ve been given the additional information of the expect number of moves. This notion of clock simplifies the retro process enormously, in a similar way that Othello games can be deduced because one knows the exact number of moves. Some people regard them as forward stipulations because you do start from the game array and can play forwards, but they are generally viewed as retros. Leading engines in this space are Natch, Euclide, Popeye and for fairy problems Jacobi.
  
  **General retros** There are fewer engines for general retro problems. These work by allowing the solver to specify constraints that are deduced by a human solver. Jacobi does this within the envelope of some notional number of moves, but the best I know is the enigmatic Rawbats, a tool only used by its maker Mario Richter, and known only by its results in augmenting its developer’s skills.
  
  **Helpmate retractors** There is a big opportunity for someone computerate to build a simple retraction engine which just tries retracting recent moves, without worrying about global legality, and then plays forwards like a regular problem engine. Such an engine, combined with a little human common sense, would be able to validate the hundreds of helpmate retractor compositions which are currently untestable.
  
  I want to finish by mentioning two retros areas which are less amenable to engine assault.
  
  **Problems based on conventions** One is the domain of retro conventions: castling, en passant and other related rules. Combining a logical reasoning system with a chess engine has not been done, and in some cases there are deep ambiguities in the conventions themselves. This work is normally left for the human to solve, but in principle if the conventions could be grounded logically, it would be an interesting research topic.
  
  **Defensive retractors** The other difficult genre of retro composition contains the highly technical defensive detractors of various kinds. These essentially involve playing chess backwards in a competitive way, and questions of position legality are normally the key without which the problems compositions make little sense.
  
  
  ---
  
  ### Answer by username_7 on 2019-11-28. Score: 6
  
  Current engines can't do this at all. Calculating backwards is quite different from calculating forward. Pieces come into existence instead of being taken.
  
  But you could certainly adapt engines to be able to perform well on this task.
  
  > **Comments:**
  > **username_8**: I disagree with the second statement - to date there is no engine even able to list fully all possible retractions (legal or illegal) from a position. And determining whether a retraction is legal is EXTREMELY difficult in retro problems - there is no neat way to encapsulate all that logic into a computer program.  
  > **username_7**: Yes, legality is difficult. I assume you'd have to find the whole game. But retractions should be relatively easily doable. And then it's just tree search.  
  > **username_8**: Tree search is horrible if only one 15-ply retraction line is legal out of many, many, many possible lines. And it doesn't even get back to the starting position. See the problem linked to in my answer for a taste of a moderately difficult retrograde problem.  
  > **username_7**: Sure, tree search requires pruning. But I concede that such an engine probably does not do well on Troitzky-problems, where there is only one legal 15-ply line. I was thinking more of the general task of recontructing the most likely line that lead to a position. I think that would be a very interesting and also tractable problem.  
  > **username_8**: Even for the general task, it is hard to say. To have an engine of some sort, we must tell it what a "legal" move/retraction is. This is indeed the hard part for regular engines (move validation), and the nearly impossible part for a retraction engine - how do you define a legal retraction in a verifiable way?  
  > **username_7**: For actual games I would try to machine learn legal / likely retractions. The final proof of legality could only be a complete game.  
  > **username_8**: @MilesRout Legal moves are defined by the rules of chess, and it is thus "easy" to check a move is legal - you just need to refer to the rules of chess. A legal retraction is defined (one possible definition) as one which starts from and results in a legal position (reachable from the starting array by legal moves). But how do you tell if a position is legal? There is no easy way to do so.  
  
  ---
  
  ### Answer by username_9 on 2019-11-29. Score: 4
  
  No.
  
  First and foremost, engines (and everybody) play against some other also (an human player, another engine, even themselves with the opposing color). They may *guess* the probable move(s) of the other actor, but they do not get too far. They pick a good move and the other actor's move helps them to narrow the range of possibilities.
  
  Reversing a game position is a different problem, as you need to *know* both players moves to solve it. You do not know if the moves were good or bad, or even if they made sense, you only know that they were legal. In that sense, rebuilding the game would be more akin to "solving" chess (getting all possible solutions of a game from the start position).
  
  Additionally, even if you strengthen the requirements ("let's guess that each player always played the move with the best analisis by the current engine") you have lots of situations where several possible predecessor states do appear. Just guess
  
  ```
  rnbqkbnr/pp1p1ppp/8/8/3p/N7/PPP1PPPP/R1B1KBNR w - - 1 13
  
  ```
  
  Does this come from?
  
  ```
  [fen ""]
  
  1. d3 c5 2. d4 e5 3. Na3 exd4 4. Qxd4 cxd4
  
  ```
  
  Or from?
  
  ```
  [fen ""]
  
  1. d3 c5 2. d4 e5 3. Na3 cxd4 4. Qxd4 exd4
  
  ```
  
  In both cases black's last move is its the strongest one, yet it does not serve you to decide which was the previous board situation. As the analysis expands backwards, the possibilities multiply.
  
  > **Comments:**
  > **username_6**: Thanks for your answer and welcome. When engaging in retrograde analysis we do jettison in almost all cases consideration of the quality of the move. Hard enough just to consider legality. I think the engine referred to in the question was a hypothetical one designed for retro purposes rather than one of the familiar forward engines like Stockfish  
  > **username_9**: @username_6 As I see it, the idea of the quality of the move is that, as a strengthening of the conditions, it would make retrograde analysis easier, as it would limit the number of possible previous boards. My point is that even with a stronger criteria uncertainty will appear.  
  > **username_6**: Thanks again for your response, username_9. How to be absolutely objective about the quality of the move? It can't depend upon an engine at a given moment in time. One futuristic idea I heard from top retro composer Nicolas Dupont is to link with the reflexmate condition, so any mate in 1 is mandatory. Under reflexmate-2, any mate in 2 is mandatory etc. So we can converge towards a world where retrograde analysis assumes perfect play. But remember the primary goal is chess composition is an artistic one: to achieve cool effects, it's not necessarily to make retroanalysis easier.  
  
  ---
  
  ### Answer by username_10 on 2019-11-29. Score: 3
  
  As others have said, current engines are not meant to do that. But from a theoretical computer science perspective, it is "possible", although likely unfeasible.
  
  Just like a "forward" chess engine can search at most a few (dozens?) moves in the future (because the possibilities explodes exponentially), a backwards engine would suffer from the exact same limitation.
  
  I think enumerating all legal backwards move from a given board state is relatively simple (contrary to what others have said), but the number of possibilities explodes exponentially the farther back we go.
  
  Anyway, since the number of board states is finite, it is theoretically "possible" to write such a program: given enough time, a computer will analyze every possible state and eventually concludes with a valid game up to that point (it is non-unique; many games can lead to the same state), or conclude that such position is impossible (even if it takes many times the age of the universe to get there, hence the quotes on "possible"). This is what we computer scientists call a [decidable problem](https://en.wikipedia.org/wiki/Undecidable_problem). Such approach is probably not feasible (as it is certainly not feasible for "forward chess").
  
  But modern chess engines does not blindly enumerates every possibility. Instead they use very advanced heuristics to decide the likelihood of a movement, and they perform very well against humans. It seems to me that similar heuristics and techniques can be used to create a backwards game of chess in a software that works at least sometimes.
  
  > **Comments:**
  > **username_11**: I don't doubt we could build a game that leads to a legal position in acceptable time in most cases. However, that result would almost positively be meaningless, as we'd have to drop the implicit assumption that the game 'makes sense'. We'd most likely get a game where first only the pawns move in position, then all missing pieces get cooperatively sacrificed, with finally each piece moving into position like clockwork.  
  > **username_10**: It may be that the reconstructed legal game is "illogical", but I highly doubt that are so many "illogical" legal paths that leads to a logical board state, specially if positional analysis is used to help with the reconstruction. In fact, the "logical" possibilities is what might help a backwards engine to filter out the unlikely paths.  
  
  ---
  
  ### Answer by username_12 on 2019-11-30. Score: 3
  
  It's true that starting from the target position, searching for possible previous moves will probably be infeasible. However, there is an approach that could yield a reasonable game that hits the target position.
  
  In normal chess engines, the computer scores each position with some criteria, such as how many pieces it has remaining. The purpose of the score is to decide how likely it is to win from that position.
  
  One could instead use a different set of scoring criteria, such as how many pieces are in correct places, and whether the set of remaining pieces matches the target.
  
  Placing two such engines playing a normal forwards-game against each other could probably generate a game that ends up in the target position.
  
  **Extra:** A fun extension would be to use the normal scoring for predicting opponent's moves and the target scoring for chess engine's own moves. This way the plays-for-target chess engine would try to force a plays-for-win opponent to end up in the specific position. Of course this would only be possible for a small subset of positions.
  
  
  ---
  
  ### Answer by username_13 on 2019-12-01. Score: 2
  
  While it might not be currently possible to write an AI that does better than humans, there are some relevant programs under the "retro, programy, úlohy" subheading [here](http://members.chello.cz/chessproblems/links0.htm)
  
  
  ---
  
  ### Answer by username_14 on 2019-11-30. Score: 1
  
  From the pure theoretical point of view: Yes, it is possible.
  
  You just need to play forward all possible games until you find at least one game that contains the current position. Then you use the moves it played forward to do your retro analysis.
  
  But you cannot **just** do it, as the amount of possible games is huge. So this point is only a proof, that it is possible in theory. In practice, the question is if it is tractable in a reasonable time.
  
  I suppose it is tractable by extending some of the current planning methods, but the details are not straightforward. I would recommend asking the question if an AI can achieve this at <https://ai.stackexchange.com>, as it is an interesting question about game AIs and may spark some quite interesting answers on that site.
  
  
  ---
  
  