Chess Steganography
incoherency.co.uk
incoherency.co.uk
It lets you interactively encode a message in your moves when playing against a player who is not in cahoots with you :)
(Disclosure: I made this).
And yeah, sorry about the lack of error-checking. If pretty much anything goes wrong it (maybe) writes an error to the console, and just does nothing.
I'd be interested to see if anybody can produce a short message which can't be encoded because it results in a state where the only legal moves are checkmate.
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-2....
Once you get a probability distribution over the moves, arithmetic encoding is the provably best (densest) way to encode them.
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?
Edit: Also (in Lichess' case) you're not trading CPU usage for disk space, you're trading CPU usage for disk space and network traffic, which you're probably paying much more for.
Small nitpick: I wanted to see the "hidden message" in The Game of the Century[0], but it says the last move is illegal:
Illegal move played?? Rc2#
Yes.
ps- got a cors issue on the “view on lichess”
If the moves actually made sense, this would be a lot more useful. There's probably something that can measure how good a move is, so I guess what you can do is make sure that the moves you use to form a message are above a certain threshold. That way, someone looking into the moves wouldn't immediately know that they're being used to encrypt messages. But honestly other than that, I dunno what you can use it for.
Also, the more you restrict the space of allowable moves, the more moves are required to encode a given message.
By the way, what was your motivation for creating this?