I am actually needing to find an algorithm that can prove that a given board position is reachable by some sequence of legal moves beginning from the standard chess initial position? Is this even remotely possible? I would prefer to have an algorithm that could execute in minutes rather than hours or days.
I realize this is super difficult and I'm almost positive it has not yet been done. I am just looking for direction, ideas and someone that might want to help try to solve this problem.[/b]
Prove that a position is legal and reachable.
Moderators: hgm, Rebel, chrisw
-
- Posts: 21
- Joined: Wed Jul 13, 2011 5:20 am
-
- Posts: 2949
- Joined: Mon May 05, 2008 12:16 pm
- Location: Bordeaux (France)
- Full name: Julien Marcel
Re: Prove that a position is legal and reachable.
This doesn't look like a trivial task, but it doesn't seem impossible either, considering that you didn't ask for the algorithm to find the "shortest solution". For example, how long would it take for a Nb1 on an empty board to reach c1? The shortest move sequence is Nb1-c3-e2-c1. But there is nearly an infinity of longer solution.DustinYoder wrote:I am actually needing to find an algorithm that can prove that a given board position is reachable by some sequence of legal moves beginning from the standard chess initial position? Is this even remotely possible? I would prefer to have an algorithm that could execute in minutes rather than hours or days.
I realize this is super difficult and I'm almost positive it has not yet been done. I am just looking for direction, ideas and someone that might want to help try to solve this problem.[/b]
Starting with that, I see a simple "general" algorithm to reach your goal:
- Starting with the final position, put on a list all the pieces from the starting position that need to be captured. (Still a lot of subtleties not to neglect: pawns can't reach all squares, nor can a white-squares bishop reach black squares and so on...)
- [EDIT]: here, assign a goal square to all the remaining pieces.
- move all the pawns for which such moves don't compromise their chances to reach their final goal (easier when those pawns need to be captured), in order to make room so all pieces can move.
- start moving the pieces that have to be captured and put them where they can be captured. Capture them and repeat until the list is empty. (Subtlety: don't compromise pawn's chances to reach their final square).
- move the remaining pieces to their final destination.
None of those steps is trivial but they seem reachable to me.
Now if you add some new constraints it becomes much more difficult. Such constraints could be:
- only plausible moves (for example don't put your queen in situation to be captured by an enemy pawn);
- shortest possible solution.
"The only good bug is a dead bug." (Don Dailey)
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
-
- Posts: 273
- Joined: Sat Apr 17, 2010 2:34 pm
- Location: Budapest
Re: Prove that a position is legal and reachable.
There is a software which searches for "proof games":
http://natch.free.fr/Natch.html
http://natch.free.fr/Natch.html
-
- Posts: 10297
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Prove that a position is legal and reachable.
I believe that somebody did something like it andDustinYoder wrote:I am actually needing to find an algorithm that can prove that a given board position is reachable by some sequence of legal moves beginning from the standard chess initial position? Is this even remotely possible? I would prefer to have an algorithm that could execute in minutes rather than hours or days.
I realize this is super difficult and I'm almost positive it has not yet been done. I am just looking for direction, ideas and someone that might want to help try to solve this problem.[/b]
I think that the way to do it is to have some evaluation function of distance from the opening position(based on the number of missing pieces and have some move generator that undo move instead of making moves).
Now you can simply start to unmake moves that reduce the distance to the opening position until you get into the opening position.
Note that I do not see a general solution and one of the problems may be with unreachable positions that the generator is not going to be able to prove that they are unreachable.
some rules to define if a position is unreachable may help and
knowing that patterns like Ba1 and pawn at b2 is unreachable can help.
-
- Posts: 900
- Joined: Tue Apr 27, 2010 3:48 pm
Re: Prove that a position is legal and reachable.
I wouldn't be surprised if there are some examples of positions which are known to be impossible to reach, yet the process for concluding so is not at all simple. If there are such positions it would give you an idea of the difficulty level of your problem.
-
- Posts: 2949
- Joined: Mon May 05, 2008 12:16 pm
- Location: Bordeaux (France)
- Full name: Julien Marcel
Re: Prove that a position is legal and reachable.
[d]rnbkqbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBKQBNR w KQkq - 0 1rbarreira wrote:I wouldn't be surprised if there are some examples of positions which are known to be impossible to reach, yet the process for concluding so is not at all simple. If there are such positions it would give you an idea of the difficulty level of your problem.
Here's one! ^^
"The only good bug is a dead bug." (Don Dailey)
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Prove that a position is legal and reachable.
... with the minor correction of removing all castling rights:JuLieN wrote:[d]rnbkqbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBKQBNR w KQkq - 0 1rbarreira wrote:I wouldn't be surprised if there are some examples of positions which are known to be impossible to reach, yet the process for concluding so is not at all simple. If there are such positions it would give you an idea of the difficulty level of your problem.
Here's one! ^^
[d]rnbkqbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBKQBNR w - - 0 1
Sven
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: Prove that a position is legal and reachable.
I remember having read a paper about this very topic some years back.
"legality of positions.pdf" it used to be available on dann corbits ftp server, which is down nowadays. Maybe someone still has a copy of this paper.
"legality of positions.pdf" it used to be available on dann corbits ftp server, which is down nowadays. Maybe someone still has a copy of this paper.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Prove that a position is legal and reachable.
That one is not so difficult, with the algorithm you proposed (even if I am forgiving about the castling rights). This one is more subtle:JuLieN wrote:[d]rnbkqbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBKQBNR w KQkq - 0 1rbarreira wrote:I wouldn't be surprised if there are some examples of positions which are known to be impossible to reach, yet the process for concluding so is not at all simple. If there are such positions it would give you an idea of the difficulty level of your problem.
Here's one! ^^
[d]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR b KQkq - 0 1
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: Prove that a position is legal and reachable.
I guess that the trial and error is the only way to go here.DustinYoder wrote:I am actually needing to find an algorithm that can prove that a given board position is reachable by some sequence of legal moves beginning from the standard chess initial position? Is this even remotely possible? I would prefer to have an algorithm that could execute in minutes rather than hours or days.
I realize this is super difficult and I'm almost positive it has not yet been done. I am just looking for direction, ideas and someone that might want to help try to solve this problem.[/b]
Much more difficult problem would be to prove that given position is not reachable from the initial position.
I guess that writing program which would be able to give the correct answer for every position effectively requires solving chess.
Joona Kiiski