The quest for a King-only proof game

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 with permission from the editor.

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.

A brief history

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.

Basic search methods

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:

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.

Forcing the Kings to change ranks

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.

A note about Dead Reckoning

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.

Combinations of game length and destination ranks attempted

		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

Figure 2: The number of 2-King diagrams for which I know the SPGs, broken down by King destination ranks, without considering Dead Reckoning. The total number of diagrams (including those for which I do not know the SPGs) is 64 outside of the diagonal band and 42 inside the band. My unique-solution 2-King SPG comes from the highlighted square.

		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

Figure 1: The maximum PG length that I analyzed for each of the 8×8 combinations of King destination ranks.

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.

Three-piece proof games

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

Table 1: The number of unique-solution 3-piece PGs that I found at each length, without considering Dead Reckoning. The highlighted numbers are definitive, having come from an exhaustive search.

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:

Are more 2-King SPGs waiting to be discovered?

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.

Preface