Computer Chess Club Archives


Search

Terms

Messages

Subject: It may be impossible to represent all board positions with 160 bits

Author: KarinsDad

Date: 13:56:22 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}


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.