This is an HTML version of an article originally published in StrateGems 58, April–June 2012, with some hyperlinks added. The article discusses problem **P0330** from the same issue, reproduced here on the right. Exceptionally, the entire StrateGems 58 issue is available online.

The problem received the following awards:

- 2nd place in the Annual Wenigsteiner Prize (problems of all types with at most 4 pieces) for the year 2012,
- selected for the FIDE Album 2010-2012.

This issue of *StrateGems* contains a "massacre" shortest proof game (in 19½ moves) that has only 2 pieces left: the white King on e5 and the black King on e2 (see **P0330**). It is the first known realization of this task in orthodox chess without additional conditions. In this article I will describe the origins of this type of proof game.

Special Prize

Die Schwalbe 1994

Black's second move is a capture

In 1895, Sam Loyd published a 2-King proof game in 17 moves (see diagram **L1**). This is an impressive early achievement since the diagram cannot be obtained in fewer moves. Unfortunately the problem has many solutions in 17 moves, so it does not satisfy the modern requirement of having a unique solution.

In 1994, Gerd Wilts and Norbert Geissler used a computer to search for a 2-King proof game in 17 moves, and their search uncovered a conditional problem (see diagram **L2**). They did not find a condition-free 2-King problem, but in the process they found 17 proof games with 3 pieces (2 white pieces + 1 black piece) in 16½ moves. Sixteen of those problems were new and were published in various magazines or in the Chess Problem Database CD-ROM. One of them requires the caption "no Dead Reckoning" (more about this later).

In 2004, Gerd Wilts found a 2-King proof game in fairy chess (see diagram **L3**). Many more examples with fairy conditions were found by Joost de Heer in 2009. All of these were posted on the Retros mailing list.

Most of the known massacre proof games were found by computers, so I believe that computers are superior to humans for this particular task. The computer method I use starts from the initial position and explores the ensuing game tree ply by ply. It is important to prune the search and eliminate transpositions. Basic pruning strategies are:

- Method No.1
- Reject a move if the number of pieces remaining is more than 2 (the two Kings) plus the number of plies remaining. This uses the simple fact that in chess we can capture at most 1 piece per ply.
- Method No.2
- Same as Method No.1, but performed individually for White and Black. The number of white pieces remaining must be at most 1 (the white King) plus the number of black moves remaining, and similarly for the number of black pieces remaining. This is a tighter condition.

In 1994, Gerd Wilts and Norbert Geissler used Method No.2 to search for a 2-King proof game in 17 moves. In 2004, I used Method No.1 to reproduce their results. Method No.1 is about twice as slow as Method No.2, but it generates 3-piece problems of both (2+1) and (1+2) types at move n−½, while Method No.2 will only find one type at move n−½ (which one depends on who has the last move). I also searched for a 2-King problem in 17½ moves, without success. Increasing the number of moves further was computationally out of reach at the time.

The basic search methods above are inefficient beyond 17½ moves because they spend too much time calculating games with the white King on ranks 1 or 2 and the black King on ranks 7 or 8. For most of these 16×16=256 end diagrams a cooked SPG is already known from the 17½-move search, so searching the same diagrams for an even longer SPG is wasteful. My idea was to impose a minimum destination rank for the white King, and similarly a maximum destination rank for the black King. This would force the computer to explore uncharted territory.

The actual pruning method I used is quite elaborate. It basically ensures that there are enough non-capturing moves left for the Kings to get to their destination ranks by counting pieces on paths between the Kings and their destination ranks. Note that pieces of either color can help save a non-capturing move when they lie on a King's path. This is clear for, say, a black piece on the white King's path, but a white piece on the white King's path can still potentially save a non-capturing move if Black captures it to turn it to a black piece before the white King gets there.

Dead Reckoning (DR) refers to Article 1.3 in the FIDE Laws of Chess, which affects many 2- or 3-piece proof games. The article says that "if the position is such that neither player can possibly checkmate, the game is drawn". In particular, this means that the last move of a 2-King proof game must be the capture of a Pawn, Rook, or Queen; otherwise the game would have ended earlier due to insufficient mating material. See Dead Reckoning: Castling & En passant (StrateGems 16, Oct–Dec 2001) for more about DR.

My approach is to search problems without considering DR, and to apply DR later. One reason for this is that if a problem fails with DR, then it can still be published with the caption "no Dead Reckoning". In contrast, if a problem requires DR to work, then I feel it should be published with the caption "Dead Reckoning" as a courtesy to solvers. Fortunately, the 2-King proof game that I found did not need a caption, according to these guidelines.

White King rank | |||||||||

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||

Black King rank | 8 | 63 | 63 | 62 | 51 | 59 | 46 | 18 | 6 |

7 | 63 | 63 | 63 | 53 | 62 | 29 | 17 | 10 | |

6 | 63 | 63 | 60 | 63 | 35 | 39 | 29 | 27 | |

