10 ms·
How to store a chess position in 26 bytes using bit-level magic (2022)
- justinzollars 3y agooh fuck. I feel like this is going to become an interview question.
- soamv 3y agoA chess position, not a game (still very interesting though!)
- calvinmorrison 3y agoStoring the game would give you the position though
- WithinReason 3y agoIt took me a moment to see your point: it might take less information to store the entire game using a chess engine by entropy coding than a single position
- calvinmorrison 3y agoYeah i guess after a certain number of moves it wouldn't but for the first half it would.
- madacol 3y agoto be more specific a snapshot of the board
- OJFord 3y agoOriginal title is: > Compressing chess positions for fun and profit Which unlike that here is correct: you can store a board, the positions, in 26B; not an arbitrary length game!
- petters 3y agoMost games could possibly be encoded in less than 26 bytes. There are not that many legal moves each time and if you sort them by probability it may not require many bits to describe which one the players chose.
- NelsonMinar 3y agothat may be but it's not what the article is about.
- lainga 3y agoA Huffman code ...? The starting board is 0, 1.e4 is 1, etc...
- OJFord 3y agoYou could probably do something to compress algebraic chess notation in such a way, and even without it as GP says it might cover a decent number of games. My point was you couldn't guarantee a fixed length in 26B, afaik. (That was the article I expected from the malformed title here: a combination of an efficient encoding and it can it can only get longer than this by repetition so here's a very clever thing we can do, or something.)
- IshKebab 3y agoI doubt it. You could maybe get as low as 1 bit per move, but how many games are only 26 moves? Would be interesting to find out though! Maybe this paper says. I didn't read it. https://www.researchgate.net/figure/Entropy-and-distribution-of-move-time-depending-on-move-number-A-Probability-of-the-70_fig2_47622010 https://www.researchgate.net/figure/Entropy-and-distribution...
- OJFord 3y ago1 bit per move would allow you a 26x8 move game in 26 bytes, not just 26.
- solardev 3y agoMeanwhile the non-comp-sci dev in me is like, "why not just store every position in a simple JSON so everyone can read it and everything can parse it". Yeah, it might be half a kB, but you don't have to run through mental gymnastics just to render the pieces...
- x86x87 3y agoIy's not meant for humans to read directly. The compact representation helps performance amd storage a lot when it comes to looking at a lot of positions. If you were to store it as a json most of your time would be spent parsing.
- Timon3 3y agoThis is illustrated very well in Sebastian Lague's video "Coding Adventure: Making a Better Chess Bot" (https://www.youtube.com/watch?v=_vqlIPDR2TU https://www.youtube.com/watch?v=_vqlIPDR2TU).
- catapart 3y agoAwesome video and, I'll admit, the timing makes me curious to know if that video maybe inspired some devs to either pick up this kind of encoding work, or maybe just to finish up some encoding work that they had already started. Most likely unrelated, I know! Just a wondering in passing.
- Timon3 3y agoIt's definitely possible! Even more so considering Sebastian also started a Coding Challenge for Tiny Chess Bots: https://www.youtube.com/watch?v=iScy18pVR58 https://www.youtube.com/watch?v=iScy18pVR58
- School-Cotton 3y agoBecause easy readable code is less important for competitive modern chess engines than maximum speed and memory efficiency.
- mrb 3y agoIt's as long as my comment
- samwillis 3y agoWhen I was building my multiplayer Sudoku app, I had fun experimenting with how small I could pack a sudoku grid into a URL. I came up with a scheme combining bit packing with the knowledge of how the grid works. So as you move through the grid, based on the knowledge of what's been placed where and the remaining digits you have a fewer options. Was fun, I was playing code golf with myself. Sadly seem to have lost the code and I didn't use it in the end. It would probably have been possible to go smaller than I got it by combining it with a sudoku solver, so stop packing positions once it's solvable. But life moved on.
- jprete 3y agoI think for Sudoku there are a lot fewer legal board configs than there are arrangements of the numbers. There’s probably a way to store the solved state as a single number and then just use 27 bits to specify which numbers are revealed. I don’t know what that single number looks like, though, and you’d have to check that there was only one legal solution to the revealed numbers.
- halfcat 3y agoThank you for the python-inline-source library. Are you still working on Tetra?
- Scarblac 3y agoStoring a chess position in 26 bytes. Storing a game is also interesting. The number of legal moves varies depending on the position. You could try to define a variable length encoding by giving more likely moves a shorter encoding, but the ordering would need to be deterministic so it could be decoded (running Stockfish for a second isn't).
- zeagle 3y agoFinally, a good use case for blockchain technology!
- r3trohack3r 3y agoI can't tell if this is in jest or not but blockchains are prolific in software. Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.
- l33t7332273 3y agoI feel like signatures and maybe even Merkle trees are used, but not blockchain.
- episteme 3y agoNearly every company, what is your source for that? I've never even heard of this before.
- deleted 3y ago[deleted]
- flangola7 3y agoNo, no they do not.
- r3trohack3r 3y agoIIUC a blockchain is a structure where each node has a content addressable hash that includes the hash of the previous node in the chain. If you change any historical node, every subsequent hash is updated. This structure is used inside your .git directory, your docker manifest, etc. Blockchains are incredibly useful structures.
- tromp 3y agoHow to store a legal chess position in log_2(8726713169886222032347729969256422370854716254) ~ 152.6 bits ~ 19.1 bytes using rankings: https://github.com/tromp/ChessPositionRanking https://github.com/tromp/ChessPositionRanking But the major point of this project is to allow for random sampling of positions with a decent likelihood of getting a legal one, which allows for accurate estimation of the number of legal positions.
- DesiLurker 3y agoI consider any reduction past the cache-line size (32B) to have diminishing returns as far as processing is concerned. unless of course if you can fit 2 of these in one.
- bumbledraven 3y agoAmazing work. This should be the top comment on this page.
- kurinikku 3y ago+1
- jade-cat 3y agoThere are two more things that should be considered. Both of them unlikely to influence a position, but they can matter - just like the en passant target. The fifty move rule[0] is quite simple, just store a number, fits in five bits. But the threefold repetition rule[1] is quite a pickle - it basically means that to know everything about a position you need to know every position that occurred before it. [0] https://en.wikipedia.org/wiki/Fifty-move_rule https://en.wikipedia.org/wiki/Fifty-move_rule [1] https://en.wikipedia.org/wiki/Threefold_repetition https://en.wikipedia.org/wiki/Threefold_repetition
- Scarblac 3y agoNot all previous positions, only the ones with the same pieces, pawn positions, castling rights and en passant rights. But the standard, FEN, doesn't store that either. It's used more in the context of a full game than with individual positions.
- jade-cat 3y agoFair enough. Still up to 50 board states that can influence the current one (the 50 move rule is coming to help here) FEN doesn't store previous states, but EPD can. It just goes to show how meanings and requirements change depending on context, which is super interesting in and of itself :P
- Scarblac 3y agoAlso, database software gets so clever with storing games that they often can't save games that have illegal moves in them. But there are plenty real games from real tournaments that had illegal moves in them that nobody noticed...
- duskwuff 3y agoWhat's the proper notation for "while White closes his eyes to think about his next move, Black quietly moves one of his pawns over a square"? :)
- pfooti 3y agoAn interesting cognitive phenomenon: if you ask chess experts and novices to memorize and recall an arbitrary chessboard, the experts are significantly better than the novices _only if_ the board is a legal board that can be arrived at during play. If it is not a legal board, there's no particular difference between novices and experts. Original ref: Chase & Simon 1973, Perception in Chess. This is usually taken to mean that the brains (or whatever) of experts see structure that can be used for compression that novices don't, but that compression has assumed invariants you cannot break.
- Scarblac 3y agoIt's not really about whether it's legal, but whether it looks normal. Very bizarre positions can easily be legal, but they're hard to remember for everyone.
- hinkley 3y agoI’ve heard this corroborated by exhibition players who play ten or fifteen opponents at once. They do better with moderately skilled opponents than random people.
- Scarblac 3y agoI don't know what you mean with "exhibition" precisely; I'd expect that to be true for blindfold chess (where you have to keep all the games in memory the whole time), but not for normal simultaneous as the strong player hardly has to think to find moves good enough to beat random players.
- deleted 3y ago[deleted]
- dmurray 3y agoNot a "legal" board, but a typical board. Both this and the original de Groot study picked positions from real games played by strong players. Experts don't do retrograde analysis on the positions, but they do recognise typical patterns that often occur in real play.
- svnt 3y agoIt’s been a minute since I did this seriously so maybe my magic is out of date but I don’t think this is how bits to bytes works: > 100 bits / ~12 bytes > 18 bits / ~2 bytes I didn’t want to spend a whole lot of effort tracking the arithmetic after this. Was it actually 28 bytes? 27 because I can squeeze those extras into one shared byte?
- deleted 3y ago[deleted]
- HALtheWise 3y agoFor what it's worth, this definitely isn't the theoretical limit for compressing a chess board position, which I would probably resort to calculating mathematically. In particular, (simplifying to boards with no pieces captured) this scheme uses 24 bytes for representing piece positions, but the constraint that no two pieces are in the same square means you should actually need only log2(64!/32!) = 22.3 bytes for that case, with 13 bits of savings. The scheme proposed here reclaims some of that overhead by granting special meaning when a piece's location overlaps with the king, but still is capable of representing other illegal positions where non-king pieces occupy the same square. Unfortunately, decoding a mathematically optimal encoding quickly devolves to making a list of all possible board configurations and indexing into it, so I'd definitely believe that the proposal here is close to the smallest practically useful representation.
- Scene_Cast2 3y agoCouldn't you make it practical by assuming all possible positions (64) for the first piece, then 63 for the second, and so on, and encode one piece at a time? (Arithmetic coding piece by piece)
- HALtheWise 3y agoYes, although 1. You'd definitely want to deduplicate positions of identical pieces for even more savings 2. That only handles the case where no pieces have been captured, and the full arithmetic coding would probably need separate "sections" of the integer range for different cases, and the number of sections is also quite high. 3. There's extra nuanced things you might want to handle in the coding, like that pawns can't be on their own back row. That is significantly harder. It looks to me like https://github.com/tromp/ChessPositionRanking https://github.com/tromp/ChessPositionRanking has resolved these sorts of issues, but I haven't dug into exactly how.
- ToValueFunfetti 3y agoThe upper bound on the number of legal chess positions given in https://en.wikipedia.org/wiki/Shannon_number https://en.wikipedia.org/wiki/Shannon_number is 8.7 * 10^45, which gives a lower bound of ln(8.7 * 10^45) = ~106 bits or 14 bytes.
- billfruit 3y agoThere is also the Forsyth-Edwards Notation which is in text, can be quite brief if there are only few pieces on the board.
- timerol 3y agoI played with this in the past (https://news.ycombinator.com/item?id=34461113#34462521 https://news.ycombinator.com/item?id=34461113#34462521), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If there are less than 16 bits set in the bitboard, ignore the last items in the list. 0000 - 0x0 - black pawn 0001 - 0x1 - black pawn (can be en-passant'd) 0010 - 0x2 - black knight 0011 - 0x3 - black bishop 0100 - 0x4 - black rook (castling unavailable) 0101 - 0x5 - black rook (castling available) 0110 - 0x6 - black king 0111 - 0x7 - black queen 1000 - 0x8 - white pawn 1001 - 0x9 - white pawn (can be en-passant'd) 1010 - 0xA - white knight 1011 - 0xB - white bishop 1100 - 0xC - white rook (castling unavailable) 1101 - 0xD - white rook (castling available) 1110 - 0xE - white king 1111 - 0xF - white queen I think that covers all possibilities to store a chess position in 64 + 32 * 4 = 192 bits, or 24 bytes exactly. The starting position would be represented with a bitboard of 0xFFFF00000000FFFF, with a list of [0xD, 0xA, 0xB, 0xF, 0xE, 0xB, 0xA, 0xD, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x5, 0x2, 0x3, 0x7, 0x6, 0x3, 0x2, 0x5], using the same position-to-number scheme in the blog post Edit: 32 pieces, not 16. Thanks to the peanut gallery for catching it quickly Edit2: To store which player is next: do nothing for white. For black, if there are 32 pieces, flip the bitboard upside down. (To check if it's black's turn, verify that black pawns are "below" white pawns, which is illegal before captures are made.) If there are less than 32 pieces and it's black's turn, invert the bitboard. (To check, count the number of set bits.) This is entirely taken from https://news.ycombinator.com/item?id=37526484 https://news.ycombinator.com/item?id=37526484
- bewaretheirs 3y agoBishops move on the diagonal and so can only stay on squares of their original color; you could thus encode the positions of the 4 bishops with 5 bits each instead of 6 each, saving a total of 4 bits, but this would preclude the use of the "store our/their king's location" hack to encode things. But you can encode bishop positions as a 4-digit base-33 number (digits 0..31 indicate the square, digit 32 is captured), which can be stored in binary as a 21-bit number. Net savings ~3 bits. The "no two pieces on the same square" constraint could similarly be used more aggressively.
- thurn 3y agoIt is of course possible to break these rules via promotion, e.g. having two dark square bishops is entirely possible.
- bewaretheirs 3y agoBut in those cases you're missing the pawn that was promoted, so the location of the second dark-square bishop would be encoded in a 6-bit pawn slot rather than a 5-bit or base-33 bishop slot.
- Dwedit 3y agoThe state of an individual chess piece can be stored in 6 bits. 3 bits for the X coordinate, 3 bits for the Y coordinate. A captured piece can use the same coordinates as the King, which would indicate that it's captured. For promoted pieces, you can use 3 bits per promoted piece type (Bishop, Rook, Knight, Queen) to indicate how many exist. For the case of 8 promoted pawns, you'd need one more bit to indicate that all pawns have been promoted and to treat a 7 as an 8. You need 1 bit to indicate who's turn it is. You need 1 bit per player to indicate if castling is still possible, and 1 bit to indicate if the last pawn move was two squares. What gets tricky is tracking for the draw rules. There's '50 moves with no pawn or capture', '3 move repetition', '5 move repetition', '75 moves with no capture or pawn move'. 50 or 75 are simple enough to count, but tracking identical boards from a previous state would be hard to do with limited bits. So then we have: 6 bits for piece coordinates of 32 pieces (192 bits) 13 bits for pawn promotion status for each player (26 bits) 1 bit per player for castling allowed (2 bits) 1 bit for whose turn 1 bit for en-passant possible 7 bits for move counter with no pawn movement or captures That works out to 29 bytes. Edit: Article did promotions much better by removing impossible promoted piece counts. 'Castling allowed' flag could be tied to 'both rooks in their original positions'. If the pieces look like they're in their original positions, but a king or rook moved, swap the two rooks so they're not in the original position anymore. En-passent check by swapping pawn order is neat, but pawn order could instead be used to eliminate the 'promoted' flag per pawn instead.
- JoshuaDavid 3y agoMinor point: the FIDE rules[1] state > Article 9: The Drawn Game > ... > 9.2 The game is drawn, upon a correct claim by a player having the move, when the same position for at least the third time (not necessarily by a repetition of moves) [happens and a draw is claimed] > 9.3 The game is drawn, upon a correct claim by a player having the move, if: ... 9.3.2 the last 50 moves by each player have been completed without the movement of any pawn and without any capture. > ... > 9.6 If one or both of the following occur(s) then the game is drawn: > 9.6.1 the same position has appeared, as in 9.2.2 at least five times. > 9.6.2 any series of at least 75 moves have been made by each player without the movement of any pawn and without any capture. If the last move resulted in checkmate, that shall take precedence. This means that, in order to store a full chess game-state, you also need to keep track of how many moves since the last pawn move or capture (for the 50 and 75 move rule (9.3.2 and 9.6.2 respectively)) and also what positions have previously occurred (for the 3 / 5 position repeats, (9.2 and 9.6.1 respectively)). The maximum number of moves from any chess position is 218 according to this post[2], so each move in the history can be uniquely identified by a single byte. You only need to store the moves since the last capture (since you can't repeat an earlier position), and you _definitely_ can't have more than 112 pawn moves without a capture (because there are only 16 pawns and they can only move forward, except in the case of en-passant which requires a different pawn to move forward twice). But that gives an upper bound of 8400 moves -- this bound is probably much higher than it needs to be though. ---- [1] https://handbook.fide.com/chapter/E012023 https://handbook.fide.com/chapter/E012023 [2] https://www.chess.com/forum/view/fun-with-chess/what-chess-position-has-the-most-number-of-possible-moves?page=2#comment-3532132 https://www.chess.com/forum/view/fun-with-chess/what-chess-p...
- Dylan16807 3y agoIf a pawn moves then you can't repeat a state either, can you? So track the last 75 "moves". > they can only move forward, except in the case of en-passant En passant still attacks forward, into the space the enemy pawn just moved through. > 112 pawn moves without a capture (because there are only 16 pawns and they can only move forward But pawns can't move through pawns. ~~At most I think you can have 4 of the pawns march all the way forward and get captured, leaving you with with 4 pawns that can move 6 spaces and 8 pawns that can move 7 spaces, for a total of 80 pawn moves without a capture.~~ Okay, if you sacrifice a bunch of other pieces to pawns, then you can get them to pair up without losing any. So that's 8 pawns moving 6 spaces, and 8 pawns moving 7 spaces. 104 pawn moves in a row without a capture.
- aimor 3y agoWhat about bishops? The bishops are limited to half the board so only need 5 bits for position. This frees up 4 bits, but you lose the capture state (can't use King's position for capture state). Well, you CAN use the king's position for capture state for two of the bishops at any given time. Then for the other two bishops use a bit to store their capture state. This saves 2 bits overall, bringing the total down to exactly 26 bytes. Gonna have to think that through for awhile, not sure if it works out. Update: I see a comment below that does this but uses 21 bits (instead of 22) by storing bishop position and capture state as a base-33 number.
- NextHendrix 3y agoIt's possible to gain bishops via promotion which may scupper this plan
- aimor 3y agoTrying to strike a balance between raw enumerations of all valid states and practicality: Rooks and Knights are identical, so their positions fall into [64 choose 2] states + 1 state for when both are captured (only one can occupy the King's location) + 3 states for when both are in the starting position and castling is available for one or the other or both 2020 states = 11 bits * 2 colors * 2 piece types = 44 bits Bishops only occupy half the board (32 states) + 1 state to track captures 33 states ^ (4 unique pieces) = 21 bits Queens and Kings just store their location 64 states = 6 bits * 4 pieces = 24 bits Pawn promotions uses the same method as the article 9 bits x 2 colors = 18 bits En passant can be stored by the column + 1 state for none 9 states = 4 bits Pawns can be in, uh, [64 choose 8] position states. (It's only 4 billionish) [64 choose 8] states = 32 bits * 2 colors = 64 bits And captured pawns can be 'unpromoted' and placed on an empty spot in the top row since unpromoted pawns will never be there. And 1 bit for whose turn it is 1 bit Total = 176 bits or 22 bytes Started out thinking about ways to use more of the duplicate pieces, rediscovered the idea of ranking and unranking, started to understand what the person with a limit of 19.2 bytes was doing, tried out just treating position state as [64 choose 32] and only got to 194 bits, then finally worked through this approach.
- omoikane 3y agoThis reminds me of how Oscar Toledo disassembled Video Chess, which ran in just 128 bytes of memory: https://news.ycombinator.com/item?id=36431917 https://news.ycombinator.com/item?id=36431917 It uses lower 4 bits of 64 bytes to store the board positions (upper 4 bits is used to store other data). 64 nibbles is 32 bytes, not too far off from the 26 bytes here.
- frud 3y agoAny scheme that does not make allowance for illegal moves or invalid positions is not suitable for purpose, IMO. In OTB situations players can make mistakes that no one catches. These illegalities become part of the official record of the game.
- Dylan16807 3y agoOh, no encoding of the turns? Then the encoding I came up with after following in the link to Forsyth–Edwards Notation is even better. Version 1: For each position on the board, store if it has a piece or not. 8 bytes for that. Then for each piece in order, 4 bits can encode color and type. 16 bytes for that. Then you can spend 4 bits on castle ability, and 4 bits to pick the pawn that is able to be captured en passant (If there isn't one, pick a pawn that isn't in position. It's impossible for all the pawns to be in a vulnerable rank and have an enemy pawn in position.) So that's 25 bytes, no sweat. Version 2: Instead of 4 bits per piece, store color|0 for a pawn, and color|1|type for anything else. Encode castle-eligible rooks and castle-ineligible rooks as separate types. This costs 14 bytes at the start of the game, and if you promote a piece at least one pawn has to die so the cost increases by 1 bit at most, up to 8 times. So 15 bytes, and you can always squeeze the bits for en passant eligibility into the 15th byte, because more promotions means fewer pawns to keep track of. You can even say whose turn it is by encoding "active turn king" and "inactive turn king" as different types. That's 23 bytes for the entire board state. Either way you can add the turn counters with 2 more bytes. Edit: Okay, this version beats mine solidly: https://news.ycombinator.com/item?id=37526804 https://news.ycombinator.com/item?id=37526804 I was thinking wrong about the number of captures versus promotions, and you can get much more clever with encoding en passant. So 22 bytes or less is enough for this sort of method.
- timerol 3y agoYour version 1 is similar to my top level comment. Note that 4 bits is enough to encode color, type, and include special types for en passantable pawn and castleable rook, so you keep a clean 24 bytes. (Compressing the two special types into one special option, decodable based on position, can get just under 23 bytes.) For version 2, note that 12 promotions can happen, since one capture (white's B pawn taking black's A pawn) can open up the promotion path for 3 pawns (white's B pawn, white's A pawn, and black's B pawn). Two bits per pawn and 5 bits per other piece start at 14 bytes, but can go as high as 17.5 bytes. (Promoting 12 pawns with 0 other captures would be pretty ridiculous as a game, but technically possible...)
- jepler 3y agoIgnoring whose turn, castling & en passant, a static huffman table isn't terrible: 0 - empty (1*32=32) 10y - pawn (color) (3*16=48) 11xxxy - piece (color) (6*16=96) The initial board takes 176 bits (22 bytes) to describe. In most games, the definition length would decrease. A game position is self-delimiting as it always has exactly 64 entries (no need to store the variable length) one of the extra 3 non-pawn piece values can be used to encode 'rook (castling unavailable)' without spending extra bits. a scheme for storing en passant without any additional bits is less clear (but doing it with 3 extra bits is, so 22.375 bytes for positions that would regularly be reached in play). I think it COULD increase in at least one specific circumstances: two promoted pawns (+6 bits total) with only 1 taken pawn (-3 bits). I think the maximum is 12 promoted pawns and 4 taken pawns which would make some hypothetical board take 204 bits (25.5 bytes) in this encoding. A static arithmetic encoding (rather than a huffman encoding) of the same values should take a hair less space.
- jepler 3y agostatic arithmetic encoding appears to store the initial board, "black to move" and 4 rook "can castle" flags and a 1-of-9 "can en passant" value in 22 bytes. "4 pawns taken + 12 pawns promoted to queens", which I still think is the "complex-est" configuration that might actually be reachable in a valid game, fits in 25 bytes. A board with just 2 kings left on it encodes in 10 bytes (en passant and can castle flags are not needed).
- Tommah 3y agoFor my chess tactics trainer at https://www.checkmatechamp.net/ https://www.checkmatechamp.net/ , I tried a lot of different techniques to compress a small set of positions (about 800). I was not concerned with storing the positions in a fixed size, so I was mainly trying things that would make the entropy of each compressed position smaller. I eventually fit these into a file that is about 14 KB in size when gzipped. Each position takes about 17.5 bytes, excluding the HTTP headers. If you go to the page and scroll through the positions, you'll see that each position loads instantly. That's because all the positions are in that 14 KB file which is loaded initially. I didn't include the castling or en passant info in that file, but I suspect it wouldn't add more than one byte per position on average. I only considered techniques that would not cause the decoder to become overly complicated. One "non-standard" technique that I used was inverting the color of all the pieces on one side of the board. Specifically, on the lower half of the board, I change all the white pieces to black and vice versa. This greatly lowers the average entropy of a typical position, since for most of the game, each player keeps most of his pieces on his side of the board. It is also easy to handle in the decoder in one line (if row < 4, then piece = -piece). I have meaning to write a blog post about it, but I haven't gotten around to it yet. If you are interested in hearing more, let me know, and I will move it up my to-do list.
- inimino 3y agoIf the colors are symmetrical, then it's just "my pieces" and "opponent's pieces". You could encode who has the move by how the board is ordered, and predict it from the king and queen position, then just encode the differences.
- jiggawatts 3y agoPeople have pointed out that due to rules about no repeats, the full state requires storing previous moves. I’m fairly convinced that the most efficient encoding would be keeping only the move history and then playing that forward to obtain the board state. E.g.: there are only 32 distinct pieces so a 5-bit number can select one uniquely. Each piece has a maximum of about 32 positions it can move to. Then the encoding is just 10 bits per ply. Typical games are 40 moves (80 ply) and hence require just 800 bits or 100 bytes for the whole game history. Then you could get clever with Huffman coding or the like, since some moves are more common than others.
- paxys 3y agoAs the game goes on the space needed to store the list of moves increases while space needed to store a snapshot of the board decreases. It would be interesting to figure out where on average the strategies meet.
- teo_zero 3y agoThe problem is that the encoding of a position by the previous moves is not unique. For example, 1.a2-a3,a7-a6; 2.h2-h3 represents the same position as 1.h2-h3,a7-a6; 2.a2-a3... Chess engines need to remember evaluated positions to avoid reevaluating them, and this scheme doesn't work well for that purpose.
- verteu 3y agoI agree with this for a typical-length game. But I'd guess its worst-case is inferior due to some pathologically long games.
- jiggawatts 3y agoYes, but pathological games are statistically rare. At scale, the average is what matters…
- jiggawatts 3y agoReplying to my own post: it seems each move can be packed into 8 bits in all but a few rare scenarios such as having many promoted pawns as queens on the board. See: https://www.chessprogramming.org/Encoding_Moves#Per_Piece_and_Square https://www.chessprogramming.org/Encoding_Moves#Per_Piece_an...
- ComplexSystems 3y agoYou can get this even lower, without the need for the extra promotion bits, if you make a note of a few things: 1. There is still redundancy in that there are multiple pieces of the same type, and if you permute their locations you get another representation of the same state. 2. You don't need to say that some pawn's location is the king if it's en passant. You can just use the back row, which pawns can't get to. Using this, you can use the permutations of the pawns to store extra information. For instance, all of the pawns will be on the board at squares #a, #b, ... . Since pawns themselves have numerical indices, you could say that the "canonical" representation of the board state has all of the pawn locations sorted in ascending order. Then, different permutations of that can carry information about promotions and which of the "pawns" are really queens, etc.
- kurinikku 3y agoOP here. Thanks for the suggestion! I really like the idea of there being redundancy for pieces of the same type. If I understand correctly, when a knight is in a particular square say it's not relevant whether it's the king-side or queen-side knight. I believe you still need to keep the ordering for the rooks due to castling, but for the knight and bishop you can store 1-bit each in the ordering. With this we end up with 7 bits for each side, thus below 26 bytes overall! Let me ponder a bit more on the pawn locations. We do need the pawn ordering since the we've encoded the string representing the promotions in sorted order. In the case of en passant we know exactly where the pawn would be, and while we can use the back row, I haven't quite figured out how to use this to encode reliably.
- teo_zero 3y ago> In the case of en passant we know exactly where the pawn would be, and while we can use the back row, I haven't quite figured out how to use this to encode reliably. If a white pawn in x4 (for x between a and h) can be captured en passant, you encode its position as x1. When decoding, if you see a white pawn in rank 1, you know it can't be there, so you place it in x4 and flags it e.p. Black pawns are analogous.
- 3y ago
- yewenjie 3y agoReading this I realized chess is not fully Markovian (you cannot know everything about the game by just looking at the board at any point), specifically because whether determining if castling and en passant are valid moves depend on the history of the board.
- phkahler 3y agoThe author of the post forgot a bit to indicate which sides turn it is. That's another piece of state you don't get by looking at the board.
- xg15 3y agoI wonder if you could shave off some more bits by considering the specific movement restrictions of some pieces: Bishops can only ever occupy squares of their respective colour, so you'd only have to encode ~32 possible positions instead of 64. Pawns (before promotion) can only move straight forward and diagonally forward, which makes their range of valid positions a sort of upside-down triangle shape, with the "tip" of the triangle at the respective pawn's starting position. (e.g. it's impossible to move the pawn from A2 to H2 - or even to H8 - without a promotion) Haven't made the exact calculations, but it might be possible to encode both positions with 5 bits each instead of 6 bits.