thrw21

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

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)

  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

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

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

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

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!

  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.

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

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