Author: Dave Gomboc
Date: 04:42:25 05/15/99
Go up one level in this thread
On May 15, 1999 at 03:27:56, Christophe Theron wrote: >On May 15, 1999 at 03:19:44, Dave Gomboc wrote: > >>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 > >Hey, you guys never sleep? :) > >Anyway, it would be nice to have one standard coding without 50 moves rules/# of >reps, and another one including these infos too. > >I mean the first one would be interesting for a book implementation. > >Coding seems to be not very difficult, isn't it? > > > Christophe Sure, I sleep during the daytime. Who can get any work done with all of those noisy people up and about? <grin> So what is your excuse? Do you think the sun comes up at a different time where you live or something? ;-) The easiest solution is to have the number of moves since the last pawn push or capture be the last term in the (((((x1)*a1+x2)*a2+x3)*a3+x4) etc.) series. Then the same routine can be used for both. 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.