5 ms·
Compressing chess moves for fun and profit
- sfeng 3y agoI would love to see this benchmarked against just running LZW compression on a list of the moves. I think the repeated nature of the moves means the entropy is actually rather low. It should be possible to come up with a compression dictionary which can save a lot more space than just a tight packing like this.
- kondro 3y agoOr a trained zstd dictionary.
- sedatk 3y ago> the repeated nature of the moves On a single game? I don’t think the goal is to pack all plays together and unpack them every time. Every game must be individually accessible as I understand.
- vardump 3y agoLZW would do very badly on a list of binary chess moves. Huffman (and even more so arithmetic encoding or ANS (asymmetric numeral systems [0]) would be significantly better, if you're careful how you encode data. [0]: https://en.wikipedia.org/wiki/Asymmetric_numeral_systems https://en.wikipedia.org/wiki/Asymmetric_numeral_systems
- sshine 3y agoRelated, compressing bingo cards: https://github.com/diku-dk/openbanko https://github.com/diku-dk/openbanko Among other things, contains: Theoretically optimal compression of excessive amounts of bingo cards GPU-accelerated massively parallel bingo simulation using Futhark I suspect the research was triggered by a late professor of Computer Science who unironically calculated how many (Danish) bingo cards there are: https://sprutskalle.dk/blog/wp-content/uploads/bankoplader.pdf https://sprutskalle.dk/blog/wp-content/uploads/bankoplader.p... -- to see the mathematical rigour played out on such a casual question is nothing but inspirational.
- srameshc 3y ago> If you're into chess, I've made a repertoire builder embeds the link chessbook.com, It's a great way to learn and practice chess.
- velcrovan 3y agoWas discussed recent-ish-ly (Sep 2023) — this was positions, not moves: https://news.ycombinator.com/item?id=37525348 https://news.ycombinator.com/item?id=37525348 Site linked there seems to be offline, so here's the archive copy: https://web.archive.org/web/20230928072950/https://www.ezzeriesa.com/index/Writing%20efa7772a3ae64a8193c7ef981ac619fc/Compressing%20chess%20positions%20for%20fun%20and%20profit%20df1fdb5364eb42fdac11eb23b25e9605.html https://web.archive.org/web/20230928072950/https://www.ezzer...
- tromp 3y agoThe 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.
- Someone 3y agoFTA: “But they don’t account for the majority of what I’m storing, which are PGNs.” If they’re storing chess games, why do they try to compress individual moves? If you compress games, you can get much better compression. For example, in any board position, deterministically order all legal moves (they’re already ignoring some illegal moves in their setup, so I think ignoring all is within the rules of the game), and write down the number of the move made. At game start, that will be an integer between 1 and 20 (16 different pawn moves, 4 different knight moves). Black’s reply similarly will be an integer between 1 and 20. For white’s second move, the maximum will depend on the first move. To compress an entire game, use arithmetic encoding (https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding). If there are, on average, n legal moves per position, that will use 2log n bits per move. https://www.chessprogramming.org/Chess_Position https://www.chessprogramming.org/Chess_Position: “The maximum number of moves per chess position seems 218”, so that will give you less than 8 bits per move. In real life, it probably will be less than 6. The only reason I see why this wouldn’t be an option is performance. Decoding would require move generation and thus be more complex. To improve on that, make a deterministic predictor of how likely moves are and use that to improve on the arithmetic encoder. That probably isn’t worth it, though because of the increased decoding complexity.
- marcusbuffett 3y agoI did end up doing something like this: https://mbuffett.com/posts/compressing-chess-moves-even-further/ https://mbuffett.com/posts/compressing-chess-moves-even-furt... You’re spot on about the performance reason I didn’t want to do this originally, but I did some testing and turns out move generation in the library I use is Blazing Fast and wouldn’t be a bottleneck
- crdrost 3y agoIt's also that PGN allows you to encode illegal moves, which is important if your dataset contains over-the-board games. That you only got to about 10-12 bits per move is actually kind of sad in a way, because it means you're not doing substantially better than the approach where you record a move as just (delete-piece-at ____, recreate-that-piece-at ____) 12-bit pairs, where castles are implicitly only recorded by moving the king further than usual and underpromotion has to be explicitly recorded with an extra 12-bit move that is otherwise semantically impossible.
- davguerrero 3y agoFor optimal compression, look into Huffman coding: https://en.wikipedia.org/wiki/Huffman_coding https://en.wikipedia.org/wiki/Huffman_coding
- andruby 3y agoI think Huffman would be good, but I don't think it would be optimal (as in, the smallest possible amount of bits)
- canucker2016 3y agoHuffman requires minimum one bit IIRC whereas Arithmetic coding or ANS ( https://en.wikipedia.org/wiki/Asymmetric_numeral_systems https://en.wikipedia.org/wiki/Asymmetric_numeral_systems ) can use fewer if there's a skewed distribution. Arithmetic coding has been avoided in practical situations due to patents, but many of those have expired ( see the patent section of https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding or maybe not, lawyers tend to advise not even reading about patent specifics )
- ska 3y agoThe core tech patents have expired. They did have some interesting ones around hardware implementations, iirc. Overall the chilling effect was interesting - I found that many people doing academic work around compression didn't really know much about it, didn't teach it, just because it was a mess. The core idea is elegant, and easily implemented.
- marcusbuffett 3y agoI mention Huffman in my follow-up post: https://mbuffett.com/posts/compressing-chess-moves-even-further/ https://mbuffett.com/posts/compressing-chess-moves-even-furt... , but chose arithmetic encoding instead.
- nmilo 3y agoNot sure the author's use case the naive solution seems like just using 6 bits for the piece's original position, 6 bits for the destination, and 2 bits to designate promotion type, for 14 total bits. Everything else can be found from the board state, and I can't imagine a scenario where you have a move, want to convert to algebraic notation, and also don't know what the board is.
- andruby 3y agoI was thinking the same thing. Often both squares will be close to each other, so I'm sure that a generic compression (eg zstd) can even reduce it even further by taking advantage of that proximity.
- jprete 3y agoI had very similar thoughts but I think one can do much better, even. Each move only needs four bits to identify the piece because each side only has 16 pieces at maximum. The game replayer would need to keep track of each pawn's starting file though (including after promotions). Variable-length encodings of the move options help a lot. Pawns only need two bits because there are never more than four legal moves for a pawn - except for promotions, but just handle those specially for those exact cases (if a pawn moves to the last rank then encode the promotion with two bits, otherwise encode the next move). Knights and kings each need three bits for the move - encode each king-castling option as a move to the appropriate rear diagonal (normally off the board so not otherwise legal). Bishops and rooks need four bits (rank and direction). Queens only need five (three bits for rank, two for direction). This way you can get down to between six and nine bits per move.
- amluto 3y ago> The game replayer would need to keep track of each pawn's starting file though (including after promotions). That seems unnecessary. Don’t index the pieces based on their type and where they started — index them based on their current location. So the piece the lexicographically first (rank, file) is piece 0, and 4 bits trivially identifies a piece once you know the color.
- Karellen 3y agoIt's kinda complex. I think my initial stab would be to encoding the source position (6 bits) and end position (6 bits) for a constant 12 bits per move. You don't need to store whether it's a capture, you can figure that out from the game state. You don't need to store disambiguations, there are none in that format. You don't need to store check/mate, you can figure that out from the game state. The only wrinkles (that I can tell) are castles and promotions. But you can get around this by the fact that kings and pawns have limited movement, so their legal destination squares are highly constrained. So you could signal a promotion by encoding the destination with opposite rank, and using the file to encode which piece. Promoting to a rook on c8 gets its destination encoded as a1 - "a" for a rook, and "1" to indicate a promotion. Similarly, you could encode a castle by encoding the king's move with opposite destination rank. Castling the king to f1 gets encoded as f8, and to g1 as g8.
- porkbrain 3y agoAs for promotion: in a valid chess position you could promote a single pawn at three files simultaneously. One by moving forward and then left and right capture. Additionally, you could have two pawns promoting on the same square, again with capture. And you can have a combination of both. Encode a white's move exd8=N with white pawns on e7 and c7 and three black queens on f8, d8 and b8.
- Karellen 3y ago> you could promote a single pawn at three files simultaneously. One by moving forward and then left and right capture. Ooh, didn't think of that, thanks. Still there's enough constraint in the legal destination squares to work around that. There's at least half the board that's inaccessible to a pawn about to promote, which should be enough to encode any of the 3 legal destination squares and 5 possible promotion targets. Edit: maybe keep the destination file as-is, and use the destination rank to encode the promotion piece? > Additionally, you could have two pawns promoting on the same square The source square should disambiguate between those though, right?
- nmilo 3y agoYou can encode a promotion as the destination file plus rank 1-4 for the 4 different kinds, since pawns can't move backwards
- evertedsphere 3y agoSome thoughts I had while reading this, probably not very original: the fact that chess moves are not random and usually adhere to opening theory to some degree means you could get some value out of using something like a trie of some small finite depth, trained on a database of games, to compress common opening lines much better, at the cost of making things like 1. a4 a5 2. h4 h5 that aren't in the trie much costlier to represent. A practical way to actually do this would likely look like applying arithmetic coding to all of the possible length-N prefixes of the game. The mid- or lategame are also far from random and could probably be compressed in small "chunks" via a coder that would (effectively) learn to predict patterns of e.g. capture being followed by a recapture and cause such chunks to require fewer bits to represent. I'm not very knowledgeable about compression algorithms, though; I'm sure others will be able to provide corrections or references.
- Spark_Ed 3y agoYou can reference specific move numbers from specific master games to compress. But you still need to compress how you store those master games. What you're describing for mid/late game might make more sense like this: you use a fixed version of stockfish to suggest moves (depth and version should be locked to static values so it reproduces the same engine move each time). If it's within the first 8 suggestions, you can flag that it's an engine move with 4 bits. Decompression time is significantly larger, but it maximizes the space for cpu trade-off.
- andruby 3y agoThat's exactly what the author seems to have done and describes in their subsequent post: https://mbuffett.com/posts/compressing-chess-moves-even-further/ https://mbuffett.com/posts/compressing-chess-moves-even-furt... (published yesterday)
- ChrisArchitect 3y agoRelated follow-up from same author: Compressing Chess Moves Even Further, To 3.7 Bits Per Move https://mbuffett.com/posts/compressing-chess-moves-even-further/ https://mbuffett.com/posts/compressing-chess-moves-even-furt...
- stevage 3y agoAwesome. Amusingly they didn't actually mention the final move size anywhere except the title.
- modeless 3y agoI wonder how this compares to using zstd with a dictionary.
- zitterbewegung 3y agoRight now I think you could compress chess games for fun and profit . Since chess databases have come along higher level chess players can look pretty far ahead. We are reaching the point where if you study your opponent you can pregame it but studying what openings they make and prepping for openings. But now we have come to the point if you can memorize large portions of chess databases you know optimal play given the database because if anyone has played the game and gets any advantage out of it people will play the line. It would be interesting to take the chess databases see their compression ratio and then how long would it take to lose against swordfish.
- sdenton4 3y agoUse StockFish to predict the next move, and only store the diff between the actual move and the prediction. Or, better, get a ranked list of all possible moves from stockfish, and use a variable-length integer to encode the position in the list. Then the best move takes ~1 bit, and worse moves take more bits. (And we can do fun things like compute how bad a player is by how big their game is after compression.)
- gus_massa 3y agoI almost agree, but as other comment says, it's probaby better to use the StocFish points to generate a probability and then use Huffman encoding.
- Retr0id 3y agoYou'd probably want to use something like CABAC rather than Huffman, since it deals better with dynamic probabilities. https://en.wikipedia.org/wiki/Context-adaptive_binary_arithmetic_coding https://en.wikipedia.org/wiki/Context-adaptive_binary_arithm...
- gus_massa 3y agoIt looks like a very interesting comparison. I still not sure how to tranform StockFish points to probabilities. (Perhaps proportional to exp(-difference/temperature), where temperature is a magical number or perhaps it's like something/elo??? There are too many parameters to tweak.)
- Retr0id 3y agoGiven OP's dataset, you could probably figure out how to map them, experimentally (e.g. by making a histogram)
- gus_massa 3y agoI was imagining downloading the lichess database and trying different strategies to compress it, It's too much work for me, but I'd love to read a blog post if somsome does that.
- bluedino 3y agoAnyone know of a discussion of say, 8 bit chess computers and their techniques and tricks?
- omoikane 3y agoIs this what you are looking for? https://news.ycombinator.com/item?id=36431917 https://news.ycombinator.com/item?id=36431917 - Video Chess disassembled and commented (2023-06-22) https://nanochess.org/video_chess.html https://nanochess.org/video_chess.html Video Chess for Atari 2600 worked with just 128 bytes of memory.
- andjd 3y agoI would be curious how this compares to a more-or-less off-the-shelf text compression algorithm like gzip. My guess is that over the entire database, this would be more efficient than the OP's ad-hoc implementation or any alternative mentioned here.
- pimlottc 3y agoThat’s my first thought as well. Plain old gzip should do pretty well and provides a baseline to beat.
- ska 3y agoUnlikely. Gzip and the like will do well with getting rid of the inherent redundancy of ascii coding but it's a general algorithm and can't take advantage of known structure.
- infogulch 3y agoHas anyone tried columnar compression of full game states instead of bit packing moves? 64 squares * (Empty | (Black | White) * (King | Queen | Bishop | Knight | Rook | Pawn)) + (Black | White) * (Can castle queenside | Can castle kingside) It could be encoded as 64 4-bit int columns + 4 bool columns = 260 bits, most of which don't change between moves. Normal columnar encoding and compression strategies could probably reduce that to a few bits per board state.
- marcusbuffett 3y agoI have actually, alongside my work of compressing moves. My compression scheme averages about 150 bits per position, or about 35% of the standard text notation in EPD format. The thing I optimized for is that there’s very often repeated blank spaces or repeated pawns on the same rank. Also instead of storing castling status separately, it’s stored as a separate piece on the appropriate rook. These take advantage of the fact that there’s 6 pieces, so 3 bits to encode them leaves two options remaining. One is PawnRepeating and the other is RookCastleAvailable, in my scheme. There’s probably improvements to be made. I’ll write a post on it when it’s finalized.
- infogulch 3y agoUsing the extra available piece indexes for "rook that can castle" and "pawn that moved two squares" is a great idea. So e.g. moving the king would not only change the squares where the king moved from and to, but would also convert both of the rooks from "rook that can castle" to "rook that can't castle". Same for a pawn that moved two squares and can be captured by en passant. I guess you also need some way to encode which player's turn it is. Though maybe you could eliminate that by flipping the board on black's move and always encoding from the perspective of the last player's move? I'm curious about whether a naive columnar encoding scheme could beat a more complex encoding scheme, after compression. Not columnar in the sense of ranks and files, but columnar in the sense of data science storage formats (e.g. parquet), where each 'column' is the state of a specific square across different board states. Given 64 such columns, a game state is a single row. The hypothesis being that if you're encoding all the game states of a large number of games (say 1000), after RLE and compression etc you would see a net compression better than more complex encoding schemes. Given a big block of game states like this, then a single 'game' would be a list of offsets into the game states. This would probably also compress very nicely in columnar format. Now I want to try it...
- bee_rider 3y agoThinking about this has made me realize I really don’t know anything about compression other than which arguments to pass to tar to get it to compress, haha. How would a typical compression algorithm do, losslessly compressing the whole game? Can you lossily compress the game? If so, you would end up, after decompressing, with a game that had some ambiguous moves, right? But, only one is valid all the way through. Why not lossily compress and then step through each game, checking if each move is valid? Is that even still considered lossy? Hypothetically you could end up with multiple valid games I guess… but they are just games, haha, who cares if a few are wrong?
- ska 3y agoIt's not lossy if you can always recover the correct data. Rather than use a general algorithm, your compressor would have to reason: I'd have to spend a bit to disambiguate x & y, but only x is a valid board state, so I won't bother and the decompressor also knows I won't bother so it will all work out. This sort of implicit coding can work, but it is fragile.
- robrenaud 3y agoOnly tangentially related, but I think the mid/late game is a much more interesting/useful/hard avenue for chess tools. Chess.com's opening explorer is pretty good, which it seems like this is kind of trying to compete against. What I struggle with is the post game review, where I make a dubious move but I don't actually understand the reason why it's bad. Sure, the engine shows better moves and the refutation to my move, but I often don't know why. The automatically generated explanation is usually pretty poor. I wish I had even a poor copy of Danya giving me commentary. Perhaps I should just lean in and try to implement something like this, but focus it more on coaching than commentary. https://arxiv.org/pdf/2212.08195.pdf https://arxiv.org/pdf/2212.08195.pdf
- jaryd 3y agoYou could check to see if one of his games has that position using https://fenfinder.com https://fenfinder.com (site I built). Of course it's a long shot given the huge possibility-space of unique positions, but hey, one can hope :).
- V-2 3y agoI think that AI, overhyped as it may be, will truly get to shine when it comes to this aspect of chess - basically, tutoring.
- dhsysusbsjsi 3y agoWhat I haven’t seen discussed here much is optimising for developer maintenance. I think the author’s solution is great for this; it’s easy to understand and each move has a bit pattern. Easy to debug. Somebody taking over in the future will understand this compression. If on the other hand you can squeeze another 10% storage from Huffman encoded inverse tree lookup tables that only neckbeards understand, you’re limiting your pool of people able to do maintenance on this system in the future when the author is long gone.
- stevage 3y agoHopefully you just use a library for the Huffman tables and there's not much to maintain.
- adrianmonk 3y ago> I run a site that stores a ton of chess lines, something like 100 million in total. Because there are so many, one approach would be to sort the list of lines lexicographically to group similar ones together, then compress the result with a sliding window compression algorithm. The sliding window compression will avoid storing repeated parts a second time, and the first part of the lines will be repeated a lot because of the sorting. There may also be some other repeated sequences. This assumes that it's OK to sort the lines, though, which might or might not be true.
- V-2 3y agoPGN is a highly redundant format, but it has the inherent advantage of being human readable. The problem is interesting, but I think it falls on the side of "fun" more than "profit". Storage is cheap, and PGN files are still small. An average PGN is still below 1 kilobyte. So one movie in BlueRay quality = about 20 million games. That's a lot. The practical problem is not storage, it's computation. Basically, querying the game database quickly. Compression gets in the way of that. For example, I've just played a game, now I want to go through the opening and fetch all games from the database that went through the same initial moves/positions (that's not the same thing, as a game may arrive at the same position through a different order of moves; AKA transposition). Let's say, all the way until move 15 or 20, because it will only be at that point that a decent game finally becomes unique by deviating from all the recorded games in the database (AKA a novelty was played). Or I want to find all games where an endgame of a Queen and a pawn against a lonely Queen occurred. There is actually a query language for that, named (surprise, surprise) Chess Query Language: https://www.chessprogramming.org/Chess_Query_Language https://www.chessprogramming.org/Chess_Query_Language I feel that whatever a superior alternative to PGN might be, its strength would likely be better queryability rather than higher storage efficiency as such.
- marcusbuffett 3y agoThe problem I’m facing with storing roughly 600 million shorter PGNs is that the database is 100GB or so, and I’m grabbing thousands of them sort of at random. This makes the query IO bound, even though the finding the pages they’re on is virtually instant with the indexes. So a smaller database means less pages read when I do these large reads, ideally. I also have other ideas on ordering the database in a smarter way, but hoping this part helps.
- V-2 3y agoSure, I see your point. Obviously a wasteful format is also getting in the way of queryability. My point is that the main goal should be to improve for queryability, which inherently requires some optimizing for storage, but that's secondary. As opposed to optimizing exlusively for data size. Because in the former case it may still be best to accept some compromise (in the form of redundancy/simplicity) to hit the sweet spot. Especially in the context of many comments that seem to have taken an extremely "code golf"-like approach towards the problem.
- aj7 3y agoPosition to position. 12 bits. Plus occasionally, an extra 12 bits for promotion. Promotion found by impossible position prefix. Whether it’s a capture, check, castle, what piece, etc. all interpreted by a reader program. What am I missing here?
- Dave_Rosenthal 3y ago+1 You're not missing anything. And there are plenty of very simple ways to just use a few "special destinations" to encode any move including possible promotions in a constant 12 bits per move and be very fast to encode/decode. The proposal in the article is just silly. But really the whole thing is silly. 100 million games is a lot of chess, but at 1KB per "inefficient" PGN you are talking a whopping 100GB--big deal. (At 12 bits and, say, 80 half-moves on average, you are talking ~12GB.) Plus the article says that he is "IO-constrained" but shrinking game size isn't going to help with random lookups--a PGN is already below the page size. If you really did care about best compression you would simply assign all legal moves an index and use a heuristic (chess engine) to figure out which moves were likely (i.e. good). In chess, it's not uncommon that good players are usually picking between only a few reasonable candidate moves. I wouldn't be surprised if good compression of human games yielded something like 2-3 bits per move.
- stevage 3y agoLichess's equivalent blog post, using an even fancier technique. https://lichess.org/@/lichess/blog/developer-update-275-improved-game-compression/Wqa7GiAA https://lichess.org/@/lichess/blog/developer-update-275-impr...
- zzo38computer 3y agoI had my own idea compressing chess moves, using one byte per move, because I think the number of legal moves can never exceed 256. Further compression may be possible due to the number of legal moves may be much less, so some of the previously numbers may be used for common sequences of moves. (It would also be possible to use some of the unused numbers to indicate e.g. resigning, agreement of a draw, and unfinished games.)
- DrNosferatu 3y agoJust Huffman code the text.
- stouset 3y agoI feel like zstd trained on a randomized sampling of games from the database would come very close to (or better than) this with nearly zero effort.
- billforsternz 3y agoI went through this process many years ago and documented it here https://triplehappy.wordpress.com/2015/10/26/chess-move-compression/ https://triplehappy.wordpress.com/2015/10/26/chess-move-comp... Basically I demonstrate how you can compress to much less than one byte per move, but settle instead on a one byte per move scheme that is also very performant, something you'd have to sacrifice for optimal compression. I used this one byte representation to good effect in my chess GUI Tarrasch https://triplehappy.com https://triplehappy.com
- lifthrasiir 3y agoThere was also a lengthy off-topic discussion about the compressed board representation this year [1]. [1] https://news.ycombinator.com/item?id=39065595 https://news.ycombinator.com/item?id=39065595
- devit 3y agoIf you actually want good compression, this is definitely not the proper way to go. The proper way to go is to compute all available moves on a given position, assign them a probability distribution and then perform arithmetic coding using it. If you want simplicity, assign an uniform distribution. For optimal compression, use an engine such as Stockfish to evaluate how strong the moves are, and then apply a statistical model that converts move strength to weights to make a probability distribution for; also use an opening books for the openings and tablebases for the endgames. My wild guess is that it will probably result in something like 3-4 bits per move on average. If you instead want a simple encoding, then encode in 4 bits the piece that moved based on any order on the chessboard squares, then in 6 bits the destination square for 10 bits per move.
- deleted 3y ago[deleted]
- ks2048 3y agoFunny, I was just working on this same thing last week. I ended up using 16 bits per move. As other comments here note, you could do it in fewer bits, but everything is a trade-off: with speed, size, and what the goal of your compression is. For me, fixed-size, two bytes per move seems good. Also, I don't bother with storing capture, or check, because those you can infer from the game state. Again, depends on how you be using the result - I just wanted to be able to re-play the game state.
- andy_threos_io 3y agoWith a better coding you don't need more than 8 bits for a move (less for some). The implementation should store a state machine for the game, a struct for each pieces, and also the board with index to the pieces (occupation). There is only 16 pieces for each player, the two players move one another. The Naive would be that you index the pieces (4 bits) and store the movement after that, Pawns 2 bits for movement (2 forward, 2 diagonal) King 4 bits for movement (normal move 1 + 3 bits, castle 1 + 1 bits) Knight 3 bits for movement (8 possible move) Rook 4 bits for movement ( 1 bit orientation horizontal/vertical 3 bit new position ) Bishop 4 bits for movement ( 1 bit orientation left/right diagonal 3 bit new position) Queen 5 bits for movement ( 2 bit orientation horizontal/vertical/ left/right diagonal 3 bits for new position) This way you need Pawn 4 (index) + 2 (movement) = 6 bits King 4 (index) + 4 (movement) = 8 bits Knight 4 (index) + 3 (movement) = 7 bits Rook, Bishop 4 (index) + 4 (movement) = 8 bits Queen 4 (index) + 5 (movement) = 9 bits But you can encode the pieces index in another way, that the Queen got 3 bit index and other pieces got longer index (Pawn 5 bits) index bits + movement 000 + 5 movement Queen -> 8 bits 00100 + 3 movement King Normal -> 8 bits 00101 + 1 movement King castle -> 6 bits 0011x + 3 movement Knight (2) -> 8 bits 01xxx + 2 movement Pawn (8) -> 7 bits 10x + 4 movement Bishop (2) -> 7 bits 11x + 4 movement Rook (2) -> 7 bits Also other bit allocations are possible, I don't know if it's worth it to make the Pawns index 1 bit longer, but in this way the max 8 bits required for a movement. (You need the state machine for the "decompression", also have to track that the black and white Pawns are moving in the opposite direction. ) There can be further compression, if you check the possible move for the piece. ex. the first possible Knight movement is only 1 place, so no need to store the movement. But this need more calculation.
- teo_zero 3y agoIt depends what the goal is. If i's to display moves to humans, then this approach seems correct (not sure if optimal). It doesn't require implementing a full chess engine just to code/decode a move, as others have suggested. If the goal is to replay the moves, instead, you need to keep track of the position anyway. In this case I would suggest a simple scheme: piece-destination. Each player only has 16 pieces at most at any moment in a game, so 4 bits will suffice. Each piece in a given square can only move to a fixed number of destination squares. A Queen can move to 27 other squares (7 horizontally, 7 vertically, 13 diagonally when in one of the four central square). All other pieces have less freedom: Kings have 8 natural moves, plus 2 castles; Pawns have 2 captures, 2 normal moves forward, and 4 possible move-and-promote; and so on. So the 27 for a Queen is the upper limit, and that needs 5 bits. In total 9 bits per move. Unfortunately that's more than one byte, so you still need some bit-wise processing...
- noir_lord 3y agoSCID (the open source chess database) has a very efficient scheme. https://scidvspc.sourceforge.net/doc/Formats.htm https://scidvspc.sourceforge.net/doc/Formats.htm