Author: KarinsDad
Date: 15:06:57 05/14/99
Go up one level in this thread
On May 14, 1999 at 17:10:38, KarinsDad 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? > >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) Oops, can cut a bit off here. Since we know the side to move, we can represent the en passant to square with 3 bits. So, a total of 9 bits for this (not that this changes anything since all of the other savings are 2 bits for latter game positions, so the lack of the odd bit does not help, but it does make it one bit smaller). Also note that the structure below works since we parse piece locations out of it. When parsing, you would save off the king locations and when either of those locations are hit, you place the king there and skip to the next location in the parse (i.e. a back rank of RNBQ.KR. would be represented as RNBQ.R. in this structure and the king would have to be filled in). KarinsDad :) > >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 :) >
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.