4 ms·

A dual to this is: how can you encode chess games in the smallest number of bits? A move has one of 64 source squares and one of 64 destination squares, so tha

A dual to this is: how can you encode chess games in the smallest number of bits? A move has one of 64 source squares and one of 64 destination squares, so that suggests a naive way to encode games using 12 bits per move. However, there are never more than 256 legal moves in any position, so we can improve on this by listing the legal moves in some reproducible order, then using 8 bits to pick one of them. Of course most positions have far fewer than 256 legal moves. And some moves are more likely than others. So we can improve on this for real chess games (though not for random chess noise or the output of the chess steganography program in non-blunderfree mode) by sorting the moves in order of decreasing likelihood and doing some Huffman encoding so more likely numbers get shorter encodings. "Order of decreasing likelihood" is not trivial to define - even using a deterministic chess engine with a large depth would not necessarily be optimal, even putting aside performance concerns. The state of the art in this is almost certainly the version used by Lichess https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-275-improved-game-compression https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-2....

gpm 8y ago
> and doing some Huffman encoding so more likely numbers get shorter encodings. Once you get a probability distribution over the moves, arithmetic encoding is the provably best (densest) way to encode them.
billforsternz 8y ago
I published a blog post on this https://triplehappy.wordpress.com/2015/10/26/chess-move-compression/ https://triplehappy.wordpress.com/2015/10/26/chess-move-comp... when I worked on the problem for my own chess GUI, it got some traction on hacker news. Funnily the Lichess blog post about their algorithm links to my article. Those guys are clearly much smarter than me - they jump straight to the optimal scheme without the painstaking exposition (and thinking) I needed :-) Basically about 2 bits per move is the best you can hope for, with aggressive and slow compression.
rjf72 8y ago
I'm not entirely understanding the motivation for this. The most naive method would be to just UCI move notation, that's simply square1-square2. Eg: e2e4 e7e5 g1f3, etc. That's 4 bytes per half move or ply (5 bytes for the once in a blue moon promotion). At an average of 80 ply per game, that's 320 bytes per game notation. So if we have a billion games that'd just be 320GB. And as you mention converting this to binary yields 6 bits per ply, for a fraction of that. In other words you could naively encode every single game that's ever been played online, offline, or anywhere for a small fraction of the space on a regular large consumer HDD and still have plenty of space left for centuries of games to come. 20TB RAID kits go for less than $1k now a days. And you could load critical (likely to be accessed multiple times and/or concurrently) games (every game ever played by a very strong player, all games within the past year, etc) on a single SSD for rapid access. Of course saving space is much better than not saving space, but the proposed method does not come for free. It involves some fairly complex heuristics. That means you're trading space for computational complexity. The former is practically free for things on this scale, but the latter very much is not. The article mentions that their decoder was only able to process around 1,111 games per second on average. Lichess has been pushing around 40k players at some times and will presumably continue to grow. Performance this low on a critical and invokable task also seems to expose a clear denial-of-service vector. And adding new servers is vastly more expensive than adding some new hard disks. By contrast encoding and decoding games in UCI is practically free. So what is the motivation here?
- dmurray 8y ago
  Agreed, I don't see the practical benefit here either, it's mostly interesting to me from an academic point of view. But we are after all in a thread about something with even less crowded practical value, hiding messages in constructed chess games.
- p1necone 8y ago
  Writing chess software as a hobby is relatively popular. And many people try to optimize as much as possible even when it's not strictly necessary. That's probably motivation enough - although lichess as a business probably doesn't have the same incentives as a hobbyist would.

gpm 8y ago

> and doing some Huffman encoding so more likely numbers get shorter encodings. Once you get a probability distribution over the moves, arithmetic encoding is the provably best (densest) way to encode them.

billforsternz 8y ago

I published a blog post on this https://triplehappy.wordpress.com/2015/10/26/chess-move-compression/ https://triplehappy.wordpress.com/2015/10/26/chess-move-comp... when I worked on the problem for my own chess GUI, it got some traction on hacker news. Funnily the Lichess blog post about their algorithm links to my article. Those guys are clearly much smarter than me - they jump straight to the optimal scheme without the painstaking exposition (and thinking) I needed :-) Basically about 2 bits per move is the best you can hope for, with aggressive and slow compression.

rjf72 8y ago

I'm not entirely understanding the motivation for this. The most naive method would be to just UCI move notation, that's simply square1-square2. Eg: e2e4 e7e5 g1f3, etc. That's 4 bytes per half move or ply (5 bytes for the once in a blue moon promotion). At an average of 80 ply per game, that's 320 bytes per game notation. So if we have a billion games that'd just be 320GB. And as you mention converting this to binary yields 6 bits per ply, for a fraction of that. In other words you could naively encode every single game that's ever been played online, offline, or anywhere for a small fraction of the space on a regular large consumer HDD and still have plenty of space left for centuries of games to come. 20TB RAID kits go for less than $1k now a days. And you could load critical (likely to be accessed multiple times and/or concurrently) games (every game ever played by a very strong player, all games within the past year, etc) on a single SSD for rapid access. Of course saving space is much better than not saving space, but the proposed method does not come for free. It involves some fairly complex heuristics. That means you're trading space for computational complexity. The former is practically free for things on this scale, but the latter very much is not. The article mentions that their decoder was only able to process around 1,111 games per second on average. Lichess has been pushing around 40k players at some times and will presumably continue to grow. Performance this low on a critical and invokable task also seems to expose a clear denial-of-service vector. And adding new servers is vastly more expensive than adding some new hard disks. By contrast encoding and decoding games in UCI is practically free. So what is the motivation here?

dmurray 8y ago
Agreed, I don't see the practical benefit here either, it's mostly interesting to me from an academic point of view. But we are after all in a thread about something with even less crowded practical value, hiding messages in constructed chess games.
p1necone 8y ago
Writing chess software as a hobby is relatively popular. And many people try to optimize as much as possible even when it's not strictly necessary. That's probably motivation enough - although lichess as a business probably doesn't have the same incentives as a hobbyist would.