# Counting chess endgames

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 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 piecs of the side-to-move, then 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) Strength of the first different piece, strong to weak (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 pointed out to me 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 I could find was in 1999's message by Hans Havermann on CCC forum: archived forum post 64263. To summarize:

The number of ... | Formula | OEIS |

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} \] | A018213 |

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:

Pieces | Endgames | Endgames Cumulative | ESMs | ESMs 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,530 | 10,648,873,950 | 62,828,356,305 |

52 | 6,282,847,506 | 37,697,085,036 | 12,565,671,261 | 75,394,027,566 |

53 | 7,391,571,330 | 45,088,656,366 | 14,783,142,660 | 90,177,170,226 |

54 | 8,670,895,455 | 53,759,551,821 | 17,341,763,505 | 107,518,933,731 |

55 | 10,143,295,635 | 63,902,847,456 | 20,286,591,270 | 127,805,525,001 |

56 | 11,833,860,640 | 75,736,708,096 | 23,667,689,815 | 151,473,214,816 |

57 | 13,770,292,256 | 89,507,000,352 | 27,540,584,512 | 179,013,799,328 |

58 | 15,983,392,920 | 105,490,393,272 | 31,966,749,880 | 210,980,549,208 |

59 | 18,507,065,720 | 123,997,458,992 | 37,014,131,440 | 247,994,680,648 |

60 | 21,378,872,240 | 145,376,331,232 | 42,757,703,560 | 290,752,384,208 |

61 | 24,640,032,560 | 170,016,363,792 | 49,280,065,120 | 340,032,449,328 |

62 | 28,336,060,632 | 198,352,424,424 | 56,672,074,888 | 396,704,524,216 |

63 | 32,516,764,280 | 230,869,188,704 | 65,033,528,560 | 461,738,052,776 |

64 | 37,236,965,920 | 268,106,154,624 | 74,473,879,480 | 536,211,932,256 |

The above table stops at 64 pieces, bound by the 8x8 board size of standard chess. However, since this is generalized chess, it may also have a larger board, and the numbers can continue their growth toward the infinity.

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 8694^{2},
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:

Pieces | Endgames | Endgames Cumulative | ESMs | ESMs 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,636 | 1,213,554 | 3,132,480 |

18 | 899,592 | 2,466,228 | 1,798,689 | 4,931,169 |

19 | 1,279,689 | 3,745,917 | 2,559,378 | 7,490,547 |

20 | 1,749,075 | 5,494,992 | 3,497,436 | 10,987,983 |

21 | 2,294,793 | 7,789,785 | 4,589,586 | 15,577,569 |

22 | 2,889,021 | 10,678,806 | 5,777,055 | 21,354,624 |

23 | 3,477,150 | 14,155,956 | 6,954,300 | 28,308,924 |

24 | 3,980,871 | 18,136,827 | 7,960,455 | 36,269,379 |

25 | 4,291,443 | 22,428,270 | 8,582,886 | 44,852,265 |

26 | 4,297,605 | 26,725,875 | 8,593,731 | 53,445,996 |

27 | 3,914,640 | 30,640,515 | 7,829,280 | 61,275,276 |

28 | 3,160,515 | 33,801,030 | 6,319,575 | 67,594,851 |

29 | 2,172,555 | 35,973,585 | 4,345,110 | 71,939,961 |

30 | 1,210,770 | 37,184,355 | 2,420,550 | 74,360,511 |

31 | 490,050 | 37,674,405 | 980,100 | 75,340,611 |

32 | 122,760 | 37,797,165 | 245,025 | 75,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:

Pieces | Endgames | Endgames Cumulative | ESMs | ESMs 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,636 | 1,213,554 | 3,132,480 |

18 | 899,592 | 2,466,228 | 1,798,689 | 4,931,169 |

19 | 1,279,689 | 3,745,917 | 2,559,378 | 7,490,547 |

20 | 1,749,075 | 5,494,992 | 3,497,436 | 10,987,983 |

21 | 2,294,793 | 7,789,785 | 4,589,586 | 15,577,569 |

22 | 2,889,021 | 10,678,806 | 5,777,055 | 21,354,624 |

23 | 3,477,150 | 14,155,956 | 6,954,300 | 28,308,924 |

24 | 3,980,871 | 18,136,827 | 7,960,455 | 36,269,379 |

25 | 4,243,148 | 22,379,975 | 8,486,296 | 44,755,675 |

26 | 3,783,484 | 26,163,459 | 7,565,650 | 52,321,325 |

27 | 2,178,319 | 28,341,778 | 4,356,638 | 56,677,963 |

28 | 613,655 | 28,955,433 | 1,226,681 | 57,904,644 |

29 | 83,625 | 29,039,058 | 167,250 | 58,071,894 |

30 | 6,090 | 29,045,148 | 12,105 | 58,083,999 |

31 | 155 | 29,045,303 | 310 | 58,084,309 |

32 | 1 | 29,045,304 | 1 | 58,084,310 |

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

The next chart shows the cumulative numbers:

This page is in the public domain under the CC0 license