# Shortest possible encoding of a chessboard? **URL:** \ **Category:** Factual Questions\ **Created:** [January 27, 2006, 5:42pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867 "2006-01-27T17:42:19Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [January 27, 2006, 5:42pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/1 "2006-01-27T17:42:19Z")
I’m down to 22 bytes and wondering if I can do any better. I got that far by generating a prefix-free code for the contents of each square. 0 signifies an empty square, while a sequence of 1s represents a piece (ranging from 1 for a pawn to 111111 for a king). After the 1s, 00 represents a white piece, and 01 a black one. The starting board works out to be 170 bits, which is padded out to 176. Can anyone beat that? ---
**Author:** ![friedo](https://avatars.discourse-cdn.com/v4/letter/f/8edcca/32.png) [@friedo](https://boards.straightdope.com/u/friedo)\ **Post date:** [January 27, 2006, 5:53pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/2 "2006-01-27T17:53:52Z")
You might be able to shave a little off by adding a code for skipping a number of squares. For example, the starting board has 32 empty squares right in the middle. Let’s say a 1111111 followed by a four-bit number means “skip that many squares.” The middle of the board is then reduced form thirty-two zeros to eleven ones. ---
**Author:** ![acaos](https://avatars.discourse-cdn.com/v4/letter/a/b5ac83/32.png) [@acaos](https://boards.straightdope.com/u/acaos)\ **Post date:** [January 27, 2006, 5:53pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/3 "2006-01-27T17:53:54Z")
You could squeeze it down a little more by having 01111111 (empty square, then seven 1s) stand for ‘this many empty squares’, following that with five bits which you would then decode into a number. That would shave the 32 0’s for the middle of the board in the starting position down to 01111111 10000. This would mostly be useful at the very beginning and in an open endgame where most of the pieces have been taken. ---
**Author:** ![acaos](https://avatars.discourse-cdn.com/v4/letter/a/b5ac83/32.png) [@acaos](https://boards.straightdope.com/u/acaos)\ **Post date:** [January 27, 2006, 6:01pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/4 "2006-01-27T18:01:56Z")
> [@friedo](#): > > You might be able to shave a little off by adding a code for skipping a number of squares. For example, the starting board has 32 empty squares right in the middle. Let’s say a 1111111 followed by a four-bit number means “skip that many squares.” The middle of the board is then reduced form thirty-two zeros to eleven ones. This is definitely a little better than my suggestion - I’d say ‘skip one plus this many squares’ so you could represent up to 32 with the four following bits. ---
**Author:** ![friedo](https://avatars.discourse-cdn.com/v4/letter/f/8edcca/32.png) [@friedo](https://boards.straightdope.com/u/friedo)\ **Post date:** [January 27, 2006, 6:04pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/5 "2006-01-27T18:04:36Z")
> [@acaos](#): > > This is definitely a little better than my suggestion - I’d say ‘skip one plus this many squares’ so you could represent up to 32 with the four following bits. Good point! ---
**Author:** ![chrisk](https://avatars.discourse-cdn.com/v4/letter/c/6de8d8/32.png) [@chrisk](https://boards.straightdope.com/u/chrisk)\ **Post date:** [January 27, 2006, 6:11pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/6 "2006-01-27T18:11:48Z")
Well, all the suggestions about square-skipping aside, (and remember guys, that might save a lot of space on the opening position, but they might cost you when the pieces are all over the place.) I applied the huffman algorithm and got it down to 164 bits, less than 21 bytes. ```auto square status count prefix code length total space taken empty 32 0 1 32 white pawn 8 100 3 24 black pawn 8 101 3 24 white knight 2 11000 5 10 black knight 2 11001 5 10 white bishop 2 11010 5 10 black bishop 2 11011 5 10 white rook 2 11100 5 10 black rook 2 11101 5 10 white queen 1 111100 6 6 black queen 1 111101 6 6 white king 1 111110 6 6 black king 1 111100 6 6 ``` Your scheme turned out pretty good… but it left a few holes that could be filled in, and wasn’t ideally balanced for the mix of pieces. The huffman algorithm kicks ass. friedo: I pulled up the first chess problem I could find on google and found fourteen empty ‘strings’ between the pieces, counting the squares top down and left to right. Spending 5 bits on each of them would take 70 bits, as opposed to just one bit per space. ---
**Author:** ![friedo](https://avatars.discourse-cdn.com/v4/letter/f/8edcca/32.png) [@friedo](https://boards.straightdope.com/u/friedo)\ **Post date:** [January 27, 2006, 6:18pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/7 "2006-01-27T18:18:46Z")
friedo: I pulled up the first chess problem I could find on google and found fourteen empty ‘strings’ between the pieces, counting the squares top down and left to right. Spending 5 bits on each of them would take 70 bits, as opposed to just one bit per space. [/QUOTE] You don’t _have_ to use the skip code for all blocks of empty space. The single zeros in **ultrafilter** ’s original spec are still available. Thus the skip code is only advantageous when you have twelve or more empty spaces in a row. ---
**Author:** ![chrisk](https://avatars.discourse-cdn.com/v4/letter/c/6de8d8/32.png) [@chrisk](https://boards.straightdope.com/u/chrisk)\ **Post date:** [January 27, 2006, 6:22pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/8 "2006-01-27T18:22:57Z")
> [@friedo](#): > > You don’t _have_ to use the skip code for all blocks of empty space. The single zeros in **ultrafilter** ’s original spec are still available. Thus the skip code is only advantageous when you have twelve or more empty spaces in a row. Whoops… I think I misunderstood that one. Hmmm… wonder what the best way of encoding multiple spaces into my code would be, or if it would be worth it to bother. 🙂 ---
**Author:** ![CaveMike](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cavemike/32/16379_2.png) [@CaveMike](https://boards.straightdope.com/u/CaveMike)\ **Post date:** [January 27, 2006, 6:27pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/9 "2006-01-27T18:27:08Z")
[This](http://www.chessbox.de/Compu/schachzahl1_e.html) is a page that uses Huffman encoding for chess positions. The results are similar to **chrisk** ’s: > [@](#): > > Using the encoding as detailed below arbitrary normal chess positions can be stored in not more than 164 bit giving 21 byte (except of extreme promotions), the encoding a full set of chess pieces in the average will actually use only 158+1/3 bit. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [January 27, 2006, 6:35pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/10 "2006-01-27T18:35:18Z")
One improvement I can see: It’s impossible for a pawn to be on the first or last ranks. So for those ranks, you could use a different encoding, with knights as 1 and kings as 11111. This will save two bytes in the initial configuration, though if everything moves off of the back ranks, you’d end up getting those bytes back. Another improvement: There are limits to the number of each piece you can have. So once you’ve enumerated all of the pawns, for instance, you can let all subsequent 1s mean the next piece up. This will also not guarantee any savings, but if you enumerate the squares in the correct order (probably starting from the middle ranks and working out), it’ll usually save a couple of bytes or so. There may be configurations which would nullify both of these advantages without giving any others (the representation shrinks every time a piece is captured, of course), but I’m not sure that any such configurations are actually attainable, and they almost certainly wouldn’t occur in a real game. On the other hand, there’s more to the state of a chessboard than which pieces are where. You’d also need to keep track of whether the kings and rooks have moved yet, to determine whether castling is currently allowed. This could be done in your six padding bits, or less if some of them are not in their original positions. I’m not sure how many bits would be needed to decide whether _en passant_ is allowed in the current position, though. ---
**Author:** ![acaos](https://avatars.discourse-cdn.com/v4/letter/a/b5ac83/32.png) [@acaos](https://boards.straightdope.com/u/acaos)\ **Post date:** [January 27, 2006, 6:35pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/11 "2006-01-27T18:35:43Z")
> [@chrisk](#): > > Whoops… I think I misunderstood that one. Hmmm… wonder what the best way of encoding multiple spaces into my code would be, or if it would be worth it to bother. 🙂 I did a little more work and got this new table: ```auto square status count prefix code length total space taken empty 32 0 1 32 white pawn 8 100 3 24 black pawn 8 101 3 24 white knight 2 10000 5 10 black knight 2 10001 5 10 white bishop 2 10010 5 10 black bishop 2 10011 5 10 white rook 2 11101 5 10 black rook 2 11110 5 10 white queen 1 1111110 7 7 black queen 1 1111111 7 7 white king 1 111000 6 6 black king 1 111001 6 6 empty RLE 1 111110 6 0 ``` As in friedo’s code, ‘empty RLE’ stands for ‘one plus the following four bits worth of empty spaces’. This code is advantageous any time there are more than 10 consecutive empty spaces on the board, and has only a 2-bit disadvantage otherwise (for the two queens). I almost selected the kings for the 7-bit codes, but then I realized they will always be on the board, but the queens might be captured, saving more space in the long run. ---
**Author:** ![chrisk](https://avatars.discourse-cdn.com/v4/letter/c/6de8d8/32.png) [@chrisk](https://boards.straightdope.com/u/chrisk)\ **Post date:** [January 27, 2006, 6:38pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/12 "2006-01-27T18:38:07Z")
> [@CaveMike](#): > > [This](http://www.chessbox.de/Compu/schachzahl1_e.html) is a page that uses Huffman encoding for chess positions. The results are similar to **chrisk** ’s: hmm… as nearly as I can see, that page’s strategy is quite a bit different, even though the results end up at the same place. 🙂 that’s kinda funny. ---
**Author:** ![chrisk](https://avatars.discourse-cdn.com/v4/letter/c/6de8d8/32.png) [@chrisk](https://boards.straightdope.com/u/chrisk)\ **Post date:** [January 27, 2006, 6:42pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/13 "2006-01-27T18:42:12Z")
> [@acaos](#): > > I almost selected the kings for the 7-bit codes, but then I realized they will always be on the board, but the queens might be captured, saving more space in the long run. On the other hand, extra queens can be created by pawn promotion, but probably only when some other pieces have been captured. Probably on average queens are captured more often than promoted. 😃 ---
**Author:** ![iamthewalrus\_3](https://avatars.discourse-cdn.com/v4/letter/i/258eb7/32.png) [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)\ **Post date:** [January 27, 2006, 6:59pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/14 "2006-01-27T18:59:52Z")
> [@acaos](#): > > I did a little more work and got this new table: > > ```auto > > square status count prefix code length total space taken > empty 32 0 1 32 > white pawn 8 100 3 24 > black pawn 8 101 3 24 > white knight 2 10000 5 10 > > ``` > > \ How can you tell between WP-empty-empty and WK? Seems like WP should be 110. ---
**Author:** ![CaveMike](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cavemike/32/16379_2.png) [@CaveMike](https://boards.straightdope.com/u/CaveMike)\ **Post date:** [January 27, 2006, 7:00pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/15 "2006-01-27T19:00:33Z")
> [@chrisk](#): > > hmm… as nearly as I can see, that page’s strategy is quite a bit different, even though the results end up at the same place. 🙂 that’s kinda funny. True. They use Huffman for most pieces, but not the king (not sure why – I guess to shorten the Huffman encodings by one byte). They also store some extra info: 1-bit for the active color and 4-bits for the e.p. flag and e.p. column of the baggy pawn (I don’t know what those mean). They also use a “filling matrix” for each square. I don’t know why, since it seems to just move a bit out of the Huffman encodings and in to the filling matrix. For example, their pieces (without the king) can get encoded in 2-4 bits, but they also use a bit for each piece in the filling matrix. This translates to a 3-5 bit encoding – which is what you would have above (if you also excluded the king). ---
**Author:** ![Ludovic](https://avatars.discourse-cdn.com/v4/letter/l/7ab992/32.png) [@Ludovic](https://boards.straightdope.com/u/Ludovic)\ **Post date:** [January 27, 2006, 7:02pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/16 "2006-01-27T19:02:03Z")
If this is to represent any chess board, it also has to include information on promoted pawns. If we ignore that, we could instead focus on which _pieces_ are left and where they are, instead of encoding each space. You’d have to use 17.84962501 bits (using fractional compression) to indicate how many pieces and which kind are left on each side (1 for each queen, 1.584962501 for each major piece [of course, you could designate each bishop and save a bit later on…], and 3.169925001 for how many pawns. Then you could designate where each piece is, using 6 bits for the first one, 5.977279923 for the second one, etc. It ends up using a lot more space in the beginning, 197 bits, but in endgame conditions it’ll save bunches. For instance if you only have 3 pieces left, you only use 35.78110124 bits or 5 bytes. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [January 27, 2006, 7:03pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/17 "2006-01-27T19:03:56Z")
> [@Ludovic](#): > > If this is to represent any chess board, it also has to include information on promoted pawns. Why? Why can’t we just store all of the pieces and figure it out from there? ---
**Author:** ![acaos](https://avatars.discourse-cdn.com/v4/letter/a/b5ac83/32.png) [@acaos](https://boards.straightdope.com/u/acaos)\ **Post date:** [January 27, 2006, 7:05pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/18 "2006-01-27T19:05:39Z")
> [@iamthewalrus(:3=](#): > > How can you tell between WP-empty-empty and WK? > > Seems like WP should be 110. You’re absolutely correct. My mistake, sorry. ---
**Author:** ![Bryan\_Ekers](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bryan_ekers/32/183_2.png) [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)\ **Post date:** [January 27, 2006, 7:11pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/19 "2006-01-27T19:11:13Z")
> [@CaveMike](#): > > the baggy pawn Isn’t that a black pawn that advises a white knight about his golf game? (pop culture reference challenge) ---
**Author:** ![Pleonast](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pleonast/32/1183_2.png) [@Pleonast](https://boards.straightdope.com/u/Pleonast)\ **Post date:** [January 27, 2006, 7:13pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/20 "2006-01-27T19:13:48Z")
It may be worth considering building a Huffman table based on piece and position (vs just the piece, as **chrisk** has done). For example, white pawn at A1, white pawn at A2, etc… Of course, you’d then need a statistical description of where different pieces are likely to be. There are online databases of games, right? This method would have the advantage of being the shortest encoding on average for a random chess position pulled from a random game. [Next page](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867.md?page=2)