Prove that a position is legal and reachable.

[DustinYoder]

Here is a rough beginning for a pseudo outline for the algorithm I described above. I am posting this as a rough beginning and I would like any comments or improvements on any of these. I'll keep editing the list until I get something that seems like it might work on paper.

--DETERMINE PIECES THAT CANNOT MOVE
-Check castling rights. (Do NOT allow the king and rooks to be moved if they can still castle in the final position)
-Check if any pawns in the final position are still in their beginning position (these pawns are NOT allowed to move if this is the case)

--DETERMINE SOME SPECIAL CASES THAT WE SHOULD CONSIDER BEFORE MOVING PIECES AROUND
-Do we need to promote any pawns (check for 2+queens, 3+knights, 2+bishops on same color, 3+rooks) We will need to promote a pawn to accomplish these requirements
-Are there any pawns doubled up or worse (pawns only change file by capturing)
-Are any pawns behind enemy pawns? (pawns only change file by capturing)

more coming soon.

[hgm]

I guess that the trial and error is the only way to go here.

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.

I am not so sure. It seems to me that unreachable positions are extremely rare. (If there isn't something obviously wrong with the number of pieces, etc.) Chess pieces are very powerful, and once they get out from behind the Pawn wall, they an basically go anywhere. So you must run into a barrier pretty quickly, or you create complete freedom.

E.g. with e2 and g2 still in place Bf1 is obviously trapped. But merely playing g3 already allows Ke1, Qd1, Bf1 (and of course the Knights) to roam the board, and Rh1 to move upto d1.

[Cubeman]

[d]6b1/ppp1pp1B/2k1p1p1/8/5P2/3PprP1/PPPrPqRP/RnK2nb1 w - -
Is a test position that George Tsavdaris posted a few years ago apparantly the position is a draw and you have to prove it.Could the program that was suggested earlier in topic http://natch.free.fr/Natch.html recreate this game?

[Uri Blass]

I guess that the trial and error is the only way to go here.

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.

I am not so sure. It seems to me that unreachable positions are extremely rare. (If there isn't something obviously wrong with the number of pieces, etc.) Chess pieces are very powerful, and once they get out from behind the Pawn wall, they an basically go anywhere. So you must run into a barrier pretty quickly, or you create complete freedom.

E.g. with e2 and g2 still in place Bf1 is obviously trapped. But merely playing g3 already allows Ke1, Qd1, Bf1 (and of course the Knights) to roam the board, and Rh1 to move upto d1.

I do not think that unreachable positions are extremely rare.
There are many positions when the pawn structure is illegal
or it is simply impossible for pieces to go to the relevant square(for example white Bh8 black king g7).

I also do not think that writing a program which would be able to give the correct answer for every position effectively requires solving chess
inspite of the fact that
I agree that it is not an easy problem to solve.

I think that smart humans can effectively give the correct answer for every position(they may need to think some hours or maybe some days about some positions).

[hgm]

I do not think that unreachable positions are extremely rare.

'Extremely rare' should be understood in the context of the total number of positions. So there coud be billions, and they could still be extremely rare, because the state space of Chess is so large.

There are many positions when the pawn structure is illegal
or it is simply impossible for pieces to go to the relevant square(for example white Bh8 black king g7).

Testing if a Pawn structure is reachable is actually quite feasible. For one there are a few easy heuristics to establish that a structure is not reachable, (e.g. white pawns on a2, a3 and b2) based on Pawn counts below each diagonal, in each file, and number of missing opponent pieces. Exhaustive (retrograde) search is qite possible with only Pawns.

The in-check problem is a short-term one. Positions like you describe, or triple checks, etc., are immediately caught because you cannot even do a single retro-move to a legal position.

[Sven]

[d]6b1/ppp1pp1B/2k1p1p1/8/5P2/3PprP1/PPPrPqRP/RnK2nb1 w - -
Is a test position that George Tsavdaris posted a few years ago apparantly the position is a draw and you have to prove it.Could the program that was suggested earlier in topic http://natch.free.fr/Natch.html recreate this game?

If you say it is "apparently a draw" but Houdini and Stockfish both say that it were mated in 10, the only possible explanation could be that retro analysis would reveal it is a draw by 50 moves rule ...

Sven

[Sven]

I tried Natch2.5b from the site above and did as described in the readme, but it always complains:

Code: Select all

Error : Found no legal Forsythe position in file : ...

for that position, even after adding several different plausible numbers for the missing 50 moves counter and full move number.

Sven

[Arpad Rusz]

Yes, using this program is tricky: you should paste the position not in FEN notation but in simple Forsyth notation followed in a second line by the number of plies:

rnbqkb1r/ppp2ppp/8/8/8/8/PPPPPPPP/RNBQKB1R
8


[D]rnbqkb1r/ppp2ppp/8/8/8/8/PPPPPPPP/RNBQKB1R w

There is only one solution in 4.0 moves:
1.Sg1-f3 Pe7-e5 2.Sf3xe5 Sg8-e7 3.Se5xd7 Se7-c6
4.Sd7xb8 Sc6xb8

[bob]

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]

It is a classic tree-search problem. And one that is likely NOT going to be done by a computer program. You just have a goal of reaching the original position, and the moves you generate to search are "unmoves" (same as normal moves for pieces, but not pawns...)

It is possible, but beyond computationally intractable...

[geots]

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]

It is a classic tree-search problem. And one that is likely NOT going to be done by a computer program. You just have a goal of reaching the original position, and the moves you generate to search are "unmoves" (same as normal moves for pieces, but not pawns...)

It is possible, but beyond computationally intractable...

I wish you would come to this side more often. You are the only one I can argue with who doesn't get his drawers in a wad. Right and wrong is irrelevant. It's just the arguing that is fun with you.


Best,

george