3 ms·

What about bishops? The bishops are limited to half the board so only need 5 bits for position. This frees up 4 bits, but you lose the capture state (can't use

by aimor 3y ago

What about bishops? The bishops are limited to half the board so only need 5 bits for position. This frees up 4 bits, but you lose the capture state (can't use King's position for capture state). Well, you CAN use the king's position for capture state for two of the bishops at any given time. Then for the other two bishops use a bit to store their capture state. This saves 2 bits overall, bringing the total down to exactly 26 bytes. Gonna have to think that through for awhile, not sure if it works out. Update: I see a comment below that does this but uses 21 bits (instead of 22) by storing bishop position and capture state as a base-33 number.

NextHendrix 3y ago
It's possible to gain bishops via promotion which may scupper this plan
aimor 3y ago
Trying to strike a balance between raw enumerations of all valid states and practicality: Rooks and Knights are identical, so their positions fall into [64 choose 2] states + 1 state for when both are captured (only one can occupy the King's location) + 3 states for when both are in the starting position and castling is available for one or the other or both 2020 states = 11 bits * 2 colors * 2 piece types = 44 bits Bishops only occupy half the board (32 states) + 1 state to track captures 33 states ^ (4 unique pieces) = 21 bits Queens and Kings just store their location 64 states = 6 bits * 4 pieces = 24 bits Pawn promotions uses the same method as the article 9 bits x 2 colors = 18 bits En passant can be stored by the column + 1 state for none 9 states = 4 bits Pawns can be in, uh, [64 choose 8] position states. (It's only 4 billionish) [64 choose 8] states = 32 bits * 2 colors = 64 bits And captured pawns can be 'unpromoted' and placed on an empty spot in the top row since unpromoted pawns will never be there. And 1 bit for whose turn it is 1 bit Total = 176 bits or 22 bytes Started out thinking about ways to use more of the duplicate pieces, rediscovered the idea of ranking and unranking, started to understand what the person with a limit of 19.2 bytes was doing, tried out just treating position state as [64 choose 32] and only got to 194 bits, then finally worked through this approach.

by aimor 3y ago

NextHendrix 3y ago

It's possible to gain bishops via promotion which may scupper this plan

aimor 3y ago

Trying to strike a balance between raw enumerations of all valid states and practicality: Rooks and Knights are identical, so their positions fall into [64 choose 2] states + 1 state for when both are captured (only one can occupy the King's location) + 3 states for when both are in the starting position and castling is available for one or the other or both 2020 states = 11 bits * 2 colors * 2 piece types = 44 bits Bishops only occupy half the board (32 states) + 1 state to track captures 33 states ^ (4 unique pieces) = 21 bits Queens and Kings just store their location 64 states = 6 bits * 4 pieces = 24 bits Pawn promotions uses the same method as the article 9 bits x 2 colors = 18 bits En passant can be stored by the column + 1 state for none 9 states = 4 bits Pawns can be in, uh, [64 choose 8] position states. (It's only 4 billionish) [64 choose 8] states = 32 bits * 2 colors = 64 bits And captured pawns can be 'unpromoted' and placed on an empty spot in the top row since unpromoted pawns will never be there. And 1 bit for whose turn it is 1 bit Total = 176 bits or 22 bytes Started out thinking about ways to use more of the duplicate pieces, rediscovered the idea of ranking and unranking, started to understand what the person with a limit of 19.2 bytes was doing, tried out just treating position state as [64 choose 32] and only got to 194 bits, then finally worked through this approach.