Sunday, September 15, 2013

[bxdewtwa] Binary encoding a chess position

64 squares.  Each square can be in one of 13 states (4 bits).  Total 256 bits.

Each piece can be on one of 64 squares (6 bits).  This sparse method is more efficient when there are 256/6=42 or fewer pieces on the board, that is, always, given 32 maximum.

(Rough calculations, not including en passant, castling, or promotion.)

chess-endgames-via-mapreduce

1 comment :

Russ Williams said...

Another way to get 192:

For each square in sequence (e.g. a1, a2, ..., a8, b1, b2, ...) have a single bit saying if the square is occupied. (64 bits total). After each "1=occupied" bit, put 4 bits telling the piece identity. 32*4=128. 64+128=192.


It seems like the idea of scanning over the squares, which are mostly sparse/vacant, could lead to a run-length-encoding approach to save space over the long gaps of empty spaces, by specifying the length of the gap to the next occupied square, but I'm not sure of a reasonable concise way to do that; presumably one would need a variable-length way to encode integers which is still sufficiently concise so that the additional overhead of handling variable-length isn't too much.

Or some kind of binary branching tree (divide and conquer) to geometrically spread out from a midpoint more concisely somehow, specifying the gap to the next "previous" and the next "following" piece...?