10

In chess, there are some dead positions (FIDE Laws of Chess).

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

Arbiters or players will terminate the game OTB, but is it possible to have computer solutions for dead position detection? If it is, then how?

3
  • 1
    @J.Doe The position you posted in another comment (in a deleted answer) is a dead position because it is a forced stalemate. We should also consider positions in which both sides have spare moves but no possible way of checkmate, like a totally closed pawn chain with all white pawns on squares of the same color, all black pawns on squares of the opposite color, and a bishop per side running on squares of the same color as its own pawns. These are positions very difficult to automatically declare dead by software, because of the loops. Sep 26 '18 at 15:59
  • The rule terminates the game. Arbiters or players on the other hand may not. See Topolov-Nakamura 2016 and my comment there. Oct 17 at 21:38
  • Luckily it doesn't make a lot of difference if a dead position is missed because it will necessarily be a draw anyway. A position incorrectly diagnosed dead is a different matter. Oct 17 at 21:44
10

Computer detection of dead positions is much trickier than people think. It is unlikely that an algorithm exists that runs in reasonable time and is 100% accurate.

It is easy to check for a simple condition like insufficient material (K+B v K, K+N v K). It is less easy to check for cases with blocked pawns, for instance:

2b1k3/8/8/1p1p1p1p/1P1P1P1P/8/8/2B1K3 w - - 0 1

since there are a lot of legal moves to check. Computers aren't based on intuition like humans: you'd have to enumerate every single possible continuation for up to 150 ply without pawn moves/captures (those reset the counter) and check that none of them end up in checkmate for either side.

You could try other tricks, like trying to store the positions reached in a tree and checked that none of the reachable positions are mate. That's only 76176 positions for the example I gave, but you'd need to check that the tree is indeed exhaustive - i.e. every legal move in every position must be tried. That's not going to be efficient.

You could also try to invent some arbitrary heuristics to help your algorithm, like checking for blocked pawns and same coloured bishops. The problem with this approach is that sometimes the heuristics are wrong, or they aren't general enough. (Brian Tower's answer is an example of an attempted heuristic, but in the comments user17439 shows it fails to flag some dead positions and I show it incorrectly flags a non-dead position.)

And I would love to see any heuristic or algorithm that can distinguish between the following positions (problem by Andrew Buchanan, StrateGems 2002)

Dead:

Bb1k1b2/bKp1p1p1/1pP1P1P1/1P6/p5P1/P7/8/8 w - - 0 1

Alive:

Bb1k1b2/bKp1p1p1/1pP1P1P1/pP6/6P1/P7/8/8 w - - 0 1

The second position is alive since mate is possible after

1.Ka6 Ke8 2.Bb7 Kd8 3.Bc8 Ke8 4.Bd7+ Kd8 5.Be8 Kc8 6.Bf7 Kd8 7.Bg8 Ke8 8.Kb7 Kd8 9.g5 Ke8 10.Kc8 a4 11.Bf7#

In sum, I do not believe you can have an algorithm that is 100% accurate in distinguishing between dead and alive positions that runs in reasonable time. Brute force is the only 100% reliable method, but it is definitely not efficient. You can get a decent success rate for "practical" positions with heuristics, but it will not be 100% accurate, even for real game positions.

1
  • I agree that in general you can't make a simple enough rule that works 100% of time. Although a sufficient one for all these 3 problems can be pretty simple: figure out which tiles are reachable for all pieces you have left. This should be pretty manageable in terms of runtime. If there is overlap between black king and white non-king pieces, position may be still alive. To eliminate 2nd as dead, simply note that only king and bishop overlap with black's king. As bishop takes just 1 tile from king, black king needs to not move to get checkmated - which isn't possible in 2nd case. Jun 16 at 11:52
2

I would expect that it is a good bit easier to write a program that is good at detecting dead positions than to write a program that plays chess well.

A simple strategy may be to play out a large number of games randomly to the end starting from the position given. If the position is dead, none of the playouts will have a result different from draw. If on the other hand the position is not dead, the probability that one playout discovers a helpmate (it need not be the shortest one) approaches one as the number of playouts tends to infinity.

In practical terms, I would conservatively expect a well-optimized random mover to be able to reach on the order of ten million playouts per second on a single core of a modern CPU. Under this assumption, 100 million random playouts per second are not unreasonable on a current PC. If we allow roughly a minute for resolution of a position as dead or alive, we can therefore probably do a few billion playouts and hence fairly reliably detect any helpmate that is found with likelihood more than, say, one in one billion under a random playout policy.

Edited: This simple strategy is likely not enough to practically solve cases like Remellion's example further up in this thread.

Nonetheless, the point stands that an algorithm that declares a position to be dead when no helpmate can be found within some computational budget will only return a wrong answer if the position contains a helpmate it cannot find. In that sense, the decision problem for dead positions is at most as hard as the problem of finding helpmates. There are good helpmate solvers and they have no trouble solving e.g. the "alive" position given by Remellion (see for instance this online solver ).

