On the number of chess positions

[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