Counting chess endgames

Introduction | Notation | G-Chess | ASP-Chess | Chess

This page summarizes some topics related to counting chess endgames. Enumerating endgames is useful in the context of solving chess endgames and variants. Please email any questions, comments, and ideas to kkryukov@gmail.com.


Introduction

In chess the term "endgame" (and "ending") may refers broadly to the final phase of the game where only few pieces remain on board. (For details, see "Chess endgame" in Wikipedia). It is also used to refer a set of all positions with a particular configurations of pieces, e.g., "King and pawn versus king endgame". In this more narrow sense, chess has many different "endgames", each with a unique set of pieces. Every capture and promotion converts one endgame into another, simpler, endgame.

It's possible to build a database containing some information (e.g., distance to mate) for all positions from a given endgame (all positions with particular material). Such database is called "endgame tablebase", and such endgame is then considered "solved" or "strongly solved". (See "Endgame tablebase" and "Solved game" in Wikipedia).

This terminology became first established when solving simple endgames with 3, 4, or 5 pieces. Confusingly, we now generalize the term "endgame" to mean any fixed combination of pieces, even those not in the endgame phase of the game. With this relaxed application of the term, the starting set of 32 pieces corresponds to just another endgame.

The questions we investigate here are: how many distinct endgames there are in chess and chess variants, and how many tablebases are needed for each number of pieces? These questions are particularly relevant in the context of solving small board chess variants, where a many endgames are accessible to solving, producing a lot of tiny tablebases.


Notation

Endgame names are constructed by listing all included pieces using their algebraic notation symbols. To avoid ambiguity, pieces are always listed in the same order: k, q, r, b, n, p, and the stronger side's material is listed first. Here the stronger side means the one with more pieces (e.g., kppkq and not kqkpp), or the one that sorts lexicographically higher by piece strength (e.g., kqppkrrb and not krrbkqpp). While both small and capital letters can be used, in practice small letters are used more often in tablebase contexts.

When solving endgames, a separate tablebase is usually constructed for each endgame + side to move (ESM). Most endgames have two distinct ESMs and two tablebases. However, symmetric endgames, such as kpkp, have a single unique ESM, and only need one tablebase, because each black-to-move position can be converted into the equivalent white-to-move position.

ESM (tablebase) names are sometimes constructed by adding "w" or "b" to endgame name. Alternatively, ESM name can be written by first listing the pieces of the side-to-move, then of the other side. We use this second approach here. For example, the "kqk" endgame contains two ESMs: "kqk" and "kkq".

There is only one endgame and one ESM with two pieces: kk. With 3 pieces, there are 5 endgames and 10 ESMs.

It's useful to have a well-defined ordering for endgames and ESMs. For both endgames and ESMs, we use the following sorting criteria: (1) Total number of pieces, small to large. (2) Number of white pieces (pieces of the side to move), large to small. (3) Value of the first different piece, large to small (k, q, r, b, n, p).


Generalized chess (G-Chess)

First we take a look at generalized chess (G-Chess for short) with unlimited supply of pieces and pawns for promotion. Adam Hair (personal communication) pointed out that in this case the number of ESMs with N pieces is given by the binomial coefficient C(N+7,9). The cumulative number of all ESMs with up to N pieces is C(N+8,10).

The number of endgames with N pieces and the cumulative number of endgames with up to N pieces are given by the alkane numbers l(12,N-2) and l(13,N-2), respectively. These numbers form 10-th and 11-th diagonals of the Losanitsch's triangle. The earliest mention of this we could find was in 1999's message by Hans Havermann on CCC forum: archived forum post 64263. To summarize:

The number of ...FormulaOEIS
ESMs with
N pieces
\[{N+7 \choose 9}\]A000582
ESMs with
up to N pieces
\[{N+8 \choose 10}\]A001287
Endgames with
N pieces
\[ \frac{1}{2} {N+7 \choose N-2} + \frac{1}{2} \begin{cases} \left( \begin{array}{cc} \displaystyle \frac{N+6}{2} \\ \displaystyle \frac{N-2}{2} \end{array} \right) & \text{if } N \text{ is even}\\ 0 & \text{if } N \text{ is odd} \end{cases} \]A018213
Endgames with
up to N pieces
\[ \frac{1}{2} {N+8 \choose N-2} + \frac{1}{2} \begin{cases} \left( \begin{array}{cc} \displaystyle \frac{N+8}{2} \\ \displaystyle \frac{N-2}{2} \end{array} \right) & \text{if } N \text{ is even}\\ \left( \begin{array}{cc} \displaystyle \frac{N+7}{2} \\ \displaystyle \frac{N-3}{2} \end{array} \right) & \text{if } N \text{ is odd} \end{cases} \]A018214

The total number of possible generalized chess endgames with 2-32 pieces is 423,838,016, and the total number of ESMs is 847,660,528.

Number of endgames and ESMs in G-Chess, for any number of pieces up to 64:

