4 ms·
> 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.
by 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 agoFor 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 agoI wonder if shingle hashes might help a lot here... https://en.wikipedia.org/wiki/MinHash https://en.wikipedia.org/wiki/MinHash