Author: KarinsDad
Date: 23:49:05 05/14/99
Go up one level in this thread
On May 15, 1999 at 01:46:12, KarinsDad wrote: [snip] > >The ideas that Eugene and I kicked around would result in a worse case of: > >1 bit side to move >1 bit ep not available (eps are smaller) >2 bits castling not available either side (castling available is smaller) >12 bits kings (6 per) >32 bits blanks (1 per) >48 bits pawns (3 per) >20 bits knights (5 per) >20 bits rooks (5 per) >20 bits bishops (5 per) >10 bits queens (5 per) > >The worse case result (shown in the chart above) is 166 bits (2 bits lower than >what Dann mentions that Robert states) or 21 bytes (maybe the reason Robert >stated 168 since it is 21 bytes). I did not carefully read Dann's message and forgot about state information such as the 50 move rule and how many times this position was found previously (for draw by repetition). Adding in these factors can add some bits. Straight up, 7 bits for the 50 move rule (0 to 100 moves) and 2 bits for number of times found previously (0 to 3). This adds 9 bits or 175 bits or 22 bytes. Also, I was thinking of various compression schemes (specifically graphics ones), but none of them appear to work well for such a small amount of data. One thing that was mentioned in Dann's post was whether some context information is in the position. I do not recall seeing a FEN position with 50 move rule or draw by rep rule. I believe that they default to 0 in both cases (I am not sure of this, if anyone knows, please let me know). So, I guess you could ignore the 50 move rule and get to 168 bits with draw by rep included or 21 bytes (if you use the 22 byte scheme, 50 move rule is handled, if you use the 21 byte scheme, 50 move rule is not handled). It just depends on what your need is (for an opening book, the 50 move rule would not be needed, but draw by rep might). KarinsDad :) PS. Dann, I could not find that site that you mentioned. I would be real interested in how it could be compressed to 143 bits (or the even more amazing claim of less than 100 bits). PSS. Here are another set of schemes (food for thought): 1 bit side to move 1 bit ep not available (eps are smaller) 2 bits castling not available either side (castling available is smaller) 12 bits kings (6 per) 64 bits pieces (1 per) (i.e. a bitboard of all pawns and pieces vs. blanks) 32 bits pawns (2 per) 16 bits knights (4 per) 16 bits rooks (4 per) 16 bits bishops (4 per) 8 bits queens (4 per) This comes out to 168 bits (2 bits more) or 177 with draw by rep and 50 move. OR putting the king into the square portion of the structure. 1 bit side to move 1 bit ep not available (eps are smaller) 2 bits castling not available either side (castling available is smaller) 64 bits pieces (1 per) (i.e. a bitboard of all pawns and pieces vs. blanks) 32 bits pawns (2 per) 16 bits knights (4 per) 16 bits rooks (4 per) 16 bits bishops (4 per) 10 bits queens (5 per) 10 bits kings (5 per) Also 168 bits. And finally, a fun one. 1 bit side to move 1 bit ep not available (eps are smaller) 2 bits castling not available either side (castling available is smaller) 12 bits kings (6 per) 48 bits pawns (6 rows * 1 byte per row) 15 bits pawn colors (1 per) last pawn color is known if there are 16 pawns 32 bits blanks (1 per) 16 bits knights (4 per) 16 bits rooks (4 per) 16 bits bishops (4 per) 8 bits queens (4 per) 167 bits.
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.