Answers.Body: <p>Easy illegality is easy: not exactly 1 king on both sides, both kings in check, pawns on the final ranks. It's also fairly easy to tally promoted material and subtract the missing pawns. A quick captures test, together with the pawn structures, is also possible.</p>
  <p>An impossibility of last move test, even if only cursorily, is already tricky.</p>
  <p>A full test is NP-hard (in whatever sense), I fear. There are many chess problems asking &quot;Legal?&quot; and they can be fiendlishly hard. (Note that the mentioned programs have no chance against them.) In any case, a quick illegality test is far easier than a quick legality test, if the position looks even remotely doubtful.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-15T15:49:10.683Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/127547/discussion-on-answer-by-hauke-reddmann-which-methods-can-be-used-to-prove-that-a).
Answers.UserDisplayName: Brian Towers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-15T23:34:21.037Z
Answers.Text: The problem for generalised chess could be in co-NP, as a sequence of legal moves to the position is a counterexample (certificate to the complement class). It depends on how the max length of a legal sequence varies by board size. If it's in co-NP then it's not likely to be NP-hard, but could be co-NP complete.
Answers.UserDisplayName: A.M.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-13T19:31:53.360Z
Answers.LastActivityDate: 2021-07-13T19:31:53.360Z
Answers.UserDisplayName: Hauke Reddmann
Body: <p>Given a board position, there are <a href="https://chess.stackexchange.com/questions/33328/given-a-legal-chess-position-is-there-an-algorithm-that-generates-a-series-of-m">programs</a> that try to find a series of legal moves that lead to it.</p>
  <p>Are there algorithms that can do the opposite - prove that the position <em>is not</em> reachable by a series of legal moves?</p>
  <p>Proof by exhaustion doesn't seem possible in the general case due to the size of the search space, but are there other methods?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-14T13:02:19.250Z
Comments.Text: Since I'm not that much of an expert at chess I thought it would be interesting to answer this a bit more from the algorithm side. The problem is that by design the algorithm has to work in a way that it can track valid moves and boards because proving this as a negative is trying to prove an unknowable. Any algorithm that would try to prove the negative would start with a basic chessboard layout and keep playing until you can say that the expected end can't be reached. But the problem is that there are always games where there are always moves to be made, no matter how arbitrary or repeated,
Comments.UserDisplayName: skippy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-14T23:07:43.007Z
Comments.Text: Related: https://chess.stackexchange.com/questions/1482/how-do-you-know-when-a-fen-position-is-legal
Comments.UserDisplayName: fartgeek
Tags: <analysis><programming><retrograde-analysis><calculation><chess-algorithms>
Title: Which methods can be used to prove that a position is illegal?
ThreadText: # Which methods can be used to prove that a position is illegal?
  
  (Asked by: username_0 on 2021-07-13)
  
  Given a board position, there are [programs](https://chess.stackexchange.com/questions/33328/given-a-legal-chess-position-is-there-an-algorithm-that-generates-a-series-of-m) that try to find a series of legal moves that lead to it.
  
  Are there algorithms that can do the opposite - prove that the position *is not* reachable by a series of legal moves?
  
  Proof by exhaustion doesn't seem possible in the general case due to the size of the search space, but are there other methods?
  
  **Tags:** analysis, programming, retrograde-analysis, calculation, chess-algorithms
  
  > **Comments:**
  > **username_1**: Since I'm not that much of an expert at chess I thought it would be interesting to answer this a bit more from the algorithm side. The problem is that by design the algorithm has to work in a way that it can track valid moves and boards because proving this as a negative is trying to prove an unknowable. Any algorithm that would try to prove the negative would start with a basic chessboard layout and keep playing until you can say that the expected end can't be reached. But the problem is that there are always games where there are always moves to be made, no matter how arbitrary or repeated,  
  > **username_2**: Related: https://chess.stackexchange.com/questions/1482/how-do-you-know-when-a-fen-position-is-legal  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2021-07-13. Score: 12
  
  Easy illegality is easy: not exactly 1 king on both sides, both kings in check, pawns on the final ranks. It's also fairly easy to tally promoted material and subtract the missing pawns. A quick captures test, together with the pawn structures, is also possible.
  
  An impossibility of last move test, even if only cursorily, is already tricky.
  
  A full test is NP-hard (in whatever sense), I fear. There are many chess problems asking "Legal?" and they can be fiendlishly hard. (Note that the mentioned programs have no chance against them.) In any case, a quick illegality test is far easier than a quick legality test, if the position looks even remotely doubtful.
  
  > **Comments:**
  > **username_4**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/127547/discussion-on-answer-by-username_3-which-methods-can-be-used-to-prove-that-a).  
  > **username_5**: The problem for generalised chess could be in co-NP, as a sequence of legal moves to the position is a counterexample (certificate to the complement class). It depends on how the max length of a legal sequence varies by board size. If it's in co-NP then it's not likely to be NP-hard, but could be co-NP complete.  
  
  ---
  
  