Author: blass uri
Date: 15:02:10 05/27/99
Go up one level in this thread
On May 27, 1999 at 15:56:07, Dann Corbit wrote:
>On May 27, 1999 at 15:10:44, J. Wesley Cleveland wrote:
>[snip]
>>I did some calculations. You can use 12 bits to represent kings and castling,
>>one bit for side on move, one bit for e.p., (if there is an e.p., you get back
>>the four bits from the pawn representations), 15^8 for the pawns, and
>>46!/(32!*2^6) for the pieces (this is from the number of combinations of 14
>>peices in the 46 remaining squares divided by two for each of the pieces there
>>are two of). If I calculated correctly, this takes 114 bits. Many, if not most
>>of these positions are legal (the exceptions are kings in check, and pieces that
>>could not move to squares because the pawns have not moved and they are
>>blocked).
>Could you spell out your method formally and in detail?
>If it works, it proves that there are less than 2.1e34 possible chess positions.
>In fact, the exact number would be less than:
>20,769,187,434,139,310,514,121,985,316,880,384
>{around 20 decillion}
No it does not prove it and it only prove that there are less than
20,769,187,434,139,310,514,121,985,316,880,384 positions with 32 pieces in the
board.
My point is that it is impossible to represent even a subset of the legal
positions
(positions with exactly 32 pieces on the board) by 100 bits even if you ignore
the right to castle and e.p.
The idea is that there are 15 possibilities for pawns at every file.
For example for the a file you must choose 2 squares from the 6 squares
a2,a3,a4,a5,a6,a7 and there are 15 options to choose 2 out of 6
If you choose a2,a4 then it is clear that a2 is white pawn and a4 is black pawn
and not the opposite.
the number of possibilites for pawns at all the files is 15^8
The number of possibilities for kings after you choose the pawn is
(64-16)*(64-17)=48*47.
The number of possibilites for queens is 46*45
The number of possibilities for white rooks after it is 44*43/2
The number of possibilities for black rooks after it is 42*41/2
The number of possibilities for white knights after it is 40*39/2
The number of possibilities for black knights after it is 38*37/2
The number of possibilities for white bishops after it is 36*35/2
The number of possibilities for black bishops after it is 34*33/2
The number of possibilities for side to move is 2
The number of these positions is 15^8*48!/32!/2^5
If you have a calculator than you can calculate this number.
It is easy to see that near 3/4 of them are not legal because of bishops problem
(2 bishops with the same colour on squares with the same colour)
but I believe that more than 1/100 of them are legal and it is enough to prove
that it is impossible to represent the subset of positions with 32 pieces by 100
bits.
The statistical proof for this is to choose 1000 random positions by choosing
random numbers(8 random numbers between 1 and 15 to find the location of pawns
and the other random numbers define the location of other pieces).
The number of legal positions out of 1000 has binomical distribution when we do
not know p.
Now you can test H0:p<0.01 against H1 p>0.01 and if we find enough legal
positions then we can reject H0 with confidence of 99%
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.