How to Store a Chess Game in 26 Bytes Using Bit-Level Magic (2022)

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by ThomasCM on Friday September 15, 2023 @12:58PM (#37526033)

Surprisingly, storing a game (with all moves) can take less space than encoding a single board. This is because you can effectively encode a move in a single byte (as there are less than 255 moves possible in each position). Applying compression to the resulting binary string will allow you to reduce the space even more.

Check out this great blog post of Lichess for more information: https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-2...

And shameless plug: Using this encoding, I'm storing millions of games on https://www.chessmonitor.com/ There you can link your Chess.com or Lichess account and view all kind of statistics of your games.

[ Parent | on HN ]

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by seabass-labrax on Friday September 15, 2023 @02:15PM (#37527079)

That is a beautifully designed website. I don't think I've ever used an OAuth authentication flow as smooth as the one that your site uses to access my Lichess credentials (same as my HN name, btw, in case you want to beat me at a correspondence game).

ChessMonitor is practically a work of art!

[ Parent | on HN ]

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by robertlagrant on Friday September 15, 2023 @03:25PM (#37528016)

I created an account just to see that flow, and it did not disappoint! How's it this fast?

[ Parent | on HN ]

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by ThomasCM on Friday September 15, 2023 @04:19PM (#37528627)

Thanks for your feedback!

I guess OAuth is relatively fast as I don't have a middleman (like Auth0) in there. It's just Passport.js.

[ Parent | on HN ]

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by gowld on Friday September 15, 2023 @02:34PM (#37527363)

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?

[ Parent | on HN ]

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by ThomasCM on Friday September 15, 2023 @04:11PM (#37528546)

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.

[ Parent | on HN ]

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by SideQuark on Friday September 15, 2023 @05:13PM (#37529198)

Average game length seems to be around 80 half moves though.

https://chess.stackexchange.com/questions/2506/what-is-the-a...

I'd expect that ordering moves by popularity at each half move index, using say the above dataset, would allow you to select lower indexed values at each step, allowing a nice context based arithmetic compression to really shrink them well.

[ Parent | on HN ]

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by ThomasCM on Friday September 15, 2023 @05:30PM (#37529364)

Yes, in contrast to storing the board (which can be a fixed size), this depends on the length of the game of course.

That said, there are some optimizations you can apply that will compress moves even further (for example the order of the moves as explained in the Lichess blog post is important). In the end it's a tradeoff between (de)serializing the game fast and reducing the size (even more).

[ Parent | on HN ]

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by omoikane on Friday September 15, 2023 @02:53PM (#37527609)

ChessMonitor looks very nice, I like how you can link to a particular opening:

https://www.chessmonitor.com/u/XqaFNTHcR61WpiMfOhEY/games?po...

[ Parent | on HN ]

Re:How to Store a Chess Game in 26 Bytes Using Bit-Level Mag... by foota on Saturday September 16, 2023 @02:34AM (#37532525)

Heh, I guess there are board states that are not possible to reach through a valid sequence of moves, but I guess otherwise it's not possible that games are more compressable by definition, since any valid board state could be represented as a sequence of moves.

This does raise the question of the efficiency of reverse engineering a series of minimal moves for some board state.

[ Parent | on HN ]