On the number of chess positions

[tromp]

On revisiting my illegality proof sketches, I found 2 mistakes, where I was able to construct a proof game after all. So there are now 535 proof games and the estimate is (4.45 +- 0.37) x 10^44.

Having completed a full review of all illegality proof sketches, I found 3 more mistakes. That brings the final counts to 538 legal and 381 illegal, with an estimate of (4.48 +- 0.37) x 10^44.

There is still a chance that one of the 381 illegality proof sketches in
https://github.com/tromp/ChessPositionR ... %3Aillegal
is overlooking something, but I consider it small enough that I'll happily offer a $64 bounty for a proof game for any of the 381.

There are also bigger bounties of $128 and $256 for software bugs, see the README at https://github.com/tromp/ChessPositionRanking

I'll be writing a paper about my results in the months to come.

Happy bounty hunting!

[tromp]

Thanks to excellent work by Texel author Peter Österlund,
we now have a very preliminary and unverified analysis of the 1 million random position sample,
leading to the following paragraph being added to the Future Work section on https://github.com/tromp/ChessPositionRanking :

Recent advancements in the Texel chess engine by Peter Österlund bring us close to that goal.
Of the 94733 possibly legal positions in testRnd1mResearch,
it finds 38707 lack a proof kernel and should thus be illegal.
The other 56026 games have an average multiplicity of 58586/56026 ~ 1.0457.
Once we find the 56026 corresponding proof games, and verify these
along with the logic and implementation of Texel's proof kernel search,
then we would establish a more accurate estimated number of legal positions of
(5.6026% +- 1.96 * sqrt(5.6026% * 94.3974% / 1000000)) * N / 1.0457,
or (4.676 +- 0.037) * 10^44, again with 95% confidence level.

[Ajedrecista]

Hello John:

Good news that the project is still alive! OTOH, it could be discouraging that, given the great human and computational efforts, the width of the confidence interval narrows so slowly and the 95% confidence level interval only gives one certain number (the first '4'), while the second is still to be 'secured'. Standard deviation being proportional to (samples)^(-½) can raise impatience in the most patient people!

Congratulations to everybody involved in the project. Keep up the good work!

Regards from Spain.

Ajedrecista.

[tromp]

A bug was found in the legality checker src/Legality.hs that would on rare occasions classify a legal position as illegal.
This didn't affect any legal position in the main 10k sample, but did produce 4 new issues:

https://github.com/tromp/ChessPositionR ... issues/922
https://github.com/tromp/ChessPositionR ... issues/923
https://github.com/tromp/ChessPositionR ... issues/924
https://github.com/tromp/ChessPositionR ... issues/925

For the 1M sample, it produced 170 extra potentially legal positions, 10 of which had proof kernels.
Correcting for these, the added paragraph now reads:

Recent advancements in the Texel chess engine by Peter Österlund bring us close to that goal.
Of the 94903 possibly legal positions in testRnd1mResearch,
it finds 38866 lack a proof kernel and should thus be illegal.
For the other 56037 positions it finds a proof kernel. Except for one, which still has a proof game.
These 56037 have an average multiplicity of 58597/56037 ~ 1.0457.
Once we find all 56037 corresponding proof games, and verify these
along with the logic and implementation of Texel's proof kernel search,
then we would establish a more accurate estimated number of legal positions of
(5.6037% +- 1.96 * sqrt(5.6037% * 94.3963% / 1000000)) * N / 1.0457,
or (4.676 +- 0.037) * 10^44, again with 95% confidence level.

[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.