4 ms·

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

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).

zeagle 3y ago
Finally, a good use case for blockchain technology!
- r3trohack3r 3y ago
  I can't tell if this is in jest or not but blockchains are prolific in software. Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.
  - l33t7332273 3y ago
    I feel like signatures and maybe even Merkle trees are used, but not blockchain.
  - episteme 3y ago
    Nearly every company, what is your source for that? I've never even heard of this before.
    - deleted 3y ago
      [deleted]
  - flangola7 3y ago
    No, no they do not.
    - r3trohack3r 3y ago
      IIUC a blockchain is a structure where each node has a content addressable hash that includes the hash of the previous node in the chain. If you change any historical node, every subsequent hash is updated. This structure is used inside your .git directory, your docker manifest, etc. Blockchains are incredibly useful structures.
      - deleted 3y ago
        [deleted]
      - JambalayaJim 3y ago
        In context blockchain is referring to a distributed set of hash structures + a consensus algorithm
      - rcxdude 3y ago
        That's a Merkle tree. Blockchains are a Merkle tree plus some form of consensus algorithm, often a trustless one. It's the usefulness of the consensus algorithm which is usually called into question by critics (generally because it's often expensive and cannot reference anything outside the system).
        r3trohack3r 3y ago
        IIUC a merkle tree is a data structure where the leaf nodes are the hashes of data. The inner nodes of the tree are hashes of the child hashes up to a root hash. Merkle trees are helpful for quickly validating the integrity of a chunked file. Both IPFS and BitTorrent use merkle trees to validate files. I do not understand how git could represent its history using a merkle tree.
        nextaccountic 3y ago
        git commits themselves are merkle trees (or more like, DAGs) that contain filesystem trees, a set of parent commits, and metadata each parent commit in turn contains their own parents etc, until you reach an initial commit the funny thing here is that parent commits don't have references to children, it's children that have references to parents (like the union find data structure) so the relationship here is inverted. that's because git objects are immutable
  - zeagle 3y ago
    It was in jest because blockchain is a solution looking for a problem, but as others have pointed out what you say isn't really the case. I'm glad it generated some discussion. Hashing previous steps for verification isn't blockchain.
ThomasCM 3y ago
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-275-improved-game-compression 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/ https://www.chessmonitor.com/ There you can link your Chess.com or Lichess account and view all kind of statistics of your games.
- seabass-labrax 3y ago
  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!
  - robertlagrant 3y ago
    I created an account just to see that flow, and it did not disappoint! How's it this fast?
  - ThomasCM 3y ago
    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.
- gowld 3y ago
  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?
  - ThomasCM 3y ago
TylerE 3y ago
I suspect it would be hard to beat pgn run through a good compression algorithmn. Or similarly essentially a binary version of pgn. Probably the optimalist of optimal is a binary specifying the starting square (6 bits), and then a minimal-width for the specified piece number that indexes against a standard set of move offsets. So, for instance, a knight has (ignoring potential exposed checks, board boundaries, etc, 8 possible moves, so to fully encode a knight move you need 6+3=9 bits. 8 also works for pawns (and annoying due to e.p. 4 doesn't). Bishops, queens, and rooks would need a 4/5 bit field. Encode castling as starting from the rook as they have 'spare' moves in their bit set, and kings don't. Encode the end state at the begining. This is going to use 2 bits for the end state, and then either 9, 10, or 11 bits per move.
- thechao 3y ago
  You only need 5b to encode the piece to move: you know whose turn it is. Also, as the game progresses, you can reindex to reduce the number of bits to define which piece is moving.
  - thaumasiotes 3y ago
    > You only need 5b to encode the piece to move: you know whose turn it is. If you want to encode the piece (rather than the square), and you're comfortable not counting "whose turn is it?" against the information requirement, you don't need 5 bits. Each player has only 16 pieces, so you can give them all four-bit names. You won't know what kind of piece they are, though.
- robertlagrant 3y ago
  > I suspect it would be hard to beat pgn run through a good compression algorithmn. I once[0] tried to spread this message :) [0] https://stackoverflow.com/a/1831841/61938 https://stackoverflow.com/a/1831841/61938
  - TylerE 3y ago
    A standard archiver like 7zip is probably a loss due to the metadata/format headers etc. When your plain text is only a few hundred bytes to start with... I suspect the winner would be something like an LZMA derivative with a fixed dictionary. I doubt not using an adaptive encoder would be a big loss as PGN (exlcuding the metadata) is quite far from random bytes.
esrauch 3y ago
That suggestion seems very reminiscent of the notion that optimally compressing wikipedia is the same problem as what generative LLMs are doing, by virtue of predicting the next letter/word/segment with high precision lets you compress it extremely well. I think for chess you could get most of the benefit with a relatively naive engine; chessbase has a weak engine built in where you can hit space bar and it does a move which is incredibly useful since there's just one obvious move for a lot of positions anyway; if the move was especially tricky/nonobvious than it's also not what you would want when hitting spacebar to just predictably proceed anyway).
dang 3y ago
Ok, we've positioned the title above. Thanks!
- kurinikku 3y ago
  Thank you!

zeagle 3y ago

Finally, a good use case for blockchain technology!

r3trohack3r 3y ago
I can't tell if this is in jest or not but blockchains are prolific in software. Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.
- l33t7332273 3y ago
  I feel like signatures and maybe even Merkle trees are used, but not blockchain.
- episteme 3y ago
  Nearly every company, what is your source for that? I've never even heard of this before.
  - deleted 3y ago
    [deleted]
- flangola7 3y ago
  No, no they do not.
  - r3trohack3r 3y ago
    IIUC a blockchain is a structure where each node has a content addressable hash that includes the hash of the previous node in the chain. If you change any historical node, every subsequent hash is updated. This structure is used inside your .git directory, your docker manifest, etc. Blockchains are incredibly useful structures.
    - deleted 3y ago
      [deleted]
    - JambalayaJim 3y ago
      In context blockchain is referring to a distributed set of hash structures + a consensus algorithm
    - rcxdude 3y ago
      That's a Merkle tree. Blockchains are a Merkle tree plus some form of consensus algorithm, often a trustless one. It's the usefulness of the consensus algorithm which is usually called into question by critics (generally because it's often expensive and cannot reference anything outside the system).
      - r3trohack3r 3y ago
        IIUC a merkle tree is a data structure where the leaf nodes are the hashes of data. The inner nodes of the tree are hashes of the child hashes up to a root hash. Merkle trees are helpful for quickly validating the integrity of a chunked file. Both IPFS and BitTorrent use merkle trees to validate files. I do not understand how git could represent its history using a merkle tree.
        nextaccountic 3y ago
        git commits themselves are merkle trees (or more like, DAGs) that contain filesystem trees, a set of parent commits, and metadata each parent commit in turn contains their own parents etc, until you reach an initial commit the funny thing here is that parent commits don't have references to children, it's children that have references to parents (like the union find data structure) so the relationship here is inverted. that's because git objects are immutable
- zeagle 3y ago
  It was in jest because blockchain is a solution looking for a problem, but as others have pointed out what you say isn't really the case. I'm glad it generated some discussion. Hashing previous steps for verification isn't blockchain.

ThomasCM 3y ago

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-275-improved-game-compression 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/ https://www.chessmonitor.com/ There you can link your Chess.com or Lichess account and view all kind of statistics of your games.

seabass-labrax 3y ago
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!
- robertlagrant 3y ago
  I created an account just to see that flow, and it did not disappoint! How's it this fast?
- ThomasCM 3y ago
  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.
gowld 3y ago
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?
- ThomasCM 3y ago

TylerE 3y ago

I suspect it would be hard to beat pgn run through a good compression algorithmn. Or similarly essentially a binary version of pgn. Probably the optimalist of optimal is a binary specifying the starting square (6 bits), and then a minimal-width for the specified piece number that indexes against a standard set of move offsets. So, for instance, a knight has (ignoring potential exposed checks, board boundaries, etc, 8 possible moves, so to fully encode a knight move you need 6+3=9 bits. 8 also works for pawns (and annoying due to e.p. 4 doesn't). Bishops, queens, and rooks would need a 4/5 bit field. Encode castling as starting from the rook as they have 'spare' moves in their bit set, and kings don't. Encode the end state at the begining. This is going to use 2 bits for the end state, and then either 9, 10, or 11 bits per move.

thechao 3y ago
You only need 5b to encode the piece to move: you know whose turn it is. Also, as the game progresses, you can reindex to reduce the number of bits to define which piece is moving.
- thaumasiotes 3y ago
  > You only need 5b to encode the piece to move: you know whose turn it is. If you want to encode the piece (rather than the square), and you're comfortable not counting "whose turn is it?" against the information requirement, you don't need 5 bits. Each player has only 16 pieces, so you can give them all four-bit names. You won't know what kind of piece they are, though.
robertlagrant 3y ago
> I suspect it would be hard to beat pgn run through a good compression algorithmn. I once[0] tried to spread this message :) [0] https://stackoverflow.com/a/1831841/61938 https://stackoverflow.com/a/1831841/61938
- TylerE 3y ago
  A standard archiver like 7zip is probably a loss due to the metadata/format headers etc. When your plain text is only a few hundred bytes to start with... I suspect the winner would be something like an LZMA derivative with a fixed dictionary. I doubt not using an adaptive encoder would be a big loss as PGN (exlcuding the metadata) is quite far from random bytes.

esrauch 3y ago

That suggestion seems very reminiscent of the notion that optimally compressing wikipedia is the same problem as what generative LLMs are doing, by virtue of predicting the next letter/word/segment with high precision lets you compress it extremely well. I think for chess you could get most of the benefit with a relatively naive engine; chessbase has a weak engine built in where you can hit space bar and it does a move which is incredibly useful since there's just one obvious move for a lot of positions anyway; if the move was especially tricky/nonobvious than it's also not what you would want when hitting spacebar to just predictably proceed anyway).

dang 3y ago

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

kurinikku 3y ago
Thank you!