TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Uri Blass

Joined: 08 Mar 2006
Posts: 5958
Location: Tel-Aviv Israel

Post subject: Re: Prove that a position is legal and reachable.    Posted: Wed May 16, 2012 1:28 pm

 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]

I believe that somebody did something like it and
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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Dustin Yoder Wed May 16, 2012 11:23 am
Julien MARCEL Wed May 16, 2012 11:45 am
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
Ricardo Barreira Wed May 16, 2012 1:49 pm
Julien MARCEL Wed May 16, 2012 1:55 pm
Sven Schüle Wed May 16, 2012 2:43 pm
H.G.Muller Wed May 16, 2012 6:25 pm
George Tsavdaris Sat May 19, 2012 2:22 pm
Edmund Moshammer Wed May 16, 2012 2:49 pm
George Tsavdaris Sat May 19, 2012 1:50 pm
Joona Kiiski Wed May 16, 2012 6:39 pm
H.G.Muller Wed May 16, 2012 6:50 pm
Alex Brown Wed May 16, 2012 10:57 pm
Sven Schüle Thu May 17, 2012 9:01 pm
Sven Schüle Thu May 17, 2012 9:27 pm
Arpad Rusz Thu May 17, 2012 9:58 pm
George Tsavdaris Sat May 19, 2012 2:40 pm
Sven Schüle Sat May 19, 2012 8:56 pm
Alex Brown Sat May 19, 2012 9:27 pm
Uri Blass Thu May 17, 2012 2:55 am
H.G.Muller Thu May 17, 2012 8:39 am
Dustin Yoder Wed May 16, 2012 6:48 pm
fernando Sat May 19, 2012 5:12 pm
Robert Hyatt Thu May 17, 2012 9:59 pm
George Speight Fri May 18, 2012 2:34 am

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
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