Hacker News Reader

Piece type and color fit in 4 bits.

So, either a fixed-length encoding of the whole board, 64 * (4 bits) = 256 bits = 32 bytes.

Or, sparse variable length encoding of pieces only, 6 bits to index each of 64 squares, = 10 bits * piece count. E.g. initial position takes 32*10 = 320 bits or 40 bytes.

View on HN

That's a fine upper bound, but it doesn't minimize but usage since it also can represent illegal positions.

While this is an upper bound for a "board position", it should be noted that it is not an upper bound for a "game state". That includes the (unbounded) whole board position history because of the threefold repetition rule. If you ignore that (and the fifty-move rule which can alternatively be kept using a six-bit counter), you also need the castling state and the en passant state. Plus one bit of the player on move, obviously :-)

The vast majority of the positions are illegal. There is only 1 black king on the board; practically all of the represented positions have more than one. And there are over a dozen kinds of pieces to repeat that for. A better upper bound is almost 100 orders of magnitude smaller.

Reply on news.ycombinator.com