Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to store a chess position in 26 bytes using bit-level magic (2022)

ezzeriesa.com

Post reply on HN
Print view View original

151–160 of 204 posts

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#151

Post by verteu »

jiggawatts wrote: post #148

People have pointed out that due to rules about no repeats, the full state requires storing previous moves. I’m fairly convinced that the most efficient encoding would be keeping only the move history and then playing that forward to obtain the board state. E.g.: there are only 32 distinct pieces so a 5-bit number can select one uniquely. Each piece has a maximum of about 32 positions it can move to. Then the encodin…

I agree with this for a typical-length game. But I'd guess its worst-case is inferior due to some pathologically long games.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#152

Post by ComplexSystems »

You can get this even lower, without the need for the extra promotion bits, if you make a note of a few things:

1. There is still redundancy in that there are multiple pieces of the same type, and if you permute their locations you get another representation of the same state. 2. You don't need to say that some pawn's location is the king if it's en passant. You can just use the back row, which pawns can't get to.

Using this, you can use the permutations of the pawns to store extra information. For instance, all of the pawns will be on the board at squares #a, #b, ... . Since pawns themselves have numerical indices, you could say that the "canonical" representation of the board state has all of the pawn locations sorted in ascending order. Then, different permutations of that can carry information about promotions and which of the "pawns" are really queens, etc.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#153

Post by dang »

Scarblac wrote: post #10

Storing a chess position in 26 bytes. Storing a game is also interesting. The number of legal moves varies depending on the position. You could try to define a variable length encoding by giving more likely moves a shorter encoding, but the ordering would need to be deterministic so it could be decoded (running Stockfish for a second isn't).

Ok, we've positioned the title above. Thanks!

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#154

Post by mlyle »

Dylan16807 wrote: post #149
alexb_ wrote: post #147

Earlier quoted context omitted.

That's just not true. Pawns can only be captured en passant on one rank for each color.

Yes for each color . That means two pawns for each column can be in position to be captured en passant. And also two pawns can be in capturing position. Edit: Column combined with whose turn it is will work, but not just column.

Part of a chess position is whose turn to move. That has to be encoded anyways.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#155

Post by JoshuaDavid »

Dylan16807 wrote: post #124
JoshuaDavid wrote: post #78

Minor point: the FIDE rules[1] state > Article 9: The Drawn Game > ... > 9.2 The game is drawn, upon a correct claim by a player having the move, when the same position for at least the third time (not necessarily by a repetition of moves) [happens and a draw is claimed] > 9.3 The game is drawn, upon a correct claim by a player having the move, if: ... 9.3.2 the last 50 moves by each player have been completed withou…

If a pawn moves then you can't repeat a state either, can you? So track the last 75 "moves". > they can only move forward, except in the case of en-passant En passant still attacks forward, into the space the enemy pawn just moved through. > 112 pawn moves without a capture (because there are only 16 pawns and they can only move forward But pawns can't move through pawns. ~~At most I think you can have 4 of the pawns…

> If a pawn moves then you can't repeat a state either, can you? So track the last 75 "moves".

You are correct.

So the board state from 75 moves previously plus 75 bytes to store the last 75 moves is sufficient to store a chess game state.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#156

Post by paxys »

jiggawatts wrote: post #148

People have pointed out that due to rules about no repeats, the full state requires storing previous moves. I’m fairly convinced that the most efficient encoding would be keeping only the move history and then playing that forward to obtain the board state. E.g.: there are only 32 distinct pieces so a 5-bit number can select one uniquely. Each piece has a maximum of about 32 positions it can move to. Then the encodin…

As the game goes on the space needed to store the list of moves increases while space needed to store a snapshot of the board decreases. It would be interesting to figure out where on average the strategies meet.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#157

Post by kurinikku »

dang wrote: post #153
Scarblac wrote: post #10

Storing a chess position in 26 bytes. Storing a game is also interesting. The number of legal moves varies depending on the position. You could try to define a variable length encoding by giving more likely moves a shorter encoding, but the ordering would need to be deterministic so it could be decoded (running Stockfish for a second isn't).

Ok, we've positioned the title above. Thanks!

Thank you!

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#158

Post by chipsrafferty »

ThomasCM wrote: post #136
gowld wrote: post #114

Earlier quoted context omitted.

Are you saying that, to encode a valid position, ignoring the cost to encode both the starting position and the move definitions, you can encode the move sequence using less information than encoding a single position?

Yes, ignoring compression each (half-)move takes up one byte. So if you want to store a sequence of 10 (half-)moves it would take only 10 bytes.

It seems, then, if you wanted to efficiently store lots of positions, it would be smart to store a large list of openings, a large list of following sequences, and then your positions can be stored as a list of sequence ids.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#159

Post by Dylan16807 »

mlyle wrote: post #154
Dylan16807 wrote: post #149

Earlier quoted context omitted.

Yes for each color . That means two pawns for each column can be in position to be captured en passant. And also two pawns can be in capturing position. Edit: Column combined with whose turn it is will work, but not just column.

Part of a chess position is whose turn to move. That has to be encoded anyways.

I guess, but the article wasn't trying to do so.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#160

Post by jiggawatts »

verteu wrote: post #151
jiggawatts wrote: post #148

People have pointed out that due to rules about no repeats, the full state requires storing previous moves. I’m fairly convinced that the most efficient encoding would be keeping only the move history and then playing that forward to obtain the board state. E.g.: there are only 32 distinct pieces so a 5-bit number can select one uniquely. Each piece has a maximum of about 32 positions it can move to. Then the encodin…

I agree with this for a typical-length game. But I'd guess its worst-case is inferior due to some pathologically long games.

Yes, but pathological games are statistically rare. At scale, the average is what matters…
Post reply on HN