News for hackers. Stuff that matters.
Re:Compressing Chess Moves for Fun and Profit by tromp on Friday March 15, 2024 @01:04PM (#39717990)
The optimum compression seems to be an index into the list of all legal moves.

But one can do better on average, by assuming that moves are not uniformly distributed. Let an engine assign each legal move m some probability p of being played. The worse the move, the lower the probability we assign to it. Then a more optimal code for move m is -log p bits, corresponding to an entropy (expected surprise) of sum -p log p bits for the distribution over legal moves.

Related: accurately estimating the number of legal positions of chess [1].

[1] https://github.com/tromp/ChessPositionRanking

Re:Compressing Chess Moves for Fun and Profit by perihelions on Friday March 15, 2024 @02:00PM (#39718730)
Though, that engine evaluation is going to be absurdly expensive, when you're compressing/decompressing billions of games.

I think everyone's optimizing the wrong thing! The size of a useful, real-world chess database would be dominated by its search indexes—indexes that allow fast, random-access lookup of every position that occurs in every game. (Or even better: fuzzy searching for nearby, "similar" positions). This is the difficult, open-ended algorithmic problem. Disk space is cheap!

(Out of curiosity, does anyone here actually know how to solve the "fuzzy search of chess positions" problem?)

Re:Compressing Chess Moves for Fun and Profit by koolba on Friday March 15, 2024 @03:27PM (#39719728)
> Out of curiosity, does anyone here actually know how to solve the "fuzzy search of chess positions" problem?

A classification based indexing would help here. The data points of the index would be not just the position of the pieces, but their relative as well. Things like the squares under attack, pinned weaker pieces, and maybe some evaluation of control of the board (again maybe via some attacking based metric).

This seems like the kind of thing that could be done by analyzing a larger dataset of games to create a set of functional categorizations.

Once the data points themselves have been identified, actually indexing them is the easy part.

Solving this more generally for the “find me games like X…” is much trickier without locking down that X to something concrete.

Re:Compressing Chess Moves for Fun and Profit by perihelions on Friday March 15, 2024 @03:55PM (#39719995)
For example: "this position, but a few of the pieces can be in different places". (Maybe penalizing pawn moves with a higher weight—a pawn move is in practice a "larger change" to a position than a piece move).

This version is easy to formalize: it's just querying a bitstring x \in {0,1}^N, a bitboard vector representation of a chess position, and asking if there's any other needles within a short Hamming distance. I haven't a clue how to solve that (or if it's solvable at all).

Re:Compressing Chess Moves for Fun and Profit by kevindamm on Friday March 15, 2024 @11:47PM (#39723212)
I wonder if shingle hashes might help a lot here...

https://en.wikipedia.org/wiki/MinHash

Re:Compressing Chess Moves for Fun and Profit by alfalfasprout on Friday March 15, 2024 @02:36PM (#39719150)
Agreed. Ultimately, the most common reason for needing to store a bunch of games is you want a chess database so you can look up a given position.

So probably some kind of tree structure so you can look up games by sequence of moves since opening. And something like zobrist hashing for looking up a given position (regardless of sequence).

Some of these ultra-small encodings would be counterproductive for this purpose.

Re:Compressing Chess Moves for Fun and Profit by perihelions on Friday March 15, 2024 @02:52PM (#39719333)
- "And something like zobrist hashing for looking up a given position"

Which gets particularly good if you combine it with some hack like a Bloom filter. There's a trick, I don't remember if it has a name, where you can effect a time/space tradeoff by partitioning a search set and building a separate Bloom filter for each partition. A lookup is a constant-time query of each Bloom filter, plus a linear scan of each partition that signaled a match.

(This is a reasonable thing to do, because (0) the size of chess databases can get extremely large and (1) the queries are human UX interactions that need to be responsive).

Re:Compressing Chess Moves for Fun and Profit by alfalfasprout on Friday March 15, 2024 @03:12PM (#39719588)
I mean, chess engines use transposition tables to store encountered positions. In this case you can use the zobrist hash as the index to a hash table and it's an O(1) lookup for a given position.

Typically that's going to be the best way to index into full games. Since you can point to an entry via a game tree search (eg; each node of the tree is a position that you can use as an index to a big transposition table).

You can probably use a bloom filter to check if a given position has ever been encountered (eg; as a layer on top of the transposition table) though. For something like storing 10 billion positions w/ a 10^-6 false positive probability (w/ reasonable number of hashes) you're looking at 30+GiB bloom filters.

Re:Compressing Chess Moves for Fun and Profit by perihelions on Friday March 15, 2024 @03:30PM (#39719750)
Right! The hash table you're describing is O(1) lookup, but its memory size is a constant multiple larger than the Bloom filter. A Bloom filter doesn't tell you anything about where the needle is–only whether the needle exists; so, if used for lookup, it reduces to O(n) brute-force search. In between the two, you can create an array of M partitions of the haystack, each with their own Bloom filter: this structure has something like O(M + n/M) lookup, but with the smaller memory size of the Bloom filter.

When I implemented this, I deliberately avoided constructing the hash table you're describing, because (to my recollection) it was larger than my remaining disk space! :)

Re:Compressing Chess Moves for Fun and Profit by ant6n on Friday March 15, 2024 @02:09PM (#39718852)
You just need to enumerate for all possible states, the possible transitions and evaluate the probabilities for them. How many could there possibly be? Store in a small database and look em up on the fly. Easy peasy.
Re:Compressing Chess Moves for Fun and Profit by anonymous-panda on Friday March 15, 2024 @02:37PM (#39719175)
I know you’re joking, but it wouldn’t really be that hard in terms of a lookup for played positions which is what OP asked for - you could have Bitboards for the relevant info so finding a state would be a refined search starting with the busy/occupied Bitboard. Since you’re only storing games that have been played rather than all positions, the size of the index shouldn’t be outrageously large compared with other things already being stored.
Re:Compressing Chess Moves for Fun and Profit by perihelions on Friday March 15, 2024 @02:14PM (#39718910)
- "and evaluate the probabilities for them"

I don't know any good, fast heuristics for predicting this (likelihood of a human choosing a specific chess move). Do you? Chess engine evaluation is computationally quite heavy.

Re:Compressing Chess Moves for Fun and Profit by svnt on Friday March 15, 2024 @02:22PM (#39719017)
Parent was making a joke. The best upper bound found for the number of chess positions is 4.8x10^44.

https://tromp.github.io/chess/chess.html

Re:Compressing Chess Moves for Fun and Profit by ant6n on Friday March 15, 2024 @04:28PM (#39720369)
You don’t need to make perfect predictions. There could actually be a lookup for a few common board states (say a couple million, to cover the first couple moves). Beyond that just use a simple scoring function, for example the value of your vs opponent pieces, whether any of your pieces (notably king) are in danger, whether u won, etc. This means u get better scores for the more likely winning moves, for capturing valuable pieces and for avoiding the loss of your own.

U could also play two or so turns of minimax, or perhaps use a neural network to evaluate the various reachable board states.

So for a given state, enumerate possible transitions, score the resulting states, and map to some sort of probability distribution, then use some prefix code (think Huffman tree[+]) based on the distribution of probabilities to encode the transition.

It’s perhaps not super fast, and not super accurate but if you can weed out the 50% of dumb moves, that already saves a bit.

[+] an easier and better approach is to map the probabilities into an interval between 0 and 1, and keep using fractional bits to „zoom in“ until one of the subintervals is uniquely defined, then recurse on that. Some of the common compression algorithms uses that (but I don’t remember the specifics, those intro courses were a long time ago).

Re:Compressing Chess Moves for Fun and Profit by crystaln on Friday March 15, 2024 @02:47PM (#39719280)
Realizing this is a joke, however you only move one piece at a time and there are limited valid moves. Standard chess notation depends on this.
Re:Compressing Chess Moves for Fun and Profit by stevage on Friday March 15, 2024 @07:39PM (#39721821)
Yeah unfortunately the blog post didn't really explain the use case well enough. There has to be a reason they want to waste space storing the redundant indicators of check and checkmate for instance.
Re:Compressing Chess Moves for Fun and Profit by lifthrasiir on Friday March 15, 2024 @11:10PM (#39723015)
> Though, that engine evaluation is going to be absurdly expensive, when you're compressing/decompressing billions of games.

It only has to be accurate enough to be beneficial though. Even a knowledge about two sets of more frequent and less frequent moves would be much better than the baseline.

Re:Compressing Chess Moves for Fun and Profit by tucnak on Saturday March 16, 2024 @03:01AM (#39723896)
I had built a demo like that a few months ago, it relied on pg_tgrm GIST indexes of the position's FEN string encoding and only a few bits of metadata per position. You could push it by "learning" some representation and perhaps relying on bloom filters or summat clever like that maybe...
Re:Compressing Chess Moves for Fun and Profit by bicijay on Friday March 15, 2024 @01:22PM (#39718249)
Sometimes i wonder, how i got so far im my software developer career...
Re:Compressing Chess Moves for Fun and Profit by vecter on Friday March 15, 2024 @01:41PM (#39718491)
"Software", like "science", is a broad term. Just like there are many kinds of scientists and you could be, say, a biologist or a physicist, there are many entirely disparate fields of software engineering. At the end of the day, software itself is just a means to an ends: solving a problem. Solving some of these problems like the one that GP discussed have more to do with math than programming. The programming is mostly the implementation of the math. So if you're not versed in that math, of course you wouldn't understand the code that's being written to implement it.

Building machine learning systems is vastly different from building operating systems which is vastly different from embedded systems which is vastly different from networking which is vastly different what most of us do (myself included), which is building CRUD apps. We're just solving different problems. Of course there are common themes to writing good code, just like there are common themes to performing science, but the code and solutions will look almost nothing alike.

Re:Compressing Chess Moves for Fun and Profit by acomar on Friday March 15, 2024 @03:23PM (#39719686)
most of the optimizations discussed are actually kind of obvious if you know how chess notation works in the first place. like the reason the starting move "Nf3" makes any sense is because only 1 knight of all 4 on the board can possibly move to f3 on the first move. what the OP is doing is trying to take that kind of information density and trying to represent it, first by assigning bits to each part of a possible move and then by paring it down where the space of legal moves excludes entire categories of possibilities. there's another article that goes much further into how much optimization is possible here: https://lichess.org/@/lichess/blog/developer-update-275-impr...
Re:Compressing Chess Moves for Fun and Profit by Operyl on Friday March 15, 2024 @01:33PM (#39718384)
Because there are so many fields of software development, and you don’t need to be good in all of them. Don’t put yourself down for not understanding, you can always put some time into algorithms again if you need to :).
Re:Compressing Chess Moves for Fun and Profit by porphyra on Friday March 15, 2024 @01:19PM (#39718212)
Indeed, compression is just the dual problem of prediction, so the better you are at predicting the next move, the better you can compress.
Re:Compressing Chess Moves for Fun and Profit by andoando on Friday March 15, 2024 @02:01PM (#39718752)
Im confused, how does probability help here when you need to encode the possibility of all legal moves?
Re:Compressing Chess Moves for Fun and Profit by jprete on Friday March 15, 2024 @02:11PM (#39718874)
Using the probability distribution of moves at any given position, so that more likely moves take less space, will result in saving space on average.

This is the same as Huffman coding, just applied to a different domain.

For that matter, it might also resemble LLM compression of input text, although LLM compression is intentionally lossy and the above schemes are not.

Re:Compressing Chess Moves for Fun and Profit by perihelions on Friday March 15, 2024 @02:07PM (#39718820)
You use variable-length encodings—shorter encodings for more likely moves, longer encodings for ones that happen infrequently.

This is the thing the parent comment was referring to,

https://en.wikipedia.org/wiki/Huffman_coding

Re:Compressing Chess Moves for Fun and Profit by neon5077 on Friday March 15, 2024 @02:27PM (#39719068)
Look up Huffman codes on Wikipedia.

In short, you put the most likely or most common values at the front of the dictionary. Values 0-255 take up one byte, 256-65535 take two bytes, etc. The lower your index, the fewer bits are needed to represent the corresponding state.

Re:Compressing Chess Moves for Fun and Profit by vitus on Friday March 15, 2024 @02:57PM (#39719386)
You're missing an important detail of Huffman codes: they need to be prefix-free so you can actually tell when one value ends and another begins.

A simplified example: suppose you have four letters in your alphabet that you want to represent in binary. You can't just represent these as A=0, B=1, C=10, and D=01, since it's impossible to tell whether "01011" is meant to represent ABABB or DDA or ACBB.

(Hamming codes on the other hand are intended for error correction, where you want maximally distant code words to minimize the chance that bitflips cause decoding errors.)

Re:Compressing Chess Moves for Fun and Profit by neon5077 on Friday March 15, 2024 @04:06PM (#39720123)
I don't really think that's too relevant to the core concept of using fewer bits for the most common codes.

That's really a problem inherent to binary streams in general, not just Huffman encoding.

Re:Compressing Chess Moves for Fun and Profit by vitus on Friday March 15, 2024 @05:21PM (#39720850)
It was a minor point re: this claim:

> Values 0-255 take up one byte, 256-65535 take two bytes

If you wanted to encode more than 256 values, then at best you'd be able to specify values 0-254 taking one byte, e.g. if you used 0xff as a special prefix to represent "use another byte for all other values", but that particular encoding means that you'd only be able to encode another 256 values with a second byte.

Re:Compressing Chess Moves for Fun and Profit by angry_albatross on Friday March 15, 2024 @02:39PM (#39719191)
I think you mean Huffman codes, not Hamming codes.
Re:Compressing Chess Moves for Fun and Profit by neon5077 on Friday March 15, 2024 @04:00PM (#39720045)
Yup.
Re:Compressing Chess Moves for Fun and Profit by dmurray on Friday March 15, 2024 @01:56PM (#39718674)
With a different engine for weaker players, whose moves would generally need a longer representation to encode. For most use cases where you're encoding a ton of PGNs, you also encode some information about the playing strength of the players, so you get that for free.
Re:Compressing Chess Moves for Fun and Profit by cjbprime on Saturday March 16, 2024 @12:10AM (#39723324)
This probably isn't necessary. Anyone past beginner is still sometimes playing one of the best moves for each move, and when they don't it is probably not bad in a predictable way.
Re:Compressing Chess Moves for Fun and Profit by sedatk on Friday March 15, 2024 @01:26PM (#39718297)
So, Huffman encoding but for chess moves?
Re:Compressing Chess Moves for Fun and Profit by vardump on Friday March 15, 2024 @01:28PM (#39718314)
Kinda, but with a different dynamically determined dictionary for each successive position.
Re:Compressing Chess Moves for Fun and Profit by transitionnel on Friday March 15, 2024 @02:11PM (#39718875)
This is the kind of discussion that will get us micro-cybernetics in that ~1 year window.
Re:Compressing Chess Moves for Fun and Profit by groby_b on Friday March 15, 2024 @02:35PM (#39719144)
Re:Compressing Chess Moves for Fun and Profit by joshka on Friday March 15, 2024 @05:53PM (#39721111)
That's neat, so it looks like ln2(216) =~ 7.7 bits to encode any valid move, and then compresses to even better!
Re:Compressing Chess Moves for Fun and Profit by groby_b on Friday March 15, 2024 @07:03PM (#39721586)
Yep. There's a paper somewhere claiming that the lower bound is ~5.1 bits/move, based on an exhaustive analysis of existing games.

https://www.chessprogramming.org/Encoding_Moves sort-of mentions it (search for 5.11), but I can't for the life of me find the actual analysis.

Re:Compressing Chess Moves for Fun and Profit by joshka on Saturday March 16, 2024 @10:18PM (#39731363)
You might be interested in the author's follow up post where they reach 3.7 bits/move after compression. https://mbuffett.com/posts/compressing-chess-moves-even-furt...
Re:Compressing Chess Moves for Fun and Profit by jstanley on Friday March 15, 2024 @05:15PM (#39720796)
If you turn an arbitrary byte string into a list of indexes into legal chess moves, then you can encode arbitrary data as chess games!

(My implementation: https://incoherency.co.uk/chess-steg/ and explanation at https://incoherency.co.uk/blog/stories/chess-steg.html )

Re:Compressing Chess Moves for Fun and Profit by stevage on Friday March 15, 2024 @07:45PM (#39721871)
That's really cute.

I'm surprised stalemate detection is harder than checkmate detection. Aren't they the same except checkmate has the extra step of detecting check?

Re:Compressing Chess Moves for Fun and Profit by bubblyworld on Saturday March 16, 2024 @01:36AM (#39723638)
Not quite - stalemate is no legal move whatsoever for any of your pieces, and checkmate is king is in check and no legal move stops check.
Re:Compressing Chess Moves for Fun and Profit by stevage on Saturday March 16, 2024 @02:31AM (#39723807)
But given that a legal move by definition ends with the king not in check, the distinction often kind of goes away. In implementation terms, I think you basically have to just look at every possible move of every piece and see if any of them end without being in check.

Stalemate can and almost always does involve pieces that can't move because they would create check.

Re:Compressing Chess Moves for Fun and Profit by bubblyworld on Saturday March 16, 2024 @04:11AM (#39724165)
Yeah, that's true, I see what you're saying. I guess knowing the king is already in check allows for optimisations, since you have to either move the king, capture the attacker or block the line of attack, and nothing else is legal. And if you're double-checked you have to move the king, no matter what. As opposed to stalemate where you really do have to check the moves of every piece.
Re:Compressing Chess Moves for Fun and Profit by stevage on Saturday March 16, 2024 @10:36PM (#39731446)
I guess that could be true if you have ready access to things like "the attacker" and "pieces that are capable of moving to block the line of attack".
Re:Compressing Chess Moves for Fun and Profit by jstanley on Sunday March 17, 2024 @07:19AM (#39733632)
It's just because of the chess.js API. It tells you if any given move is a checkmate, so you know to ignore those moves without playing them, but to find out if a move is a stalemate, you need to "play it" on a cloned game and then see if the opponent has any legal moves.
Re:Compressing Chess Moves for Fun and Profit by adrianmonk on Friday March 15, 2024 @05:48PM (#39721082)
> Let an engine assign each legal move m some probability p of being played.

This assumes you're storing moves of players who are good at chess!

Re:Compressing Chess Moves for Fun and Profit by cjbprime on Saturday March 16, 2024 @12:08AM (#39723314)
No, it just saves more space when the players are good. (Note the engine assigns each legal move a probability.)
Re:Compressing Chess Moves for Fun and Profit by adrianmonk on Saturday March 16, 2024 @02:43AM (#39723833)
They said one can do better on average this way. That conclusion does rest on an assumption.

Anyway, I wrote it in the form of a joke, but I was trying to suggest that for optimal compression, you may need to model how a player actually plays, not how they should ideally do it.

Re:Compressing Chess Moves for Fun and Profit by sudosysgen on Saturday March 16, 2024 @01:03PM (#39727549)
On the flipside, if the player is not good, the moves might take more space but there might be fewer of them :)
Re:Compressing Chess Moves for Fun and Profit by programjames on Friday March 15, 2024 @06:44PM (#39721460)
Yep, make an LLM but for chess moves.
Re:Compressing Chess Moves for Fun and Profit by sterlind on Friday March 15, 2024 @09:21PM (#39722460)
what you're describing is arithmetic coding, correct?