On the number of chess positions

[tromp]

Me and Peter Österlund (but mostly Peter and his program Texel) have completed analyzing all 1 million positions in the random 1 million sample and determined that with 56011 legal positions with average inverse multiplicity of ~0.98013, the most accurate estimate of the number of chess positions is (4.79 +- 0.04) * 10^44 (at 95% confidence level).

So approximately 4.8 x 10^44, with 2 digits of accuracy.

https://github.com/tromp/ChessPositionRanking

[Ajedrecista]

Hello John:

Me and Peter Österlund (but mostly Peter and his program Texel) have completed analyzing all 1 million positions in the random 1 million sample and determined that with 56011 legal positions with average inverse multiplicity of ~0.98013, the most accurate estimate of the number of chess positions is (4.79 +- 0.04) * 10^44 (at 95% confidence level).

So approximately 4.8 x 10^44, with 2 digits of accuracy.

https://github.com/tromp/ChessPositionRanking

Thank you for the update. Little changes in the percentage of legal positions and the average (inverse) multiplicity change things a lot, like the confidence interval of legal positions, where the former upper bound is less than the current lower bound. An extra digit of accuracy would cost around 100 times more positions to be analysed, which seems unfeasible nowadays. What a huge effort to 'only' reach two digits of accuracy! The payback is very low, but the order of magnitude shall be enough, so thank you very much again.

Regards from Spain.

Ajedrecista.

[Daniel Shawul]

Me and Peter Österlund (but mostly Peter and his program Texel) have completed analyzing all 1 million positions in the random 1 million sample and determined that with 56011 legal positions with average inverse multiplicity of ~0.98013, the most accurate estimate of the number of chess positions is (4.79 +- 0.04) * 10^44 (at 95% confidence level).

So approximately 4.8 x 10^44, with 2 digits of accuracy.

https://github.com/tromp/ChessPositionRanking

Nice work both of you!
Peter is very good at this kind of stuff -- it was fun to do perft estimation competition with him a while ago.
I hope you can tighten the error bound more with some more innovations.

[tromp]

the former upper bound is less than the current lower bound

Well, the currently stated interval for the 10k sample is
(5.38% +- 1.96 * sqrt(5.38% * 94.62% / 10000)) * N * 0.97847 = (4.59 +- 0.38) * 10^44
which properly contains the interval for the 1m sample of
(5.6% +- 1.96 * sqrt(5.6% * 94.4% / 10000)) * N * 0.98013 = (4.79 +- 0.04) * 10^44
since 4.79 + 0.04 = 4.84 < 4.97 = 4.59 + 0.38

I had previously divided by the average multiplicity, which as Peter pointed out to me, gives
a slightly wrong result. Now I correctly multiply by average inverse multiplicity.
Basically, each legal position in the sample with multiplicity m estimates the number of
legal positions as N/m (while each illegal position estimates it as 0). These are unbiased estimates
whose expectation equals the number of legal positions.
So we average these estimates over the entire sample to get an accurate estimate.

[tromp]

I hope you can tighten the error bound more with some more innovations.

I think 2 digits of accuracy is enough for my taste.
Analyzing a 100m sample for another digit of accuracy seems not quite worth the effort.

[petero2]

Nice work both of you!
Peter is very good at this kind of stuff -- it was fun to do perft estimation competition with him a while ago.

Thanks Daniel. Yes, those were fun times.

What a huge effort to 'only' reach two digits of accuracy! The payback is very low, but the order of magnitude shall be enough, so thank you very much again.

I think working on a problem I find interesting is a form of payback in itself, so I don't think the effort was too big compared to the outcome.

[petero2]

I hope you can tighten the error bound more with some more innovations.

I think 2 digits of accuracy is enough for my taste.
Analyzing a 100m sample for another digit of accuracy seems not quite worth the effort.

If we were to use the available software in the current state, here is what to expect, based on extrapolating what happened for the 1M sample:

Using the ChessPositionRanking software to create 100M positions would take a couple of hours.

Analyzing those 100M positions using Texel software would take around 100 days on my 24 core computer. The result would be a lot of positions classified as legal or illegal, but also around 6500 positions that the software failed to analyze. Those would have to be analyzed manually. Around 1200 of those would be illegal, so the manual analysis would have to come up with proofs that they indeed are illegal. The remaining would be legal, so the manual analysis would have to come up with proof games for those positions.

The 100 day computation time might be acceptable (and the work could also be distributed to more computers), but the manual analysis of ~6500 positions would be too tedious I think.

To make this feasible I think the software would have to be improved to both get better at finding proof games and at proving positions to be illegal. This might be quite complicated I suspect.

[JVMerlino]

To make this feasible I think the software would have to be improved to both get better at finding proof games and at proving positions to be illegal. This might be quite complicated I suspect.

Pardon my ignorance, but by "illegal" do you mean "illegal by the rules of chess" or "unreachable from the initial position"?

[petero2]

To make this feasible I think the software would have to be improved to both get better at finding proof games and at proving positions to be illegal. This might be quite complicated I suspect.

Pardon my ignorance, but by "illegal" do you mean "illegal by the rules of chess" or "unreachable from the initial position"?

I mean "unreachable from the initial position". Technically I am not sure there is a difference though. I assume that by "rules of chess" we mean the FIDE laws of chess and consider only standard chess, not chess 960:

https://www.fide.com/FIDE/handbook/LawsOfChess.pdf

In the document there is for example no explicit rule that forbids white from having pawns on a2, a3 and b2 at the same time. The fact that such a position can never appear is just a consequence of the rules saying what the starting position is and rules saying how pawns are allowed to move.

Similarly, there is for example no rule forbidding white from having an elephant on a3. It is just a consequence of the starting position and the absence of any rule that could cause an elephant piece to appear.

So, neither having white pawns on a2, a3 and b2 at the same time or having an elephant on a3 is explicitly "illegal by the rules of chess". The fact that such positions cannot appear in a game of chess is just an indirect consequence of the FIDE laws of chess.

[dangi12012]

Very cool work!