# Shortest possible encoding of a chessboard?

**URL:** <https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867>\
**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:** 4\
**Page:** 4

<div class="post-metadata">

**Author:** ![borschevsky](https://avatars.discourse-cdn.com/v4/letter/b/97f17d/32.png) [@borschevsky](https://boards.straightdope.com/u/borschevsky)\
**Post date:** [January 31, 2006, 3:19pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/61 "2006-01-31T15:19:43Z")

</div>

> [@puggyfish](#):
>
> 3 for a knight and 2 for a pawn

There are cases when you’d need more than 2 for pawns, if you’re counting promotions as distinct pawn moves. With a white pawn on b7, and black pieces on a8 & c8, the pawn has 12 different moves.

---

<div class="post-metadata">

**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 31, 2006, 6:33pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/62 "2006-01-31T18:33:41Z")

</div>

> [@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?

I figured this was just an intellectual exersize. Even with a bad dialup connection, the difference between the best and worst algorithm we’ve discussed in this thread is an extra hundredth of a second to transmit the whole board. On a decent broadband connection, we’re talking about a couple hundred microseconds.

---

<div class="post-metadata">

**Author:** ![Bytegeist](https://avatars.discourse-cdn.com/v4/letter/b/9dc877/32.png) [@Bytegeist](https://boards.straightdope.com/u/Bytegeist)\
**Post date:** [February 1, 2006, 12:23am UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/63 "2006-02-01T00:23:43Z")

</div>

> [@InvisibleWombat](#):
>
> I figured this was just an intellectual exersize. Even with a bad dialup connection, the difference between the best and worst algorithm we’ve discussed in this thread is an extra hundredth of a second to transmit the whole board.

Ah, but what the OP didn’t tell you is that he wishes to encode the state of the _entire_ chessboard . . . **down to the atomic level**.

You may assume the pieces are made of cheap hollow plastic, and not marble let’s say, for better compression. You may also ignore air molecules. But don’t forget to include the “castling” and “en-passant” flags in your state representation somewhere. You’ll feel foolish if you successfully transmit all those atom states, but overlook the last few bits critical to play.

Also, you may assume a 64-bit address space to work with, for a nice big sliding window. Watch out for VM swapping though. Try to take advantage of locality for good cache performance. Justify your trade-offs and choic of data structure.

(Hmm, after re-reading, it seems the OP asked for no such thing after all. I could have _sworn_ otherwise.)

---

<div class="post-metadata">

**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:** [February 1, 2006, 10:38pm UTC](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867/64 "2006-02-01T22:38:45Z")

</div>

> [@Bytegeist](#):
>
> You may assume the pieces are made of cheap hollow plastic, and not marble let’s say, for better compression. You may also ignore air molecules. But don’t forget to include the “castling” and “en-passant” flags in your state representation somewhere.

Silly me. At first, I thought solid plastic would be better. I put a bunch of solid pieces and a bunch of hollow pieces in the trash compacter, though, and found that the hollow ones do, indeed, provide better compression.

I found the best way to represent the castling flag was with a real flag. It settles into a hole in the top of each rook, and is removed as soon as that rook may no longer castle.

[Previous page](https://boards.straightdope.com/t/shortest-possible-encoding-of-a-chessboard/341867.md?page=3)