Author: Dann Corbit
Date: 19:40:48 05/14/99
Go up one level in this thread
Here is a contribution by Peter Klausler from a while back: "The smallest representation that I know for a FEN position, which sounds like what you want here, is 173 bits, but it is extremely hard to encode and decode. CDB uses a 192-bit (24 byte) representation for some positions that require a context-free representation, and the details are elaborated in the CDB internal documentation (http://reality.sgi.com/pmk_craypark). In a database, however, one seldom needs to use a context-free representation, and great space savings are possible. Most positions in a CDB database are represented with a 12-byte record." Here is something from Roberto Waldteufel: "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." Here was a contribution by Dr. Hyatt: "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.