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

Discussion of chess software programming and technical issues.

Moderator: Ras

User avatar
towforce
Posts: 12157
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

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

Post by towforce »

abulmo2 wrote: Tue Jan 14, 2025 11:51 amAn interesting number would be the number of positions not only legal but also plausible, although it might be quite subjective.

This is just "thinking out loud", and only a bare outline of a solution, but...

* Definition: a position that appears in a chess database is "plausible"

* the larger the database, the more positions will be repeated

* use statistics, curve fitting, maths and common sense to build the following function f:

Probability of a position being repeated = f ( move number, number of positions at that move number in the database )

* rearrange expressions from the coupon collector's problem (link) to have a guess at how many "plausible" positions there are (so instead of asking "how many cereal boxes must I buy to get all 10 plastic toys?", you're asking "I've bought 20 cereal boxes, I've got 8 different toys, how many toys are there in total?")

* decide how many moves you're going to go to (100 might be sensible: there probably aren't enough "plausible" games beyond that to make a significant difference)

* sum the number of plausible games from move number 1 to 100
Want to attract exceptional people? Be exceptional.
abulmo2
Posts: 446
Joined: Fri Dec 16, 2016 11:04 am
Location: France
Full name: Richard Delorme

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

Post by abulmo2 »

tromp wrote: Tue Jan 14, 2025 3:01 pm
abulmo2 wrote: Tue Jan 14, 2025 11:51 am 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" ?
I agree that the definition of plausible is a subjective and arbitrary point of view. I do not deny either the interest of the number you get, it is interesting and a great achievement. You did a good job.
Nevertheless, the problem is to have multiple underpromotions (to rooks, bishops, and knights) by both sides. I know there are a few games where the human player trolls his opponent by underpromoting many pieces, for example here: https://www.youtube.com/watch?v=HbIhabDSBuk; but this multiple underpromotion is made by only one side. I guess having some limits on the number of promoted pieces on the board can be a first step towards plausible positions. Another problem, is having a position obtained with a legal path that go through several mates in 1 (or 2, 3, ...) or through several obvious piece captures.
Eliminating such positions could be great to have an idea of the space of the chess game in order to solve it.
Richard Delorme
User avatar
towforce
Posts: 12157
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

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

Post by towforce »

abulmo2 wrote: Wed Jan 15, 2025 10:45 amEliminating such positions could be great to have an idea of the space of the chess game in order to solve it.

The evidence that chess is drawn is overwhelming. Just suppose for a moment that it's a win for white, though: the fact that we haven't yet found the win would imply that one or more of the moves needed to get the win are not obvious. The fact that these moves aren't obvious would imply that they look like bad moves. So if we eliminate positions resulting from bad moves, we might eliminate the space in which the solution lies.
Want to attract exceptional people? Be exceptional.
syzygy
Posts: 5664
Joined: Tue Feb 28, 2012 11:56 pm

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

Post by syzygy »

abulmo2 wrote: Wed Jan 15, 2025 10:45 amEliminating such positions could be great to have an idea of the space of the chess game in order to solve it.
To determine the value of a game tree of depth d with uniform branching factor b, you basically need to look at at least 2 * b^(d/2) nodes. This minimum bound can be achieved by perfect move ordering. The total size of the game tree would be N = b^d, so 2 * b^(d/2) = 2 * sqrt(N).

So perhaps a very rought estimate for the size of a minimal proof tree would be 2 * sqrt(4.8 * 10^44) = 4.4 * 10^22.
Since chess is probably a draw, you would need a proof tree that shows that white is not losing and a proof tree that shows that black is not losing. But they could be solved separately and in parallel.

Howewver:
- The full game tree of chess does not have a uniform branching factor, which (I think) reduces the size of the minimal tree.
- To keep the size of the full game tree at 4.8 * 10^44, you need to deal with transpositions. I fear this is nearly impossible to get right (graph history interaction).
- We cannot hope to always guess the best move right.
Henk
Posts: 7238
Joined: Mon May 27, 2013 10:31 am

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

Post by Henk »

If you can find all legal check mate positions. Then for each legal check mate position find out if it can be reached from the start position with good play.
Maybe this is the way to find out whether chess is a draw.

