Author: Andrew Dados
Date: 11:18:27 05/16/99
Go up one level in this thread
On May 16, 1999 at 13:51:31, KarinsDad wrote:
>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.
That is a nice one, KarinsDad!
However 23 bytes suffice:). I just noticed I can pack EP info + castle status +
king positions
into 12 bits which brings schema of mine down to 23 bytes total....Let me recap
the format:
-8 bits 50 move counter+side to move
-64 bits piece location bitmap
-up to 12 bits (with one exception) for:
1 bit *any* castle availability (none being worst case). if no castling for
either side then two 5 bit indexes for kings, otherwise 1 bit for castle[white]
followed by either 5 bit king[white] location or 2 bits castle status. This
followed by same structure for black...
1 bit EP possibility. If yes then 3 bit EP file in which case I don't have to
store max of 30 pieces, but 29 (I mark it mow as pawn and skip during unpacking
pieces)
-up to 100 bits for 30 pieces (I pack 3 piece/color info (5x2=10 states for 1
piece) into 10 bits (1000 states fits in 1024 :))
when there is EP I save 3 bits here by storing only up to 29 pieces (those 3
bits I need extra for EP file).
total just equals 184 bits == 23 bytes.
Andrew
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.