6

This question already has an answer here:

Edit This question is not a duplicate, as mentioned in my comment. The linked supposedly-duplicate question addresses neither my below question #1, nor question #3, nor question #2 except tangentially mentioned in an answer. The linked question is about sufficient mating material whereas my question is about cases where material may be sufficient but nevertheless checkmate is impossible.


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!). 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.

marked as duplicate by Brian Towers, Herb Wolfe, GloriaVictis, Ywapom, lenik Jul 5 '18 at 8:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • I doubt there are positions hard for human to find out whether there is mate possible or not. – hoacin Jun 29 '18 at 6:55
  • 2
    @BrianTowers, that question is closely related but it's not a duplicate. The question itself is asking something quite different. The accepted answer there touches on the topic but doesn't really address any of (1)-(3) except maybe a bit of (2). – usul Jun 29 '18 at 12:26
  • @hoacin, I'm inclined to agree, but then we should be able to write fast algorithms for this, right? – usul Jun 29 '18 at 12:27
  • 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. – MaxW Jun 29 '18 at 13:08
  • Re (2) It would be impossible for a human to see that these games are winnable. – MaxW Jun 29 '18 at 13:21
4

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 zaifrun: 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.

-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.

  • 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? – lenik Jun 29 '18 at 7:52
  • Yes, but I meant 1 king and bishop vs 1 king. I have edited the answer – zaifrun Jun 29 '18 at 10:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.