Hacker News Reader

You also need to account for:

- Whose turn is it

- If the king is in its initial position, whether the king has moved previously (that player can't castle anymore).

- For the pawns, you may need the previous position/move to allow en-passant capturing [1]

The standard specification used for this is the Forsyth–Edwards Notation (FEN). [2] It was invented way earlier than computers, so it was targeting humans / isn't optimized for digital compression, but it at least specifies _almost_ everything that you need to track.

The _almost_ is because to account for the repetition rule [2] you need to track all previous positions. At this point, the problem changes from "how to efficiently store the positions of the pieces in the board" to "how to efficiently store (partial) games", and you are probably better off listing the moves than the board state.

[1] https://en.wikipedia.org/wiki/En_passant

[2] https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notati...

[3] https://en.wikipedia.org/wiki/Threefold_repetition

I remembered current turn later but I could not think of your 2nd and 3rd point, you are right

I guess you can't just take a look at board to see current game state, I was too focused on what game looks like while there are additional off the board info

https://news.ycombinator.com/item?id=39066345

You could probably modify this solution, I am already using 3 bits for piece type

0-3 rook queen bishop knight

4 Non-moved king (can castle)

5 moved king

6 pawn that moved 2 squares last turn (can be captured using en passant)

7 other pawns

And then a single extra bit to store whose turn it is

instead of encoding "moved king", encode "moved rook" on each rook. Since a pawn can never be on its home rank, overlap rook (not moved) & pawn (en passant) codes. Now you have a code for "king (to move)" and "king (not to move)".

If you use a variable length encoding you can also use different static probabilities for the different ranks, since "rook (not moved)" and "pawn (en passant)" can only appear on certain ranks and only depending on the piece color (well, pawns can't appear on ranks 1 or 8 at all)

You’d need the same information for rooks to handle castling.

I love bit-bashing to squeeze something down to the smallest representation possible. There was a related discussion here on HN recently, where I came up with this:

A good representation needs to keep the full game history due to the no-repeat rule, and also because this is generally useful. There are only 32 pieces so a 5-bit number can select one uniquely. Each piece has a maximum of about 32 positions it can move to on its turn, for another 5 bits. Then the encoding is just 10 bits per ply. Typical games are 40 moves (80 ply) and hence require just 800 bits or 100 bytes for the whole game history. Some additional data is required to track promotions, but that's it.

Then you could get clever with Huffman coding or the like, since some moves are more common than others. E.g.: on the first turn, only the pawns or the knights can move. For quite a few turns, pieces either can't move or are very restricted in where they can move to. Pawns always have so few moves available that their next move could be represented with just 2 bits instead of the full 5. Etc...

In practice, it ought to be possible to get the typical standard game representation down to 8 bits per move or less, especially for short games.

To represent games starting from arbitrary configurations, there needs to also be included 32 6-bit numbers to encode where each of the unique pieces is on the 64-square board. This adds just 24 bytes for this initial "setup".

You could generate a list of legal moves with a specific algorithm, and use the necessary number of bits to indicate which one happened.

>To represent games starting from arbitrary configurations, there needs to also be included 32 6-bit numbers to encode where each of the unique pieces is

In that case, you can either omit pieces not in play or omit pieces in their standard starting position to shave off a few more bits.

Just encoding algebraic chess notation gets you to 9 bits without much skill: 3 bits for the 6 pieces, 3 bits for rank and 3 bits for file, with the edge cases shoved in the extra encoding space given that you have 3 bits to encode 6 pieces.

On average, chess has a branching factor of 30-40, so you need a touch more than 5 bits on average even with clever Huffman coding. Just Huffman coding regular algebraic chess notation for movement would probably get you down to 6 bits on average.

Of course, the other issue is that the tighter you compress the data, the harder it is to actually manipulate that data, and it's not clear that the space saving for denser encodings is worth it.

That’s a lot of extra wasted bits! There are only 32 pieces in total, and only one of 16 can move each turn. So a mere 4 bits is sufficient to select the moved piece.

The assumption here is that this is an encoding “at rest” and isn’t used directly, except perhaps for equality comparisons. The decoder would have to track the game state and expand this into a much larger format for programmatic manipulation.

That's a better reasoning in general (see my other comment for the GP's scheme), but you can do much better.

First, you should encode the number of total pieces (and their general compositions) in the beginning, which can greatly shrink all subsequent fields. For example you are using a repeating square index to denote the end of piece list, but you have at most 15 such pieces unless there is a chess variant where new piece is created out of nothing, so you can just encode that as 4 bits instead of a 6-bit separator.

Second, use a fractional number of bits per each field. Each piece occupies one square and prohibits some more squares, and those squares should not be available for encoding. So you need an arithmetic or equivalent coding for the maximal efficiency. A careful ordering can then even eliminate much more squares from further encoding. I think you've essentially done this for pawns, but you can do much more in general.

Using 3 bits for piece type (including empty) and 1 bit for color makes a simple matrix enconding of the board just 8x8x4=256 bits. Add run length encoding for empty squares and it will be much smaller.

4 bits per square has room in it for RLE flags and even counts, without increasing the worst case size.

248 is max in my case (actually later I noticed I could shave another 4 bits), if there are less pieces, there will be less data

But probably with encoding your solution would be better

But probably there can be a middle grounds.

1 bit for each square represent there is a piece on that pos so 64 bits

then for each side, 4 bits to represent number of pieces and 3 bits for each piece to represent their type

At max 64 + 2x(4 + 3 x 16)=168 bits for 16 pieces each side.

edit: nvm this wouldn't work since you wouldn't know the colors of the pieces on board. You need to store 4 bits for each piece, 1 color + 3 type so it is 64 + 2 * 4 * 16 = 196. I am not sure if this is better anymore

https://news.ycombinator.com/item?id=37525348

As far as max size goes, 64 bits plus data per piece seems to be the right path. Especially if you huffman the pawns to be 3 bits each while other pieces are 4 bits.

The grandparent method gets pretty bloated when you start promoting.

Actually it's 192 bits, not 196.

To beat it you must encode each piece with a different number of bits. E.g.

  Q c00
  N c01
  P c10
  B c110
  R c1110
  K c1111

where c is 0 for white or 1 for black. Since there are 2xK, 2xQ, 4xB, 4xN, 4xR, 16xP, you will need 2x5 + 2x3 + 4x4 + 4x3 + 4x5 + 16x3 = 112 bits. Adding the 64 bits for the bitmap, the grand total would be 176 bits.

The issue is that each time a P is promoted to R or B (a stupid thing to do, since a Q would be better) you need one or two bits more. On the other hand, you spare 3 to 5 bits for each captured piece. In normal play, captures outnumber promotions, and promotions are either to Q or N, never R or B, but theoretically...

Even something very simple like listing piece positions in a given order should result in less. Let's say King, Queen, Rooks, Bishops, Knights, pawns. Give a position for each for both players in 6×32 (192) bits.

If a piece is taken, repeat the position of the king. If a pawn is promoted (and there are more than than the starting number of the piece it was promoted into) repeat the position of the piece it was promoted into.

1 bit for whose move it is. (193b)

3 bits for the en-passant column. (196b)

50 move rule (I suppose 7 bits, as you need it in ply?) 203b. Then the data for the extra pieces, in the order encountered if any. ?×6b (how many are possible? There are 16 pawns, but I suppose it isn't possible to promote all)

How would you enforce the three repetitions rule this way?

I guess you can't do that without the full PGN. I guess the 50 move rule might be extraneous as well.

You don’t always need the entire move list.

Whenever any piece is taken (permanently decreasing the number of occupied squares), a pawn is moved, castling rights change, or an en passant opportunity isn’t taken, there won’t be any more repetitions of the board matching past board positions, so you can forget all earlier board positions.

My objective was to reduce average size, the example calculation I made is the max size

My objective was to show that it's quite complicated for dubious gain. What do you think the average would be?

  What do you think the average would be?

No idea, I don't know what kind data OP stores (mostly few pieces? or lots of pieces? etc). You can probably tailor your format if you have more insights. But no matter what, you can always have some gain compared to a naive approach. I would say storing a pos for each piece might be naive, since there are a lot of rules that allows you to exploit things

My 248 bit was the absolute worst, when you have 8 promotions on board and lost none of (non-pawn) pieces. For example the initial board would be about 190 bits as well and most would be lower as you capture pieces. I think that would be a worst case for you as well but I don't get this part

  If a pawn is promoted (and there are more than than the starting number of the piece it was promoted into) repeat the position of the piece it was promoted into

You mean you first need to tell the position of the piece it is promoted to and then another position for the position of the pawn (now promoted)? Then you have a pretty bad worst case as well

But you are right, I made an overcomplicated solution. Here is a simpler one that should perform better https://news.ycombinator.com/item?id=39066557

>Then you have a pretty bad worst case as well

It would be really rare though, virtually all positions would be 192bits for the position as such.

I don't think you need en passant for each pawn, there can only be one, so you only need to mark the column, with 3 bits, and there always must be a column where it can't happen, that you can use where there isn't any. Or, maybe it's more, IDK.

After some more thinking and feedback:

  2 bits per square
  00 empty
  01 white pawn
  10 black pawn
  11 other piece
  =128 bits

4 bit index of white king on board (one of the others)

4 bit index of black king

for each "other piece" on board that is not a king: 1 bit color + 2 bit type

1 bit for current player

2 bits for each king if they moved (optional, only exists if king is at thair initial square. Otherwise it is moved)

1 bit for each pawn if they can be captured en passant (optional, these bits only exists for their pawns if there is a pawn at 4th row for white or 5th row for black)

(And i will ignore the draw rule)

> =128 bits

Notice that this alone is more than a lot of positions with my "naive" implementation - 36 bits per side for the best case, with only the king, and at most one queen: 6b for the king, 6 bits for the queen, or its absence, 6 bits each for the absent rooks, bishops, knights and pawns.

I thought of combining the two:

1 bit per square (empty/non empty) 64 bit.

Then we need at worst 5 bits (32 non empty squares or less) per piece to indicate the positions of the big pieces. (80 bits, typical worst case)

Then we only need 1 bit per pawn, to indicate color. (16 bit at most)

The typical worst case: 160 bits.

Now this is some good nerd sniping content.

A few quick thoughts.

You could have a move counter, and pick representations based on total moves (early on, you could probably use lots less space simply storing the movement from original position and piece type).

Bishops can only be in one of 32 spots but you need to know which one (ordering?).

Trying to not shave off bits but have more zeros so that it can be compressed more effectively - having positions based on the delta from their most likely position could help.

  Bishops can only be in one of 32 spots but you need to know which one (ordering?).

I was thinking of that but piece type is already 2 bits for 4 piece types so you can't have unique color bishop types without adding additional bits. Ordering wouldn't work since you can only have one bishop or an extra one or two of same color etc.

   Seperator (6 bits)

   Black King pos (6 bits)

Maybe we can even skip the separator?

Since each player has to have a king on the board. So the first piece in the list is the white king, and everything after it is white, until the second king in the list, and then that one and everything after it is black.

Number of chess pieces are dynamic so you wouldn't know if white pieces are over and next piece is black king (kings don't have a type bits)

But now I think about it, instead of a separator I could simple use 4 bits to represent how many (non pawn) chess pieces there are for each player. It is at most 15 (7 initial + 8 promotion) so only 4 bits instead of 6 bit seperator shaved another 4 bits!

Don't forget to track if the rooks or kings have moved, for castling eligibility. And what the previous move was for en passant. And the full game history back to the most recent capture for draw by repetition.

  And the full game history back to the most recent capture for draw by repetition.

Ouch, I will leave this as an exercise to reader

That part is easy.

1. store the oldest full board you care about

2. for each turn, record either:

2A. two 6-bit coordinates

2B. 1-8 bits to say which move they picked out of the full list of legal options

You could actually run a small chess engine a few moves ahead to sort the full list of legal options into the order of obviousness.

Then you can use a variable length encoding (Huffman coding?) to encode the moves, with more obvious moves taking fewer bits. You could even encode multiple moves into a single code point, and it might be possible to encode an entire sequence of obvious moves (like a complex exchange) into a single code point, which might be encoded as just a single bit.

You would definitely use arithmetic encoding at that point. Then you can directly use fractional bits to encode moves.

How do you account for promoted pieces?

They are dead and the piece that got promoted is just another regular piece