ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Prove that a position is legal and reachable.
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: General Topics Flat
View previous topic :: View next topic  
Author Message
Julien MARCEL



Joined: 05 May 2008
Posts: 2269
Location: Nantes (France)
PostPost subject: Re: Prove that a position is legal and reachable.    Posted: Wed May 16, 2012 11:45 am Reply to topic Reply with quote
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]


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.

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.
_________________
Author of Prédateur chess engine: http://predateur-chess.blogspot.fr
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
Prove that a position is legal and reachable. Dustin Yoder Wed May 16, 2012 11:23 am
      Re: Prove that a position is legal and reachable. Julien MARCEL Wed May 16, 2012 11:45 am
            Re: Prove that a position is legal and reachable. Arpad Rusz Wed May 16, 2012 1:22 pm
      Re: Prove that a position is legal and reachable. Uri Blass Wed May 16, 2012 1:28 pm
      Re: Prove that a position is legal and reachable. Ricardo Barreira Wed May 16, 2012 1:49 pm
            Re: Prove that a position is legal and reachable. Julien MARCEL Wed May 16, 2012 1:55 pm
                  Re: Prove that a position is legal and reachable. Sven Schüle Wed May 16, 2012 2:43 pm
                  Re: Prove that a position is legal and reachable. H.G.Muller Wed May 16, 2012 6:25 pm
                        Re: Prove that a position is legal and reachable. George Tsavdaris Sat May 19, 2012 2:22 pm
      Re: Prove that a position is legal and reachable. Edmund Moshammer Wed May 16, 2012 2:49 pm
            Re: Prove that a position is legal and reachable. George Tsavdaris Sat May 19, 2012 1:50 pm
      Re: Prove that a position is legal and reachable. Joona Kiiski Wed May 16, 2012 6:39 pm
            Re: Prove that a position is legal and reachable. H.G.Muller Wed May 16, 2012 6:50 pm
                  Re: Prove that a position is legal and reachable. Alex Brown Wed May 16, 2012 10:57 pm
                        Re: Prove that a position is legal and reachable. Sven Schüle Thu May 17, 2012 9:01 pm
                              Re: Prove that a position is legal and reachable. Sven Schüle Thu May 17, 2012 9:27 pm
                                    Re: Prove that a position is legal and reachable. Arpad Rusz Thu May 17, 2012 9:58 pm
                              Re: Prove that a position is legal and reachable. George Tsavdaris Sat May 19, 2012 2:40 pm
                                    Re: Prove that a position is legal and reachable. Sven Schüle Sat May 19, 2012 8:56 pm
                                    Re: Prove that a position is legal and reachable. Alex Brown Sat May 19, 2012 9:27 pm
                  Re: Prove that a position is legal and reachable. Uri Blass Thu May 17, 2012 2:55 am
                        Re: Prove that a position is legal and reachable. H.G.Muller Thu May 17, 2012 8:39 am
      Algorithm Ideas Dustin Yoder Wed May 16, 2012 6:48 pm
            Re: Algorithm Ideas fernando Sat May 19, 2012 5:12 pm
      Re: Prove that a position is legal and reachable. Robert Hyatt Thu May 17, 2012 9:59 pm
            Re: Prove that a position is legal and reachable. George Speight Fri May 18, 2012 2:34 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: General Topics

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads