Author: Eugene Nalimov
Date: 21:43:42 05/15/99
Go up one level in this thread
I slept, too and here is small correction: if you want to decrease not the *average length*, but the *worst case*, you can squeeze 2 more bits: with suggested schema, in the worst case we store 14 bits for kings squares and castling status. It's possible to store that in 12 bits, but those 12 bits (or at least half of them) must always present. There are 3612 (not 3812 as I posted here yesterday) legal kings configurations. There are enough values left to 4096 to store castling status. If one of the kings lost both castlings, but second still can castle, we must store position of first king as well as which castlings are possible for the second king - 2*64*3 values. Also there are the cases when both knigs still can castle - 3*3 values. Total is 4005 values, so all those values can be stored in 12 bits. Theoretically you can use remaining to 4096 values to shorten the case when some castlings are available, and don't store all 12 bits in that case. Eugene 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.
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.