| Heres a few naive options to get a ballpark idea: A) fixed list of piece coordinates: 32 pieces × (3 bits for row + 3 bits for column + 1 bit for whether it's alive) = 224 bits B) list of live pieces: (3 bit row + 3 bit column + 1 bit for color + 3 bits for which piece) × up to 32 pieces = up to 320 bits C) 8x8 array of the board: 64 squares × (1 bit for color + 3 bits for which piece) = 256 bits Then there's the gamestate that isn't directly visible on the board: - whose turn it is: 1 bit. - castling rights: A needs 2 bits. B and C can pack it in with the 3 bits for pieces. there's 6 pieces so there's room for two more, one of which is a rook that's eligible to castle with. - en passant: A needs a flag for each pawn so 16 bits. B and C can also pack in with the other spare piece being a pawn that just advanced two spaces. - promotion: B and C get it free. A needs another 3 bits per pawn to indicate if and what it's promoted to (so 48 bits max) - 50 moves without capture/pawn move optional stalemate: 6 bit counter from 0 to 50. - 75 moves without capture/pawn move forced stalemate: make that 7 bits - repitition stalemates: don't see a way around needing to know the previous board states. you need a copy of everything except the 50 move counter for previous turns. you can prune states that are impossible to return to. A: 301 + (294 × #repeatable_states) bits B: 328 + (321 × #repeatable_states) bits C: 264 + (257 × #repeatable_states) bits I'm sure there's savings to be made further compressing any of these with variable length encodings though (see links in other replies). I especially like the idea of encoding information as illegal states. edit: originally said 4 bits for row and column but it's 3. |