Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Why not do it simpler? : Create an array with 16 elements, one element per piece, black + white. Every array element is 7 bits wide, 1 bit for captured or not, and 6 bits for the square number the piece is on (8 x 8). Then you need 16 * 7 = 112 bits = 14 bytes. (And the captured-bit can even be compressed further as a 65th square, but that makes it more calculation intensive to extract a position)


Each side has 16 pieces, so you need 32 elements.


Ah how silly of me, that woud make it 28 bytes. (I had the nagging feeling I was missing something :-) And promotions are also not covered by this...


+ 3 bits for piece type?


You only need the piece type for pawns (that can be upgraded), and a bit on the king to track if castling is possible; otherwise a single bit for on-board/captured is sufficient, since the types of the other pieces are implicit in the array index. (You can shave single bits in a few places -- if the state represents a game in progress the king-captured bit isn't needed; natural bishops only need 5 bits for position on board, etc. This doesn't really add up though.)

On the other hand, there are 32 pieces (max) on a chess board, not 16, so grandparent is off by a factor of more than two.


Two bits on the king for castling, queenside and kingside.


Why not just one bit "castled"?


You can only castle if neither the king nor the rook have been moved (and none of the three squares the king uses may be under attack, and all the squares between the rook and the king must be empty).

Since you could move either rook somewhere and then back to their starting squares, you have to track their eligibility separately. If the king moves, both rooks lose eligibility.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: