Not strictly a question, more of a puzzle…

Over the years, I've been involved in a few technical interviews of new employees. Other than asking the standard "do you know X technology" questions, I've also tried to get a feel for how they approach problems. Typically, I'd send them the question by email the day before the interview, and expect them to come up with a solution by the following day.

Often the results would be quite interesting – wrong, but interesting – and the person would still get my recommendation if they could explain why they took a particular approach.

So I thought I'd throw one of my questions out there for the Stack Overflow audience.

Question: **What is the most space-efficient way you can think of to encode the state of a chess game (or subset thereof)? That is, given a chess board with the pieces arranged legally, encode both this initial state and all subsequent legal moves taken by the players in the game.**

No code required for the answer, just a description of the algorithm you would use.

EDIT: As one of the posters has pointed out, I didn't consider the time interval between moves. Feel free to account for that too as an optional extra đź™‚

EDIT2: Just for additional clarification… Remember, the encoder/decoder is rule-aware. The only things that really need to be stored are the player's choices – anything else can be assumed to be known by the encoder/decoder.

EDIT3: It's going to be difficult to pick a winner here đź™‚ Lots of great answers!

## Best Solution

Update:I liked this topic so much I wrote Programming Puzzles, Chess Positions and Huffman Coding. If you read through this I've determined that theonlyway to store a complete game state is by storing a complete list of moves. Read on for why. So I use a slightly simplified version of the problem for piece layout.## The Problem

This image illustrates the starting Chess position. Chess occurs on an 8x8 board with each player starting with an identical set of 16 pieces consisting of 8 pawns, 2 rooks, 2 knights, 2 bishops, 1 queen and 1 king as illustrated here:

Positions are generally recorded as a letter for the column followed by the number for the row so Whiteâ€™s queen is at d1. Moves are most often stored in algebraic notation, which is unambiguous and generally only specifies the minimal information necessary. Consider this opening:

which translates to:

The board looks like this:

An important ability for any programmer is to be able to

correctly and unambiguously specify the problem.So whatâ€™s missing or ambiguous? A lot as it turns out.

## Board State vs Game State

The first thing you need to determine is whether youâ€™re storing the state of a game or the position of pieces on the board. Encoding simply the positions of the pieces is one thing but the problem says â€śall subsequent legal movesâ€ť. The problem also says nothing about knowing the moves up to this point. Thatâ€™s actually a problem as Iâ€™ll explain.

## Castling

The game has proceeded as follows:

The board looks as follows:

White has the option of castling. Part of the requirements for this are that the king and the relevant rook can never have moved, so whether the king or either rook of each side has moved will need to be stored. Obviously if they arenâ€™t on their starting positions, they have moved otherwise it needs to be specified.

There are several strategies that can be used for dealing with this problem.

Firstly, we could store an extra 6 bits of information (1 for each rook and king) to indicate whether that piece had moved. We could streamline this by only storing a bit for one of these six squares if the right piece happens to be in it. Alternatively we could treat each unmoved piece as another piece type so instead of 6 piece types on each side (pawn, rook, knight, bishop, queen and king) there are 8 (adding unmoved rook and unmoved king).

## En Passant

Another peculiar and often-neglected rule in Chess is En Passant.

The game has progressed.

Blackâ€™s pawn on b4 now has the option of moving his pawn on b4 to c3 taking the White pawn on c4. This only happens on the first opportunity meaning if Black passes on the option now he canâ€™t take it next move. So we need to store this.

If we know the previous move we can definitely answer if En Passant is possible. Alternatively we can store whether each pawn on its 4th rank has just moved there with a double move forward. Or we can look at each possible En Passant position on the board and have a flag to indicate whether its possible or not.

## Promotion

It is Whiteâ€™s move. If White moves his pawn on h7 to h8 it can be promoted to any other piece (but not the king). 99% of the time it is promoted to a Queen but sometimes it isnâ€™t, typically because that may force a stalemate when otherwise youâ€™d win. This is written as:

This is important in our problem because it means we canâ€™t count on there being a fixed number of pieces on each side. It is entirely possible (but incredibly unlikely) for one side to end up with 9 queens, 10 rooks, 10 bishops or 10 knights if all 8 pawns get promoted.

## Stalemate

When in a position from which you cannot win your best tactic is to try for a stalemate. The most likely variant is where you cannot make a legal move (usually because any move when put your king in check). In this case you can claim a draw. This one is easy to cater for.