PiecesEndgamesEndgames
Cumulative
ESMsESMs
Cumulative
2 1 1 1 1
3 5 6 10 11
4 30 36 55 66
5 110 146 220 286
6 365 511 715 1,001
7 1,001 1,512 2,002 3,003
8 2,520 4,032 5,005 8,008
9 5,720 9,752 11,440 19,448
10 12,190 21,942 24,310 43,758
11 24,310 46,252 48,620 92,378
12 46,252 92,504 92,378 184,756
13 83,980 176,484 167,960 352,716
14 147,070 323,554 293,930 646,646
15 248,710 572,264 497,420 1,144,066
16 408,760 981,024 817,190 1,961,256
17 653,752 1,634,776 1,307,504 3,268,760
18 1,021,735 2,656,511 2,042,975 5,311,735
19 1,562,275 4,218,786 3,124,550 8,436,285
20 2,343,770 6,562,556 4,686,825 13,123,110
21 3,453,450 10,016,006 6,906,900 20,030,010
22 5,008,003 15,024,009 10,015,005 30,045,015
23 7,153,575 22,177,584 14,307,150 44,352,165
24 10,080,720 32,258,304 20,160,075 64,512,240
25 14,024,400 46,282,704 28,048,800 92,561,040
26 19,284,460 65,567,164 38,567,100 131,128,140
27 26,225,628 91,792,792 52,451,256 183,579,396
28 35,304,920 127,097,712 70,607,460 254,186,856
29 47,071,640 174,169,352 94,143,280 348,330,136
30 62,203,340 236,372,692 124,403,620 472,733,756
31 81,505,820 317,878,512 163,011,640 635,745,396
32 105,959,504 423,838,016 211,915,132 847,660,528
33 136,719,440 560,557,456 273,438,880 1,121,099,408
34 175,174,205 735,731,661 350,343,565 1,471,442,973
35 222,945,905 958,677,566 445,891,810 1,917,334,783
36 281,963,990 1,240,641,556 563,921,995 2,481,256,778
37 354,465,254 1,595,106,810 708,930,508 3,190,187,286
38 443,085,225 2,038,192,035 886,163,135 4,076,350,421
39 550,858,165 2,589,050,200 1,101,716,330 5,178,066,751
40 681,329,000 3,270,379,200 1,362,649,145 6,540,715,896
41 838,553,320 4,108,932,520 1,677,106,640 8,217,822,536
42 1,027,233,130 5,136,165,650 2,054,455,634 10,272,278,170
43 1,252,716,850 6,388,882,500 2,505,433,700 12,777,711,870
44 1,521,162,500 7,910,045,000 3,042,312,350 15,820,024,220
45 1,839,537,700 9,749,582,700 3,679,075,400 19,499,099,620
46 2,215,814,250 11,965,396,950 4,431,613,550 23,930,713,170
47 2,658,968,130 14,624,365,080 5,317,936,260 29,248,649,430
48 3,179,209,800 17,803,574,880 6,358,402,050 35,607,051,480
49 3,787,984,200 21,591,559,080 7,575,968,400 43,183,019,880
50 4,498,241,475 26,089,800,555 8,996,462,475 52,179,482,355
51 5,324,436,975 31,414,237,53010,648,873,950 62,828,356,305
52 6,282,847,506 37,697,085,03612,565,671,261 75,394,027,566
53 7,391,571,330 45,088,656,36614,783,142,660 90,177,170,226
54 8,670,895,455 53,759,551,82117,341,763,505107,518,933,731
5510,143,295,635 63,902,847,45620,286,591,270127,805,525,001
5611,833,860,640 75,736,708,09623,667,689,815151,473,214,816
5713,770,292,256 89,507,000,35227,540,584,512179,013,799,328
5815,983,392,920105,490,393,27231,966,749,880210,980,549,208
5918,507,065,720123,997,458,99237,014,131,440247,994,680,648
6021,378,872,240145,376,331,23242,757,703,560290,752,384,208
6124,640,032,560170,016,363,79249,280,065,120340,032,449,328
6228,336,060,632198,352,424,42456,672,074,888396,704,524,216
6332,516,764,280230,869,188,70465,033,528,560461,738,052,776
6437,236,965,920268,106,154,62474,473,879,480536,211,932,256

These numbers are computed without considering any specific board. Although the standard 8x8 chess board may accomodate up to 64 generalized chess pieces, many of possible piece configurations have no legal position on this board. For example, chess position can not have any pawns on the first and last ranks, therefore any endgame that includes more than 48 pawns of the same color will have no possible way to place them on the 8x8 board. Also there are piece configurations where every position has the side to move attacking the opponent's king (for example, two kings, 48 white pawns and 14 white rooks). Therefore, the precise number of generalized chess endgames that have legal positions on an 8x8 board is still unknown.

These numbers are relevant for small board chess variants. For example, in the already solved 2-to-9 piece subset of 4x4 chess, the data is stored in 19,448 files, one for each ESM. The complete solution of 3x4 chess is distributed across 184,756 files (cumulative number of ESMs with up to 12 pieces).

Here you can also download the precomputed lists of ESMs and endgames, for up to 16 pieces.


