3 ms·
Different board representations in computer chess
- DougMerritt 4y agoI lost touch with this subject long ago, but looking around recently for the first time in ages, it seemed like the "bitboard" representation (one of many in this article) is very much a current favorite. So I plan to read that part more carefully.
- fl0ps 4y agoThis is a great resource. I was recently surprised by the different ways to note boards/moves/pieces when trying to get ChatGPT to play a game of chess with me. Bonus points: Ask it to invent Fairy Chess deviant moves [https://en.wikipedia.org/wiki/Fairy_chess https://en.wikipedia.org/wiki/Fairy_chess]
- timerol 4y agoI wonder how compactly you could represent most chess games. On a per-piece basis, each non-pawn would require 6 bits of location, plus 1 bit for whether it exists, for 16 * 7 = 112 bits. Each pawn can only access half of the squares at most (never row 1 or 8, capturing diagonally creates a fan of at most 32 squares, at minimum 21 for the flank pawns) so an additional 16 * 6 = 96. You would need to add an extension for promoted pawns, likely average out to never relevant. It could be stored as an illegal pawn position, so 208 bits in the normal case, but a variable-length format. With bitboards: There are 12 types of pieces, so could use 4 bitboards[0] to capture all of the information. 64 * 4 = 256 bits. I think the most compact would be a combination. One bitboard (64 bits) marking where pieces are, and then a list of 4 bit integers[0] noting which piece is which, ordered by how they show up on the bitboard. With 32 pieces that's an additional 128 bits, for 192 total. And the size could only go down from there, as pieces are removed. Writing this out, I see how 4 bitboards would be much simpler than 1 bitboard and a weirdly-indexed list that needs to be reordered every move. [0] Boards could be 1=white/0=black, 1=more/0=less than 4 points, 1=royal-or-minor/0=rook-or-pawn, 1=queen-bishop-rook-or-pawn/0=king-knight-or-nothing, so that all 0s means no piece, and 1000, 0100, and 1100 as unused values. The full list would be: 0000 - empty 0001 - black pawn 0010 - black knight 0011 - black bishop 0100 - reserved 0101 - black rook 0110 - black king 0111 - black queen 1000 - reserved 1001 - white pawn 1010 - white knight 1011 - white bishop 1100 - reserved 1101 - white rook 1110 - white king 1111 - white queen
- alexb_ 4y agoThis sounds like an amazing code-golf-esque project. You would also have to store the last move made by a side to determine if en passant is legal, if the kings can castle, as well as which side is to move. Reserved values could be used for this as well as flags for other things to improve compression.
- Zababa 4y agoIf the goal is to be as compact as possible, I think we could say that a board is read in a very specific order, always the same, that a single bit at 0 is an empty square, and that a bit at 1 starts a block of 4 bits that encode a single piece. And maybe there's a way to reduce that even more, by allowing different ways of reading through the board, and trying to use that to order the pieces so that we can use less bits for encoding them. For example, if the board starts with 0 it's a regular pattern of doing line A, 1 to 8, then line B, etc, but if it starts with 1 we read it as a spiral, so A1 to A8 to H8 to H1 to B2. And maybe this way we can at least find a place where two of the same pieces are following each other and we can organize everything so that for each piece that is the same as the one before we can only use a single bit at 1. You can probably go much deeper than that, but it's already a fun start.
- captn3m0 4y agoThe Chess Programming Wiki has some great details about using bitboards, such as magic bitboards that can be used for efficient move generation by hashing the bitboard itself into a lookup table. Bitboards themselves make efficient board serialisation of chess possible and somewhat portable, making it amenable to modern AI tooling. An interest area of mine is to work towards similar representations for other games, especially modern Eurogames. https://www.chessprogramming.org/Magic_Bitboards https://www.chessprogramming.org/Magic_Bitboards
- algo_trader 4y agoThis is opposite of the "bitter lesson", where human provide simpler representations (and invent new games!), and a scalable algorithm/compute can provide an optimized equivalent. I will be PM with some thoughts and hope to hear from you.