7 ms·
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 distr
by tromp 3y ago
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 https://github.com/tromp/ChessPositionRanking
- porphyra 3y agoIndeed, compression is just the dual problem of prediction, so the better you are at predicting the next move, the better you can compress.
- bicijay 3y agoSometimes i wonder, how i got so far im my software developer career...
- Operyl 3y agoBecause 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 :).
- vecter 3y ago"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.
- acomar 3y agomost 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-improved-game-compression/Wqa7GiAA https://lichess.org/@/lichess/blog/developer-update-275-impr...
- sedatk 3y agoSo, Huffman encoding but for chess moves?
- vardump 3y agoKinda, but with a different dynamically determined dictionary for each successive position.
- transitionnel 3y agoThis is the kind of discussion that will get us micro-cybernetics in that ~1 year window.
- dmurray 3y agoWith 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.
- cjbprime 3y agoThis 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.
- perihelions 3y agoThough, 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 agoYou 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 agoParent 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 agoYou 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).
- andoando 3y agoIm confused, how does probability help here when you need to encode the possibility of all legal moves?
- perihelions 3y agoYou 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 https://en.wikipedia.org/wiki/Huffman_coding
- deleted 3y ago[deleted]
- jprete 3y agoUsing 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.
- neon5077 3y agoLook 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.
- angry_albatross 3y agoI think you mean Huffman codes, not Hamming codes.
- neon5077 3y agoYup.
- groby_b 3y agoLichess covered that :) https://lichess.org/@/lichess/blog/developer-update-275-improved-game-compression/Wqa7GiAA https://lichess.org/@/lichess/blog/developer-update-275-impr...
- joshka 3y agoThat's neat, so it looks like ln2(216) =~ 7.7 bits to encode any valid move, and then compresses to even better!
- groby_b 3y agoYep. 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 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.
- joshka 3y agoYou 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-further/ https://mbuffett.com/posts/compressing-chess-moves-even-furt...
- jstanley 3y agoIf 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/ https://incoherency.co.uk/chess-steg/ and explanation at https://incoherency.co.uk/blog/stories/chess-steg.html https://incoherency.co.uk/blog/stories/chess-steg.html )
- stevage 3y agoThat'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?
- bubblyworld 3y agoNot 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.
- stevage 3y agoBut 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.
- bubblyworld 3y agoYeah, 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.
- adrianmonk 3y ago> 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!
- cjbprime 3y agoNo, it just saves more space when the players are good. (Note the engine assigns each legal move a probability.)
- adrianmonk 3y agoThey 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.
- sudosysgen 3y agoOn the flipside, if the player is not good, the moves might take more space but there might be fewer of them :)
- programjames 3y agoYep, make an LLM but for chess moves.
- sterlind 3y agowhat you're describing is arithmetic coding, correct?