Chess with any starting position (ASP-Chess)

Moving closer to standard chess, let's use the standard set of pieces, but allow any starting position (ASP-Chess for short). This means that the total number of pieces resulting from promotions plus remaining pawns should not exceed 8 for each side. The ASP-Chess values agree with those from G-Chess for 2 to 10 pieces, and begin to diverge from 11 pieces.

ASP-Chess has 37,797,165 endgames and 75,585,636 ESMs in total (about 11 times less than G-Chess with up to 32 pieces).

The total number of ESMs (75,585,636) can be computed as 86942, since there are 8694 possible material configurations of one side. The number of endgames (37,797,165) can be computed as 8694*8695/2: it includes (8694*8693)/2 asymmetric endgames + 8694 symmetric ones.

These numbers were previously mentioned by Ratko Tomic on CCC in 1999: archived post 77068.

Number of endgames and ESMs in ASP-chess, for each number of pieces:

PiecesEndgamesEndgames
Cumulative
ESMsESMs
Cumulative
2 1 1 1 1
3 5 6 10 11
4 30 36 55 66
5 110 146 220 286
6 365 511 715 1,001
7 1,001 1,512 2,002 3,003
8 2,520 4,032 5,005 8,008
9 5,720 9,752 11,440 19,448
10 12,190 21,942 24,310 43,758
11 24,309 46,251 48,618 92,376
12 46,233 92,484 92,340 184,716
13 83,817 176,301 167,634 352,350
14 146,094 322,395 291,978 644,328
15 244,350 566,745 488,700 1,133,028
16 393,114 959,859 785,898 1,918,926
17 606,777 1,566,6361,213,554 3,132,480
18 899,592 2,466,2281,798,689 4,931,169
191,279,689 3,745,9172,559,378 7,490,547
201,749,075 5,494,9923,497,43610,987,983
212,294,793 7,789,7854,589,58615,577,569
222,889,02110,678,8065,777,05521,354,624
233,477,15014,155,9566,954,30028,308,924
243,980,87118,136,8277,960,45536,269,379
254,291,44322,428,2708,582,88644,852,265
264,297,60526,725,8758,593,73153,445,996
273,914,64030,640,5157,829,28061,275,276
283,160,51533,801,0306,319,57567,594,851
292,172,55535,973,5854,345,11071,939,961
301,210,77037,184,3552,420,55074,360,511
31 490,05037,674,405 980,10075,340,611
32 122,76037,797,165 245,02575,585,636

Chess

Standard chess has a fixed starting position, which requires captures before any promotions can happen. In 1999, Ratko Tomic formulated the criteria for a material configuration to be possible in an actual chess game (archived CCC post 77068):

Number of white promotions cannot exceed

    2 * (# of black pawns captured)
  + # of black non-pawns captured
  + # of white pieces captured (pawns or non-pawns),

or symbolically:

      wp <= 2*bpc + bnc + wc   (1)

     (and similar for the reverse colors, via prefix swap w<->b)

Under this condition the number of possible ESMs is 58,084,310 and the number of endgames is 29,045,304 (observed by Ratko Tomic in CCC posts 77068 and 77859).

Number of endgames and ESMs in standard chess, for each number of pieces:

PiecesEndgamesEndgames
Cumulative
ESMsESMs
Cumulative
2 1 1 1 1
3 5 6 10 11
4 30 36 55 66
5 110 146 220 286
6 365 511 715 1,001
7 1,001 1,512 2,002 3,003
8 2,520 4,032 5,005 8,008
9 5,720 9,752 11,440 19,448
10 12,190 21,942 24,310 43,758
11 24,309 46,251 48,618 92,376
12 46,233 92,484 92,340 184,716
13 83,817 176,301 167,634 352,350
14 146,094 322,395 291,978 644,328
15 244,350 566,745 488,700 1,133,028
16 393,114 959,859 785,898 1,918,926
17 606,777 1,566,6361,213,554 3,132,480
18 899,592 2,466,2281,798,689 4,931,169
191,279,689 3,745,9172,559,378 7,490,547
201,749,075 5,494,9923,497,43610,987,983
212,294,793 7,789,7854,589,58615,577,569
222,889,02110,678,8065,777,05521,354,624
233,477,15014,155,9566,954,30028,308,924
243,980,87118,136,8277,960,45536,269,379
254,243,14822,379,9758,486,29644,755,675
263,783,48426,163,4597,565,65052,321,325
272,178,31928,341,7784,356,63856,677,963
28 613,65528,955,4331,226,68157,904,644
29 83,62529,039,058 167,25058,071,894
30 6,09029,045,148 12,10558,083,999
31 15529,045,303 31058,084,309
32 129,045,304 158,084,310

The following chart shows all the actual numbers and upper bounds for 2-32 pieces:

Number of endgames, 2-32 pieces

The next chart shows the cumulative numbers:

Number of endgames, cumulative, 2-32 pieces

Created in 2013-2024 by Kirill Kryukov
This page is in the public domain under the CC0 license