Answers.Body: <p>Update on the comment by usul.
  The algorithm is now described here:
  <a href="https://chasolver.org/FUN22-full.pdf" rel="nofollow noreferrer">https://chasolver.org/FUN22-full.pdf</a></p>
  <p>It combines a search of variations with a dedicated mechanism for identifying blocked positions such as:
  <a href="https://lichess.org/hPiwD75i#97" rel="nofollow noreferrer">https://lichess.org/hPiwD75i#97</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-27T17:03:53.963Z
Answers.LastActivityDate: 2022-04-27T17:03:53.963Z
Answers.UserDisplayName: Miguel Ambrona
Answers.Body: <p>I just learned of an engine that analyzes chess positions to determine if checkmate by one side is impossible: <a href="https://elrubiongamma.ddns.net/chess-unwinnability-analyzer/about.html" rel="nofollow noreferrer">https://elrubiongamma.ddns.net/chess-unwinnability-analyzer/about.html</a></p>
  <p>So you can solve this problem in practice by running the algorithm for both sides.</p>
  <p>It is called the Chess Unwinnability Analyzer 2. The source code is available here: <a href="https://github.com/miguel-ambrona/D3-Chess" rel="nofollow noreferrer">https://github.com/miguel-ambrona/D3-Chess</a></p>
  <p>I don't see a description of how the algorithm works, but it seems to be roughly based on brute force. There is a faster mode that is not quite as accurate. If someone knows more about the algorithm, please expand this answer!</p>
  <p>Here is an interesting example position linked by the author where checkmate is impossible, but it's not immediately obvious (I've put this in the question now as a motivating example): <a href="https://lichess.org/bKHPqNEw#81" rel="nofollow noreferrer">https://lichess.org/bKHPqNEw#81</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-26T22:08:03.530Z
Answers.LastActivityDate: 2022-01-27T20:25:38.303Z
Answers.LastEditDate: 2022-01-27T20:25:38.303Z
Answers.UserDisplayName: usul
Answers.Body: <p>Well, this is really 3 questions, not sure I am answering everything here.</p>
  
  <p>But there is an 'algorithm' for this problem, but it is NP complete, that is basically brute force in essence although you can make some Optimizations. This is basically the table base generating algorithm. Of course with large number of pieces this becomes difficult to apply, even for a single position.</p>
  
  <p>This Rule is basically there, so you can claim a draw in positions that are obviously drawn such as bishop and king vs lone king with no pawn and similar positions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-29T07:52:29.163Z
