6 ms·

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 fi

by Tommah 3y ago

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.

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!
lifthrasiir 3y ago
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 https://stackoverflow.com/a/66345772 [2] https://old.reddit.com/r/chess/comments/o4ajnn/whats_the_most_possible_legal_moves_in_a_chess/ https://old.reddit.com/r/chess/comments/o4ajnn/whats_the_mos... [3] https://triplehappy.wordpress.com/2015/10/26/chess-move-compression/ https://triplehappy.wordpress.com/2015/10/26/chess-move-comp...

by Tommah 3y ago

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!

lifthrasiir 3y ago

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 https://stackoverflow.com/a/66345772 [2] https://old.reddit.com/r/chess/comments/o4ajnn/whats_the_most_possible_legal_moves_in_a_chess/ https://old.reddit.com/r/chess/comments/o4ajnn/whats_the_mos... [3] https://triplehappy.wordpress.com/2015/10/26/chess-move-compression/ https://triplehappy.wordpress.com/2015/10/26/chess-move-comp...