Author: KarinsDad
Date: 22:46:12 05/14/99
Go up one level in this thread
On May 14, 1999 at 21:11:58, Christophe Theron wrote: >On May 14, 1999 at 15:21:57, Dann Corbit wrote: > >>0: >>Title says it all. What binary format does your program use when you want to >>store a board position in the smallest space possible? >> >>1: >>Is anyone willing to provide source for a EPD to Binary converter that operates >>in both directions? >> >>2: >>What are the tradeoffs between the smallest size that you can crush a position >>into and the fastest binary format that you can create? > >I would be interested in such coding/decoding routines too. Speed is not really >an issue I think. > >I would add to the desired features that the encoded position should always take >the same space. Variable length ones are fine since you can pad them with zero between the minimum size and the maximum size and turn them into fixed length ones. 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). This allows 2 bits room for a promoted pawn (a pawn will add 1 bit when it promotes and another 1 bit once that promoted piece moves to row 2 through 7), however, a pawn cannot promote without another pawn or piece being taken to remove the pawn from in front of the promoted pawn. Hence, at least another pawn must be taken (or in other words, to gain these 1 or 2 bits, you must lose 3 or more bits due to the removal of a pawn or some other piece). Hence, every promotion must be purchased with the opponent taking a pawn or piece. So, this structure can never get higher than 166 bits. I'm not sure you can get it much smaller without some form of compression or something (every other scheme I can think of has resulted in even more bits). KarinsDad :) > >Why? I currently use such an encoding to store positions in my opening book (I >don't want to rely on hash codes, as a hash code cannot be converted back to a >position). Variable length encoding is of no interest in this case. > >Being able to extract positions from my book has several purposes, one of it is >to be able to edit it without knowing the move sequence that lead to a position. > >Without working too much on it I have found a simple way to encode positions on >32 bytes for any possible (legal) position. I read somewhere else in the thread >that a near 20 bytes encoding is possible. That would be nice, so guys keep on >thinking about it... But you should also think about the worst case. It doesn't >help much to be able to crush a position into 10 bits if the algorithm in the >worst case needs 320 bits... > > > 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.