Author: James Robertson
Date: 09:27:16 05/15/99
Go up one level in this thread
On May 15, 1999 at 07:42:25, Dave Gomboc wrote: >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 If you guys ever decide on a nice format, please tell me, as I can make use of it in my program.... James
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.