NULP

(Number of Unique Legal Positions in chess endgames)

Number of endgames

What is an endgame?

An endgame is a set of all positions with particular material on board. Endgame name is written by listing algebraic notation symbols of one, then the other side's material, in order: K, Q, R, B, N, P. To avoid ambiguity 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).

An ESM is a combination of endgame and side to move. Normally an endgame corresponds to 2 ESMs, however symmetrical ones (like kpkp) have just 1 ESM.

Generalized chess

How many endgames and ESMs are there in chess? First let's 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 CCC Discussion. 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. You can also check the pre-computed values for up to 64 pieces.

Chess with no starting position

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 G-Chess ones 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 numbers for each particular number of pieces are also available.

The total number of ESMs (75,585,636) can be computed as 8694², 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.

Chess

Standard Chess has a fixed starting position, which requires captures before any promotions can happen. Tomic formulated the criteria for a material configuration to be possible in an actual Chess game:

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 Tomic here and here). The numbers for each particular number of pieces can be seen here.

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

The next chart shows the cumulative numbers:

Number of endgames, cumulative, 2-32 pieces


© 2013–2014 Kirill Kryukov Available under the CC BY 3.0 License