Author: blass uri
Date: 10:09:56 07/11/99
I did a short program in C to calculate an upper bound to the number of legal
position in chess and I need exact representation of numbers like 64! to have an
exact bound.
This program run for some minutes and give the number 2.88456157249518055*10^47
as an upper bound to the number of legal positions in chess if I was not wrong
in copying the number.
I did not consider side to move, castling, en passant rule and the 50 move rule
so the real upper bound is bigger but on the other side it is possible to
improve the bound because there are some inequalities that I did not use.
This program calculates an upper bound for the number of positions for every
material configuration and add the numbers
some explanation about this program:
m[k]=k!=1*2*3...*k
x1 is the number of white pawns
x2 is the number of white knights
x3 is the nuber of white bidhops
x4 is the number of white rooks
x5 is the number of white queens
y1 is the the number of black pawns
y2 is the number of black knights
y3 is the nuber of black bidhops
y4 is the number of black rooks
y5 is the number of black queens.
m[48]/(m[x1]*m[y1]*m[48-x1-y1] is an upper bound for the number of pawns
configuration in the board(asuuming x1 white pawns and y1 black pawns).
I can improve this program
There are some inequalities that I did not use(for example if x2>2 then
y1+y2+y3+y4+y5<15)
Here is the program
#include <stdio.h>
#include <conio.h>
main()
{
clrscr();
char x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,i;
long double k,n=0;
long double m[65];
m[0]=1;
for (i=1; i<65; i++)
m[i]=m[i-1]*i;
for (x1=0; x1<9; x1++)
for (x2=0;x2<11-x1;x2++)
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];
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++)
n=n+(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-x2-x3-x4-x5-y2-y3-y4-y5]));
}
printf("%Lf\n",n);
}
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.