The article itself doesn't arrive at the correct number of 5898 moves, but some of the commenters do. At my own page http://tromp.github.io/chess/longest.html you can play through a 3-moves-shorter game.
"Chess program" has to be defined in a way the general audience can agree to. Many people could also code a non-chess implementation in much less than 487 bytes and call it chess.
It still looks like an impressive exercise, but any talk of broken records demands widely accepted set of rules that have been met.
These 'minimal chess' programs trace their lineage (and mostly their rules) back to ZX Chess [0] for the ZX81, which was a significant accomplishment, and remains notable in the history of personal computing, cropping up from time to time in lists of the greatest program ever written. It says this at the top of the page.
It is not a naive prototype. I'd be very surprised if the programmer couldn't play chess. It's a part of computing history. And the competition to reduce the number of bytes is > 35 years old.
Seems like longest chess game is about less than 300 turns, there are 64 cells, and even if you don't know chess, and even without efficiently coded there are max of 128bits per turn (a lot of them not valid, and probably space that can be explored better) - e.g. it feels like not only the current position, but the history can be recorded in small amount of data in an URL.
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.
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.
...but I was more impressed by the Atari 2600 chess game which had castling and en passant. Having 256 bytes seems like a good excuse to leave out such nonsense.
FTA: “But they don’t account for the majority of what I’m storing, which are PGNs.”
If they’re storing chess games, why do they try to compress individual moves?
If you compress games, you can get much better compression. For example, in any board position, deterministically order all legal moves (they’re already ignoring some illegal moves in their setup, so I think ignoring all is within the rules of the game), and write down the number of the move made.
At game start, that will be an integer between 1 and 20 (16 different pawn moves, 4 different knight moves). Black’s reply similarly will be an integer between 1 and 20. For white’s second move, the maximum will depend on the first move.
To compress an entire game, use arithmetic encoding (https://en.wikipedia.org/wiki/Arithmetic_coding). If there are, on average, n legal moves per position, that will use 2log n bits per move.
https://www.chessprogramming.org/Chess_Position: “The maximum number of moves per chess position seems 218”, so that will give you less than 8 bits per move. In real life, it probably will be less than 6.
The only reason I see why this wouldn’t be an option is performance. Decoding would require move generation and thus be more complex.
To improve on that, make a deterministic predictor of how likely moves are and use that to improve on the arithmetic encoder. That probably isn’t worth it, though because of the increased decoding complexity.
Fitting a chess game state in 128 bytes is for sure doable; what is really impressive is being able to use the same memory not just for the current position, but also to compute the next moves in a decent way.
This is a great example of how you can trade time for space. There’s no reason you couldn’t do the same thing for chess, except it would take, er, quite a bit of disk space…
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.
reply