Live data from Hacker News

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

ezzeriesa.com

71–80 of 204 posts

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

#71

Earlier quoted context omitted.

Not all previous positions, only the ones with the same pieces, pawn positions, castling rights and en passant rights. But the standard, FEN, doesn't store that either. It's used more in the context of a full game than with individual positions.

Fair enough. Still up to 50 board states that can influence the current one (the 50 move rule is coming to help here) FEN doesn't store previous states, but EPD can. It just goes to show how meanings and requirements change depending on context, which is super interesting in and of itself :P

Also, database software gets so clever with storing games that they often can't save games that have illegal moves in them. But there are plenty real games from real tournaments that had illegal moves in them that nobody noticed...

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

#72
post #68
post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

A nitpic, to castle, the king AND the rook must not have moved from their starting squares. Using this approach, you would need to store castling available/unavailable for the kings as well.

If the king has moved, you can just mark both rooks as castling unavailable.

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

#73
post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

A position, as stored in FEN notation, also includes side-to-move.

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

#74
post #68
post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

A nitpic, to castle, the king AND the rook must not have moved from their starting squares. Using this approach, you would need to store castling available/unavailable for the kings as well.

No you don't. If the king moves, you update both rooks to be unavailable for castling.

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

#75
post #5

Meanwhile the non-comp-sci dev in me is like, "why not just store every position in a simple JSON so everyone can read it and everything can parse it". Yeah, it might be half a kB, but you don't have to run through mental gymnastics just to render the pieces...

Now try building a chess site to store millions of games with hundreds of millions of game states to search over. It's nice that you can very cheaply fit a board into a fixed size column on a database and store the entire game history into around a kilobyte.

You'd write a wrapper to extract our the dense form to something with a nice interface.

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

#77
The state of an individual chess piece can be stored in 6 bits. 3 bits for the X coordinate, 3 bits for the Y coordinate.

A captured piece can use the same coordinates as the King, which would indicate that it's captured.

For promoted pieces, you can use 3 bits per promoted piece type (Bishop, Rook, Knight, Queen) to indicate how many exist. For the case of 8 promoted pawns, you'd need one more bit to indicate that all pawns have been promoted and to treat a 7 as an 8.

You need 1 bit to indicate who's turn it is. You need 1 bit per player to indicate if castling is still possible, and 1 bit to indicate if the last pawn move was two squares.

What gets tricky is tracking for the draw rules.

There's '50 moves with no pawn or capture', '3 move repetition', '5 move repetition', '75 moves with no capture or pawn move'. 50 or 75 are simple enough to count, but tracking identical boards from a previous state would be hard to do with limited bits.

So then we have:

6 bits for piece coordinates of 32 pieces (192 bits)

13 bits for pawn promotion status for each player (26 bits)

1 bit per player for castling allowed (2 bits)

1 bit for whose turn

1 bit for en-passant possible

7 bits for move counter with no pawn movement or captures

That works out to 29 bytes.

Edit: Article did promotions much better by removing impossible promoted piece counts.

'Castling allowed' flag could be tied to 'both rooks in their original positions'. If the pieces look like they're in their original positions, but a king or rook moved, swap the two rooks so they're not in the original position anymore.

En-passent check by swapping pawn order is neat, but pawn order could instead be used to eliminate the 'promoted' flag per pawn instead.

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

#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 without the movement of any pawn and without any capture.

> ...

> 9.6 If one or both of the following occur(s) then the game is drawn:

> 9.6.1 the same position has appeared, as in 9.2.2 at least five times.

> 9.6.2 any series of at least 75 moves have been made by each player without the movement of any pawn and without any capture. If the last move resulted in checkmate, that shall take precedence.

This means that, in order to store a full chess game-state, you also need to keep track of how many moves since the last pawn move or capture (for the 50 and 75 move rule (9.3.2 and 9.6.2 respectively)) and also what positions have previously occurred (for the 3 / 5 position repeats, (9.2 and 9.6.1 respectively)).

The maximum number of moves from any chess position is 218 according to this post[2], so each move in the history can be uniquely identified by a single byte. You only need to store the moves since the last capture (since you can't repeat an earlier position), and you _definitely_ can't have more than 112 pawn moves without a capture (because there are only 16 pawns and they can only move forward, except in the case of en-passant which requires a different pawn to move forward twice).

But that gives an upper bound of 8400 moves -- this bound is probably much higher than it needs to be though.

----

[1] https://handbook.fide.com/chapter/E012023

[2] https://www.chess.com/forum/view/fun-with-chess/what-chess-p...

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

#79
post #68
post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

A nitpic, to castle, the king AND the rook must not have moved from their starting squares. Using this approach, you would need to store castling available/unavailable for the kings as well.

[deleted]

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

#80
post #5

Meanwhile the non-comp-sci dev in me is like, "why not just store every position in a simple JSON so everyone can read it and everything can parse it". Yeah, it might be half a kB, but you don't have to run through mental gymnastics just to render the pieces...

In the early 90ies, we used to have pocket electronic chess games. I used to have myself one that was about the size of a pocket calculator (it actually was also a pocket calculator), which included a tiny board with tiny, tiny chess pieces. Not a strong opponent and quite slow, but good enough for casual games on the road.

I doubt you could fit that JSON file in its NVRAM. Sometimes I wonder how much sooner we could have had what smartphones offer us today if some technical choices had been made more... wisely.

But that's the endless conundrum Worse is better [1].

[1] https://dreamsongs.com/RiseOfWorseIsBetter.html

Post reply on HN