11 ms·

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

by thrw21 3y ago

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

IanCal 3y ago
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.
- thrw21 3y ago
  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.
teo_zero 3y ago
How do you account for promoted pieces?
- thrw21 3y ago
  They are dead and the piece that got promoted is just another regular piece
codetrotter 3y ago
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.
- thrw21 3y ago
  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!
vnorilo 3y ago
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.
- thrw21 3y ago
  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
  - thrw21 3y ago
    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
    - Dylan16807 3y ago
      https://news.ycombinator.com/item?id=37525348 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.
    - teo_zero 3y ago
      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...
kilburn 3y ago
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 https://en.wikipedia.org/wiki/En_passant [2] https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notati... [3] https://en.wikipedia.org/wiki/Threefold_repetition https://en.wikipedia.org/wiki/Threefold_repetition
- thrw21 3y ago
  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
  - thrw21 3y ago
    https://news.ycombinator.com/item?id=39066345 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
    - jepler 3y ago
      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)
blackboxlogic 3y ago
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.
- thrw21 3y ago
  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
  - Dylan16807 3y ago
    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
    - phire 3y ago
      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.
      - Dylan16807 3y ago
        You would definitely use arithmetic encoding at that point. Then you can directly use fractional bits to encode moves.
lifthrasiir 3y ago
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.
Anotheroneagain 3y ago
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)
- 317070 3y ago
  How would you enforce the three repetitions rule this way?
  - Anotheroneagain 3y ago
    I guess you can't do that without the full PGN. I guess the 50 move rule might be extraneous as well.
    - Someone 3y ago
      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.
- thrw21 3y ago
  My objective was to reduce average size, the example calculation I made is the max size
  - Anotheroneagain 3y ago
    My objective was to show that it's quite complicated for dubious gain. What do you think the average would be?
thrw21 3y ago
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)
- Anotheroneagain 3y ago
  > =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.
- Anotheroneagain 3y ago
  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.
deleted 3y ago
[deleted]

by thrw21 3y ago

IanCal 3y ago

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.

thrw21 3y ago
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.

teo_zero 3y ago

How do you account for promoted pieces?

thrw21 3y ago
They are dead and the piece that got promoted is just another regular piece

codetrotter 3y ago

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.

thrw21 3y ago
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!

vnorilo 3y ago

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.

thrw21 3y ago
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
- thrw21 3y ago
  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
  - Dylan16807 3y ago
    https://news.ycombinator.com/item?id=37525348 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.
  - teo_zero 3y ago
    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...

kilburn 3y ago

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 https://en.wikipedia.org/wiki/En_passant [2] https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notati... [3] https://en.wikipedia.org/wiki/Threefold_repetition https://en.wikipedia.org/wiki/Threefold_repetition

thrw21 3y ago
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
- thrw21 3y ago
  https://news.ycombinator.com/item?id=39066345 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
  - jepler 3y ago
    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)

blackboxlogic 3y ago

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.

thrw21 3y ago
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
- Dylan16807 3y ago
  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
  - phire 3y ago
    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.
    - Dylan16807 3y ago
      You would definitely use arithmetic encoding at that point. Then you can directly use fractional bits to encode moves.

lifthrasiir 3y ago

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.

Anotheroneagain 3y ago

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)

317070 3y ago
How would you enforce the three repetitions rule this way?
- Anotheroneagain 3y ago
  I guess you can't do that without the full PGN. I guess the 50 move rule might be extraneous as well.
  - Someone 3y ago
    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.
thrw21 3y ago
My objective was to reduce average size, the example calculation I made is the max size
- Anotheroneagain 3y ago
  My objective was to show that it's quite complicated for dubious gain. What do you think the average would be?

thrw21 3y ago

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)

Anotheroneagain 3y ago
> =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.
Anotheroneagain 3y ago
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.

deleted 3y ago

[deleted]