Chess/Analysis of KQK Endgame

a b c d e f g h
8a8 black kingb8 black kingc8 black kingd8 black kinge8 black kingf8 black kingg8 black kingh8 black king8
7a7 black kingb7 black kingc7 black kingd7 black kinge7 black kingf7 black kingg7 black kingh7 black king7
6a6 black kingb6 black kingc6 black kingd6 black kinge6 black kingf6 black kingg6 black kingh6 black king6
5a5 black kingb5 black kingc5 black kingd5 black kinge5 black kingf5 white queeng5 black kingh5 black king5
4a4 black kingb4 white kingc4 black kingd4 black kinge4 black kingf4 black kingg4 black kingh4 black king4
3a3 black kingb3 black kingc3 black kingd3 black kinge3 black kingf3 black kingg3 black kingh3 black king3
2a2 black kingb2 black kingc2 black kingd2 black kinge2 black kingf2 black kingg2 black kingh2 black king2
1a1 black kingb1 black kingc1 black kingd1 black kinge1 black kingf1 black kingg1 black kingh1 black king1
a b c d e f g h
Sample position for K+Q vs. K mate

This book is an exact analysis of the KQK endgame, where one player has a King and a Queen and the other player has only a King. It is relatively easy to generate a computer database, called a tablebase, which has all the possible positions and the number of moves to checkmate for each position. Although this tablebase provides a complete solution to the KQK endgame, it is in a format that can only be used by a computer. This book shows the optimum method for forcing checkmate in a human-understandable format.

In normal play, there is no need to follow an optimal algorithm. A much simpler algorithm like the one in the Chess Wikibook will deliver checkmate only a few moves later than the optimal algorithm, but easily within the 50-move limit.

In all the positions given, by convention the stronger side is White. The number of moves to checkmate is the number of moves required by White, including the checkmating move. For example, in the sample position given, "White to play mates in 5" means that White's fifth move is the checkmating move, e.g. 1.Kb5 Kc7 2.Qe6 Kd8 3.Qf7 Kc8 4.Kc6 Kd8 5.Qd7#. If it is Black's move, "Black to play loses in 5" means that White's fifth move (which is numbered 6) is the checkmating move, e.g. 1... Kc6 2.Qd3 Kb7 3.Qd7+ Kb8 4.Kb5 Ka8 5.Kb6 Kb8 6.Qd8#. The results are for optimal play by both sides. If Black plays less than optimally, he could get checkmated sooner, and if White plays less than optimally, it could take longer to checkmate.

Drawn Positions edit

a b c d e f g h
8        8
7        7
6        6
5        5
4        4
3        3
2        2
1        1
a b c d e f g h
Stalemate position A
a b c d e f g h
8        8
7        7
6        6
5        5
4        4
3        3
2        2
1        1
a b c d e f g h
Stalemate position B
a b c d e f g h
8        8
7        7
6        6
5        5
4        4
3        3
2        2
1        1
a b c d e f g h
Stalemate position C
a b c d e f g h
8        8
7        7
6        6
5        5
4        4
3        3
2        2
1        1
a b c d e f g h
Stalemate position D

There are a total of 23,048 drawn positions in the KQK endgame. The drawn positions consist of only positions where Black is stalemated or the white queen is en prise.

There are four stalemate configurations, which are shown in the diagrams. If the black king is in the corner, the three flight squares can be covered by the queen as shown in stalemate position A. The white king can be on any of the remaining 59 squares, so considering rotations and reflections, there are 59 x 8 = 472 positions of this type. If the white king covers two of the flight squares (stalemate position B), the queen only needs to cover one square. If the white king is on b6, the queen has to attack along the diagonal, so there are five possible squares, while if the white king is on a6, it can also attack along the file, so there are ten squares. Considering rotations and reflections, there are 15 x 8 = 120 positions of this type.

With the black king on the side of the board, there are also two types of stalemate. In Stalemate position C, the queen covers four of the five flight squares, and the white king covers the fifth square, which it can do from five possible squares. The same thing happens with the position shifted 1, 2, 3, or 4 files to the right. When shifted 5 files to the right there are only two places for the white king. Thus, with rotations and reflections, there are 27 x 8 = 216 positions of this type. Stalemate position D shows a fourth type of stalemate. The queen covers four of the five flight squares again, but the fifth square is now next to the black king instead of diagonal from it. There are two squares the white king can be on, and the position can be shifted 1, 2, or 3 positions to the right. So with rotations and reflections, there are 8 x 8 = 64 positions of this type.

Next, we need to calculate the number of positions with the queen en prise. There are 64 possible positions for the black king. The white queen must be next to the black king, so there are three possibilities if the black king is in the corner, five possibilities if it is on the side, and eight possibilities if it is in the middle. The white king can not be next to the black king, as that would create an illegal position, and it can not be next to the queen, as it would then be protecting the queen from capture. The following table shows the number of possibilities for the white king for each configuration of white queen and black king.

