Hacker News Reader

thrw21on Lowercase letters save data

  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

thrw21on Lowercase letters save data

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

thrw21on Lowercase letters save data

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)

thrw21on Lowercase letters save data

  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

thrw21on Lowercase letters save data

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

thrw21on Lowercase letters save data

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

thrw21on Lowercase letters save data

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

thrw21on Lowercase letters save data

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

thrw21on Lowercase letters save data

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!

thrw21on Lowercase letters save data

  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.

thrw21on Lowercase letters save data

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

thrw21on Lowercase letters save data

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