Could a chess engine do retro analysis?

Question

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.]

Answer 1

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.)

See for instance this problem by 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".

Answer 2

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.

Answer 3

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 4

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 5

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.

Answer 6

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. 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.

Answer 7

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 8

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

Answer 9

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.