fast chess proof algorithm, not shortest

[DustinYoder]

I am in need of an algorithm which will return the list of legal moves required to create a given chess position. This algorithm can assume the position being supplied is a valid position. I am not interested in shotest proofs. Just a systematic proof thaT can be calculated very very quickly. Is this available already or do I need to try to make one?

[JuLieN]

Hello to you too, Dustin.

What you are searching for is called a retrograde analysis algorithm. AFAIK there is no publicly available one, although there exist a program, called Retractor, that can do that.

http://www-cs-students.stanford.edu/~hw ... Retractor/

Note that this "backward chess" problem is much more difficult than normal chess and I don't think there will ever be a program fast enough to give you all the moves that led to a position say at move 40 in a reasonable time.

[Vladimir Xern]

Hello to you too, Dustin.

What you are searching for is called a retrograde analysis algorithm. AFAIK there is no publicly available one, although there exist a program, called Retractor, that can do that.

http://www-cs-students.stanford.edu/~hw ... Retractor/

Note that this "backward chess" problem is much more difficult than normal chess and I don't think there will ever be a program fast enough to give you all the moves that led to a position say at move 40 in a reasonable time.

I don't think that this is quite the same as other retrograde analysis problems. It seems that he's asking for something that will take a certain position like the following:

[d] 1Brb1rbN/1P1pkp1P/1q1qpq1q/1N1QbQ1B/1Qn1n1nQ/2Q3Q1/3R1R2/4K3 w - -

and generate all of the moves to get from the starting position to the given position. This is called a "proof" game because it proves the position is legally reachable.

Aside from the shortest proof game solvers Natch and Euclide, I know of nothing that can do what he's asking for. It might be possible to modify Natch to try to find any proof game, rather than the shortest one, but I don't think anyone's written something like this before.

[DustinYoder]

Sorry for no introduction, I'm very excited to find a forum on programming chess since I have not done this before.

I am more excited to hear no one has written this as it would be a key concept to something I am working on. Although now it looks like I may to try to write this myself. At least I may be heading down the correct path.

Anyone interested in hashing this algorithm out?

It seems to me that we would have to start by figuring out what pieces will remain on the board and which ones will have to be removed. Sound correct? Then we'd look at how many pawns need to be promoted to something else and figure out what exactly.