Author: Robert Hyatt
Date: 10:03:38 08/13/98
Go up one level in this thread
On August 13, 1998 at 06:26:40, Roberto Waldteufel wrote: > >On August 09, 1998 at 00:24:27, Danniel Corbit wrote: > >>What is the most compact known method for storing a chess position with all the >>relevant information like castling status, en-passant squares, etc.? [Also best >>move from here .. don't really care about what the test set is though...] >>I want to store a large database of chess positions, and compaction would really >>help. When I am finished, I will share the final specifications and the data >>also, if anyone is interested. > > >Hi Danniel, > >Check out http://caissa.onenet/chess/texts/FewBits for an interesting article >about this. I seems that there are several approaches that offer promise - one >claim is for 143 bits, but there is also an amazing claim by J Nievergelt that >it can be done in significantly less than 100 bits. > >Best wishes, >Roberto We had a lond discussion about this a few years back on r.g.c.c (or perhaps r.g.c before the split). The generally accepted theory ended up at roughly 160 bits, storing all pieces, enpassant status, castling status, 50 move rule counter, using arithmetic encoding... I don't remember the specifics, but I believe that 168 was the magic number. We can rehash that discussion here if you'd like. Arithmetic encoding might start like this: 2 6 bit values for the king locations. then 10 4-bit counters for each type of piece. each counter would normally be between 0 to 10, for the number of each piece type present... if a counter is non-zero, then it would be followed by N 6 bit values for the squares those pieces are on. You would tack on to this a 4 bit enpassant file target, 0=no ep possible, and finally 2 bits for each castling right for each side, and the 50 move rule counter which would need 6 bits also... adding this up, for the initial position, you get 12 bits for the two kings, 10*4 since all counters would be present, plus 30*6 for the squares of the non- king pieces. This all adds up to more than 168 bits, so I have obviously left out some tricks that were discussed... but this is a good starting point... some of the tricks involve real bit-twiddling... ie getting rid of leading zeros on each square will cut the bits to 1/2 the original number for the squares in the average case... We can start here if you want, or with another approach.
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.