Author: Christophe Theron
Date: 00:27:56 05/15/99
Go up one level in this thread
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
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.