▲ | amelius 8 hours ago | ||||||||||||||||||||||
What is the least number of bits that can describe any reachable chess board? update: article says there are approximately 8.7x10^45 reachable chess positions and https://github.com/lechmazur/ChessCounter says this is an upper bound. (this would correspond to about 153 bits) | |||||||||||||||||||||||
▲ | jcranmer 3 hours ago | parent | next [-] | ||||||||||||||||||||||
The king can reach any of 64 tiles. Rooks, queens, and knights can also do so, but they can also be captured, so 65 states for those 5 pieces. Bishops can only reach half of those tiles, so those two pieces get 33 states each. Pawns are interesting: they can promote into 4 pieces that each can move 64 tiles, they can be captured, or they can move into a somewhat variable number but 20-30ish positions as a pawn, or about 290 states per pawn. This means it takes 111.something bits to represent the board position of a color, or rounding up, 224 bits to represent the board positions of both black and white. En passant and castling restrictions don't add to the bit representations once you round up, since that's just 1 extra state for several pieces. That's probably the most compact representation for a fixed-size direct board representation. For a sparse representation, note that both kings have to exist, so you can represent the live pieces with a base-10 number of n digits with n + 2 64-bit numbers representing piece position, and a little bit extra information for castling and en passant legality. If half the pieces are gone (a guesstimate for average number of pieces on the board), that amounts to about 180 bits for a board representation. Move history requires about 10 bits per move (pair of white/black turns, with a ply of around 32 = 5 bits), which means you get to 18 moves, which appears to be somewhat shorter than the halfway point of an average chess game. To be honest, it looks to me like getting more compact than the upper hundreds will require building impossibly large dictionaries. | |||||||||||||||||||||||
▲ | tromp 8 hours ago | parent | prev | next [-] | ||||||||||||||||||||||
That's ceil(log2(~4.8x10^44)) = 149 bits. But to make it efficiently decodable you'd use the ceil(log2(8726713169886222032347729969256422370854716254)) = 153 bit representation of the ChessPositionRanking project linked to in my other comment. The ChessCounter project does not provide an efficiently decodable code. | |||||||||||||||||||||||
▲ | cabirum 8 hours ago | parent | prev | next [-] | ||||||||||||||||||||||
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. | |||||||||||||||||||||||
| |||||||||||||||||||||||
▲ | LegionMammal978 4 hours ago | parent | prev [-] | ||||||||||||||||||||||
The 8.7e45 "restricted" number in that repo rules out certain patterns of pawn promotions. It looks like the 5.68e50 "general" number is the true upper bound, allowing any promotions possible. | |||||||||||||||||||||||
|