Author: Flemming Rodler
Date: 10:22:49 04/21/00
Go up one level in this thread
On April 21, 2000 at 07:31:30, Alessandro Scotti wrote: >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. > >Well, at most it will expand the length by one bit, used to indicate that we're >*not* using Huffman for this position... Huffman coding bitboards (or other entropy coding schemes for that matter) will be infeasable for a complete bitboard. The reasons being: 1) There are too many possible bitboard configurations (ie. the input alphabet is too large). 2) You will need to be able to assign a nonzero propabillity to every bitboard configuration (only the legal configurations of course). Maybe Huffman coding 8 bits (or even 16 bits) at a time might work. The a diffeeent Huffman table could be assigned for each rank of the chessboard. Besides searching the for all positions with say a knight on e5 might be extremely difficult. /Flemming
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.