Number of Unique Legal Positions (NULP)
in chess endgames

Updated on 2025-03-05

Kirill Kryukov

About

In this document we describe NULP (Number of Unique Legal Positions) as the measure of state-space complexity of chess endgames. We discuss the definitions of uniqueness and legality, and share the NULP values of various endgames.

This paper gets updated when we get new ideas or results. This work is in public domain using the CC0 license. Please email any questions, comments, and ideas to kkryukov@gmail.com. Especially welcome are confirmations or corrections of any results.

Introduction

In 1950 Claude Shannon famously estimated the number of possible chess positions to be "of the general order of 64!/32!(8!)²(2!)⁶, or roughly 10⁴³" (Shannon (1950) "Programming a Computer for Playing Chess"). This includes some illegal positions (e.g., pawns on the first rank, both kings in check) and excludes legal positions following captures and promotions. Later estimates include 10⁵⁰ by Victor Allis (with upper bound of 5x10⁵²). More recently John Tromp has shown the upper bound of 2¹⁵⁵ (about 10^46.7). Significantly improving the estimate for the whole game is difficult with today's methods and computers, however much better estimates are possible for subsets of the game, such as opening of endgame.

On the opening side, one well-known statistic is Perft, which is the number of move paths of N plies from the starting position. Perft is known for up to 15 plies and is widely used for testing and benchmarking move generators. There are 20 move choices in the starting position, so 20 different legal positions can occur after white's first move, and 400 after black's first reply. These numbers agree with Perft(1) and Perft(2), respectively. Perft(3), however, is larger than the number of different legal positions, because it counts transpositions independently from each other. The number of transpositions grows rapidly with each extra ply. This means that while Perft can be used as the upper bound for the number of positions, it does not provide a very good estimate. I'm not aware of any efforts to count different legal positions beyond the first 2 plies.

On the endgame side most of the estimates of endgame sizes come from solving projects. Strongly solving an endgame typically involves storing a value for each indexed position, thus endgame size can be measured as the number of indexed positions. The choice of the indexing method is crucial here and has to balance database compactness with indexing speed: storing fewer positions makes the database more compact, but complicates the indexing, degrading performance. As the result common indexing method use relaxed concepts of position legality and uniqueness.

In summary, currently available estimates of endgame sizes suffer from following limitations:

• Many illegal positions are included.
• Some redundant positions are included.
• Some legal positions are omitted (those with castling rights).
• The results are only available for solved endgames.
• The resutls are usually limited to 8x8 board.

In this experiment I aim to advance on all of these points. This means providing more accurate estimates for endgame sizes in chess and chess variants, while trying to avoid illegal and redundant positions when possible. The motivations for computing such estimates include:

• Knowing the endgame size in advance can be helpful for solving as it allows estimating the required time and hardware.
• NULP-based statistics (e.g., number of wins / NULP) can be used for comparing results of independent solving efforts.
• A well defined NULP allows discussing index efficiency (NULP / number of indexed positions) and compactness (NULP / byte) of different databases.
• Comparing NULP values with other estimates may allow improving estimates for larger endgames or even for the whole game.

At first this data was a by-product of solving experiments, but then I decided to share it separately from solving results.

Definitions

Position

For the purpose of this experiment a position is defined as a combination of piece placement, side to move, castling rights and en-passant rights. Storing the evaluations for all such positions from a particlar endgame allows perfect play from the point of entering that endgame, so the number of such positions is directly related to the amount of necessary storage space.

A complete game state should include the move counter for detecting a draw by 50-move rule. Move counter can be very important when distance to mate (DTM) is stored in the database and used for choosing the moves. However using distance to zeroing (DTZ) allows to avoid storing the move counter while still respecting the 50-move rule. (Most of endgame databases in use today simply ignore the 50-move rule, in which case the move counter is also unnecessary).

A complete game state should also include the relevant part of game history for detecting 3-fold repetitions. Repetitions can't occur in a winning line if the winning side plays perfectly, and they won't matter in a drawing line, therefore the history can be safely omitted as well.

Uniqueness

