On the number of chess positions

I wrote the Haskell program at https://github.com/tromp/ChessPositionRanking/blob/main/src/CountChess.hs to compute an upper bound on the number of possible chess positions. Its output is

fixwr=0 fixbr=0 ep=0 4317116501858047620299900728599356147494556640
fixwr=0 fixbr=0 ep=1 31999595200733582973106880061728861929069928
fixwr=0 fixbr=1 ep=0 6922142764395483618137561107749568789790148
fixwr=0 fixbr=1 ep=1 54444384271688044810990508417111948991768
fixwr=0 fixbr=2 ep=0 136530769984693307040227830128737122354029
fixwr=0 fixbr=2 ep=1 1035365889143551932685537903363800096422
fixwr=1 fixbr=0 ep=0 6922142764395483618137561107749568789790148
fixwr=1 fixbr=0 ep=1 54308353407259673025385006313129004055128
fixwr=1 fixbr=1 ep=0 11745419798256512510493235052589222172668
fixwr=1 fixbr=1 ep=1 98172517157950055940864091510815802248
fixwr=1 fixbr=2 ep=0 235958281122206691085936171885340863152
fixwr=1 fixbr=2 ep=1 1903336650826558863672909067902430108
fixwr=2 fixbr=0 ep=0 136530769984693307040227830128737122354029
fixwr=2 fixbr=0 ep=1 1028637537652354045548219736317757984742
fixwr=2 fixbr=1 ep=0 235958281122206691085936171885340863152
fixwr=2 fixbr=1 ep=1 1895642836539897140574420164647093916
fixwr=2 fixbr=2 ep=0 4729971278292293446735355275667009679
fixwr=2 fixbr=2 ep=1 36635290891989131864827262732080222
total positions: 8726713169886222032347729969256422370854716254

The 3*3*2 = 18 different counts, all assuming white to move, distinguish the number of fixed white rooks (i.e. ways that white can castle), the number of fixed black rooks, and whether a white pawn can capture a black pawn en-passant.

The final number (call it N ~ 8.7E45) is twice the sum of these 18 numbers, to account for positions with black to move. This is a 2x improvement over the 1.77894E46 bound obtained by Shirish Chinchalkar in 1996.

More importantly, I was able to write a much more complex Haskell program that can efficiently map back and forth between positions and integers 0..N-1. This allows me to sample positions at random to determine the fraction that is legal. From a sample of size 100, I found 8% to be legal, which suggests a count of (very roughly) 0.08*N ~ 7E44 legal chess positions. To have some confidence in a correct first digit, a much larger sample is needed though, between 1000 and 10000 random positions. I've just completed generating sets of both sizes,

and am currently writing code to help analyze them.

I'll be happy to share the list of 1000 random FENs if people are interested.

Feedback is more than welcome.

-John

Good job, thank you for sharing.
This 8.7 E45 is the upper bound, do you have any idea about the lower bound?
Besides the illegal positions, there are also irrelevant positions, like 3 light square bishops vs. two rooks. Do you have any idea on the fraction of sensible positions?
How did you determine legality of your positions? There is a thread here about illegal positions and often a position posted as illegal is found to be legal and otherwise.
A sample size of 100 seems too small to establish the fraction of legal positions.

I have no provable lower bound, but the sampling technique can give very high confidence in lower bounds like 1E44. One can probably prove a lower bound around 1E40 by enumerating large classes of positions where Kings are in fixed places and shielded from checks, and remaining pieces are manouverable, but it would be laborious and not particularly interesting.

I don't think there's any sensible way to define "sensible position".

I determined legality manually. For instance:

B r . k . B K .
N . R B p . b R
. . . . q . . b
B . . B P . p .
. . p r n . . .
. R b r . N . Q
. n . . . . P Q
. . . . . B . .
wpx = 8-2-6 = 0 maxuwp = 3+3-6 = 0
bpx = 8-3-2 = 3 maxubp = 0+3-2 = 1
minopp = max 2-0 3-1 = 2
White Kg9 in check by qe6
Black kd8 not in check
Illegal because wProms=6 requires missing pawn files to come in 3 adjacent pairs (e.g. if 2nd oppose were on f instead of g file)

 Here are all the reasons for illegality I found:

53x Illegal due to both kings in check
11x Illegal due to impossible double check on king
10x Illegal due to adjacent kings
7x Illegal due to same colored bishops requiring extra promotion
(the above ~80% of illegalities should be automatically recognized, leaving roughly half of remaining positions (half)legal)
1x Illegal because wProms=6 requires missing pawn files to come in 3 adjacent pairs
1x Illegal due to Ba1 trapped by Pb2
1x Illegal due to no white pieces captured to double black c pawns
1x Illegal due to doubled h pawn requiring extra capture
1x Illegal due to 3 black pawns on and b files?!
1x Illegal due to w made no captures while black needs 3 piece captures to get her pawns around white original a,b,e pawns
1x Illegal due to black pawns on f,g,h files not supporting promotions by captures of pawns only

100 is enough to distinguish a fraction of 10% from a fraction of 90% with high confidence.

But not to distinguish 8% from 4% or from 12%.

Relevant < sensible < legal < possible
Example of an illegal position:

Example of a legal but non sensible position:

Example of a legal, sensible, but non relevant position:

I guess the real fraction of legal positions is far less than 8%. The more men on the board, the larger the fraction of illegal positions. Also the more men on the board the more possible positions.
Example of an illegal position:

How did you generate your random positions? Chess positions can be classified according to the number of men on the board. If your sample contains proportionally less 32 men positions, then you get a too high fraction of legal positions.
Just look at the initial position with all white pawns on the 2nd rank and all black pawns on the 7th rank. There are 8!8!/64 = 2e7 positions to shuffle the 16 non-pawns behind their pawns, only 1 of which is legal. That is far far less then 8%. That is why your sample size of 100 seems too low: it cannot contain representative numbers of the classes from 3 to 32 men.
All 2 and 3 men positions are relevant, sensible, legal. Some 4 men positions are irrelevant, not sensible or illegal. The vast majority of 32 men positions are irrelevant, not sensible, or illegal.

I suggested there is no sensible way to define "sensible position", and you seem to agree, by providing examples rather than a definition. The same goes for "relevant position". I challenge you to define these terms.

> I guess the real fraction of legal positions is far less than 8%.

I bet it's more than 4% (of the set of N positions counted by the provided Haskell program, which is the set I sample from uniformly).

> How did you generate your random positions?

By generating a random number in the range 0..N-1 and mapping it to the corresponding position.

> If your sample contains proportionally less 32 men positions

My sample of 100 contained no position with 32 men. In fact it had the following distribution of men counts: 1 with26 men, 22 with 27 men, 73 with 28 men, and 4 with 29 men.

> That is far far less then 8%

Obviously the legal fraction will be lower among positions where pieces are hemmed in. Such as the positions you describe. But these positions make up a tiny fraction of the total N.

> That is why your sample size of 100 seems too low: it cannot contain representative numbers of the classes from 3 to 32 men.

I only need my sample to be representative of *random* positions. If I sample 1 million positions uniformly at random from the N, and find 72682 to be legal, i.e. 7.2682%, then the estimate 0.072682 * N  ~ 6.34274e44 gives me > 95% confidence that the number of legal positions is within 0.1e44 of 6.3e44. I.e. to get 2 significant digits, a sample size of 1 million would suffice. And would almost certainly contain no position with less than 8 men.

In fact, I just went and calculated the number of positions with at most 24 men. It is only 821847357290469878793756744630037190296318, which as a fraction of N is only .000094176, i.e. less than 0.001 %

#5
I agree that is difficult to define when a position is relevant or sensible, so it is more appropriate to discuss legal positions only now.
Nevertheless here are tentative definitions for your consideration
A position is sensible if there are per side at most 3 promotions and at most 1 minor promotion and at most 1 quadruple pawn or 2 triple pawns or 3 double pawns.
A position is relevant if 9 * number of queens + 5 * number of rooks + 3 * number of bishops + 3 * number of knights + number of pawns does not differ more than 10 between white and black.

"My sample of 100 contained no position with 32 men. In fact it had the following distribution of men counts: 1x26 22x27 73x28 1x29"
1+22+72+1 = 96 so 4 seem missing, but that is no big deal
This distribution on a small sample of 100 seems to indicate that 72 + 22 = 94% of all possible positions of 3 to 32 men count either 28 or 27 men. Is that true? Can that be confirmed by a larger sample? It has been conjectured that there is a maximum of positions for a number of men < 32, but it is surprising if it were that spiky around 28-27. It would also imply that chess is most complex after 2 captures, when 28 men are reached.

Did you determine legality manually or by a program?
Besides the reasons you gave also other reasons are possible, like pawns h2, h3, g3, pawns a2 b2 c2 b3, pawns h4 h2 g2 f2, 8 pawns on ranks 2 and 3 and a rook in front of them, a white king on rank 8, but black pawns on ranks 7 and 6 with no access, king in check, but no legal last move... If you determined legality manually, then you might have some illegal positions with slipped through as legal.

> A position is sensible if there are per side at most 3 promotions and at most 1 minor promotion and at most 1 quadruple pawn or 2 triple pawns or 3 double pawns.

I could change my program to count positions with such limits on promotions and underpromotions, and I expect most will happen to satisfy the pawn restrictions as well, but they still won't look sensible due to the piece placements.

>1+22+72+1 = 96 so 4 seem missing

I fixed a typo, it should be 4 positions with 29 men. And I had 73, not 72.

> Did you determine legality manually or by a program?

You can find my manual analysis of the 100 positions at http://talkchess.com/forum3/viewtopic.php?f=7&t=77685

Let me know if you find any mistakes.

This position you list is legal, but not sensible

I advocate to label all positions with more than 2 queens, more than 2 rooks, more than 1 light square bishop, more than 1 dark square bishop, more than 3 knights as not sensible.

This position is illegal: doubled white pawn and 16 black men. Apart from that it is clearly not sensible

> I advocate to label all positions ... as not sensible.

You're free to do so, and even attempt to estimate the number of sensible positions. But you'll have to agree the definition is rather arbitrary, and will include many positions with a nonsensical piece placement. So I doubt it will be of much interest.

At the least the definition of legal is completely non-arbitrary, and so there is widespread interest in determining the number of legal positions. 

#10
Yes, the primary question is about the number of legal positions.
However, the upper bound of the number of legal positions is often used in discussions about solving chess, where in fact the number of relevant, sensible, and legal positions is needed.
It would also be good if we had a graph of logarithm of legal positions versus number of men, like the graph in the paper that proved checkers is a draw.
https://www.researchgate.net/publication/231216842_Checkers_Is_Solved 
A position is legal if and only if it can be expressed as a PGN starting from the initial position.
A position is illegal if but not only if
Kings are on adjacent squares
Both kings are in check
A king is in check, but there is no legal retrograde move that delivered the check
There is no missing black man for each white double pawn
There is a double white pawn and there are white pawns on all files within the isosceles triangle with the back row as base and the more advanced double pawn as top.
There is a promoted white piece, but no black pawn missing.
There is a promoted light square bishop, but no path to a light promotion square.
There is a king on the opposing back rank, but no entry path.
...
I will be happy to review any FEN where you are not sure if it is legal or not.
Semi-legal positions do not exist: a position is either legal or illegal.

Here you go,  counts by captures:

captures: 0 positions: 4414743002908203199541644837500000
captures: 1 positions: 912735289402442208796550731465464000000
captures: 2 positions: 2523665506471226536013730409647223583460000
captures: 3 positions: 498256845263855270818320571779073919475774720
captures: 4 positions: 6324483068227594053453117530949791912185532880
captures: 5 positions: 1726145421274176959199733647339062167161640320
captures: 6 positions: 162649677964723028114590870024481216875621152
captures: 7 positions: 11831731552406878902042862259462784080890864
captures: 8 positions: 773159479964250059384248807555303950507304
captures: 9 positions: 46045967923747942460406037996737428502064
captures: 10 positions: 2510208893658907146587320147097702283828
captures: 11 positions: 125656912928297899353461998966321571056
captures: 12 positions: 5788072370222087915468364995630045320
captures: 13 positions: 245572507350867177793057002405802112
captures: 14 positions: 9594590663174347475978399180772256
captures: 15 positions: 344706000987776814635482924174464
captures: 16 positions: 11358753155823902464481207072904
captures: 17 positions: 342071649303023620811720215416
captures: 18 positions: 9372344180647137623501629680
captures: 19 positions: 232353768921896478618792944
captures: 20 positions: 5178118210244937623803680
captures: 21 positions: 102914255143972865739008
captures: 22 positions: 1806562746158907902944
captures: 23 positions: 27673311493270249824
captures: 24 positions: 364256024687982492
captures: 25 positions: 4037164893744720
captures: 26 positions: 36641451949418
captures: 27 positions: 261516365480
captures: 28 positions: 1376431148
captures: 29 positions: 4750192
captures: 30 positions: 8064
Total: 8726713169886222032347729969256422370854716254

This confirms that 4 captures dominate. Note that with 2 white and 2 black pawns captured, all remaining pawns can promote.

While we're at it, we can do by number of promotions:

