Fwd: RE: [Retros] Ultimate question

[Christoph Fieberg]

>>You could extend the question to the ultimate question:

>>

>>         Which of the maximum 30,3*10^45 chess positions are (S)PGs?'

>

>Why not to make tree of all published SPG's in NET? And then manually add

>correct SPG's in there? If someone have good program, computer-adds of course

>possible.

>

>>For the figure which I calculated as lowest maximum number of distinct 

>>chess positions see my article in the magazine "Computer Schach & 

>>Spiele", issue 2/02.

>

>Could you explain/paste your method here?


First I have to correct the given number to 60,6 (instead of 30,3) * 10^45 
(this was found out after appearance of my article).

To calculate the number in a first step I determined all legal possibilites 
how the pieces are distributed.
For 2 pieces (wK, bK) there is only 1 possibility.
For 3 pieces I count 5 possibilites: 2 Kings plus either Queen or Rook or 
Bishop or Knight or Pawn
(No double count of possibilities with completely changed colours.)

The figures for n=2 to n=6 were well known as they are basic for the 
endgame databases. However the determination of figures for all n was new.

The figures for n-pieces are:
n
2        1
3        5
4        30
5        110
6        365
7        1.001
8        2.520
9        5.720
10      12.190
11      24.309
12      46.233
13      83.817
14      146.094
15      244.350
16      393.114
17      606.777
18      899.592
19      1.279.689
20      1.749.075
21      2.294.793
22      2.889.021
23      3.477.150
24      3.980.871
25      4.287.069
26      4.224.901
27      3.532.712
28      2.271.125
29      405.699
30      26.905
31      485
32      1

Number of pawns and maximum number of promoted pieces have to be taken into 
consideration.
For example the maximum of 16 promoted pieces can only be reached for sets 
of 18 to 24 pieces.
The total number of different set of pieces is 32.885.724.

As second step I determined a formula which allows to calculate the number 
of possible combinations for each of the 32.885.724 sets. There are 1.806 
possibilites to place the two Kings on the empty board. Then on the 
remaining 62 squares player A has a certain number of combinations for his 
pieces. For pawns there is a general limitation of 48 squares which has to 
be taken into consideration. For the remaining squares (depending on how 
many pieces player A has) a certain number of combinations exists for 
player B to place its pieces. The formula is:
number of positions = 1.806 * (48! / (Pawns A! * (48 - Pawns A)!)) *((62 - 
Pawns A)!) / (Knights A! * Bishops A! * Rooks A! * Queens A! * (62 - Pieces 
A)!)) * ((48 - Pawns A)!) / (Pawns B! * (48 - Pawns A - Pawns B)!) * ((62 - 
Pieces A - Pieces B)! / (Knights B! * Bishops B! * Rooks B! * Queens B! * 
(62 - Pieces A - Pieces B)!))

For example the calculation of the number of positions for the following 
set (n=10):
2 Knights + 3 Pawns (Player A) versus 1 Rook + 4 Pawns (Player B)
This is 1.806 * 29.593.456 (A) * 7.896.735 (B) = 422.047.173.657.684.000 
positions (as upper bound)

I wrote a short basic program to calculate the number of positions for all 
32.885.724 sets.
The sum of all positions of all sets is 60,6*10^45 which is the lowest 
upper bound for the total number of chess positions.
Note that this is a diagram view. Turn to move, en-passant and castling 
rights are not considered.

Of course this number still contains illegal positions (eg white pawns on 
a2, a3, b2, b3). A detailed analysis of the possible pawn structures could 
help to louwer the upper bound.

It would be worth to look at set of pieces > 22 as they contain the highest 
number of positions.
n=29 has with 38*10^45 the most positions in total.

Best regards,
Christoph


Note to Yefim:
As short way to find a low upper bound I would calculate:
number of positions = sum of 64! (32 + i)! for all i from 0 to 30. The 
result is < 10^54 (without turn to move, en-passant and castling)