Black king/White queen Number of positions
a8/b8, b8/a8 464 x 2
b8/a7 448
a8/b7, b7/a8 220 x 2
b8/b7, c8/c7, d8/d7, b7/b8, c7/c8, d7/d8 440 x 6
b8/c7, c8/b7, c8/d7, d8/c7, d8/e7, b7/c8, c7/b8, c7/d8, d7/c8, d7/e8 424 x 10
b8/c8, c8/b8, c8/d8, d8/c8, d8/e8 448 x 5
b7/c7, c7/b7, c7/d7, c7/c6, d7/c7, d7/e7, d7/d6, c6/c7, c6/d6, d6/d7, d6/c6, d6/e6, d6/d5, d5/d6, d5/e5 416 x 15
b7/c6, c6/b7, c6/d5, d5/c6, d5/e4 200 x 5
c7/b6, c7/d6, d7/c6, d7/e6, c6/d7, d6/c7, d6/e7, d6/c5, d6/e5, d5/e6 400 x 10
Total 22176

The 22,176 positions with queen en prise plus the 872 stalemate positions account for the 23,048 drawn positions.


Checkmate positions edit

a b c d e f g h
8        8
7        7
6        6
5        5
4        4
3        3
2        2
1        1
a b c d e f g h
Type A checkmating position
a b c d e f g h
8        8
7        7
6        6
5        5
4        4
3        3
2        2
1        1
a b c d e f g h
Type B checkmating position
a b c d e f g h
8        8
7        7
6        6
5        5
4        4
3        3
2        2
1        1
a b c d e f g h
Type C checkmating position

There are a total of 364 checkmating positions, which appear as "Black to move loses in 0" in the tablebase.

All of the checkmating positions have the black king on the side of the board or in the corner. With the black king in the middle of the board, there are two cases: the queen sitting next to the black king and the queen at least two squares away. If the queen sits next to the black king, it must be protected by the white king. As a result, the white king does not cover any squares not already covered by the queen, and the queen can not cover all the squares. If the queen is at least two squares away, it can only cover four squares in addition to giving check, and the white king can only cover three.

The checkmate positions fall into three major categories. In positions of type A, the kings are in opposition, with the queen checking from the side. The queen needs to be at least two squares from the black king, so there are six positions with the king on a8 and five each with the king on b8, c8, or d8. When the black king is on a8, the white king can be on b6 as well as a6, so there are six additional positions for a total of 27, so including rotations and reflections there are 27 x 8 = 216.

In positions of type B, the queen stands next to the black king, protected by the white king. There are two positions with the king on a8 and three each with the king on b8, c8, or d8. With the king on a8, the queen can also be on b7, so there are three more positions for a total of 14. Since one of the positions has all three pieces on the diagonal, rotations and reflections give (1 x 4) + (13 x 8) = 108 positions.

In positions of type C, the white king is on the file adjacent to the black king, and the queen checks from the side, two squares away. The square left uncovered by moving the king to the side is covered by the queen. There is one position with the black king on b8, and two each with the black king on c8 and d8 for a total of five, or 40 with rotations and reflections.

That gives a total of 216 + 108 + 40 = 364 positions, which are all the checkmating positions.

Positions of type C only make an evaluation difference for themselves and positions one ply previous. For example, going back from the diagram position, the queen must have moved last, and it could only have come from one of the following squares: a4, b5, e1, e2, e3, e4, e5, e7, f7, g6, or h5, since it could not have been giving check. If it was on e7 or f7, White could have chosen to checkmate on c7 instead of e8.

If the white queen was on one of the other squares and Black moved from b8, White would have missed a (Type A) checkmate. If Black moved from either d7 or d8, he could have moved to one of e7, d7, or d8 instead of c8, escaping checkmate for a while. The analysis is similar for the position moved one file to the right or one, two, or three files to the left, which are all the Type C positions. Thus, Type C positions can be safely ignored unless White has an immediate checkmate.


White mates in 1 edit

There are 2,448 positions where White mates in 1. With the black king in the corner, there are 744 positions. If the position is rotated and reflected to put the black king on a8, the white king will be on either a6 (376 positions), b6 (320 positions), or c6 (48 positions). With the black king on the side of the board, there are 968 positions with the kings in opposition and 736 with White's king one square to the side.

The longest position edit

a b c d e f g h
8        8
7        7
6        6
5        5
4        4
3        3
2        2
1        1
a b c d e f g h
White to move, mate in 10

There is only one position (8 with rotations and reflections) that is mate in 10 with White to play. Since there are 8 squares the black king might have come from, there are 8 positions that are lost in 10 with Black to move. Since two of these have all the pieces on the same long diagonal, there are 56 total positions including rotations and reflections.

From the diagram, any move except 1.Qd5+?? and 1.Qc6+?? will work.


General algorithm edit

The next logical step in this process is to provide a general algorithm that can be used for all positions. I have not completed this analysis yet. I am having difficulty generating a list of possible moves from a given position (yeah - it seems really simple, but there are thousands of positions). I need to verify that all the moves that fit the pattern are actually optimal.

The general outline of the algorithm is:

1. Restrict the black king to either:

  a. the rank or file at the edge of the board

  b. the two ranks or two files at the edge of the board

  c. the same half of the board as the white king, or

  d. the same quarter of the board as the white king

2. Bring the white king near the black king

3. Force the black king to the edge of the board

4. Deliver checkmate