9 ms·

Though, that engine evaluation is going to be absurdly expensive, when you're compressing/decompressing billions of games. I think everyone's optimizing the wr

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?)

ant6n 3y ago
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.
- perihelions 3y ago
  - "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.
  - svnt 3y ago
    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 https://tromp.github.io/chess/chess.html
  - ant6n 3y ago
    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).
- anonymous-panda 3y ago
  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.
- crystaln 3y ago
  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.
alfalfasprout 3y ago
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.
- perihelions 3y ago
  - "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).
  - alfalfasprout 3y ago
    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.
    - perihelions 3y ago
      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! :)
koolba 3y ago
> 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.
- perihelions 3y ago
  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).
  - kevindamm 3y ago
    I wonder if shingle hashes might help a lot here... https://en.wikipedia.org/wiki/MinHash https://en.wikipedia.org/wiki/MinHash
stevage 3y ago
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.
lifthrasiir 3y ago
> 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.
tucnak 3y ago
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...

ant6n 3y ago

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.

perihelions 3y ago
- "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.
- svnt 3y ago
  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 https://tromp.github.io/chess/chess.html
- ant6n 3y ago
  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).
anonymous-panda 3y ago
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.
crystaln 3y ago
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.

alfalfasprout 3y ago

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.

perihelions 3y ago
- "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).
- alfalfasprout 3y ago
  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.
  - perihelions 3y ago
    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! :)

koolba 3y ago

> 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.

perihelions 3y ago
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).
- kevindamm 3y ago
  I wonder if shingle hashes might help a lot here... https://en.wikipedia.org/wiki/MinHash https://en.wikipedia.org/wiki/MinHash

stevage 3y ago

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.

lifthrasiir 3y ago

> 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.

tucnak 3y ago

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...