Author: KarinsDad
Date: 10:51:31 05/16/99
I noticed that Andrew had put together another 24 byte schema while I was writing this up, but I haven't yet checked it out. I'll go do that now. This one is somewhat lengthy. Several of the earlier schemas proposed could store some variant subset of positions (those that could be found in normal play) in 22 or 23 bytes, but potential information was possibly lost (for bizarre positions normally not found in play). 25 bytes was the previous low for the schemas proposed on this forum (in the last few days) that handled all legal positions. However, here is a schema for storing all legal positions in 24 bytes (which also fits within the magic 24 bytes for a computer). The header contains the special information as follows: 1 bit for side to move 1 bit for en-passant possible 1 bit for castling possible 2 bits for move by repetition 7 bits for 50 move rule The total so far is 12 bits. The position can be broken up into the following 2 subsets (labeled A and B): A Squares on row 1 and 8 B Squares on row 2 through 7 So, a 2 byte structure for rows 1 and 8 and a 6 byte structure for rows 2 through 7 (is is probably preferable to separate these out into 2 structures as opposed to having one 8 byte bitboard, but either can be done). The total so far is 76 bits. Now comes the tricky part. An earlier representation used 4 bits per piece to represent the 12 possible pieces. This representation uses approximately 3.6 bits per piece. This allows us to save .4 bits per piece * 32 pieces ~ 13 over the 25 byte structure. Subset A has 10 possibilities of pieces (black and white pawns cannot exist there). Since there are up to 16 maximum pieces that could be in this subset (16 pieces in 16 squares), the minimum number of bits that could represent 16 pieces is 54 bits. Subset B has 12 possibilities of pieces (black and white pawns included). Since there are up to 32 pieces that could be in this subset (32 pieces in 48 squares), the minimum number of bits that could represent 32 pieces is 115 bits. However, whenever all of the 16 pieces are on row 1 and 8 and all 16 pawns are on rows 2 through 7 (starting position and early opening positions), there are only 16 pieces (i.e. pawns) on rows 2 through 7. The minimum number of bits that could represent 16 pieces on rows 2 through 7 is 58 bits. So, the starting position can be represented with 54 bits for rows 1 and 8 and 58 bits for rows 2 through 7 for a total of 112 bits. So, with 32 pieces on the board, the smallest representation of the pieces in this schema is 112 bits and the largest is 115 bits for a total of 191 bits (76 plus 115) or 24 bytes. In this schema, every time a piece is removed, either 3 or 4 bits subtract out of the structure, so it can be a variable sized structure if desired. The smallest representation would be the 2 kings at 76 + 8 (or 7) = 84 bits or 11 bytes. Ok, here is how I get to 115 bits for 32 pieces. There are 10 different pieces on the board for subset A (i.e. rows 1 and 8, pawns do not exists on rows 1 or 8). If you have no pieces in subset A (i.e. there are no pieces in row 1 or 8), then the all 16 bits in the bitboard will be 0 and you are done. If you have 1 piece in subset A, then there are 10 possibilities for that piece or 4 bits. If you have 2 pieces in subset A, then there are 110 possibilities for that piece or 7 bits (note: not 8 bits, it only increased by 3 bits, not 4). Since we think in decimal, this is easy to understand. 1,110 possibilities for 3 pieces or 11 bits. 11,110 possibilities for 4 pieces or 14 bits. down to: 11,111,111,111,111,110 possibilities for 16 pieces or 54 bits. At a 4 bit per piece representation, 16 pieces would require 64 bits. So, as you add pieces to rows 1 and 8, you either increase the number of bits need by 3 or 4, the average being less than 3.4. For subset B, the same applies, however, there are 12 possible pieces on from 0 to 32 squares. So, this works out to 3.73^34 if you have 32 pieces in the 48 squares or 115 bits. The calculations are the same: 1 pieces = 12 possibilities = 4 bits 2 pieces = 12 * 12 + 12 possibilities = 156 = 8 bits 3 pieces = 12 * 156 + 12 possibilities = 1884 = 11 bits (a bit is saved here) etc. The total so far is 191 bits (or 24- bytes). Note: As you move pieces from subset A to subset B, occasionally, you will change the number of bits from 112 to 113, back down to 112, back to 113, to 114, and eventually to 115 when all 32 pieces are subset B. There are cases where you will need 116 bits (e.g. 1 piece in subset A = 4 bits, 31 pieces in subset B = 112 bits). However, we have one bit left over in our structure to handle this. So the total maximum representation is 192 bits or 24 bytes (cool how this worked out). So, now we only have to consider en-passant and castling. Every time you have en-passant, you must add in 4 bits to represent the direction of the en-passant. However, you can subtract 6 bits from the data (and turn off 2 bits in the bitboard) since you know where at least 2 of the EP pawns are locationed (there could be 3, e.g. black pawn on e4 and g4 and white pushes f4, but you ignore the other one). Castling is similar. In the header, the following shows up: 0 indicates no castling. 1wxyz where w allows castle white kingside, x allows castle white queenside, y allows caste black kingside, and z allows castle black queenside. Once a castle is allowed, you can remove the appropriate king(s) and rook(s) from the square structure (and the 2 bits from the bitboard). So, you gain 4 bits, but lose from 6 to maybe 13 bits (depending on everything else) since the pieces are removed from the square structure. Voila! Thanks to Eugene and Andrew for getting me to think in these directions. KarinsDad : ) PS. I wrote a VB program to prove that 116 bits is the maximum number for subsets A and B.
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.