On the number of chess positions

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

[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"?

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.

Yeah, I should have been a bit clearer. By "illegal" I meant things that are much easier to determine, like "White to move and the Black King is in check", or "pawns on the 1st or 8th".

Thanks for the clarification.

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

The original 1 million sample was generated with version 1.1 of the Haskell package System.Random
Using the newer 1.2 revision instead causes `make testRnd1mFENs` to generate a completely different 1m sample. We have analyzed this new sample, yielding a slightly different estimate of (4.853 +- 0.039) * 10^44.

Combining the two estimates yields the sqrt(2) more accurate combined estimate of
(4.822 +- 0.028) * 10^44.

[Michel]

Very nice research!

[petero2]

Here is a document describing the algorithms used to determine if a position is legal or illegal:

https://github.com/peterosterlund2/texe ... oofgame.md