How to store a chess position in 26 bytes using bit-level magic (2022)

Storing a chess <i>position</i> in 26 bytes.<p>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&#x27;t).

I played with this in the past (<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=34461113#34462521">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=34461113#34462521</a>), but am willing to take another stab at it.<p>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.<p><pre><code> 0000 - 0x0 - black pawn 0001 - 0x1 - black pawn (can be en-passant&#x27;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&#x27;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 </code></pre> I think that covers all possibilities to store a chess position in 64 + 32 * 4 = 192 bits, or 24 bytes exactly.<p>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<p>Edit: 32 pieces, not 16. Thanks to the peanut gallery for catching it quickly<p>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&#x27;s black&#x27;s turn, verify that black pawns are &quot;below&quot; white pawns, which is illegal before captures are made.) If there are less than 32 pieces and it&#x27;s black&#x27;s turn, invert the bitboard. (To check, count the number of set bits.) This is entirely taken from <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=37526484">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=37526484</a>

There 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.<p>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.<p>[0] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Fifty-move_rule" rel="nofollow noreferrer">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Fifty-move_rule</a> [1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Threefold_repetition" rel="nofollow noreferrer">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Threefold_repetition</a>

An 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&#x27;s no particular difference between novices and experts. Original ref: Chase &amp; Simon 1973, Perception in Chess.<p>This is usually taken to mean that the brains (or whatever) of experts see structure that can be used for compression that novices don&#x27;t, but that compression has assumed invariants you cannot break.

For what it&#x27;s worth, this definitely isn&#x27;t the <i>theoretical</i> 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!&#x2F;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&#x27;s location overlaps with the king, but still is capable of representing other illegal positions where non-king pieces occupy the same square.<p>Unfortunately, decoding a mathematically optimal encoding quickly devolves to making a list of all possible board configurations and indexing into it, so I&#x27;d definitely believe that the proposal here is close to the smallest practically useful representation.

How to store a legal chess position in log_2(8726713169886222032347729969256422370854716254) ~ 152.6 bits ~ 19.1 bytes using rankings:<p><a href="https:&#x2F;&#x2F;github.com&#x2F;tromp&#x2F;ChessPositionRanking">https:&#x2F;&#x2F;github.com&#x2F;tromp&#x2F;ChessPositionRanking</a><p>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.

When 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&#x27;s been placed where and the remaining digits you have a fewer options.<p>Was fun, I was playing code golf with myself. Sadly seem to have lost the code and I didn&#x27;t use it in the end.<p>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&#x27;s solvable. But life moved on.

Original title is:<p>&gt; Compressing chess positions for fun and profit<p>Which unlike that here is correct: you can store a <i>board</i>, the positions, in 26B; not an arbitrary length game!

You can get this even lower, without the need for the extra promotion bits, if you make a note of a few things:<p>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&#x27;t need to say that some pawn&#x27;s location is the king if it&#x27;s en passant. You can just use the back row, which pawns can&#x27;t get to.<p>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 &quot;canonical&quot; 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 &quot;pawns&quot; are really queens, etc.

What about bishops?<p>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&#x27;t use King&#x27;s position for capture state). Well, you CAN use the king&#x27;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.<p>Gonna have to think that through for awhile, not sure if it works out.<p>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.

Meanwhile the non-comp-sci dev in me is like, &quot;why not just store every position in a simple JSON so everyone can read it and everything can parse it&quot;. Yeah, it might be half a kB, but you don&#x27;t have to run through mental gymnastics just to render the pieces...

A chess <i>position</i>, not a game (still very interesting though!)

Ignoring whose turn, castling &amp; en passant, a static huffman table isn&#x27;t terrible:<p><pre><code> 0 - empty (1*32=32) 10y - pawn (color) (3*16=48) 11xxxy - piece (color) (6*16=96) </code></pre> 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)<p>one of the extra 3 non-pawn piece values can be used to encode &#x27;rook (castling unavailable)&#x27; 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).<p>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.<p>A static arithmetic encoding (rather than a huffman encoding) of the same values should take a hair less space.

People have pointed out that due to rules about no repeats, the full state requires storing previous moves.<p>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.<p>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.<p>Then you could get clever with Huffman coding or the like, since some moves are more common than others.

Bishops 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 &quot;store our&#x2F;their king&#x27;s location&quot; 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.<p>The &quot;no two pieces on the same square&quot; constraint could similarly be used more aggressively.

For my chess tactics trainer at <a href="https:&#x2F;&#x2F;www.checkmatechamp.net&#x2F;" rel="nofollow noreferrer">https:&#x2F;&#x2F;www.checkmatechamp.net&#x2F;</a> , 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&#x27;ll see that each position loads instantly. That&#x27;s because all the positions are in that 14 KB file which is loaded initially. I didn&#x27;t include the castling or en passant info in that file, but I suspect it wouldn&#x27;t add more than one byte per position on average.<p>I only considered techniques that would not cause the decoder to become overly complicated. One &quot;non-standard&quot; 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 &lt; 4, then piece = -piece).<p>I have meaning to write a blog post about it, but I haven&#x27;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.

Oh, no encoding of the turns? Then the encoding I came up with after following in the link to Forsyth–Edwards Notation is even better.<p>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&#x27;t one, pick a pawn that isn&#x27;t in position. It&#x27;s impossible for all the pawns to be in a vulnerable rank <i>and</i> have an enemy pawn in position.) So that&#x27;s 25 bytes, no sweat.<p>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 &quot;active turn king&quot; and &quot;inactive turn king&quot; as different types. That&#x27;s 23 bytes for the entire board state.<p>Either way you can add the turn counters with 2 more bytes.<p>Edit: Okay, this version beats mine solidly: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=37526804">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=37526804</a> 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.

The state of an individual chess piece can be stored in 6 bits. 3 bits for the X coordinate, 3 bits for the Y coordinate.<p>A captured piece can use the same coordinates as the King, which would indicate that it&#x27;s captured.<p>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&#x27;d need one more bit to indicate that all pawns have been promoted and to treat a 7 as an 8.<p>You need 1 bit to indicate who&#x27;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.<p>What gets tricky is tracking for the draw rules.<p>There&#x27;s &#x27;50 moves with no pawn or capture&#x27;, &#x27;3 move repetition&#x27;, &#x27;5 move repetition&#x27;, &#x27;75 moves with no capture or pawn move&#x27;. 50 or 75 are simple enough to count, but tracking identical boards from a previous state would be hard to do with limited bits.<p>So then we have:<p>6 bits for piece coordinates of 32 pieces (192 bits)<p>13 bits for pawn promotion status for each player (26 bits)<p>1 bit per player for castling allowed (2 bits)<p>1 bit for whose turn<p>1 bit for en-passant possible<p>7 bits for move counter with no pawn movement or captures<p>That works out to 29 bytes.<p>Edit: Article did promotions much better by removing impossible promoted piece counts.<p>&#x27;Castling allowed&#x27; flag could be tied to &#x27;both rooks in their original positions&#x27;. If the pieces look like they&#x27;re in their original positions, but a king or rook moved, swap the two rooks so they&#x27;re not in the original position anymore.<p>En-passent check by swapping pawn order is neat, but pawn order could instead be used to eliminate the &#x27;promoted&#x27; flag per pawn instead.

I wonder if you could shave off some more bits by considering the specific movement restrictions of some pieces:<p>Bishops can only ever occupy squares of their respective colour, so you&#x27;d only have to encode ~32 possible positions instead of 64.<p>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 &quot;tip&quot; of the triangle at the respective pawn&#x27;s starting position. (e.g. it&#x27;s impossible to move the pawn from A2 to H2 - or even to H8 - without a promotion)<p>Haven&#x27;t made the exact calculations, but it <i>might</i> be possible to encode both positions with 5 bits each instead of 6 bits.

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

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

Minor point: the FIDE rules[1] state<p>&gt; Article 9: The Drawn Game<p>&gt; ...<p>&gt; 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]<p>&gt; 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.<p>&gt; ...<p>&gt; 9.6 If one or both of the following occur(s) then the game is drawn:<p>&gt; 9.6.1 the same position has appeared, as in 9.2.2 at least five times.<p>&gt; 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.<p>This means that, in order to store a <i>full</i> 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 &#x2F; 5 position repeats, (9.2 and 9.6.1 respectively)).<p>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&#x27;t repeat an earlier position), and you _definitely_ can&#x27;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).<p>But that gives an upper bound of 8400 moves -- this bound is probably much higher than it needs to be though.<p>----<p>[1] <a href="https:&#x2F;&#x2F;handbook.fide.com&#x2F;chapter&#x2F;E012023" rel="nofollow noreferrer">https:&#x2F;&#x2F;handbook.fide.com&#x2F;chapter&#x2F;E012023</a><p>[2] <a href="https:&#x2F;&#x2F;www.chess.com&#x2F;forum&#x2F;view&#x2F;fun-with-chess&#x2F;what-chess-position-has-the-most-number-of-possible-moves?page=2#comment-3532132" rel="nofollow noreferrer">https:&#x2F;&#x2F;www.chess.com&#x2F;forum&#x2F;view&#x2F;fun-with-chess&#x2F;what-chess-p...</a>

This reminds me of how Oscar Toledo disassembled Video Chess, which ran in just 128 bytes of memory:<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=36431917">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=36431917</a><p>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.

It’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:<p>&gt; 100 bits &#x2F; ~12 bytes<p>&gt; 18 bits &#x2F; ~2 bytes<p>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?

It&#x27;s as long as my comment

There is also the Forsyth-Edwards Notation which is in text, can be quite brief if there are only few pieces on the board.

oh fuck. I feel like this is going to become an interview question.