Is the dead position problem solvable?

Question

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?

Answer 1

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.

Answer 2

Miguel Ambrona’s CHA solver “Chess Unwinnability Analyzer” (GitHub repo, white paper) is an efficient solution to this problem. It uses an incomplete algorithm to analyse positions and determine whether there is a possible checkmate by either side, optionally falling back to a slower, more thorough “brute force” analysis when the incomplete algorithm isn’t able to conclude whether a checkmate is possible with certainty.

In practice, the thorough search only ends up being necessary for constrained positions where there are few moves available for each side, so even then it ends up being fast.

From the paper:

Definition (Unwinnability) We say that a position is unwinnable for a given player if there does not exists a sequence of legal moves that ends in a checkmate by the player.

Note that the above definition focuses on whether a specific player can still win, typically the player whose opponent ran out of time. Concluding that a position is dead would require two individual analyses, one for each player as the intended winner.

[…]

Answer 3

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

Answer 4

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 field in FEN 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 field in FEN 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).

Answer 5

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.

Answer 6

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.