Different board representations in computer chess | Hacker News Reader

Different board representations in computer chess

lichess.org

22 pointstosh7 comments

The 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

This 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.

I 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

This 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.

If 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.

This 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]

I 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.

Reply on news.ycombinator.com