Number of positions in chess endgames

[Kirill Kryukov]

Knowing the exact number of positions in a chess endgame is important for solving an endgame, because it allows to compare statistics with those from independently obtained solutions. In my experiments I use the number of unique legal positions (NULP for short) for reporting statistics (even though this is not what I store in the database).

I use simple definition of legality: 1. Side to move does not give check. (2. No pawns on promotion rank or before the starting rank. 3. Exactly one white king and exactly one black king are on the board). Often people define legal position as the one that can be obtained from the starting position after a sequence of legal moves. I don't use this for practical reasons: 1. Verifying the relation to the starting position can be non-trivial and time consuming. 2. In some chess variants there is no established starting position.

The uniqueness concept is similarly simple: The number of unique legal positions should count only one position out of all of its symmetrical equivalent variants. This includes swapping the side to move, and also diagonal symmetries and rotations of the board. An example can be seen on 4x4 chess site.

Although chess endgame have been studied to great depth, I've been unable to find the numbers of unique legal positions in chess endgames. If someone knows of any reports of such numbers, I'll appreciate if you direct me to them.

The number of 2-piece positions (bare kings) in chess is well known: 462. However, not for 3 pieces or more (AFAIK). Last year Guy Haworth kindly posted statistics from Nalimov tablebases up to 6 pieces. These numbers are a good start, except for these issues: 1. Some positions are counted twice (diagonally symmetrical positions with kings on the main diagonal, as far as I understand). 2. Positions with castling rights are not counted. 3. 5-vs-1 positions are not counted.

My current numbers for chess are:

Pieces NULP 2 462 3 368,079 4 125,246,598 5 25,912,594,054 6 3,787,154,440,416

Any help verifying or debugging these numbers will be greatly appreciated. If anyone prefers to compare numbers for particular endgame, or for modified chess rules (no castling, different board size, etc), I am interested as well.

Thanks,
Kirill

[h.g.muller]

For 3 pieces and more it would depend on the kind of piece, right? The more powerful the piece, the more positions there are where it would check the King, and these would all be illegal with that side to move (in your definition).

I never bother calculating legal positions; I always express everything as a percentage of the number of non-broken (= no coinciding pieces) positions. Then I report the fraction king-capture positions. That is usually very helpful, because it should be similar to the number of positions where on the first move you can capture any other piece, showing you how badly the statistics of a certain end-game is contaminated by positions that are really a sub-end-game because of a hanging piece.

[Kirill Kryukov]

For 3 pieces and more it would depend on the kind of piece, right? The more powerful the piece, the more positions there are where it would check the King, and these would all be illegal with that side to move (in your definition).

Yes, of course.

I never bother calculating legal positions; I always express everything as a percentage of the number of non-broken (= no coinciding pieces) positions. Then I report the fraction king-capture positions. That is usually very helpful, because it should be similar to the number of positions where on the first move you can capture any other piece, showing you how badly the statistics of a certain end-game is contaminated by positions that are really a sub-end-game because of a hanging piece.

Do you consider all symmetries when counting positions? If I'll understand the exact method you use for reporting stats, I may implement it as an option.

Do you see the benefit from comparing statistics with others? If yes, then how do you propose to do that - should the others compute statistics in same way you do?

The NULP approach that I propose above is more or less independent from implementation, and closer to the true chessic sense. I guess that those who are just interested in chess (not in constructing tablebases), would prefer to see endgame stats in terms of NULP (unique legal positions). Perhaps it's the extra effort needed to compute such values that is stopping you and others from using them? I find the effort needed for computing stats in NULP insignificant compared to the effort of solving an endgame.

[syzygy]

The uniqueness concept is similarly simple: The number of unique legal positions should count only one position out of all of its symmetrical equivalent variants. This includes swapping the side to move, and also diagonal symmetries and rotations of the board.

What about swapping pieces of identical type and color?

1. Some positions are counted twice (diagonally symmetrical positions with kings on the main diagonal, as far as I understand).

What I do is count positions that are "unique" in my generated table twice, and count the positions for which the diagonally symmetrical twin is also in the table once. Then I divide the total by 2.