The second variant is by threefold repetition. If the same board position occurs three times in a game (or will occur a third time on the next move), a draw can be claimed. The positions need not occur in any particular order (meaning it doesnâ€™t have to the same sequence of moves repeated three times). This one greatly complicates the problem because you have to remember every previous board position.

If this is a requirement of the problem the only possible solution to the problem is to store every previous move.Lastly, there is the fifty move rule. A player can claim a draw if no pawn has moved and no piece has been taken in the previous fifty consecutive moves so we would need to store how many moves since a pawn was moved or a piece taken (the latest of the two. This requires 6 bits (0-63).

## Whose Turn Is It?

Of course we also need to know whose turn it is and this is a single bit of information.

## Two Problems

Because of the stalemate case, the only feasible or sensible way to store the game state is to store all the moves that led to this position. Iâ€™ll tackle that one problem. The board state problem will be simplified to this:

store the current position of all pieces on the board ignoring castling, en passant, stalemate conditions and whose turn it is.Piece layout can be broadly handled in one of two ways: by storing the contents of each square or by storing the position of each piece.

## Simple Contents

There are six piece types (pawn, rook, knight, bishop, queen and king). Each piece can be White or Black so a square may contain one of 12 possible pieces or it may be empty so there are 13 possibilities. 13 can be stored in 4 bits (0-15) So the simplest solution is to store 4 bits for each square times 64 squares or 256 bits of information.

The advantage of this method is that manipulation is

incrediblyeasy and fast. This could even be extended by adding 3 more possibilities without increasing the storage requirements: a pawn that has moved 2 spaces on the last turn, a king that hasnâ€™t moved and a rook that hasnâ€™t moved, which will cater for a lot of previously mentioned issues.But we can do better.

Base 13 Encoding

It is often helpful to think of the board position as a very large number. This is often done in computer science. For example, the halting problem treats a computer program (rightly) as a large number.

The first solution treats the position as a 64 digit base 16 number but as demonstrated there is redundancy in this information (being the 3 unused possibilities per â€śdigitâ€ť) so we can reduce the number space to 64 base 13 digits. Of course this canâ€™t be done as efficiently as base 16 can but it will save on storage requirements (and minimizing storage space is our goal).

In base 10 the number 234 is equivalent to 2 x 10

^{2}+ 3 x 10^{1}+ 4 x 10^{0}.In base 16 the number 0xA50 is equivalent to 10 x 16

^{2}+ 5 x 16^{1}+ 0 x 16^{0}= 2640 (decimal).So we can encode our position as p

_{0}x 13^{63}+ p_{1}x 13^{62}+ ... + p_{63}x 13^{0}where p_{i}represents the contents of squarei.2

^{256}equals approximately 1.16e77. 13^{64}equals approximately 1.96e71, which requires 237 bits of storage space. That saving of a mere 7.5% comes at a cost ofincreased manipulation costs.significantly## Variable Base Encoding

In legal boards certain pieces canâ€™t appear in certain squares. For example, pawns cannot occur at in the first or eighth ranks, reducing the possibilities for those squares to 11. That reduces the possible boards to 11

^{16}x 13^{48}= 1.35e70 (approximately), requiring 233 bits of storage space.Actually encoding and decoding such values to and from decimal (or binary) is a little more convoluted but it can be done reliably and is left as an exercise to the reader.

## Variable Width Alphabets

The previous two methods can both be described as

fixed-width alphabetic encoding. Each of the 11, 13 or 16 members of the alphabet is substituted for another value. Each â€ścharacterâ€ť is the same width but the efficiency can be improved when you consider that each character is not equally likely.Consider Morse code (pictured above). Characters in a message are encoded as a sequence of dashes and dots. Those dashes and dots are transferred over radio (typically) with a pause between them to delimit them.

Notice how the letter E (the most common letter in English) is a single dot, the shortest possible sequence, whereas Z (the least frequent) is two dashes and two beeps.

Such a scheme can significantly reduce the size of an

expectedmessage but comes at the cost of increasing the size of a random character sequence.It should be noted that Morse code has another inbuilt feature: dashes are as long as three dots so the above code is created with this in mind to minimize the use of dashes. Since 1s and 0s (our building blocks) donâ€™t have this problem, itâ€™s not a feature we need to replicate.

Lastly, there are two kinds of rests in Morse code. A short rest (the length of a dot) is used to distinguish between dots and dashes. A longer gap (the length of a dash) is used to delimit characters.

So how does this apply to our problem?

## Huffman Coding

There is an algorithm for dealing with variable length codes called Huffman coding. Huffman coding creates a variable length code substitution, typically uses expected frequency of the symbols to assign shorter values to the more common symbols.

In the above tree, the letter E is encoded as 000 (or left-left-left) and S is 1011. It should be clear that this encoding scheme is

unambiguous.This is an important distinction from Morse code. Morse code has the character separator so it can do otherwise ambiguous substitution (eg 4 dots can be H or 2 Is) but we only have 1s and 0s so we choose an unambiguous substitution instead.

Below is a simple implementation:

with static data:

and:

One possible output is:

For a starting position this equates to 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 bits.

## State Difference

Another possible approach is to combine the very first approach with Huffman coding. This is based on the assumption that most expected Chess boards (rather than randomly generated ones) are more likely than not to, at least in part, resemble a starting position.

So what you do is XOR the 256 bit current board position with a 256 bit starting position and then encode that (using Huffman coding or, say, some method of run length encoding). Obviously this will be very efficient to start with (64 0s probably corresponding to 64 bits) but increase in storage required as the game progresses.

## Piece Position

As mentioned, another way of attacking this problem is to instead store the position of each piece a player has. This works particularly well with endgame positions where most squares will be empty (but in the Huffman coding approach empty squares only use 1 bit anyway).

Each side will have a king and 0-15 other pieces. Because of promotion the exact make up of those pieces can vary enough that you canâ€™t assume the numbers based on the starting positions are maxima.

The logical way to divide this up is store a Position consisting of two Sides (White and Black). Each Side has:

As for the pawn location, the pawns can only be on 48 possible squares (not 64 like the others). As such, it is better not to waste the extra 16 values that using 6 bits per pawn would use. So if you have 8 pawns there are 48

^{8}possibilities, equalling 28,179,280,429,056. You need 45 bits to encode that many values.Thatâ€™s 105 bits per side or 210 bits total. The starting position is the worst case for this method however and it will get substantially better as you remove pieces.

It should be pointed out that there are less than 48

^{8}possibilities because the pawns canâ€™t all be in the same squareÂ The first has 48 possibilities, the second 47 and so on. 48 x 47 x â€¦ x 41 = 1.52e13 = 44 bits storage.You can further improve this by eliminating the squares that are occupied by other pieces (including the other side) so you could first place the white non-pawns then the black non-pawns, then the white pawns and lastly the black pawns. On a starting position this reduces the storage requirements to 44 bits for White and 42 bits for Black.

## Combined Approaches

Another possible optimization is that each of these approaches has its strength and weaknesses. You could, say, pick the best 4 and then encode a scheme selector in the first two bits and then the scheme-specific storage after that.

With the overhead that small, this will by far be the best approach.

## Game State

I return to the problem of storing a

gamerather than aposition. Because of the threefold repetition we have to store the list of moves that have occurred to this point.## Annotations

One thing you have to determine is are you simply storing a list of moves or are you annotating the game? Chess games are often annotated, for example:

Whiteâ€™s move is marked by two exclamation points as brilliant whereas Blackâ€™s is viewed as a mistake. See Chess punctuation.

Additionally you could also need to store free text as the moves are described.

I am assuming that the moves are sufficient so there will be no annotations.

## Algebraic Notation

We could simply store the the text of the move here (â€śe4â€ť, â€śBxb5â€ť, etc). Including a terminating byte youâ€™re looking at about 6 bytes (48 bits) per move (worst case). Thatâ€™s not particularly efficient.

The second thing to try is to store the starting location (6 bits) and end location (6 bits) so 12 bits per move. That is significantly better.

Alternatively we can determine all the legal moves from the current position in a predictable and deterministic way and state which weâ€™ve chosen. This then goes back to the variable base encoding mentioned above. White and Black have 20 possible moves each on their first move, more on the second and so on.

## Conclusion

There is no absolutely right answer to this question. There are many possible approaches of which the above are just a few.

What I like about this and similar problems is that it demands abilities important to any programmer like considering the usage pattern, accurately determining requirements and thinking about corner cases.

Chess positions taken as screenshots from Chess Position Trainer.