Author: Uri Blass
Date: 17:13:49 01/18/02
Go up one level in this thread
On January 18, 2002 at 17:13:29, Sune Fischer wrote:
>On January 18, 2002 at 16:43:16, Dann Corbit wrote:
>
>>On January 18, 2002 at 16:26:06, Sune Fischer wrote:
>>
>>>On January 18, 2002 at 15:12:07, Dann Corbit wrote:
>>>
>>>>Here is the numeric output of Uri's program:
>>>>3.70106301211527e+046
>>>>
>>>>Which would indicate (if I interpret it correctly) that there are _at most_
>>>>3.7e46 distinct positions in chess.
>>>
>>>That number is still on the large side,
>>>a simple calculation can bring it under 10^43.
>>>
>>>32 pieces on the board:
>>>(64*(64 - 4)*62!)/((62 - 30)!*(8!*2!*2!*2*2)^2)= 1.1*10^42
>
>I should add a few factors to make it larger:
>Side to move: 2
>En-passent: no idea, but less than 2 I guess
>Castle rights: can be ignored because the restrictions on king and rook will
>make this number magnitudes smaller.
>
>
>>>The factors are:
>>>white king 64 squares
>>>black king 64-4 squares (if white king in corner)
>>>rest of the pieces: 62!/(62-30)!
>>>white pawns can cycle: 8!
>>>white knights can cycle: 2!
>>>white rooks can cycle: 2!
>>>white's white squared bishop half the board 2
>>>white's black squared bishop half the board 2
>>>square the last few factors since those are identical for black
>>>
>>>Now realize that the white pawns can only move from rank 2 to 6, this is
>>>another huge factor that is not included in the above.
>>>
>>>Okay, now we shoud add the number of positions with 31 pieces and 30 and ...
>>>down to the two kings.
>>>
>>>Each of those elements in the sum will be orders of magnitudes smaller than the
>>>number above (right?), so they can be ignored.
>>
>>Smells like hand-waving. Remove one pawn. Orders of magnitude less? Maybe
>>there are more, because of less possible illegal positions. And we must add 30
>>different categories on the way down to the two kings.
>
>Hehe, this was the old:
>(64*(64 - 4)*62!)/((62 - 30)!*(8!*2!*2!*2*2)^2)= 1.1*10^42
>capture a piece and turn a pawn into a queen:
>(64*(64 - 4)*62!)/((62 - 29)!*7!*8!*2!(2!*2!*2*2)^2)= 1.33*10^41
>
>OK, so its about a factor 10 or maybe about same order of magnitude, they drop
>fairly quickly though.
There are many cases that you do not consider here(promotion to another piece or
capturing another piece,capture with 2 or 3 promotions)
The number of positions with 31 pieces is clearly bigger than the number of
positions with 32 pieces.
>
>>Here is the table of numbers Uri's program dumps as it goes (which is the list
>>by category):
>
>I would like to know his approach ;)
Note that I did not consider side to move en passant or castling in my
calculations so the real upper bound that I proved can be 2 times bigger
I simply calculated an upper bound for every pseudo possible material structure
and calculated the sum of the numbers.
Here is my modified program that Dann sent me(my original program used long
double and not exact numbers)
I did not give comments in my program but I can give in this post
some comments before the source code.
x1 is the number of white pawns(x1<=8)
x2 is the number of white knights(x1+x2<=10)
x3 is the number of white bishops (x1+x3<=10,x1+x2+x3<=12)
x4 is the number of white rooks
x5 is the number of white queens
y1,y2,y3,y4,y5 are the same for black
The ineaulaities that were used in the program for x1-x5 and y1-y5 are trivial
to find(I wrote <9 instead of <=8 but it change nothing because these are
integers)
The inequalities that were used when both x and y participate are less trivial
They are based on bounds on the number of promoted pieces.
In my program
i is a trivial lower bound for the number of promoted white pieces(for example
if there are 3 white knights then it adds 3-2 to i)
j is a trivial lower bound for the number of promoted black pieces
Note that it is not truth that every capture of white increases the number of
passed pawns of white by at most 2 because there may be pawns at a2 a3 a4 a5 a6
that suddenly becomes passed pawns after capturing a7.
I wanted to prove that 3 captures of white cannot generate more than 6 white
passed pawns that mean 6 promoted pieces.
It leaded me to define good pawns and bad pawns
Good pawns are passed pawns or double pawns or promoted pawns when bad pawns are
other pawns and in this case it is clear that every capture increse the number
of good pawns of the attacker by at most 2 and the number of good pawns is at
least the number of promoted pawns.
Every capture of a black piece generates at most 2 good pawns for white and at
most 1 good pawn for black.
Every capture of white piece has similiar influence in the opposite direction.
The number of promoted pieces is not more than the number of the good pawns
and it means that a lower bound for the number of promoted pieces is not bigger
than an upper bound of the number of the good pawns.
I remember that this idea was improved later by Retko V.tomic(I am not sure
about the exact name) when he considered captures of pawns as a special case but
I am not sure if it was exactly the idea and you need to look in the archives to
find if he improved it correctly(I had the impression that he did it correctly
but I am not sure of it now).
Here is my code
#include <iostream.h>
#include "qhead.h"
#include "qfloat.h"
int main (void)
{
char x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, j, i, a;
qfloat k, n = 0;
qfloat m[65], w[65];
m[0] = 1;
w[0] = 0;
for (i = 1; i < 65; i++)
{
w[i] = 0;
m[i] = m[i - 1] * (qfloat)(double) i;
}
n = 0;
for (x1 = 0; x1 < 9; x1++)
{
cout << "new x1:" << x1 << endl;
for (x2 = 0; x2 < 11 - x1; x2++)
{
cout << "new x2:" << x2 << endl;
for (x3 = 0; (x3 < 11 - x1 && x1 + x2 + x3 < 13); x3++)
for (x4 = 0; (x4 < 11 - x1 && x1 + x2 + x4 < 13 && x1 + x3 + x4 < 13 &&
x1 + x2 + x3 + x4 < 15); x4++)
for (x5 = 0; (x5 < 10 - x1 && x1 + x2 + x5 < 12 && x1 + x3 + x5 < 12
&& x1 + x4 + x5 < 12 && x1 + x2 + x3 + x5 < 14 && x1 + x2 + x4 + x5 < 14 && x1 +
x3 + x4 + x5 < 14 && x1 + x2 + x3 + x4 + x5 < 16); x5++)
{
k = m[x2] * m[x3] * m[x4] * m[x5];
i = 0;
if (x2 > 2)
i = i + x2 - 2;
if (x3 > 2)
i = i + x3 - 2;
if (x4 > 2)
i = i + x4 - 2;
if (x5 > 1)
i = i + x5 - 1;
for (y1 = 0; y1 < 9; y1++)
for (y2 = 0; y2 < 11 - y1; y2++)
for (y3 = 0; (y3 < 11 - y1 && y1 + y2 + y3 < 13); y3++)
for (y4 = 0; (y4 < 11 - y1 && y1 + y2 + y4 < 13 && y1 + y3 +
y4 < 13 && y1 + y2 + y3 + y4 < 15); y4++)
for (y5 = 0; (y5 < 10 - y1 && y1 + y2 + y5 < 12 && y1 + y3
+ y5 < 12 && y1 + y4 + y5 < 12 && y1 + y2 + y3 + y5 < 14 && y1 + y2 + y4 + y5 <
14 && y1 + y3 + y4 + y5 < 14 && y1 + y2 + y3 + y4 + y5 < 16); y5++)
{
j = 0;
if (y2 > 2)
j = j + y2 - 2;
if (y3 > 2)
j = j + y3 - 2;
if (y4 > 2)
j = j + y4 - 2;
if (y5 > 1)
j = j + y5 - 1;
a = x1 + x2 + x3 + x4 + x5 + y1 + y2 + y3 + y4 + y5;
if ((i <= 2 * (15 - y1 - y2 - y3 - y4 - y5) + (15 - x1
- x2 - x3 - x4 - x5)) && (j <= 2 * (15 - x1 - x2 - x3 - x4 - x5) + (15 - y1 - y2
- y3 - y4 - y5)))
w[a] = w[a] + (m[48] / (m[x1] * m[y1] * m[48 - x1
- y1])) * (m[64 - x1 - y1] / (k * m[y2] * m[y3] * m[y4] * m[y5] * m[62 - x1 - y1
- x2 - x3 - x4 - x5 - y2 - y3 - y4 - y5]));
}
}
}
}
k = 0;
for (i = 0; i < 31; i++)
{
cout << i << w[i] << endl;
k += w[i];
}
cout << k << endl;
return 0;
}
Uri
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.