Author: J. Wesley Cleveland
Date: 12:10:44 05/27/99
Go up one level in this thread
On May 21, 1999 at 20:49:02, blass uri wrote: >I think that even representing positions when >there are 32 pieces on the board is impossible by 100 bits. > >we have 15^8 options for the pawns. >15 options in every file(choosing the pawns in a file is chossing 2 squares out >of 6). > >31 bits are not enough to represent 15^8. > >17 bits are not enough to represent the bishops on the board(after the choice of >the squares for the pawns) >(in the worst case we have 32*31*16*15 options to choose squares for the bishops >if the squares for the pawns were with the same colour and it is more than 2^17) > >10 bits are not enough to represent the kings on the board. >10 bits are not enough to represent the queens on the board. >9 bits are not enough to represent the white rooks on the board. >9 bits are not enough to represent the black rooks on the board. >9 bits are not enough to represent the white knights on the board. >9 bits are not enough to represent the black knights on the board. > >31+17+10+10+9+9+9+9=104 bits > >I remember that I checked random positions with 32 pieces(generated by a >computer program) some years ago and I found that most of them are not legal but >a small part of them(more than 1/10 of the cases that I checked) are legal and I >could generate a game that prove that they are legal. > >We probably need more than 100 bits only to represent positions with all the >pieces on the board and I believe that these is only a small part of the legal >chess positions. > >Uri 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).
This page took 0.01 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.