Author: J. Wesley Cleveland
Date: 10:49:57 05/28/99
Go up one level in this thread
Sorry, I failed to make clear that my calculations were for all the pieces on
the board, thus no promotions. I was trying to set a lower bound for the number
of possible positions.
On May 27, 1999 at 16:56:22, KarinsDad 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}
>
>
>Sorry Dann, but his calculations prove nothing.
>
>They fail to take into account pawn promotions and makes major assumptions on
>which pieces are still on the board (i.e. the comment "divided by two for each
>of the pieces there are two of").
>
>I have worked on this problem for the last 2 weeks and have come up with some
>detailed and sophisticated algorithms that handle a vast majority of the pawn
>promotion cases. However, there are still a small handful of multiple promotion
>cases which force the number of bits into the ballpark of 161 to 166 or so (i.e.
>21 bytes).
>
>I am starting to come to the conclusions that:
>
>1) It may be impossible to get down as low as 160 bits for all cases.
>
>2) Due to the "tricks" being used to decrease the number of bits, the actual
>number of legal positions may be greater than 2^x where x = minimum number of
>bits it can be fit into. For example, if I had a 4x4 chess board and only one
>piece to place on it, it is obvious that there would be 16 possibilities or 4
>bits required to represent it normally (assuming the piece had to be on the
>board). If I could then use some compression trick to drop it down to 3 bits, it
>would not mean that the number of possibilities dropped from 16 to 8, it would
>just mean that I was clever.
>
>KarinsDad :)
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.