NULP

Method

What is a 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:

Note that board 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.

4-th transformation can produce identical position if all pieces are located on a8-h1 diagonal. 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).