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

[towforce]

Here's another idea: might be impractical, but it's a fun challenge to think about!

1. write some code to generate all random chess positions (it would, of course, be impossible to actually run it)

2. from this code, you'll be able to calculate the number of positions the code would generate if it were possible to run it

3. write a list of ways a position can be illegal

4. for each way a position can be illegal, work out the probability that it will apply to a random position

5. hence calculate the probability that a randomly selected random position is legal (hopefully, the answer is close to Peter's number: 5e-32)

6. The number of legal chess positions will be (step 2 result) * (step 5 result)

[tromp]

Here's another idea: might be impractical, but it's a fun challenge to think about!

1. and 2. are already done. The number is the aforementioned N = 8726713169886222032347729969256422370854716254

3. this list is practically impossible to write, as anyone who has a moderate amount of solving retrograde chess problems (such as going through any of Smullyan's books) will likely realize.It can take many pages of reasoning and seemingly arbitrarily complex case analysis to judge a position illegal.

4. the resulting probabilities will also be utterly impossible to determine.

5. no such calculation is possible since positions can be illegal for a multitude of reasons, and the corresponding events are not independent.

[tromp]

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

The most essential line in the source code is the ranking composition:

-- Chess Position Ranking
cpr :: Ranking URPosition
cpr = sideToMoveRanking `composeURI` (caseRanking `composeRI` wArmyStatRanking `composeURI` bArmyStatRanking `composeRI` guardRanking `composeRI` enPassantRanking `composeURI` epOppRanking `composeURI` sandwichRanking `composeRI` opposeRanking `composeURI` pawnRanking `composeURI` castleRanking `composeURI` wArmyRanking `composeURI` bArmyRanking `composeURI` pieceRanking) $ emptyURPosition

First, we pick the side to move, then we pick numbers of unmoved rooks and number of en-passant pawns, then we pick the white army statistics (#total #pawns #promotions #factorial_product), then we pick the black army statistics, then we check whether the promotions in the two armies are feasible, then we pick a possible en-passant location or not, then we pick whether the two en-passant files (if present) have an opposing pawn, then we pick the amount of pawn free squares that are sandwiched between opposing white and black pawns, then we pick the actual locations of opposing pawn pairs, then we pick the locations of all remaining pawns (anywhere except in between opposing pawn pairs), then we
pick locations of unmoved rooks, then we pick the composition of the white army (how many pieces of each type), then we pick the composition of the black army, and finally we pick all the piece placements.

[towforce]

The most essential line in the source code is the ranking composition:

-- Chess Position Ranking
cpr :: Ranking URPosition
cpr = sideToMoveRanking `composeURI` (caseRanking `composeRI` wArmyStatRanking `composeURI` bArmyStatRanking `composeRI` guardRanking `composeRI` enPassantRanking `composeURI` epOppRanking `composeURI` sandwichRanking `composeRI` opposeRanking `composeURI` pawnRanking `composeURI` castleRanking `composeURI` wArmyRanking `composeURI` bArmyRanking `composeURI` pieceRanking) $ emptyURPosition

First, we pick the side to move, then we pick numbers of unmoved rooks and number of en-passant pawns, then we pick the white army statistics (#total #pawns #promotions #factorial_product), then we pick the black army statistics, then we check whether the promotions in the two armies are feasible, then we pick a possible en-passant location or not, then we pick whether the two en-passant files (if present) have an opposing pawn, then we pick the amount of pawn free squares that are sandwiched between opposing white and black pawns, then we pick the actual locations of opposing pawn pairs, then we pick the locations of all remaining pawns (anywhere except in between opposing pawn pairs), then we
pick locations of unmoved rooks, then we pick locations of remaining white pieces, then we pick the composition of the white army (how many pieces of each type), then we pick the composition of the black army, and finally we pick all the piece placements.

Thank you: that is clear and helpful.

Does this result in a legal position, or does it result in a position which might be legal? If the second, then how does it cope with the fact that only an extremely tiny proportion of positions will ever be legal?

[tromp]

Does this result in a legal position, or does it result in a position which might be legal? If the second, then how does it cope with the fact that only an extremely tiny proportion of positions will ever be legal?

This a ranking of N positions that includes all legal ones and nearly 19x more illegal ones. The proportion of legal ones at over 5% is not at all "extremely tiny".

[towforce]

This a ranking of N positions that includes all legal ones and nearly 19x more illegal ones. The proportion of legal ones at over 5% is not at all "extremely tiny".

OK - I'm ready for my first guess at the whole process:

* You've worked out categories ("cats") of positions

* For each cat, you:

....1. Generate a sample of candidate positions

....2. Calculate the proportion of generated positions which are legal

....3. calculate how many positions code would generate within each cat if allowed to run until finished

....4. The number of legal positions in the cat is (step 2 result) * (step 3 result)

* To get the overall number of legal positions, you sum the outcome of step 4 above for all the cats

[petero2]

This a ranking of N positions that includes all legal ones and nearly 19x more illegal ones. The proportion of legal ones at over 5% is not at all "extremely tiny".

OK - I'm ready for my first guess at the whole process:

There is no need to guess since the actual process is described in the first link in the first post of this thread. Here is the link again: https://github.com/tromp/ChessPositionRanking. In particular the section called "Estimating the number L of legal positions" explains the process. Your guess is roughly correct, except that there is only one "category".

Another description of the same process is available here: https://github.com/peterosterlund2/texe ... oofgame.md. This document also describes the algorithms used to decide whether a random chess position is legal or not.

[Ajedrecista]

Hello John:

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

While true, I see that CPW links to On the number of chess positions thread that leaded to the last estimate at Postings section, at the bottom of the page. It would be nice to update the estimate at [n]Number of Positions[/b] section of CPW, though, because the old estimate is circa ×16 times your latest research.

Regards from Spain.

Ajedrecista.

[abulmo2]

The sample positions on github with multiple rooks and knights look quite unlikely to happen in real games. An interesting number would be the number of positions not only legal but also plausible, although it might be quite subjective.

[tromp]

The sample positions on github with multiple rooks and knights look quite unlikely to happen in real games. An interesting number would be the number of positions not only legal but also plausible, although it might be quite subjective.

I strongly suspect that

1. any definition of "plausible" will be quite arbitrary, and

2. will exclude some positions that have occurred in real games, and

3. will include many positions that still look like they would never occur in real games.

And for that reason I would find such numbers not very interesting.

Out of curiosity, how would you define "plausible" ?