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.
I'd be interested in the shortest word that can't be encoded in the "one-sided" mode when playing against a strong AI. I played Stockfish as white while having black try to encode "hello" but Stockfish was able to checkmate black before it had finished.
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.
I published a blog post on this 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.
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.
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.
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.
Sure I completely get that, but what the core issue I was hitting on is that you end up trading an expensive resource (computing power) for a very cheap resource (disk space). In cases where disk space requirements become enormous this can be a necessary trade, but here that's not really an issue. I enjoy not strictly necessary optimization as much as anybody, but unless I'm missing something this optimization seems that it would ultimately result in a less performant system with very little to show for it so it wouldn't be particularly fair to call it an optimization.
Ah yes, but this way you get to write compression algorithms and do performance optimization. The journey is more important than the destination.
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.
this is really cool on so many levels - this could lead to a general turn based game playing steganography - like go, poker etc? just need a little more time :)
This is pretty fun. You might run into a useless result, such as "Hi, I'd like to buy some weed." without blunders translating to a 369 move game, but if you have the freedom to experiment with minor variations, you can find one that works. "Hi, I'd like to buy some weed" is only 41 moves.
So, I'd don't have a board readily available and don't know the notation to well. But does "resign" mean give up in this context? Would it be possible to make this actually run into chess mates at the end of the message?
I wonder if theres an anti steganography move pattern to obfuscate your opponents move.
Or do you just win quickly to avoid them sending a useful message?
I've just tried to unsteg one of my real games to find out if I had anything smart to say, but got "chess-steg.js:139 Uncaught URIError: URI malformed"
Yeah... I had thought that this would be a good way to share messages secretly, but the thing is the moves are nonsensical, so anyone who bothered to check out what the game progresses would know something is up and would google "Chess message encoding" (the fifth result is the blog post for it, lol).
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.
What you describe is exactly what the "without blunders" mode attempts to do, but evaluating every possible move for each player to a useful search depth takes a long time, so it doesn't search very far.
Also, the more you restrict the space of allowable moves, the more moves are required to encode a given message.
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.