Answers.Text: is the bishops are different colors, mate is possible: k1K5/b7/2B5/8/8/8/8/8 w - - 0 1, do you want me to show you a sequence of legal moves, that can end up in this position?
Answers.UserDisplayName: lenik
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-29T10:16:26.110Z
Answers.Text: Yes, but I meant 1 king and bishop vs 1 king. I have edited the answer
Answers.UserDisplayName: zaifrun
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-05T08:29:49.300Z
Answers.Text: Strange claim that it is NP complete. What is `n` in this case? Can you explain how you would reduce other NP problems to this?
Answers.UserDisplayName: RemcoGerlich
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-17T14:20:05.563Z
Answers.Text: @RemcoGerlich In particular, it is a category error to call algorithms NP-complete, only computational _problems_ can be. Computing an optimal strategy for generalised chess on an n×n board is EXPTIME-complete, however. (Wikipedia gives the reference `Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214`). Most problems on an 8×8 board are "trivial" in the context of complexity theory, as they can be solved in constant time. (even if that constant is too large to solve it in practice)
Answers.UserDisplayName: Discrete lizard
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-29T06:14:40.167Z
Answers.LastActivityDate: 2018-06-29T10:17:07.470Z
Answers.LastEditDate: 2018-06-29T10:17:07.470Z
Answers.UserDisplayName: zaifrun
Answers.Body: <p>What you're asking goes by the name of "Dead Reckoning" in the domain of problems and retro problems.</p>
  
  <p>(1) There isn't an algorithm I know of except the one mentioned by zaifrun: brute force. The reason is because you can find pretty amazing positions...</p>
  
  <p>(2) Check out many problems relying on Dead Reckoning at <a href="http://www.anselan.com/chess.html" rel="noreferrer">Andrew Buchanan's website</a>.
  Also there are problem databases (<a href="https://pdb.dieschwalbe.de/" rel="noreferrer">like this one</a>) where you can run a search for 'DR' in the stipulation.</p>
  
  <p>A concrete example I recall is <a href="https://pdb.dieschwalbe.de/search.jsp?expression=PROBID=&#39;P1003981&#39;" rel="noreferrer">this one</a>, which I reproduce here. By Andrew Buchanan, in StrateGems 2002. White to move; what was the last move in this position? (The position is dead but the last move made must have been from a legal and live position - so it's uniquely determinable.)</p>
  
  <pre><code>Bb1k1b2/bKp1p1p1/1pP1P1P1/1P6/p5P1/P7/8/8 w - - 0 1
  </code></pre>
  
  <p>(3) Even grandmasters have technically made moves in a dead position! See <a href="http://wismuth.com/chess/illegal-moves.html" rel="noreferrer">François Labelle's page</a> for examples.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-29T14:41:40.050Z
Answers.LastActivityDate: 2018-06-29T14:48:05.227Z
Answers.LastEditDate: 2018-06-29T14:48:05.227Z
Answers.UserDisplayName: Remellion
Body: <p>The <a href="http://www.fide.com/fide/handbook.html?id=208&amp;view=article" rel="nofollow noreferrer">laws of chess</a> say</p>
  <blockquote>
  <p><strong>1.5.</strong> If the position is such that neither player can possibly checkmate the opponent’s king, the game is drawn (see Article 5.2.2).</p>
  <p><strong>5.2.2.</strong> The game is drawn when a position has arisen in which neither player can checkmate the opponent’s king with any series of legal moves. The game is said to end in a ‘dead position’. This immediately ends the game, provided that the move producing the position was in accordance with Article 3 and Articles 4.2 – 4.7.</p>
  </blockquote>
  <p>[Articles 3, 4.2-4.7 basically deal with making legal moves.]</p>
  <p>This is interesting because it seems possibly non-obvious whether this condition applies (though presumably rare in actual games!). <strong>Update</strong> here is an interesting example. The game is legally a draw in this position because neither side can possibly checkmate by any sequence of moves. (The game will be a draw before white can checkmate.)</p>
  <pre><code>[fen &quot;1k6/1P5p/BP3p2/1P6/8/8/5PKP/8 b - - 0 41&quot;]
  </code></pre>
  <p>I think this must have been investigated before. I'm wondering:</p>
  <p>(1) How computationally difficult is it to determine that <strong>no sequence of legal moves ends in checkmate</strong>? Is there a better algorithm than brute force?</p>
  <p>(2) Do you know of interesting examples of positions where it is hard for a human to tell whether this condition applies?</p>
  <p>(3) Are there any examples of historical games where this law was not followed due to players and officials not realizing the condition held? Especially interesting if the game did not end in a draw due to time expiring for one player.</p>
  <p>Inspired by <a href="https://old.reddit.com/r/chess/comments/8ulfrt/using_fide_rules_if_white_runs_out_of_time_in/" rel="nofollow noreferrer">https://old.reddit.com/r/chess/comments/8ulfrt/using_fide_rules_if_white_runs_out_of_time_in/</a></p>
  <p>(edit) See also <a href="https://chess.stackexchange.com/questions/5028/what-is-sufficient-mating-material">this closely related question</a> where the accepted answer has a couple more examples where there is sufficient material to mate, but it is impossible from that position.</p>
  <p>(edit) Essentially the same question is when a helpmate is possible; here is a <a href="https://chess.stackexchange.com/questions/18587/helpmate-of-arbitrary-length/">closely related question</a>.</p>
  <p>(edit) Essentially the same question, <a href="https://chess.stackexchange.com/questions/22555/is-the-dead-position-problem-solvable">is the dead position problem solvable?</a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-29T06:55:46.963Z
Comments.Text: I doubt there are positions hard for human to find out whether there is mate possible or not.
Comments.UserDisplayName: hoacin
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-29T13:08:30.700Z
Comments.Text: There is rule **9.3.2** *the last 50 moves by each player have been completed without the movement of any pawn and without any capture.* which creates a draw. In the back of my mind I remember a computer analysis that showed a forced mate in more moves than that. Such an analysis is NP complete and therefore no polynomial time algorithm could find it.
Comments.UserDisplayName: MaxW
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-29T13:21:47.950Z
Comments.Text: **Re (2)** It would be impossible for a human to see that [these games](https://en.wikipedia.org/wiki/Chess_endgame#Longest_forced_win) are winnable.
Comments.UserDisplayName: MaxW
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-24T16:22:31.310Z
Comments.Text: MaxW, note that "winnable" asks if one side can force a checkmate when the other side plays optimally, but this question is if there exists a helpmate.
Comments.UserDisplayName: usul
Tags: <rules><endgame><checkmate><chess-algorithms><dead-position>
Title: When checkmate is impossible in a position
ThreadText: # When checkmate is impossible in a position
  
  (Asked by: username_0 on 2018-06-28)
  
  The laws of chess say
  
  1.5. If the position is such that neither player can possibly checkmate the opponent’s king, the game is drawn (see Article 5.2.2).
  5.2.2. The game is drawn when a position has arisen in which neither player can checkmate the opponent’s king with any series of legal moves. The game is said to end in a ‘dead position’. This immediately ends the game, provided that the move producing the position was in accordance with Article 3 and Articles 4.2 – 4.7.
  
  [Articles 3, 4.2-4.7 basically deal with making legal moves.]
  This is interesting because it seems possibly non-obvious whether this condition applies (though presumably rare in actual games!). Update here is an interesting example. The game is legally a draw in this position because neither side can possibly checkmate by any sequence of moves. (The game will be a draw before white can checkmate.)
  [fen "1k6/1P5p/BP3p2/1P6/8/8/5PKP/8 b - - 0 41"]
  
  I think this must have been investigated before. I'm wondering:
  (1) How computationally difficult is it to determine that no sequence of legal moves ends in checkmate? Is there a better algorithm than brute force?
  (2) Do you know of interesting examples of positions where it is hard for a human to tell whether this condition applies?
  (3) Are there any examples of historical games where this law was not followed due to players and officials not realizing the condition held? Especially interesting if the game did not end in a draw due to time expiring for one player.
  Inspired by https://old.reddit.com/r/chess/comments/8ulfrt/using_fide_rules_if_white_runs_out_of_time_in/
  (edit) See also this closely related question where the accepted answer has a couple more examples where there is sufficient material to mate, but it is impossible from that position.
  (edit) Essentially the same question is when a helpmate is possible; here is a closely related question.
  (edit) Essentially the same question, is the dead position problem solvable?
  
  **Tags:** rules, endgame, checkmate, chess-algorithms, dead-position
  
  > **Comments:**
  > **username_1**: I doubt there are positions hard for human to find out whether there is mate possible or not.  
  > **username_2**: There is rule **9.3.2** *the last 50 moves by each player have been completed without the movement of any pawn and without any capture.* which creates a draw. In the back of my mind I remember a computer analysis that showed a forced mate in more moves than that. Such an analysis is NP complete and therefore no polynomial time algorithm could find it.  
  > **username_2**: **Re (2)** It would be impossible for a human to see that [these games](https://en.wikipedia.org/wiki/Chess_endgame#Longest_forced_win) are winnable.  
  > **username_0**: username_2, note that "winnable" asks if one side can force a checkmate when the other side plays optimally, but this question is if there exists a helpmate.  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_8 on 2018-06-29. Score: 11 | Accepted answer
  
  What you're asking goes by the name of "Dead Reckoning" in the domain of problems and retro problems.
  (1) There isn't an algorithm I know of except the one mentioned by username_4: brute force. The reason is because you can find pretty amazing positions...
  (2) Check out many problems relying on Dead Reckoning at Andrew Buchanan's website.
  Also there are problem databases (like this one) where you can run a search for 'DR' in the stipulation.
  A concrete example I recall is this one, which I reproduce here. By Andrew Buchanan, in StrateGems 2002. White to move; what was the last move in this position? (The position is dead but the last move made must have been from a legal and live position - so it's uniquely determinable.)
  Bb1k1b2/bKp1p1p1/1pP1P1P1/1P6/p5P1/P7/8/8 w - - 0 1
  
  (3) Even grandmasters have technically made moves in a dead position! See François Labelle's page for examples.
  
  
  ---
  
  ### Answer by username_3 on 2022-04-27. Score: 2
  
  Update on the comment by username_0.
  The algorithm is now described here:
  <https://chasolver.org/FUN22-full.pdf>
  
  It combines a search of variations with a dedicated mechanism for identifying blocked positions such as:
  <https://lichess.org/hPiwD75i#97>
  
  
  ---
  
  ### Answer by username_0 on 2022-01-26. Score: 1
  
  I just learned of an engine that analyzes chess positions to determine if checkmate by one side is impossible: <https://elrubiongamma.ddns.net/chess-unwinnability-analyzer/about.html>
  
  So you can solve this problem in practice by running the algorithm for both sides.
  
  It is called the Chess Unwinnability Analyzer 2. The source code is available here: <https://github.com/miguel-ambrona/D3-Chess>
  
  I don't see a description of how the algorithm works, but it seems to be roughly based on brute force. There is a faster mode that is not quite as accurate. If someone knows more about the algorithm, please expand this answer!
  
  Here is an interesting example position linked by the author where checkmate is impossible, but it's not immediately obvious (I've put this in the question now as a motivating example): <https://lichess.org/bKHPqNEw#81>
  
  
  ---
  
  ### Answer by username_4 on 2018-06-29. Score: -5
  
  Well, this is really 3 questions, not sure I am answering everything here.
  
  But there is an 'algorithm' for this problem, but it is NP complete, that is basically brute force in essence although you can make some Optimizations. This is basically the table base generating algorithm. Of course with large number of pieces this becomes difficult to apply, even for a single position.
  
  This Rule is basically there, so you can claim a draw in positions that are obviously drawn such as bishop and king vs lone king with no pawn and similar positions.
  
  > **Comments:**
  > **username_5**: is the bishops are different colors, mate is possible: k1K5/b7/2B5/8/8/8/8/8 w - - 0 1, do you want me to show you a sequence of legal moves, that can end up in this position?  
  > **username_4**: Yes, but I meant 1 king and bishop vs 1 king. I have edited the answer  
  > **username_6**: Strange claim that it is NP complete. What is `n` in this case? Can you explain how you would reduce other NP problems to this?  
  > **username_7**: @username_6 In particular, it is a category error to call algorithms NP-complete, only computational _problems_ can be. Computing an optimal strategy for generalised chess on an n×n board is EXPTIME-complete, however. (Wikipedia gives the reference `Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214`). Most problems on an 8×8 board are "trivial" in the context of complexity theory, as they can be solved in constant time. (even if that constant is too large to solve it in practice)  
  
  ---
  
  