Author: J. Wesley Cleveland
Date: 10:21:56 04/21/00
Go up one level in this thread
On April 21, 2000 at 02:03:53, Dann Corbit wrote: >On April 21, 2000 at 01:44:07, Tom Kerrigan wrote: >>On April 20, 2000 at 11:58:55, KarinsDad wrote: >>>On April 20, 2000 at 04:21:58, James Robertson wrote: >>> >>>>What is the current minumum number of bits required to store a chess position? >>>>If somebody could send me instructions on how to encode a chess position in as >>>>few bits as possible, I would be very happy. >>>> >>>>Thanks, >>>>James >>>>jrobertson@newmail.net >>> >>> >>>I think the answer is around 155 or so bits with a enumeration algorithm, but >>>I'm not sure if anyone has actually written one and proved it. The reason is >>>that it would be a bit of a bear to write (but doable). >>> >>>My best is 162 bits with the algorithm I put together. It also has not been >>>written. However, it would be quicker to calculate than an enumeration >>>algorithm. >>> >>>A good algorithm is the one used in EDP. It requires 192 bits, but is extremely >>>simple to code up. Something like: >>> >>> 64 64 bits bitboard >>>128 4 bits per piece times 32 pieces >> >>Hmm. I wonder if some sort of Huffman encoding would be useful for the bitboard. >>Of course, then you get positions that are variable bit lengths, but if that's >>not a requirement... > >that is an excellent idea for average length reduction, but I think it will >actually expand the worst case length by a few bits. I don't think so. Say you use the simplest Huffman of 3 bits for pawns, and 4 bits for other pieces. For every two promotions (adds 2 bits), one man must be removed (subtracts 3-4 bits), so the total length is smaller.
This page took 0.04 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.