Counting, solving or storing the same position twice is obviously a waste of time and space. Similarly, if two positions can be proven to produce identical outcomes with best play of both sides (let's call such positions equivalent), it's a waste of space to store both of them independently. Whether it's also a waste of time depends on how fast the equivalence can be tested and on how it impacts indexing design and performance.

In this experiment I require equivalence to perfectly take into account board mirroring, board rotation and color swapping. Such equivalence is easy to test, so counting unique positions (or equivalence classes) is possible. (It's less trivial to design a gapless indexing scheme omitting all redundant positions, but this is outside of the scope of current experiment).

Two positions are called equivalent if one can be obtained from the other through a sequence of transformations, which may include:

Rotations and mirroring around the other diagonal can be produced by combining several of the listed transformations. Also you can notice that this equivalence is reflexive, symmetric and transitive.

The 4-th transformation can produce identical position if all pieces are located on the a8-h1 diagonal. The 2-nd and 3-rd transformations can produce identical positions on an odd-sized board. The 1-st transformation however can be applied to any position, and will always produce a non-identical position. Therefore every position has at least one equivalent non-identical variant. Each transformation applied twice returns back to the original position, so the maximum possible number of equivalent non-identical variants for a position is 16.

Here is one example of equivalence class — all these positions are considered to be equivalent to each other (4x4 board is used for compactness):

Counting unique positions means counting such equivalence classes (or counting only one position out of each equivalence class).

One case of trivial equivalence ignored in the definition above is between two positions that differ by just en-passant capture right, when the en-passant capture is not a legal move. Such two positions have identical sets of available moves, so it's redundant to solve or store both of them. However in this experiment I count such positions separately.

Legality

Traditionally legal positions are defined as those that can be reached from the starting position after a sequence of legal moves. Checking for such legality is prohibitively expensive, so more simple concepts of legality are used in endgame solving. Such legality is easy to verify, but can include some positions that are illegal in traditional sense. Here is the definition used in this experiment:

A position is called illegal when any of the following conditions holds:

• The number of white kings or the number of black kings on board is different from 1.
• There is a pawn on its side's last (promotion) rank.
• There is a pawn below its side's starting rank (second rank in standard chess).
• Side to move can capture the opponent's king.

All other positions are considered to be legal and counted in this experiment (none of the illegal positions are counted).

Numbers

NULP in chess

The number of unique legal positions in chess endgames with 8 or fewer pieces is 38,603,956,906,065,185.

The following table and chart show the NULP for each number of pieces.

Pieces Positions 2 462 (*) 3 368,079 (*) 4 125,246,598 (*) 5 25,912,594,054 (*) 6 3,787,154,440,416 (*) 7 423,836,835,667,331 (*) 8 38,176,306,877,748,245 (*)

This sequence is the start of OEIS sequence A318266 [OEIS-A318266].

The numbers link to text files with NULP for each endgame. The asterisks link to text files with NULP for each ESM. The definition and notation for endgames and ESM are discussed in "Counting Chess Endgames".

Largest endgames

Castling

Endgames with castling rights are extremely rare, so they are typically ignored in endgame solving. The next table shows the number of Chess positions with castling rights with up to 8 pieces. The numbers in parentheses and the chart show proportion of such positions.

Pieces Positions with castling rights 2 0 (0.000%) 3 211 (0.057%) 4 113,158 (0.090%) 5 29,955,209 (0.116%) 6 5,216,780,406 (0.138%) 7 672,112,496,048 (0.159%) 8 68,300,985,290,716 (0.179%)

As expected, very few endgame positions have castling rights: about 0.1% of all positions with 4 or 5 pieces. The proportion is slowly increasing with extra pieces, probably reaching 0.2% with 10 pieces.

Clearly space saving consideration alone can't justify the exclusion of these positions from solving. The extra effort required for implementing the indexing of these positions is likely the main reason why these positions are usually omitted. Since loss of the castling right is irreversible, it's possible to construct a separate database for just positions with castling rights, which can be used alongside with existing endgame database.

En passant capture

How many chess positions have en passant capture rights? Here are the numbers for up to 8 pieces.

En passant capture and castling

How many positions have both en passant capture and castling rights? How many have just castling or just en passant? How many have none? Here are the numbers for up to 8 pieces ('C' = castling rigths, 'E' = en passant capture rights). Numbers link to text files with NULP for each endgame, asterisks link to text files with NULP for each ESM.

The next table shows the proportion of positions with/without en passant and castling rights among all positions with the same number of pieces. The chart compares columns 'C' and 'E'.

Pieces Positions, % — C E E&C 2 100.000 0.000 0.000 0.000 3 99.943 0.057 0.000 0.000 4 99.891 0.090 0.018 0.000 5 99.838 0.116 0.046 0.000 6 99.781 0.138 0.081 0.000 7 99.720 0.158 0.122 0.000 8 99.652 0.179 0.169 0.000

Positions with castling rights are more abundant than those with en passant, when the number of pieces is 8 or less. However it's safe to say that from 9 pieces the relation reverses.

Chess960

Chess960 (Fischer Random Chess) is a popular chess variant featuring additional starting positions. From endgame solving point of view its only difference from Chess is that many more positions can potentially have castling rights:

Chess960 has more than 20 times more positions with castling rights than Chess. With 7 pieces already over 3% of Chess960 positions have castling rights, which is insane compared to Chess. Here space and time saving can be an argument for omitting such positions, however this way we'll miss more than 3% of beauty and complexity of Chess960 endgames, which weddcccccc see as a big loss. The Chess960/Chess ratio of the number of positions with castling rights is remarkably stable around 21-22, and is slowly increasing with extra pieces, almost perfectly linearly.

Using the castling data above it's easy to find the number of Chess960 positions:

Chess960 is a superset of Chess: every Chess position exists in Chess960, but not the vice versa - some Chess960 positions are not found in Chess. The following table/figure shows the proportion of Chess960 endgame positions overlapping with Chess.

Pieces Among Chess960 positions % in Chess % not in Chess 2 100.000 0.000 3 98.869 1.131 4 98.218 1.782 5 97.715 2.285 6 97.271 2.729 7 96.849 3.151 8 96.435 3.565

History

References