The number of legal chess positions is ~ 4.8 * 10^44

[tromp]

Happy New Year, chess programmers!

In 2021 I determined the number of legal chess positions to be approximately 4.8 * 10^44, based on randomly sampling 2 million positions and, with the help of many other people, in particular Peter Österlund with custom Texel code, determining for each one whether it is legal or not (producing either a proof game or a proof of impossibility) [1].

Btw, my profile on the chessprogramming wiki [2] only mentions a much older 7.729*10^45 upperbound of mine, and fails to mention the more recent Chess Position Ranking project that renders the earlier bound obsolete. Perhaps someone is able and willing to update the entry.

[1] https://github.com/tromp/ChessPositionRanking

[2] https://www.chessprogramming.org/John_Tromp

[towforce]

In 2021 I determined the number of legal chess positions to be approximately 4.8 * 10^44, based on randomly sampling 2 million positions and, with the help of many other people, in particular Peter Österlund with custom Texel code, determining for each one whether it is legal or not (producing either a proof game or a proof of impossibility).

https://github.com/tromp/ChessPositionRanking

A smart way to approach the challenge!

[chesskobra]

Thanks for the post. Your github repository has many references, which I have not looked at. But could you indicate a reference where I can read the details on how the positions are sampled uniformly randomly. I think chess positions (legal or not) would be permutations over an alphabet with repetitions of letters allowed, with a few additional restrictions. Does the book Kreher and Stinson give a rank function (or a grey code?) for such a problem (e.g., a grey code for all FENs)?

I first learned the idea of sampling from Feller's probability book. If I remember, he motivates the idea with the problem of counting fish in a pond.

[tromp]

Thanks for the post. Your github repository has many references, which I have not looked at. But could you indicate a reference where I can read the details on how the positions are sampled uniformly randomly. I think chess positions (legal or not) would be permutations over an alphabet with repetitions of letters allowed, with a few additional restrictions. Does the book Kreher and Stinson give a rank function (or a grey code?) for such a problem (e.g., a grey code for all FENs)?

Positions are sampled exactly as described in Kreher and Stinson [1]:

> Efficient ranking and unranking algorithms have severeal potential uses. We mention a couple now. One application is the generation of random objects from a specified set S. This can be done by generating a random integer i \in {0,...,M},
where N = |S|, and then unranking i. This algorithm ensures that every element of S is chosen with equal probability 1/N, assuming that the random number generator being used is unbiased.

The major contribution of the Chess Position Ranking is to develop such efficient (un)ranking algorithms for chess positions, which has never been done before, or even considered possible. As I wrote in the Section "Interesting observations" on the project webpage, the (un)ranking is defined as a composition of 14 more elementary (un)ranking algorithms. Only some of these are discussed by Kreher and Stinson. The most important one is what I call the multinomial ranking [2], which as far as I can tell is not discussed by Kreher and Stinson, but can probably be found elsewhere in the literature.

Btw, gray codes are used for sequential enumeration and are thus not useful for this project, as sequentially enumerating over 10^45 elements would be sheer impossible.

[1] https://www.taylorfrancis.com/books/mon ... as-stinson

[2] https://github.com/tromp/ChessPositionR ... hs#L16-L45

[chesskobra]

I will look at the book and may ask a few questions here. For now only one more question: since the number of legal positions is a very small fraction of the number of positions (~10^(-76)?) I suspect that generating a few million random positions and then estimating the fraction of total positions that are legal would have a very large variance. Is this an issue, and if so how do you handle this?

[tromp]

since the number of legal positions is a very small fraction of the number of positions (~10^(-76)?) I suspect that generating a few million random positions and then estimating the fraction of total positions that are legal would have a very large variance. Is this an issue, and if so how do you handle this?

If you read the webpage, you see that the number of positions we sample from is N = 8726713169886222032347729969256422370854716254 ~ 8.7E45 so the probability of being legal is more than 5%.
The sample statistics are all detailed in the section "Estimation from million sized samples" where we compute:

$ cat Texel.out.94903 Texel.out.95544 | src/estimate.pl 2000000
Exp[Y] ~ 0.0552548 * N
Var[Y] ~ 0.051689 * N^2
Sigma[Y] ~ 0.227352 * N
Sigma[Y[S]] ~ 0.000160762 * N
n = 2000000 samples 112754/190447 legal 108547 3418 705 56 3 23 2 avg 1/mult 0.980095015106633
estimate 4.82193e+44 +- 2.74973e+42 at 95% confidence

I encourage you to read the entire README.

[petero2]

