Could this program be written?

[sje]

Anyone who has written a tablebase generator program knows how to implement a retro move generator that outputs all possible prior moves (for a piece distribution class) that lead to a given position. That's the easy part. However, consider the much harder challenge of writing a program that generates a sequence of retro moves, say, all the way back to the initial array. (Or proves that such a sequence doesn't exist for a particular position.)

Is this task unreasonable or impossible? Has anyone tried it?

[bob]

Anyone who has written a tablebase generator program knows how to implement a retro move generator that outputs all possible prior moves (for a piece distribution class) that lead to a given position. That's the easy part. However, consider the much harder challenge of writing a program that generates a sequence of retro moves, say, all the way back to the initial array. (Or proves that such a sequence doesn't exist for a particular position.)

Is this task unreasonable or impossible? Has anyone tried it?

It seems just as hard as searching to the end of the game. Except that you would know (I assume) how many moves have been made so if you search backward beyond that limit without reaching the starting position you could abort that path. But otherwise, if you start at move 20, it would be a huge computational task and alpha/beta doesn't seem to apply very well.

[sje]

It seems just as hard as searching to the end of the game. Except that you would know (I assume) how many moves have been made so if you search backward beyond that limit without reaching the starting position you could abort that path. But otherwise, if you start at move 20, it would be a huge computational task and alpha/beta doesn't seem to apply very well.

First, I can see a minor application of such a program for certain kinds of problem solving. Also, it could be used to boot out otherwise legal FEN specifications.

Let's say that the number of prior moves is not important; we just want to know if the position is reachable from the initial array and provide some sequence that works. The only hard and fast constraint is that the move sequence must be legal when played in the forward direction. (It's like Rubik's Cube descrambler algorithm that can detect an impossible parity cube configuration while solving any reachable position.)

I can think of some ideas that will work some of the time and maybe most of the time. But there seem to be some positions where it would require exponential work to navigate a reverse path.

[bob]

It seems just as hard as searching to the end of the game. Except that you would know (I assume) how many moves have been made so if you search backward beyond that limit without reaching the starting position you could abort that path. But otherwise, if you start at move 20, it would be a huge computational task and alpha/beta doesn't seem to apply very well.

First, I can see a minor application of such a program for certain kinds of problem solving. Also, it could be used to boot out otherwise legal FEN specifications.

Let's say that the number of prior moves is not important; we just want to know if the position is reachable from the initial array and provide some sequence that works. The only hard and fast constraint is that the move sequence must be legal when played in the forward direction. (It's like Rubik's Cube descrambler algorithm that can detect an impossible parity cube configuration while solving any reachable position.)

I can think of some ideas that will work some of the time and maybe most of the time. But there seem to be some positions where it would require exponential work to navigate a reverse path.

I suppose you could use some sort of "Hamming distance" evaluation, where in this case, rather than the number of bits different, it would be the distance between the starting position and the current position, to give a clue that you are getting closer.

[Uri Blass]

Anyone who has written a tablebase generator program knows how to implement a retro move generator that outputs all possible prior moves (for a piece distribution class) that lead to a given position. That's the easy part. However, consider the much harder challenge of writing a program that generates a sequence of retro moves, say, all the way back to the initial array. (Or proves that such a sequence doesn't exist for a particular position.)

Is this task unreasonable or impossible? Has anyone tried it?

I remember reading that there are people who did it and have a program that try to compose a game that lead to specific position.

They use the idea that Bob Hyatt mentioned in his last post.

The program cannot work for every position but it can find games that lead to specific positions in many cases.

Uri

[Rein Halbersma]

Anyone who has written a tablebase generator program knows how to implement a retro move generator that outputs all possible prior moves (for a piece distribution class) that lead to a given position. That's the easy part. However, consider the much harder challenge of writing a program that generates a sequence of retro moves, say, all the way back to the initial array. (Or proves that such a sequence doesn't exist for a particular position.)

Is this task unreasonable or impossible? Has anyone tried it?

It seems just as hard as searching to the end of the game. Except that you would know (I assume) how many moves have been made so if you search backward beyond that limit without reaching the starting position you could abort that path. But otherwise, if you start at move 20, it would be a huge computational task and alpha/beta doesn't seem to apply very well.

If you have a database (hashtable) of chess games (I guess the good ones have several million games, perhaps tens of millions of positions) it becomes somewhat easier. Starting from a position to prove, if a retrograde search encounters any of the positions from the database, you are done. Disproving is harder of course, since you have to prove that none of the backward branches leads to the initial position.

Just as an utopian solution: for games that are strongly solved (i.e. have endgame tablebases up to the initial position) it can be done by computing a "reachability tablebase". Just start with a tablebase that has a 1 for the initial position and 0 for every other position. Then keep searching forward and add a 1 for every position that you encounter until no new positions are found.