Hacker News Reader

Comment by Tommah | Hacker News Reader

I used this effect in my chess trainer (the link is in my profile). I have a file with 800 compressed chess positions, and I used a lot of tricks to get the file as small as I could. One trick was to invert the color of every piece on White's side of the board. In a typical position outside of the endgame, White's pieces will tend to be on his side of the board, and Black's will tend to be on his side. By inverting the piece colors on one side, I ended up with positions where almost all of the pieces are black, and here and there you'll have a white piece. It's similar to how most of the letters in text are lowercase, and occasionally you'll see an uppercase letter. I think I shrank the file by 5% or so this way.

View on HN

Here is how I would it

Board is 8x8, which is 6 bits. 4 piece type (rook, queen, knight, bishop. I will represent others (king and pawn) in a special way) is 2 bits. So 8 bits in total per piece

I would not use a bit to represent piece color but instead use a seperator to seperate one player's piece from another. Repeating the same position as the last piece can act as a separator since two pieces can't share same square

Kings are special that they must exist, so you don't have to specify their type

Pawns are special, most likely you will have 1 pawn (of each color) in one column and they can be on rows 2 to 7, or they can be dead or they can be "irregular" which means the pawn moved to another column and there are two pawns in that column now. This data is 3 bits per pawn so 48 bits in total. After that data you can put position of all irregular pawns (additional 6 bits for each irregular pawn). If a pawn promotes, it is represented as a regular piece (and can be considered dead in this 48 bit pawn data)

So a chess state is

   Pawn data (48 bits)

   Irregular pawns (6 bit each but I can't tell how many there can be at max. 8 maybe?)

   White king pos (6 bits)

   White pieces (6 bits for pos + 2 bits for type \* number of pieces)

   Seperator (6 bits)

   Black King pos (6 bits)

   Black pieces (same as white)

   Seperator (6 bits, represents end of data)

I think the worst case scenario is there are 8 promotions which would make it add up 248 bits

If number of pawns on board is small, it might worth representing them using their full positions and using a bit to decide which representation you picked

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.

How do you account for promoted pieces?

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

   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!

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

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.

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.

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.

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.

I guess your code is not publicly available, though I can easily see what you've done. And I'm not sure it took a lot of tricks. In my understanding, your format is essentially as follows:

    Prepare an empty chess board.
      Empty square is represented as 0.
      White piece is represented as +1 to +6 in the order of RNBQKP.
      Black piece is represented as -1 to -6 in the order of RNBQKP.
    
    Also prepare the reference chess board, which is same to initial positions except:
      3rd and 4th ranks are filled with black pawns, like 2nd.
      5th and 6th ranks are filled with white pawns, like 7th.
      Somehow, f1 and f8 are filled with rooks, not bishops. (Is this a bug?)
    
    Read the initial board. Start at a1 and continue until all squares are filled:
      Read one byte as bit fields AAAABBBB.
      Skip A squares. Wrap to the first file of the next rank on the last file.
      If -5 <= B-7 <= 6,
        The current square is set to B-7.
        If the current square is on 1st--4th ranks, invert the piece's color (if any).
        Skip to the next square.
      Otherwise, let C be 1 if B-7 = -6 (normally a white pawn), or B-5 otherwise.
      Repeat the following C times:
        The current piece is taken from the same square in the reference board.
        Skip to the next square.
    
    Read one byte as bit fields AAAABBBB.
    A indicates the current run. White if A = 1, black otherwise.
    I don't know B, but only one half-move will be read unless B = 1.
    
    Read one half-move or as many half-moves as possible:
      Read two bytes A and B, which are interpreted as square indices 0..63 (a1..h8).
      If A is on the 7th rank and a white pawn is at A,
        B's rank is reinterpreted as the promoted piece index (0 = no promotion, 1..4 = RNBQ).
        B's rank is then always reset to the 8th.
      If A is on the 2nd rank and a black pawn is at B, do the similar adjustement.
      Put a move from A to B, with the promotion indicated if any. But do NOT alter the board.

This format uses 1/3 to 1 byte to encode a single piece, unless there are 4 pieces or less in which case there may be some more overhead (since you can skip at most 15 squares at once). This is not particularly efficient; even a simple Huffman coding will be as efficient as that [1]. You should also make use of the fact that there are at most specific number of pieces per type, since once you've seen a black king, you won't see more so the corresponding representation is wasted. (Promotions make other pieces more complicated though.) I guess 10 bytes might be possible without a very complicated scheme.

This format also uses two bytes to encode a single turn. This again is hardly efficient, especially because there are much smaller number of legal (half-)moves given a particular position. (218 is believed to be the maximum, and the upper bound is not much larger than that [2].) So you can just enumerate legal moves and encode the index as a single byte. If the number of legal moves is far smaller, say 16, you can pack multiple moves into a single byte as well. A much involved scheme would then assign a smaller number of bits to a more likely move, using heuristics and neural networks and whatever else [3].

[1] https://stackoverflow.com/a/66345772

[2] https://old.reddit.com/r/chess/comments/o4ajnn/whats_the_mos...

[3] https://triplehappy.wordpress.com/2015/10/26/chess-move-comp...

> This format uses 1/3 to 1 byte to encode a single piece... even a simple Huffman coding will be as efficient as that.

Not when you consider that his file was compressed after encoding (per the article).

Ah, I hadn't seen Adler's comment before. I did most of my work on this before he posted that comment. His scheme is probably more efficient than mine (he is Mark Adler, after all), but I'd have to run it on the same set of positions to know for sure.

You figured out how I'm representing the position correctly, but I'm only storing one half-move per position, specifically the current player's best move. I use that for the "Show hint" feature.

> I'm only storing one half-move per position, specifically the current player's best move. I use that for the "Show hint" feature.

I think you are describing B = 1 case. When is the B != 1 case used then?

I also wonder why the reference board seems to have an obvious mistake (rooks in place of bishops). Again, I hardly know any chess, so that might be my oversight and that does improve the compression for this particular data set.

Reply on news.ycombinator.com