I will look at the book and may ask a few questions here. For now only one more question: since the number of legal positions is a very small fraction of the number of positions (~10^(-76)?) I suspect that generating a few million random positions and then estimating the fraction of total positions that are legal would have a very large variance. Is this an issue, and if so how do you handle this?

The "number of positions" is not actually well-defined. If you assume any square can contain any piece, there are 13^64~=2e71 piece arrangements (en passant/castling flags/side to move not included). If you assume each side has exactly one king, there are at most 64^2 * 11^62 ~= 1.5e68 piece arrangements. By taking more and more effects into account (e.g. kings cannot be adjacent to each other, pawns are not allowed on the first/last rank, there are at most 32 pieces, etc.), you can decrease this number further. The Chess Position Ranking project took this approach much further and was able to construct a set of size 8.7e45 that is guaranteed to contain all legal chess positions.

For your example of N=1e76, the probability that a random position is legal is ~5e-32, so any sample of a size that would fit in a computer would with very high probability contain 0 legal positions. Having a representation where N is sufficiently small is required for the random sample approach to work at all in practice.

[towforce]

The "number of positions" is not actually well-defined. If you assume any square can contain any piece, there are 13^64~=2e71 piece arrangements (en passant/castling flags/side to move not included). If you assume each side has exactly one king, there are at most 64^2 * 11^62 ~= 1.5e68 piece arrangements. By taking more and more effects into account (e.g. kings cannot be adjacent to each other, pawns are not allowed on the first/last rank, there are at most 32 pieces, etc.), you can decrease this number further. The Chess Position Ranking project took this approach much further and was able to construct a set of size 8.7e45 that is guaranteed to contain all legal chess positions.

For your example of N=1e76, the probability that a random position is legal is ~5e-32, so any sample of a size that would fit in a computer would with very high probability contain 0 legal positions. Having a representation where N is sufficiently small is required for the random sample approach to work at all in practice.

I would approach it as follows (assuming I want to include positions with just 2 kings - no idea whether I should):

* Pick a random number between 2 and 32 for the number of pieces

* Place the white king on a random available square

For n from 2 to number of pieces

if n=2 pick the black king, otherwise select a random piece

Make a list of available squares and choose one at random for the selected piece

if the resulting position is illegal
--Illegal++
--Break out of the For loop and start again

end For loop

If overall position is reachable
--Legal++
else
--illegal++

Of course, there would be biases in this method that should probably be corrected (e.g. looking too much at small numbers of pieces and not enough at large numbers of pieces), but my intuition tells me that this method could get to a decent number of legal random positions.

[tromp]

* Pick a random number between 2 and 32 for the number of pieces

* Place the white king on a random available square

Of course, there would be biases in this method that should probably be corrected (e.g. looking too much at small numbers of pieces and not enough at large numbers of pieces), but my intuition tells me that this method could get to a decent number of legal random positions.

You'd have no clear idea just how large the biases are. For instance, what would you take to be the frequencies of positions with 16, 27,28, or 29 (out of 32) pieces?

Even for a random 2 piece position (just the 2 kings) the white king is not positioned randomly (e.g. it's more likely to be on a1 than on c3).
There are many more biases, such as in the number of promotions, in number of pawns, in specific pawn structures, which all compound in complex ways (such as pawn structure determining the number of possible promotions), causing you to accumulate a large error in your estimation. The worst part is that you don't even have a good way to determine how large your error is likely to be.

[towforce]

* Pick a random number between 2 and 32 for the number of pieces

* Place the white king on a random available square

Of course, there would be biases in this method that should probably be corrected (e.g. looking too much at small numbers of pieces and not enough at large numbers of pieces), but my intuition tells me that this method could get to a decent number of legal random positions.

You'd have no clear idea just how large the biases are. For instance, what would you take to be the frequencies of positions with 16, 27,28, or 29 (out of 32) pieces?

Even for a random 2 piece position (just the 2 kings) the white king is not positioned randomly (e.g. it's more likely to be on a1 than on c3).
There are many more biases, such as in the number of promotions, in number of pawns, in specific pawn structures, which all compound in complex ways (such as pawn structure determining the number of possible promotions), causing you to accumulate a large error in your estimation. The worst part is that you don't even have a good way to determine how large your error is likely to be.

I agree that the biases would be very difficult to satisfactorily resolve. I've noticed another problem as well: if, as Peter said, the proportion of random positions which are legal is about 5e-32, then my method would not even begin to generate a satisfactory sample size.

To save us ploughing through your code in GitHub, could you provide an outline of how your program works, please?