4

In chess, there are some dead positions (FIDE Laws of Chess). Arbiter or players will terminate the game OTB, but is it possible to do computer solution for dead position detection? If it is, then how?

  • 3
    What's a dead positon? – SmallChess Sep 26 '18 at 15:15
  • 3
    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. – user17439 Sep 26 '18 at 15:19
  • 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. – Daniel Alfredo Sottile Sep 26 '18 at 15:59
4

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.

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.

  • 2
    To me it’s not clear why you think a computer could differentiate between a dead position and a possible mate in a position with sufficient material. Your answer boils down to “I think it should be possible” but you don’t show why. Even if the question had asked “is it possible” it would have been a thin answer, but the OP also asked “how”. – 11684 Sep 27 '18 at 10:10
  • 1
    I don't see a reason for downvoting this answer. The concept of "no future captures" is original and I still couldn't refute it. – Daniel Alfredo Sottile Sep 27 '18 at 12:54
  • 1
    But @11684, couldn't the lone king make a capture? In that case, why not? – Daniel Alfredo Sottile Sep 27 '18 at 14:41
  • 1
    @11684 Don't forget about "any series of legal moves" (like in a helpmate). We should not analyze correct play here. – Daniel Alfredo Sottile Sep 27 '18 at 14:47
  • 2
    Invalid. See this position. FEN: 5K1r/5N2/5k2/8/8/8/8/8 w - - 0 69 There are no pawns. Capture is forced, but it is a dead position. – user17439 Sep 28 '18 at 20:08
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.

  • 1
    This answer is valid, but it does not cover all dead positions possible. – user17439 Sep 26 '18 at 15:21
  • @J.Doe It does. – SmallChess Sep 26 '18 at 15:22
  • 2
    Wrong. There can be 32 piece dead position. FEN: bqn1KN2/rrk1pB2/nb1pPp1p/p1pP1PpP/PpP3P1/1P2N1R1/4Q3/1R4B1 w - - 0 1 – user17439 Sep 26 '18 at 15:24
  • @J.Doe Enumerate all possibilities until a certain depth. You'll find it all the positions repeated. – SmallChess Sep 26 '18 at 15:30
  • 1
    @J.Doe I think you would need a full chess engine, although most of them are not programmed to find dead positions (if they can’t find any progress in the lines they analysed they evaluate the position on static factors). The needed changes would be quite trivial, but I don’t believe @SmallChess’ assertion “a modern laptop should have the memory to do it”. How? Even in a very quiet position without pawn moves or captures you’d have to analyse all lines 100 plies deep to rule out finding any progress. – 11684 Sep 27 '18 at 7:51

Your Answer

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