Author: Dave Gomboc
Date: 00:19:44 05/15/99
Go up one level in this thread
On May 15, 1999 at 02:49:05, KarinsDad wrote: >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. Whatever you come up with, it will be of more general utility if it is able to disambiguate every state. So, please include the 50-move counter and the number of times the position has been repeated with the same permanent castling and en passant options. J. Nievergelt is a professor at ETH Zurich. Did he make such a claim in a publication? Perhaps he is being misquoted, and his comment refers to the average cost to represent a game from the normal start position. !? Dave
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.