Author: KarinsDad
Date: 16:22:23 05/28/99
Go up one level in this thread
On May 28, 1999 at 17:16:24, blass uri wrote:
>
>On May 28, 1999 at 16:02:20, KarinsDad wrote:
>
>>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
>
>There are 48 squares for the bishop and not only 8 different files.
Uri,
There are 24 squares for an individual bishop (where it can conflict with the
pawns). You are correct, however, that there is are mistakes in my calculation
here:
1 bishop = 15^7*10 (10 = number of pawn pairs on a file if one bishop is on the
same file, instead of 15) * 3 (different squares the bishop can be on in that
file) * 8 (different files the bishop can be on) * 8 * 7 * 8 * 4 (different
bishops) = 73,483,200,000,000
The 2 bishops case also had an error which increases the total:
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 (files the first bishop can be on) * 7 (files the
second bishop can be on) ]] * 8 * 8 * 2 (different colors) = 8,558,460,000,000
2 bishops (different color) = [[ 15^7 * 3 (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 (files the first bishop can be
on) * 7 (files the second bishop can be on) ]] * 8 * 7 * 4 (different color
bishop combinations) = 14,977,305,000,000
2 bishop total = 23,535,765,000,000
This may put the 3 bishop total around 8,000,000,000,000 and the 4 bishop total
around 3,000,000,000,000.
So, the overall total would be around:
1.16e14 instead of 3.57e13 for the pawn/bishops.
This puts it at about 107 bits instead of 105 bits (sorry about that). Hence, it
would be a little more difficult to drop this to 100 bits (since I think the
most it can be dropped is about 6 bits for the illegal cases). This also more
closely explains my thinking that you should have used 18*17/2 for both of your
bishop cases since that would drop your 112 bits down to 108 bits, very close to
this calculation of 107 bits.
I broke the pawn/bishop confliction apart into the various possibilities and
realized that the total number of possibilities in the 3 and 4 bishop in the 48
squares cases DRASTICALLY decreases the overall number of possibilities there
are since the more bishops you have in the 48 squares, the fewer squares left
for the pawns and the fewer number of bishops on the back ranks. If you drop the
3 and 4 bit cases from my calculations above, it drops from 1.16e14 to 1.05e14,
so you can see how little I think these two cases add in (about 10%).
I could be totally incorrect on the 3 and 4 bishop cases, however, the 3 bishop
case alone would need 3 bishops on one file numbers; plus 2 bishops on one file
and the third bishop on another numbers (broken into the 2 bishop being the same
color and the 2 bishops being different colors); plus each bishop on a different
file numbers. This would be a large set of calculations for a relatively small
result (compared to the 2 bishop case). And it would be worse for the 4 bishop
case.
>
>We do not know the square of the bishop by the file of the bishop and the kind
>of the bishop out of 4 cases.
>
>It is not easy to do this calculation and I used the estimate that if we do not
>look first at the squares of the bishops then we discover that close to 1/4 of
>the cases are legal
>The probability of white bishop to be in white square is 1/2 and the
>probability of the second bishop to be in white square is 1/2 so if all the
>events are independent then the probabilty of white bishops to be in squares
>with different colour is 1/2.
>
>This assumption is not correct but it is close to be correct.
Not really. Only about 1/15th (not 1/16th) of the cases will be legal. The
reason is that your white square bishop calculations used 36*35/2 instead of
18*17/2 and your black square bishop calculations used 34*33/2 instead of
18*17/2. You cannot say that there is 36 squares remaining for a white square
bishop when it can only go on the white squares (approximately 36/2 = 18
squares). So, each of your numbers were about twice as large as it should have
been and with 4 numbers, your calculation was approximately 2^4 or 16 times too
large (actually closer to 15).
>
>It is possible to prove it practically by doing the experiment of generating
>random positions and find the number of cases when there is a bishop problem.
>I did not try to follow the rest of your calculation but it is not logical that
>the numbers drops when you have 2 bishops that can affect pawns placement.
Actually, it is totally logical. Maybe I will post the 3 bishop case later to
prove it. The main issue is that of overall cases, not one of individual cases
(this is a semi-difficult concept to explain). When you go from a case of having
0 bishops to 1 bishop in the 48 squares, you lose a factor of times 7 in the
back rank due to the fact that the bishop is no longer in the back rank.
However, you gain a factor of times 4 since there are possibilities of bishops
moving from the back rank to the 48 squares. You also gain a factor of about
times 24 since there are 24 possibilities of squares the bishop can move to and
you lose a factor of about 1.5 due to squares that pawns can no longer be on
(since the bishop is there). Overall, this increases the 0 bishops to 1 bishop
case by about a factor of 9 (4 * 24 / 7 / 1.5).
Sorry, I have to go pick up Karin. I will explain more later.
But quickly, from 2 to 3 would be a factor of about 3/8 (1/4 * 22 / 7.5 / 2)
using the same type of equation as above for the 0 to 1 case, I will explain in
detail later.
KarinsDad :)
>
>You can simply look at it like this:
>First put the pawns so no bishops can affect pawns placement.
>After it you have 16 squares that could affect pawns placement and
>48 squares that cannot affect pawns placement
>
>I expect that in most of the cases there will be at least 2 bishops out of 4 in
>the 48 squares.
>
>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.