Author: KarinsDad
Date: 13:02:20 05/28/99
Go up one level in this thread
On May 27, 1999 at 18:02:10, blass uri wrote:
>
>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
Well done Uri!!!
But when we make it more accurate, it gets a lot closer to 100 bits.
Since bishops can only be on one color, you can figure out approximately how
many pawns AND bishop possibilities there are:
Each white square bishop can be on one of 32 squares (same for black square
bishops). Hence:
32 x 31 x 32 x 31 takes care of all bishops.
However, this limits (i.e. conflicts with) the pawns. So, the bishops get broken
up into:
8 squares where they do not affect the pawns, 24 squares where they do.
And there are 5 cases: 0 bishops can affect pawn placement (i.e. all 4 bishops
are somewhere on the back rank), 1 bishop can affect pawn placement, ..., all 4
bishops can affect pawn placements.
So:
0 bishops = 15^8 * 8 (white squared white bishop) * 7 (white squared black
bishop) * 8 (black squared white bishop) * 7 (black squared black bishop) =
8,037,225,000,000
1 bishop = 15^7*10 (10 = number of pawn pairs on a file if one bishop is on the
same file, instead of 15) * 8 (different files the bishop can be on) * 8 * 7 * 8
* 4 (different bishops) = 24,494,400,000,000
2 bishops (same color) = [ 15^7 * 3 (possible ways to place 2 same colored
bishops on a file not including back rank) * 6 (remaining pawn combinations on
that file) + 15^6*10*10 ] * 8 * 8 * 2 (different colors) = 539,460,000,000
2 bishops (different color) = [ 15^7 * 9 (possible ways to place 2 different
colored bishops on a file not including back rank) * 6 (remaining pawn
combinations on that file) + 15^6*10*10 ] * 8 * 7 * 4 (different color bishop
combinations) = 2,321,865,000,000
2 bishop total = 2,861,325,000,000
The reason these numbers drop is for each bishop that gets placed (beyond 1) is
that you drop one bishop from the back rank. Hence, you lose a multiple of 8 (or
7) squares. You also drop the number of pawn combinations remaining on the
file(s) with the bishops(s).
3 bishops ~= 300,000,000,000 (I did not bother to exactly calculate the 3 and 4
bishop possibilities since it changes the overall calculation by VERY little if
I am somewhat off, if someone else wishes to be more precise, be my guest)
4 bishops ~= 35,000,000,000
So, the pawn and bishop total is approximately:
3.57e13
Now, this can be multiplied by the other pieces to get:
3.57e13 pawns and bishops
44*43 kings
42*41 queens
40*39*38*37/4 knights
36*35*34*33/4 rooks
2 side to move
1.13e31 which is still slightly more than 100 bits (about 105 bits).
Note, however, that a LOT of illegal positions have not dropped out. The
question comes down to whether 1.03e31 of these positions are illegal and hence,
the number of legal positions can get down below 1e30. I think the answer to
this question is probably no, but it is close enough to be possible.
The calculations above did not take into account that at least some pawns must
be pushed in order to let most pieces out (knights being the exception). So,
this would decrease the overall legal set of moves by a small percentage, maybe
10% to 30% (I based this on the fact that all pieces with the exception of rooks
could get to the other side with very few pawn pushes and even rooks could make
it to practically anywhere on the board with a 2 square push of say a knight
pawn for each color). This is enough to get it down to about 103 bits.
The other main set of illegal positions is with the king of the side not to move
being in check. However, on average, I would estimate that with all of the
pieces on the board that there are probably about an average of maybe 12 legal
squares for each king, hence, maybe 8% of the positions are illegal due to kings
being on illegal squares. This would not even drop it to 103 bits. The average
would have to be about 6 legal king squares per position to drop it down to 100
bits.
So, when you combine these two factors of 30% pawn push requirements (this means
70% remain as legal) and 12 legal king squares per position (about 1 square in 5
or 20%), it would still take 101 bits to store ALL of the legal 32 piece
positions. However, either one or both of these two estimates could be off by
enough to get down to 100 bits (but probably not much lower). And, of course, my
estimates for the 3 and 4 bishop cases above could be off, or I could have some
other error in these calculations, for example, I am only estimating the number
of bits for each of these.
This does not take into account en-passant and castling which increases the
state possibilities for some percentage of the positions (probably about 1/4000,
not enough to adversely affect the calculations).
KarinsDad :)
PS. You'll note that Uri's calculation came out to be about 3.78e33 (or 112
bits). Due to the bishop problem, he estimated that 3/4s of the positions would
be illegal. It actually comes out to be about 99.7% (combined different due to
bishop error and bishop/pawn conflictions) since he used the equation 36*35/2
and 34*33/2 when bishops can only be on half of the squares, so he should have
used the approximates 18*17/2 and 18*17/2 (the second set of bishops do not
conflict with the first set, so they also average about 18 and 17 squares left
respectively). This alone multiplied the estimate by a factor of 15 (and made
the bishop estimate 93.3% too high, the other 6.4% appears to be due to the
bishop/pawn conflictions).
>
>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.