New estimate of the number of legal chess positions

[petero2]

I have computed a new more accurate estimate of the number of legal chess positions. The estimate is based on random sampling from a superset of all legal chess positions, using "texelutil rndfen" and then analyzing the legality of the positions in the sample. The sampling procedure produces an unbiased estimate and an estimated standard error. The result is:

Code: Select all

N_legal ≈ 4.823692e44
std_dev ≈ 0.001974e44

Or, with a 95% confidence interval:

Code: Select all

N_legal ≈ (4.823692 +- 0.003870) * 1e44
        = [4.819822, 4.827561] * 1e44

The main difference compared to the old method is a 2-stage sampling process that reduces the total work substantially compared to my prediction from 2022, without sacrificing much of the accuracy. The new 95% confidence interval is around 7.2 times smaller than the old.

More details are available here: https://github.com/peterosterlund2/texe ... umlegal.md

The old result from 2022 was:

Code: Select all

(4.822 +- 0.028) * 10^44  (at 95% confidence level)

[Ajedrecista]

Hello Peter:

This serves to check how accurate the first estimate was, so close to the second. You narrow the interval by a good amount now. Congratulations!

Would you mind to explain why the starting space size is N = 2 * 3969 * 2^62 * 2^30 * 5^30 * 6? I mean: what is 2 (white or black to move), what is 3969 (63², but why) and so on. Thank you in advance.

Regards from Spain.

Ajedrecista.

[petero2]

Would you mind to explain why the starting space size is N = 2 * 3969 * 2^62 * 2^30 * 5^30 * 6? I mean: what is 2 (white or black to move), what is 3969 (63², but why) and so on. Thank you in advance.

Hi Ajedrecista,

Sure, the factors are like this:
* 2 : The side to move
* 3969 : The number of possible ways to place two kings on the board without them attacking each other, and considering castling possibilities. A white king on e1 has four castling possibilities (none, right, left, both). A white king on any other square has 1 castling possibility (none). Correspondingly for the black king. This number is computed by an exhaustive enumeration, see the source code. I hadn't even noticed this is 63^2. There might be a simple combinatorial reason for this, or it could be "random".
* 2^62 : There are 62 empty squares after placing the kings, so there are 2^62 ways to decide which remaining squares are non-empty. Choices having more than 30 1-bits are considered illegal.
* 2^30 : There are at most 30 non-kings, so there are 2^30 ways to decide the color of those pieces. If there are fewer than 30 non-kings, the left-over bits must be 0 for a legal position. This ensures the super-set does not contain a legal position more than once, which would bias the sampling.
* 5^30 : There are 5 non-king piece types and at most 30 non-king pieces, so the same reasoning as for 2^30 applies.
* 6 : There are at most 6 en passant possibilities in a position. Values larger than what is possible in a certain position are considered illegal, again in order to not have duplicated legal positions.

The maximum en passant possibilities case happens for example in this position

[d]rnbqkbnr/p1pp1pp1/8/8/PpPPpPPp/8/1P2P2P/RNBQKBNR b KQkq - 0 1

The en passant target square is one of none, a3, c3, d3, f3, g3.