O wait too many check mate positions.
Uri Blass
Posts: 10693
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

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

Post by Uri Blass »

Henk wrote: Sat Jan 18, 2025 10:16 pm If you can find all legal check mate positions. Then for each legal check mate position find out if it can be reached from the start position with good play.
Maybe this is the way to find out whether chess is a draw.

O wait too many check mate positions.
First question is what is the percentage of checkmate out of the random legal positions.

We can use it to get an estimate for the number of checkmates.
We can do the same for positions when the side to move has mate in 1 or positions when the side to move cannot prevent mate in the next move and continue in this way.
tromp
Posts: 44
Joined: Sun May 02, 2021 10:23 pm
Full name: John Tromp

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

Post by tromp »

Uri Blass wrote: Sun Jan 19, 2025 10:16 pm We can use it to get an estimate for the number of checkmates.
As mentioned in the project README, all the proof games for 2 million random positions appear in two files. which we can grep for checkmate as

Code: Select all

$ grep -c "#"  Texel.out.94903 Texel.out.95544
Texel.out.94903:2152
Texel.out.95544:2146
which represents a fraction of (2152+2146)/(94903+95544) = 2.2568 % of legal games.
jefk
Posts: 881
Joined: Sun Jul 25, 2010 10:07 pm
Location: the Netherlands
Full name: Jef Kaan

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

Post by jefk »

syzygy wrote
Since chess is probably a draw,
well i know you are a mathematician, but even then the word 'probably' imo isn't correct.
It's almost certain (*) chess is a draw starting from the initial position and assuming 'best play'
(in fact it's sufficient when Black stays within the drawing margin). And it's most likely (**) that
Black wins after the erroneous move 1.g4.
you would need a proof tree that shows that white is not losing and a proof tree that
shows that black is not losing. But they could be solved separately and in parallel.
that would be some sort of brute force method, whereby i (still contend) that
there are easier ways (or reasoning methods) to determine it's a draw (ultra
weak solution). For a rigid 'weak solution' the current Chinese database plus
the latest SF running on a fast comp with approx 1 min calc time/move would
imo be sufficient, but not a 'rigid mathematical 'proof' (yet), i admit. But it might
become so in a few years i predict with additional reasoning (which i leave to others,
eg. within the circles of academia, similar as Schaeffer reasoned for checkers)

Meanwhile bruteforce numbercrunching projects could be done ofcourse (although i then would
first suggest intnatnl draughts as first goal); and also then you also need a only (very) small subset
of all possible moves, namely those which are not obviously losing or winning (eg. +/- 3.0 pawn
cutoff). Checkers was also not (weakly) solved with a bruteforce method, but with selective
methods; believe it or not. Similar (next step) with draughts (most likely a draw, btw)

(*) for me based on my knowledge it's 100 pct certain (but it's apparently hard
to convey such (eg. ches opening) knowledge to others, well i don't care.
(**) for me almost certain
petero2
Posts: 712
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

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

Post by petero2 »

tromp wrote: Mon Jan 20, 2025 10:43 am
Uri Blass wrote: Sun Jan 19, 2025 10:16 pm We can use it to get an estimate for the number of checkmates.
As mentioned in the project README, all the proof games for 2 million random positions appear in two files. which we can grep for checkmate as

Code: Select all

$ grep -c "#"  Texel.out.94903 Texel.out.95544
Texel.out.94903:2152
Texel.out.95544:2146
which represents a fraction of (2152+2146)/(94903+95544) = 2.2568 % of legal games.
Those files also contain illegal positions, so we also need to count the number of legal positions in those files:

Code: Select all

$ grep -c " legal: "  Texel.out.94903 Texel.out.95544
Texel.out.94903:56011
Texel.out.95544:56743
So the fraction of checkmate positions is (2152+2146)/(56011+56743) = 3.81%. This means there are around 4.82e44 * 3.81e-2 = 1.84e43 legal checkmate positions.

Edit: Actually that calculation is also slightly wrong, because it does not take the multiplicity into account.
Uri Blass
Posts: 10693
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

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

Post by Uri Blass »

Maybe somebody can analyze the random positions to find how many of them are forced mates and in how many moves.

I guess only in a small part of the positions engines cannot prove forced mate for one of the players.