5 | 50 | 50 | 63 | 34 | 4 | 13 | 4 | 0 | |

4 | 56 | 59 | 32 | 3 | 20 | 0 | 0 | 0 | |

3 | 24 | 22 | 42 | 20 | 45 | 0 | 0 | 0 | |

2 | 10 | 12 | 37 | 14 | 37 | 0 | 0 | 0 | |

1 | 2 | 2 | 34 | 11 | 17 | 0 | 0 | 0 |

White King rank | |||||||||

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||

Black King rank | 8 | 18½ | |||||||

7 | 18 | ||||||||

6 | |||||||||

5 | 19 | ||||||||

4 | |||||||||

3 | |||||||||

2 | 19½ | ||||||||

1 |

On and off over the years, I have attempted various combinations of game length and King destination ranks, roughly in order of increasing computational difficulty. Eventually I did a full search of 2-King proof games in 18 moves (without any rank constraint) using Method No.2, but found no problem. I kept attempting more difficult combinations, until the combination *"length = 19½, white King rank ≥ 5, black King rank ≤ 3"* finally uncovered a unique-solution 2-King SPG. That particular combination took about 10 core-months of computing time and 2 terabytes of disk space. **Figure 1** illustrates the entire search space I explored. Warning: The figure does not represent a chessboard; read the axis labels carefully!

**Figure 2** shows, for each combination of King destination ranks, the number of 2-King diagrams that I reached (without considering DR) with a search up to the respective game length given in Figure 1. Increasing the game length limit would increase those numbers, up to the number of legal 2-King diagrams with given King ranks: 64 when the ranks differ by 2 or more, and 42 otherwise. The largest number in the figure is 63 and, amusingly, for all such cases the missing diagram is the one where both Kings are on the a-file.

original

original

length | (2+1) | (1+2) | total |
---|---|---|---|

16½ | 17 | 1 | 18 |

17 | 38 | 62 | 100 |

17½ | 111 | 40 | 151 |

18 | 1 | 61 | 62 |

18½ | 14 | 0 | 14 |

19 | 0 | 4 | 4 |

Proof games with 3 pieces are easier to find because there are more combinations. I obtained 349 of them as the by-product of the search. **Table 1** gives the counts. The full search of 2-King proof games in 18 moves confirmed the previously known 3-piece problems in 16½ and 17 moves, and generated 111 new problems of type (2+1) in 17½ moves (all highlighted in the table). Searches with King-rank constraints uncovered some more 3-piece problems, but not all the problems with those constraints—just those that survived the particular pruning method I was using.

In keeping with the theme of King travel, here are two 3-piece proof games where one King travels all the way to the opposite rank:

**L4:**1.e4 d5 2.Ke2 dxe4 3.Ke3 Qxd2+ 4.Kxe4 Qxf2 5.Be3 Qxg1 6.Bxa7 Qxh2 7.Bxb8 Qxg2+ 8.Bxg2 e5 9.Kxe5 Rxa2 10.Bxb7 Bxb7 11.Bxc7 Bxh1 12.Qxh1 Rxa1 13.Qxh7 Rxb1 14.Qxg8 Rxb2 15.Qxg7 f6+ 16.Kxf6 Bxg7+ 17.Kxg7 Rxc2 18.Kxh8 Rxc7**L5:**1.d4 h6 2.Bxh6 c5 3.Bxg7 Rxh2 4.Bxf8 Rxh1 5.Bxe7 Kxe7 6.Sc3 Kd6 7.dxc5+ Kxc5 8.Qxd7 Rxg1 9.Qxb7 Rxg2 10.Qxa7+ Kb4 11.Qxf7 Rxf2 12.Qxg8 Rxe2+ 13.Bxe2 Rxa2 14.Bd3 Qxd3 15.Qxc8 Rxb2 16.Qxb8+ Kxc3 17.Qxb2+ Kxb2 18.cxd3 Kxa1.

Looking at **Figure 2**, out of 64×42 + 42×22 = 3612 possible 2-King diagrams, I found SPGs for 1824 (50.5%) of them: 1823 were cooked and one was sound. This success rate indicates there could be another problem hiding in the unexplored 49.5%. Actually, looking at the success rate of 3-piece diagrams for which I have more data, I think the probability of getting a unique SPG for a given 2-King diagram might be closer to 1/1000. We might have been unlucky that it took so long to find one. This view is supported by the situation in fairy chess where 2-King PGs were found more quickly. Non-shortest PGs are also a possibility, although less likely than SPGs: Among the 695 2-King diagrams for which I know both the number of SPGs and the number of PGs in ½ extra moves, only four diagrams have fewer solutions in ½ extra moves. Still, finding another 2-King PG in orthodox chess will not be easy and I fear it will require more computing power, a better pruning method, or plain luck.

page last updated: November 27, 2015

back to Chess Problems by Computer

the diagrams on this page were created using these chess piece images