5
  • When you say play out a large number of games to the end, how do you define end? E.g. in @Remellion's first position. Oct 11 at 20:24
  • Or, simpler, this position? FEN:4k3/8/8/8/8/8/8/4K3 w - - 0 1 Oct 11 at 20:54
  • Obviously a helpmate solver that will reliably run in sufficiently quick time and use sufficiently little storage would be the answer OP is looking for. To be confidently used a proof of the time and storage requirements would be necessary. You say that they cope with the alive position given by Remellion, but how long do the take to annnounce "no solution" for the two dead positions in my previous comments? Oct 12 at 14:23
  • I am not sure exactly which question the OP has asked. There are various degrees to "solving" the problem of dead position detection. The hardest might be something like decide aliveness for any legal position and output a short proof of death along with a proof of legality, while refusing (with proof) illegal positions. Easiest would be something like "decide aliveness quickly with lower error rate than a human arbiter for positions that may arise in games".
    – Polytropos
    Oct 12 at 20:22
  • My argument would show something like "Ability to quickly supply short proof of liveness for many positions that are hard for humans, ability to correctly classify as dead all dead positions". I would not be too pessimistic that helpmate solvers could get to a point where it becomes infeasible to construct a legal alive position they can't solve (which is of course less than nonexistence of such difficult helpmates), but I could be wrong about that, of course. I would be pessimistic about exact proof (not necessarily short) for all dead positions, but could be wrong about that as well.
    – Polytropos
    Oct 12 at 20:28
1

I think the answer is probably not. In fact I would say that the introduction of the dead position rule to replace the previous draw by insufficient material was a mistake. (Btw why did FIDE excise the draw by insufficient material rule when they introduced the dead position rule but not the stalemate rule?)

The following position is dead under FIDE competition rules because there is no legal continuation that will result in mate before the game terminates under the 75 move rule.

7k/3N4/5K2/6B1/8/8/8/8 w - - 0 1

White to play. Ply count 146.

The following position is also dead if the position (as defined in the 5 fold repetition rule) that would occur after Kf7 has already occurred four times previously.

7k/3N4/5K2/6B1/8/8/8/8 w - - 0 1

White to play. Ply count 144.

The arbiter (and any software seeking to solve the dead position problem) needs to keep track of possible helpmates taking both the 75 move rule and 5 fold repetition rules into account.

How do arbiters cope? The answer of course is they don't. The following game actually terminated in a dead position with White's move 132, but was recorded as a draw under the 75 move rule after Black's move 132 (which wasn't actually part of the game).

https://www.chessgames.com/perl/chessgame?gid=1825274

For software to cope it would require helpmate EGTBs.

Since helpmates are generally shorter than forced mates these would possibly take less computation than the existing forced mate variants under FIDE basic rules (which now exclude any n move or n fold repetition rules) but the fact is there are also many more positions where helpmates are possible and forced mates are not, so the storage requirement would be much greater.

Under FIDE competition rules the EGTBs would need to store helpmate lengths under a DTZ75 metric for all possible combinations of positions that have been repeated four times and both the computation and storage requirements would greatly exceed those required for the current forced mate EGTBs.

I would also class the following position as dead according to the FIDE rules. (There is nothing in the FIDE rules that states that a position can become dead only as a result of a move being 'made' under art 4.7 and before a piece is touched as in art 4.3 by the player who then has the move - indeed on my reading the two events may be simultaneous.)

k6K/8/6PR/7P/8/8/8/1R6 w - - 0 1

White to play. White has touched the h6 rook.

Of course if the solution is required only for computer "chess" the solution could ignore such positions, because computer "chess" never properly implements art 4. But if the solution were intended as an aid to arbiters or chess players then these situations would also need to be taken into account (whether under basic or competition rules).

15
  • 1
    To my best knowledge (and I only recently made my national arbiter license), assume in your last position you add a bPh7 and White loses on time before completing the forced Rxh7. Still 0-1, touch-move is NOT relevant for the "future". Oct 10 at 16:50
  • @Hauke Reddmann Art 5.2.2 is 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.* Immediately White touches the h6 rook the rule applies (whether or not there is a black pawn on h7 as far as I can see) and the position is dead at that point. So I'm struggling to follow your comment. Oct 10 at 21:06
  • @Hauke Reddmann Time doesn't enter into it. The rule says neither player can checkmate the opponent's king, time is not involved (not even under competition rules). Oct 10 at 21:17
  • @Hauke Reddmann I don't have an arbiter's license, but I would still question your evaluation of the score should the flag fall in the circumstances you posit. Art 6.9 says Except where one of Articles 5.1.1, 5.1.2, 5.2.1, 5.2.2, 5.2.3 applies, if a player does not complete the prescribed number of moves in the allotted time, the game is lost by thatplayer. However, the game is drawn if the position is such that the opponent cannot checkmate the player’s king by any possible series of legal moves. The last sentence would appear to apply even ignoring the dead position rule. Oct 10 at 21:25
  • The first position is a bad example because in all realistic situations it would have already been drawn via the 50-move rule. The current rules are the best rules that apply properly in most reasonable situations. The previous rulesets that used to be in place also came with their (worse) shortcomings. For instance, under United States Chess Federation rules, there are some positions where a player has forced mate but you can get a draw by letting the clock run out
    – David
    Oct 10 at 21:58
0

There are two classes of dead position (positions from which helpmate is impossible)

  • Insufficient material

  • Positions where both pawn moves are impossible and future captures are also impossible

The first is trivial to program. The second less so but I think still possible. Checking for possible pawn moves is straightforward. Checking for possible future piece captures is less straightforward but should still be possible.

0
0

Detecting for insufficient materials for checkmate is super easy. Just get the FEN position, and look for the number of pieces remaining and what they are.

The second solution requires enumerating all possibilities until a certain depth. If there is really no legal way to make progress, the variations will quickly repeat. A modern laptop should have the memory to do it.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy