Fwd: RE: [Retros] Ultimate question
Christoph Fieberg
christoph at fieberg.com
Wed Feb 9 20:54:51 EST 2005
>>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)
More information about the Retros
mailing list