Another question is what to do with pieces of the same type and color. I ignore those symmetries in my statistics, because my generator ignores those as well (I compress them out later). It is possible to correct for these, but it is not completely trivial (you can't simply divide by 2!=2 or 3!=6, since there is interaction with other symmetries).

I don't count en passant, since I don't store ep positions in my tables (the tables do respect the en passant rule though).

Let's see, 3 pieces:
KQvK: 46137
KRvK: 50015
KBvK: 52234
KNvK: 53806
KPvK: 165676
total: 367868

3 368,079

Hmm
I don't have an explanation for the difference of 211.

What might help is compare the number of legal positions in KXvK with black to move: 28056 (for X = Q/R/B/N).

[Kirill Kryukov]

The uniqueness concept is similarly simple: The number of unique legal positions should count only one position out of all of its symmetrical equivalent variants. This includes swapping the side to move, and also diagonal symmetries and rotations of the board.

What about swapping pieces of identical type and color?

Since such positions are not only equivalent, but indistinguishable when looking at the board (also described by identical FENs), only one of such variants is counted for the NULP. This is another concept that is relevant only for programmers, normal chess people won't even understand what we are talking about. So I want to take care of such issues before communicating any results.

1. Some positions are counted twice (diagonally symmetrical positions with kings on the main diagonal, as far as I understand).

What I do is count positions that are "unique" in my generated table twice, and count the positions for which the diagonally symmetrical twin is also in the table once. Then I divide the total by 2.

Should be OK, as long as our numbers match. What I do is decide which of the "non-unique" positions will be representative, and count only those, skipping the others. In chess we are lucky that the board dimensions are even, so king placement takes care of horizontal and vertical symmetries automatically. We only need to worry about the diagonal symmetry. With some other board sizes there are also horizontal and vertical symmetries to worry about.

Another question is what to do with pieces of the same type and color. I ignore those symmetries in my statistics, because my generator ignores those as well (I compress them out later). It is possible to correct for these, but it is not completely trivial (you can't simply divide by 2!=2 or 3!=6, since there is interaction with other symmetries).

I also don't store such extra positions.

I don't count en passant, since I don't store ep positions in my tables (the tables do respect the en passant rule though).

It's OK to throw away positions when storing them (I also throw many), but conceptially it's more beautiful to count them anyway for the stats. Throwing away positions is again an implementation detail, which will very likely differ from one solver to the other, so the stats won't be comparable. Also, when introducing the results to others, you will have to mention all these little implementation details, which confuse and scare people.

Let's see, 3 pieces:
KQvK: 46137
KRvK: 50015
KBvK: 52234
KNvK: 53806
KPvK: 165676
total: 367868

3 368,079

Hmm
I don't have an explanation for the difference of 211.

If I count without castling, I also get 367868.

What might help is compare the number of legal positions in KXvK with black to move: 28056 (for X = Q/R/B/N).

Agreed on this number, except KKR, where I count 28170 due to castling. My current numbers by endgame:

Endgame WTM BTM kqk 18,081 28,056 krk 22,056 28,170 kbk 24,178 28,056 knk 25,750 28,056 kpk 81,664 84,012

Thanks for the input!

[syzygy]

Indeed, I do not include positions with castling rights

[h.g.muller]

I always make the effort to count symmetry-reduced positions twice when I take the statistics. This because I am interested in answering the question: "when you set up a random position, how large is the probability it is won (lost)?". When two different positions are symmetry equivalent, it is still twice as likely one of them would occur as for a unique symmetric position.

For comparing with stats of other EGT generators, it has the advantage that it is an implementation-independent well-defined number. In practice symmetry reduction is often not carried out fully. (E.g. in my generator I do only pay attention to two pieces, and if they are both on the diagonal I don't consider the others to see if it is truly symetric.)

[koistinen]

I like it! Metrics have many benefits. To clarify could you look at the position and explain?

rnb1kbnr/pppp1ppp/8/4p3/5PPq/8/PPPPP2P/RNBQKBNR w


How many ULPs have the pieces on the squares as above and why?

[Kirill Kryukov]

Unless I'm missing something, it should be 16 (4x4), because with this piece placement both white and black can have 4 different possibilities of castling rights.

[koistinen]

Unless I'm missing something, it should be 16 (4x4), because with this piece placement both white and black can have 4 different possibilities of castling rights.

Ok, that is very reasonable, because it could get complicated if you had to consider if those rights might ever be used when counting.

4k3/8/2q5/3Pp3/4K3/8/8/8 w


Similarly, 2 ULPs would have the pieces on the squares as above due to different en passant values?

[Kirill Kryukov]

Ok, that is very reasonable, because it could get complicated if you had to consider if those rights might ever be used when counting.

...

Similarly, 2 ULPs would have the pieces on the squares as above due to different en passant values?

Yes, 2 ULPs. Exactly, the idea is to keep the counting as simple as possible by removing just the obvious redundancies and illegalities.

[Kirill Kryukov]

I always make the effort to count symmetry-reduced positions twice when I take the statistics. This because I am interested in answering the question: "when you set up a random position, how large is the probability it is won (lost)?". When two different positions are symmetry equivalent, it is still twice as likely one of them would occur as for a unique symmetric position.

Sorry, I'm still not clear about your counting.
1. Some positions have more than two symmetrical variants, what do you count for those? For example, what would you count for the example 4x4 chess position - I show 16 variants of that position on that page, but count only one for the NULP.
2. When the board had odd width or height (e.g., 5x5 board), do you always consider left-right and up-down symmetries properly (including those with en-passant rights on/off center, etc).?

I think it will help if you'll show the example numbers for some positions and endgames.

For comparing with stats of other EGT generators, it has the advantage that it is an implementation-independent well-defined number.

I'm still hoping to understand (and possibly implement) your method of counting. The number of unique legal positions (NULP) that I use is actually implementation-independent and well-defined number, with more simple definition. Which is why I think it's more well-suited for the purpose of stats exchange.

Another reason why I prefer NULP - it more directly corresponds to state-space complexity. Intuitively it makes sense to me to require that no two states can be symmetrical variants of each other.

In practice symmetry reduction is often not carried out fully. (E.g. in my generator I do only pay attention to two pieces, and if they are both on the diagonal I don't consider the others to see if it is truly symetric.)

I think it's a commonly used simplification, used also by Nalimov (IIRC). I think counting the actually stored positions does not have to be the only way to report statistics. (I report stats in unique legal positions (NULP), but it's not what I store in the database).

[Kirill Kryukov]

NULP values from some test runs. Always square board, no double pawn move, no castling, pawns start at 1-st rank. All possible piece combinations (endgames) are included. Board sizes from 3x3 to 20x20, 2 to 5 pieces (total number including the kings), NULP values below 1 trillion.

. . .

On the second plot the horizontal axis (board size) uses log scale. Note the almost straight lines - this means good fit with the power function, as expected.

(If anyone needs the actual numbers, let me know).

[Kirill Kryukov]

More test runs. Number of unique legal positions (NULP) in endgames on square boards from 3x3 to 8x8, pawns start at 1-st rank, no double step, no castling.

. . .

Board occupancy = how large proportion of board area is occupied. E.g., 2 pieces on 4x4 board means occupancy of 2/16*100 = 12.5%.

[Kirill Kryukov]

Number of unique legal positions in 7-piece chess endgames: 423,836,835,667,331. This number is for standard set of rules: pawns start on 2-nd rank, can double step, with en-passant capture and with castling.

[Kirill Kryukov]

I decided to make a small web-site dedicated just to counting chess endgame positions: NULP. I will gradually add more data and discussion to those pages. Please enjoy and let me know if you'll have any comments, questions or requests.

[Kirill Kryukov]

The number of unique legal positions in 8-piece chess endgames: 38,176,306,877,748,245. Not sure if I'll count for 9-pieces.

[Kirill Kryukov]

The number of 8-piece FRC positions: 39,587,704,309,395,475.

[Kirill Kryukov]

Someone asked me about the number of positions with en passant capture rights, and how it compares to number of positions with castling rights. So I added such numbers to the NULP site (link).

In particular, the following chart may be interesting.


"C" line shows the percentage of positions with castling rights but without en passant rights.
"E" line shows the percentage of positions with en passant rights but without castling rights.
(Among all positions with the same number of pieces).

The chart shows that, although positions with castling rights are more abundant in endgames with up to 8 pieces, the situation reverses with 9 or more pieces: positions with en-passant rights are more abundant there.

(This all has nothing to do with frequency of any of those positions appearing over the course of typical chess game).

[Doirse]

this is incredibly fascinating!

Is it possible to create W/D/L results for all possible positions in a specific endgame? For example, looking at the NULP results for KRKP endgames there are 9,041,298 possible legal positions. How would one go about determining how many of those are W/D/L for btm and wtm?

I have seen results given on other websites using databases of games, which of course means imperfect play.

Has this work been done before, and if so can someone point me in the right direction? If not, is this something I can learn to generate myself using an EGTB?

Many thanks in advance.

[Kirill Kryukov]

this is incredibly fascinating!

It is!

Is it possible to create W/D/L results for all possible positions in a specific endgame? For example, looking at the NULP results for KRKP endgames there are 9,041,298 possible legal positions. How would one go about determining how many of those are W/D/L for btm and wtm?

I have seen results given on other websites using databases of games, which of course means imperfect play.

Has this work been done before, and if so can someone point me in the right direction? If not, is this something I can learn to generate myself using an EGTB?

Many thanks in advance.

Well, since a EGTB stores the outcome of all positions, it's possible to traverse all positions, check the EGTB for each, and count wins/draws/losses. Also, a EGTB genetator typically performs this counting and reports the numbers. For instance, you can obtain Nalimov's statistics by clicking on "tbs" links on this page: http://kirill-kryukov.com/chess/tablebases-online/ . Also, you can try syzygy generator, or ask someone to post its statistics.

The limitations of those stats are:
1. They normally don't consider uniqueness and legality in the same sense as I did when counting positions (NULP page).
2. Nalimov's generator does not care about the 50 moves rule. Syzygy's one does.
3. They don't know about castling.

Still this might be close to what you are looking for?