# 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:** 3
**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 28, 2006, 12:14am UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/41 "2006-01-28T00:14:23Z")
> [@glee](#): > > And whether ‘en passant’ is legal (did a pawn just move two squares past an opposition pawn?). > > Plus if the position has been repeated exactly (3 times can be claimed as a draw), and whether 50 moves have passed without a pawn move or a capture (again a claimable draw). Oh, that’s the answer to my question above – thanks. The link in post #9 uses 4-bits of the e.p (e.p. flag and e.p. column of the baggy pawn). ---
**Author:** ![MaxTheVool](https://avatars.discourse-cdn.com/v4/letter/m/9fc29f/32.png) [@MaxTheVool](https://boards.straightdope.com/u/MaxTheVool)\ **Post date:** [January 28, 2006, 2:47am UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/42 "2006-01-28T02:47:09Z")
The most efficient way to encode a move is almost certainly a look up table of some sort, as it’s relatively easy to calculate all possible moves from a given board position. Just calculate them all in some systematic fashion, list them in some systematic order, find the chosen move in that list, and provide its index. The only theoretical improvement over that would be some scheme which knows which moves are “likely” to be made, and does variable length encoding such that likely moves are shorter than unlikely ones. ---
**Author:** ![duality72](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/duality72/32/3910_2.png) [@duality72](https://boards.straightdope.com/u/duality72)\ **Post date:** [January 28, 2006, 6:18am UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/43 "2006-01-28T06:18:31Z")
Something I’ll throw out there because I bothered to think about it and it’s different from all the other suggestions. It’s not an all-inclusive solution, but a different way of thinking about it. 1. Record the position (6 bits) of each of the 16 original pieces (96 bits total). All other positions are of course empty. 2. Any piece that repeats the position of a king is not actually on the board; disregard its position reading. 3. Promoted pieces have to be encoded with an additional 6 bits: 1 for black/white, 3 for which pawn it takes the place of (so you’ll still use the position reading for that original pawn), and 2 bits for the promotion type (queen, rook, knight, bishop). I guess this seems to benefit from a smaller starting size by not having to encode the empty spaces, but doesn’t shrink at all with fewer pieces on the board (even increases a bit in the case of promotions, but not much). ---
**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 28, 2006, 6:26pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/44 "2006-01-28T18:26:37Z")
> [@duality72](#): > > 1. Record the position (6 bits) of each of the 16 original pieces (96 bits total). All other positions are of course empty. There are actually 32 original pieces, so you’d need to double that. ---
**Author:** ![duality72](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/duality72/32/3910_2.png) [@duality72](https://boards.straightdope.com/u/duality72)\ **Post date:** [January 28, 2006, 7:51pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/45 "2006-01-28T19:51:36Z")
:smack: I knew I had to be missing something. What I get for posting tired, I guess. ---
**Author:** ![friedo](https://avatars.discourse-cdn.com/v4/letter/f/8edcca/32.png) [@friedo](https://boards.straightdope.com/u/friedo)\ **Post date:** [January 28, 2006, 7:58pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/46 "2006-01-28T19:58:02Z")
> [@ultrafilter](#): > > Maybe in the 1980s, but today we have the internet. The question arose in the context of a distributed, online chess game that has to broadcast the board to two players and an arbitrary number of viewers, some of whom might be on dialup. It’s still probably not very important, but it’s interesting in its own right. Oh, well in that case you should definitely use XML over SOAP with a web-based, AJAX enabled distribution system. I imagine you could encode an entire chessboard in less than half a meg! ---
**Author:** ![Gary\_Robson](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/gary_robson/32/3448_2.png) [@Gary\_Robson](https://boards.straightdope.com/u/Gary_Robson)\ **Post date:** [January 28, 2006, 7:59pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/47 "2006-01-28T19:59:47Z")
> [@Mathochist](#): > > Make a list of all valid positions, then use the entry number in the list. That was the first way I came at this, too. It certainly generates the shortest _fixed-length_ encoding of the board, but the variable-length systems will beat it for an average length. The list of all valid positions has to leave room for a lot of highly unlikely positions (theoretically, white _could_ have ten knights on the board). The answer also changes depending on application. The OP presented a short _context-free_ representation of a board. If you’re looking at representing the state of a game, it requires extra data (as previously noted). If you’re looking at preserving the record of a game, it’s almost certainly shorter to list the moves than to save the state of the game after each move. ---
**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 29, 2006, 10:13pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/48 "2006-01-29T22:13:13Z")
> [@](#): > > That was the first way I came at this, too. It certainly generates the shortest fixed-length encoding of the board, but the variable-length systems will beat it for an average length. The list of all valid positions has to leave room for a lot of highly unlikely positions (theoretically, white could have ten knights on the board). Not necessarily. We’re already assuming that we have some sort of end-of-file signal, or the variable-length systems have no advantage. Then we just need some way of systematically deciding which positions are more likely, and put those earlier on our lookup table. They’ll then get lower numbers, which can be represented in fewer bytes. The net savings should be the same as for the other variable-file-length methods, or even greater (since some unlikely positions nevertheless have few pieces on the board). ---
**Author:** ![Polerius](https://avatars.discourse-cdn.com/v4/letter/p/d78d45/32.png) [@Polerius](https://boards.straightdope.com/u/Polerius)\ **Post date:** [January 29, 2006, 11:17pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/49 "2006-01-29T23:17:18Z")
> [@chrisk](#): > > 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 > > ``` Taking the above idea, and noticing that pieces are more likely to be around pieces of their own color, I changed the Huffman categories from black and white to ‘of same color as previous piece’ and ‘of opposite color to previous piece’. The results are ```auto square status weight prefix code length empty 320 0 1 similar pawn 120 111 3 opposite pawn 40 1100 4 similar rook 30 1000 4 opposite rook 10 110100 6 similar knight 30 1001 4 opposite knight 10 110101 6 similar bishop 30 1010 4 opposite bishop 10 110110 6 similar queen 15 10110 5 opposite queen 5 1101110 7 similar king 15 10111 5 opposite king 5 1101111 7 ``` The starting board comes out to be 149 bits with the particular choice of weights given above. Since we need 1 additional bit to indicate what color the first piece is, the total comes out to 150 bits. You can tweak the weights depending on how frequent color switches are on a typical chess board. Using the above set of weights, each color switch costs about 2 bits. Other sets of weights can punish color switches more or less. For example: ```auto square status weight prefix code length empty 320 0 1 similar pawn 140 10 2 opposite pawn 20 11101 5 similar rook 35 11110 5 opposite rook 5 1110001 7 similar knight 35 11111 5 opposite knight 5 1110010 7 similar bishop 35 1100 4 opposite bishop 5 1110011 7 similar queen 18 11010 5 opposite queen 2 11100000 8 similar king 18 11011 5 opposite king 2 11100001 8 ``` which brings the starting board to 143 bits, but punishes color switches with 3 bits each time. We can get more fancy and add 1 bit to indicate whether we are using the codebook above or a codebook which does not punish color switches (i.e. which has equal weights for similar and opposite pieces, and which results in a codebook similar to the one given by **chrisk** ) This way, we would use the above codebook for chess boards during the beginning of the game, when there are a lot of pieces, and few color switches, and we could use **chrisk** ’s codebook later on when there are fewer pieces and we have a lot of color switches. I think that using something like the above, you should get away with less than 150 bits to represent just about any chess board. ---
**Author:** ![Malacandra](https://avatars.discourse-cdn.com/v4/letter/m/45deac/32.png) [@Malacandra](https://boards.straightdope.com/u/Malacandra)\ **Post date:** [January 30, 2006, 10:41am UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/50 "2006-01-30T10:41:01Z")
One other thing about castling: you need to flag King’s and Queen’s side separately. Moving either Rook bars castling on that side, but it’s still valid on the other. (There’s a line in the Benko Gambit where Black exchanges Bishops on f1, and if White takes with the KR he could still castle long, though why he’d want to in the Benko is a whole other question.) I’m just as much a chess geek as **glee** , but by no means as good a _player_. 🙂 ---
**Author:** ![puggyfish](https://avatars.discourse-cdn.com/v4/letter/p/3ab097/32.png) [@puggyfish](https://boards.straightdope.com/u/puggyfish)\ **Post date:** [January 30, 2006, 12:34pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/51 "2006-01-30T12:34:56Z")
> [@N9IWP](#): > > According to this: > [chessbox.de](http://www.chessbox.de/Compu/schachzahl1b_e.html) > > There are about 2[super]154[/super] possible positions, so generating a lookup table and transmitting an index number doesn’t actually save that much… > > Not quite what THe OP is after: > > One move can be encoded in 12 bits (6 bits initial square, 6 bits destination) (neglecting castles and such, call it 16 bits). Since the initial configuarion is known, any game came be encode by a list of moves. Certainly better than transmitting the entire board configuration after every move. (unless you want people to watch starting midgame) > > Brian Encoding moves can be done better than that. 6 bits for the initial square. That identifies the piece to be moved, which then has a limited number of moves, with 28 being the maximum (for a queen). A consistent definition for the numbering needs to be created so that it works anywhere on the board (e.g., for the queen, start heading up the board - from White to Black - and move outwards, then rotate clockwise). With this you require 6 bits for the initial square, then 5 bits if a queen is moving, 4 for a rook, bishop or king (to include castling), 3 for a knight and 2 for a pawn (to include taking, which includes en passant). Using data from [http://www.vanheusden.com/misc/datamining\_on\_chess.html](http://www.vanheusden.com/misc/datamining_on_chess.html) I calculate that the average number of bits required for the move is around 3.4. So the average per move is 9.4. Notes: 1. This can be reduced further by choosing consistent ways to only take into account the moves that can be made. I don’t have the stats for that, but I would guess that most queen moves would require 4 bits only, most Bishop, Rook and King moves only 3 and most pawn moves only 1. The average per move should drop to below 9 bits. 2. On promotion you’ll need an extra 2 bits for the pawn to choose the piece, but this only accounts for a very small fraction of moves). 3. Feel free to compress the resulting data and gain further savings. This is still inefficient compared to other schemes mentioned here past move 15-20, but is good for the opening moves, which will not benefit from any savings due to sparsity. So add an extra bit at the start of each position to choose between move encoding and some positional variant that benefits from sparsity later in the game. ---
**Author:** ![puggyfish](https://avatars.discourse-cdn.com/v4/letter/p/3ab097/32.png) [@puggyfish](https://boards.straightdope.com/u/puggyfish)\ **Post date:** [January 30, 2006, 12:38pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/52 "2006-01-30T12:38:37Z")
Obvious improvement: Maximum of 5 bits for the initial piece to be moved - forget identifying the squares. Promotions retain the identifier of the pawn they were promoted from. That’s around 8 bits per move, so move encoding should be efficient compared to most schemes up to move 20 or so. ---
**Author:** ![mr.jp](https://avatars.discourse-cdn.com/v4/letter/m/48db29/32.png) [@mr.jp](https://boards.straightdope.com/u/mr.jp)\ **Post date:** [January 30, 2006, 12:52pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/53 "2006-01-30T12:52:05Z")
I think we should encode the possibility of castling and en passant, but not the repetition stuff and 3 moves. They are a more integral part of the game. The 4 castling possibilities, I think, could just be four 0/1 pairs after all the squares have been covered. Then we place the kings according to Chronos idea. Then, if an en passant can be made, we code the square at which the en passant pawn is positioned. Otherwise we just end the code. ---
**Author:** ![mr.jp](https://avatars.discourse-cdn.com/v4/letter/m/48db29/32.png) [@mr.jp](https://boards.straightdope.com/u/mr.jp)\ **Post date:** [January 30, 2006, 12:54pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/54 "2006-01-30T12:54:39Z")
and 50\* moves, I meant ---
**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 30, 2006, 9:31pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/55 "2006-01-30T21:31:59Z")
> [@](#): > > Maximum of 5 bits for the initial piece to be moved - forget identifying the squares. Promotions retain the identifier of the pawn they were promoted from. Still not quite right. Don’t identify the piece by piece name, identify it by its current position on the board. That is to say: Start at the top left corner of the board. Go through all of the spaces, in order. Whenever a space is occupied, increment your count. When the count reaches the number specified, that’s the piece you’re supposed to move. Also, you only need three bits for the king. A king in vacuum has eight “normal” moves, which is 3 bits. The king also, in general, has two castling moves. But it never has both. If castling is still possible, the king must still be in its starting position, meaning that it has (at most) five normal moves, plus the two castlings. So it’s still always 8 possibilities or less, and 3 bits suffices. If we’re concerned about practical applications, of course, we need to sacrifice a little efficiency. All of the super-efficient methods proposed thus far would give radically different results if a single bit of the transmission is flipped. Given this, it would be prudent to add some number of check bits, for error correction or at least detection. ---
**Author:** ![Bytegeist](https://avatars.discourse-cdn.com/v4/letter/b/9dc877/32.png) [@Bytegeist](https://boards.straightdope.com/u/Bytegeist)\ **Post date:** [January 30, 2006, 11:05pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/56 "2006-01-30T23:05:19Z")
> [@Chronos](#): > > All of the super-efficient methods proposed thus far would give radically different results if a single bit of the transmission is flipped. Given this, it would be prudent to add some number of check bits, for error correction or at least detection. Yep. It would be embarrassing during a tournament, to decode a garbled bit-stream and have one player suddenly end up with, say, three kings. Or, nothing but pawns. Or all his pieces located on the same square … or spelling out a rude word. _People, people._ Are we not playing with fire? ---
**Author:** ![galt](https://avatars.discourse-cdn.com/v4/letter/g/35a633/32.png) [@galt](https://boards.straightdope.com/u/galt)\ **Post date:** [January 31, 2006, 12:35am UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/57 "2006-01-31T00:35:55Z")
If the goal is to reduce bandwidth as much as humanly possible, a pretty obvious improvement is to not send the entire board state every turn. If a board description can contain a reference to a previous board plus a list of moves that define the delta from that referenced board, then most transmissions will be a few bytes. You need a protocol that’s designed to detect the situation where the two sides are not in agreement about what initial board the delta should be applied to, but that’s not too hard to do. ---
**Author:** ![Harmonious\_Discord](https://avatars.discourse-cdn.com/v4/letter/h/74df32/32.png) [@Harmonious\_Discord](https://boards.straightdope.com/u/Harmonious_Discord)\ **Post date:** [January 31, 2006, 2:59am UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/58 "2006-01-31T02:59:45Z")
Why would bandwidth be a problem with a chess game between two players? What is wanted here, to get a program to fit in a small foot print, or to make it faster for an AI can make a move? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [January 31, 2006, 4:21am UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/59 "2006-01-31T04:21:15Z")
> [@Harmonious Discord](#): > > Why would bandwidth be a problem with a chess game between two players? What is wanted here, to get a program to fit in a small foot print, or to make it faster for an AI can make a move? Two players and an arbitrary number of viewers, who may join in or drop off at any time. That also makes it difficult to not pass the entire board every round. ---
**Author:** ![Harmonious\_Discord](https://avatars.discourse-cdn.com/v4/letter/h/74df32/32.png) [@Harmonious\_Discord](https://boards.straightdope.com/u/Harmonious_Discord)\ **Post date:** [January 31, 2006, 5:52am UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/60 "2006-01-31T05:52:27Z")
That’s the clarification I wanted. One observation though, the players need to be in real time, but the observers can experience a delay in viewing, without a critical problem. I understand the reason for limiting data transmission here. The problem is set in it’s proper form now. [Previous page](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867.md?page=2) [Next page](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867.md?page=4)