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?)
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.
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).
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.
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).
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.
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! :)
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.
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).
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.
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.
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.
This is the thing the parent comment was referring to,
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.
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.)
That's really a problem inherent to binary streams in general, not just Huffman encoding.
> 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.
https://lichess.org/@/lichess/blog/developer-update-275-impr...
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.
(My implementation: https://incoherency.co.uk/chess-steg/ and explanation at https://incoherency.co.uk/blog/stories/chess-steg.html )
I'm surprised stalemate detection is harder than checkmate detection. Aren't they the same except checkmate has the extra step of detecting check?
Stalemate can and almost always does involve pieces that can't move because they would create check.
This assumes you're storing moves of players who are good at chess!
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.
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