promotions: 0 positions: 19201527561695835455154058755564594798074
promotions: 1 positions: 382355871178268365234183218244670372695068
promotions: 2 positions: 3666683498600457464891752992187014354136188
promotions: 3 positions: 22267499667290257736558400874926183060238400
promotions: 4 positions: 95095065373967146179514528215894174339720228
promotions: 5 positions: 300571414300527313744528888013946849776424304
promotions: 6 positions: 721668497316402902485416452421325823057710432
promotions: 7 positions: 1329934072135692805837128923570048899100334756
promotions: 8 positions: 1874962044164806332602085236357597905810647344
promotions: 9 positions: 1980800128935921108339671872170042183548439128
promotions: 10 positions: 1492529839915108301878747832838229979840571492
promotions: 11 positions: 722080907452760073481816196266539169729817880
promotions: 12 positions: 175351843526979273665005184194531833618491680
promotions: 13 positions: 7338473695924787177946719990630518998574920
promotions: 14 positions: 45087168602668580254351850721788483191140
promotions: 15 positions: 55323182237139471340692375109727946960
promotions: 16 positions: 11716401834002951530424702440978260
Total: 8726713169886222032347729969256422370854716254

Compare to the 2014 paper"On the number of positions in chess without promotion" by Stefan Steinerberger

https://link.springer.com/article/10.1007/s00182-014-0453-7

who writes:

"We improve Shannon’s estimate and show that the number of positions where any number of chessmen may have been captured but no promotion has occured is bounded from above by 2×10^40."

He is counting diagrams though, ignoring side to move, castling, and en-passant status.

Our count of no promotion diagrams is only 8932998258872778996105271178879172718656, or ~ 0.9 * 2^40, so that's a big improvement there as well.

Well that was an easy read... 😉

#12 #13
Wow, great job, very interesting.
Do you need any help to determine legality of FEN?

I'm good for now. Once I've dealt with the easy cases, I will post the remaining ones here for others to help analyze.

#12
You wrote:
"captures: 24 positions: 364256024687982492
captures: 25 positions: 4037164893744720
captures: 26 positions: 36641451949418
captures: 27 positions: 261516365480
captures: 28 positions: 1376431148
captures: 29 positions: 4750192
captures: 30 positions: 8064"
This does not correspond to
http://kirill-kryukov.com/chess/nulp/results.html 

2 462 (*)
3 368,079 (*)
4 125,246,598 (*)
5 25,912,594,054 (*)
6 3,787,154,440,416 (*)
7 423,836,835,667,331 (*)
8 38,176,306,877,748,245 (*)

There's 2 reasons why their counts differ.

1) I include illegal positions such as those with the side not to move having their king in check, or even the two kings being adjacent.

2) As described in http://kirill-kryukov.com/chess/nulp/method.html they remove all possible symmetries, including board symmetries, color symmetries, and side-to-move symmetries. That makes sense for space-optimizing table bases, but not for my goal of counting legal positions.

So my 8064 = 64 * 63 * 2, where 2 is for side to move.

While their 462 puts the king to move in one of the 10 squares at a1,b2,c3,d4 or below, and the other king either on or below the a1-h8 diagonal (if the first king is on that diagonal), or anywhere (otherwise).

#18
I understand, but if you are counting legal positions then 2 bare kings i.e. 30 captures should be 4*60+24*58+36*55=3612 instead of your 8064. That is no big deal for the trivial case of 2 bare kings, but it means that all of your figures, including N are way too high. So your upper bound N can be lower if you would just eliminate the 2 adjacent kings, or 2 kings in check, of which 2 adjacent kings is a special case. Is not it possible to adapt your Haskell program to at least eliminate these obviously illegal positions in the first place?
If you would just add the illegality criterion 'Side to move can capture the opponent's king.'.

>  if you are counting legal positions

I am not. My goal is to accurately estimate the number of legal positions, which can only be done by sampling from a larger set of positions that can be efficiently (un)ranked, which is mapping numbers 0..N-1 to positions (unranking) and back (ranking).

Avoiding king adjacency HUGELY complicates a program for (un)ranking,  so it was not worth it.

> all of your figures, including N are way too high.

Avoiding king adjacency only reduces the sample space by about 10%, which is not that high. Both kings being in check is a much larger cause of illegality.

> Is not it possible to adapt your Haskell program to at least eliminate these obviously illegal positions in the first place?

It would make the program hugely more complicated, and worse, would make the (un)ranking vastly more time consuming.

And it would serve little purpose. I can easily remove these obviously illegal positions *after* sampling, and be left with positions where roughly 50% is legal and requires manual confirmation. So I should focus on making the (un)ranking program as feasible as possible. It's already quite complicated as it is.