Author: KarinsDad
Date: 14:10:38 05/14/99
Go up one level in this thread
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? Without thinking about it alot, here is my first cut (my program does not do this yet): 10 bits for side to move, en passant possible, en passant to square (4 bits since there are only 16 legal squares for this), white kingside castle possible, white queenside castle possible), black kingside castle possible, black queenside castle possible (note: for a program, it may be better to know if a rook moved and if the king moved, but you save 2 bits without that info here) 12 bits for the king location (6 bits for each color) since the kings must exist the rest of the structure is based on what piece is in a square (a1 to h1, then a2 to h2, etc.): 0 blank 10x pawn 1100x knight 1101x bishop 1110x rook 1111x queen Since for most positions, there are more blanks and pawns, they get the smallest sizes. where x is the color bit. So, for a normal set of pieces, this would take up 150 bits. You would lose 2 bits everytime a pawn is promoted to a piece. The grand total is 172 bits or 21.5 bytes (for normal positions). This also means that you could have 2 promoted pieces on the board and still store it in 22 bytes. However, when pawns and pieces are taken, this structure decreases in size. And, of course, you could put a compression routine on top of this. KarinsDad :) > >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? Without thinking about it alot, here is my first cut: 12 bits for side to move, en passant possible, en passant to square (4 bits since there are only 16 legal squares for this), white king rook has moved, white king has moved, white queen rook has moved, black king rook has moved, black king has moved, black queen rook has moved. 12 bytes (square locations) for all pawns (6 bytes for black pawns, 6 for white) both kings (12 bits) since both kings must exist, 6 bits can represent each the rest of the structure is based on if the piece exists: 1yyyyyy queen 01yyyyyy rook 001yyyyyy bishop 0001yyyyyy knight where y is location, place white pieces first, than a separator of 0000 then black pieces.
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.