15

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

  • 2
    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. – Cort Ammon - Reinstate Monica Nov 28 at 17:12
  • 1
    I asked a similar question some time ago: chess.stackexchange.com/questions/15146/… – Adrenaxus Nov 29 at 7:56
  • 1
    I think you could probably trick the people over at the Code Golf SE into writing a solver for this for you :-D – Aaron F Nov 29 at 17:20
  • 2
    @AaronF: And then they would give you a Jelly program and leave you to make your input into jelly format, or worse still Hexagony. – user21820 Dec 1 at 7:25
15

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

  • 1
    That's interesting. One thing that humans can do better! – Snack_Food_Termite Nov 28 at 8:49
  • 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. – Sopel Nov 28 at 22:58
  • 1
    @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. – Evargalo Nov 29 at 8:02
  • 1
    @Wrzlprmft It is not trivial and the setup is indeed distinguishable: chess.stackexchange.com/a/23541/15989 – Remellion Nov 29 at 9:16
  • 1
    @Wrzlprmft That's one of the reasons. Another one (quite a broad topic) is how en passant retractions interact with castling rights. See 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. – Remellion Nov 29 at 9:53
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.

  • 1
    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. – Remellion Nov 28 at 8:27
  • 1
    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. – BlindKungFuMaster Nov 28 at 8:34
  • 1
    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. – Remellion Nov 28 at 8:46
  • 1
    For actual games I would try to machine learn legal / likely retractions. The final proof of legality could only be a complete game. – BlindKungFuMaster Nov 28 at 9:19
  • 1
    @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. – Remellion Nov 29 at 5:18
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.

  • 1
    Unless I'm misunderstanding something, constructing a table of all possible ways in which a game could come about (tablebases) is much much harder than working out just one way that a game could come about (retro analysis). – Miles Rout Nov 28 at 20:59
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.

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.

  • 3
    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 – Laska Nov 29 at 2:37
  • 2
    @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. – user20689 Nov 29 at 18:20
  • 1
    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. – Laska Nov 29 at 18:35
2

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.

  • 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. – Sudix Nov 30 at 10:14
  • 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. – lvella Dec 2 at 13:54
2

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.

1

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

0

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.

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.