Programmer Puzzle: Encoding a chess board state throughout a game

user_40410 0
Viewed 54489

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!

puzzle chess language-agnostic algorithm
31 Answers

Most of the answers overlooked 3 fold repetition. unfortunately for 3 fold repetition you have to store all the positions played so far...

The question required us to store in space efficient manner so we really don't need to store position as long as we can construct it from the list of moves (provided we have standard starting position). We can optimize PGN and thats it we are done. Bellow is a simple scheme.

There are 64 squares on the board, 64 = 2^ 6. If we store only the initial and final square of each move that would take 12 bits (Promotion will be tackled later). Note that this scheme already covers player to move, emphassant, piece captured, castling etc; as of these can be constructed from just replaying the move list.

for promotion we can keep a separate array of vectors which would say "at move N promote to Piece XYZ". we can keep a vector of (int, byte).

It is tempting to optimize (To,From) vector also, Since many of these (To,From) vectors are not posible in chess. eg. there wont be a move from e1 to d8 etc. But I couldnt come up with any scheme. Any further ideas are most welcomed.

user_1163710

This is how I would encode the game steps. For a game with 40 steps this will take about 180 bits or so.

First, create a list of all the choices using an engine that knows all the chess rules. Each step, do this:

  1. Enumerate all pieces that are possible to move (at start, white can move 8 pawns and 2 knights, totals 10.
  2. Store both the number of possible choices and the choice itself.
  3. Enumerate all possible movement positions. (when pawn was choosen at the start, you can move 1 or 2 fields forward, so you have 2 possible choices.
  4. Again, store the number of possible choices and the choice itself.

This will get you a list like this:

[[10, 3], # choose white pawn at index #3
 [2, 0],  # move it one step forward
 [10, 2], # choose black pawn #2 
 [2, 1],  # move it two steps forward
 ...
]

And so on. To encode it, you just need to store the choice, not the number of possible moves. One way to store it is to find out how many bits are required for each choice:

[[10, 3], # 10 choices => 4 bits
 [2, 0],  # 2 choices => 1 bit
 [10, 2], # 10 choices => 4 bits
 [2, 1],  # 2 choices => 1 bit
 ...
]

Totals 4+1+4+1=10 bits for the first two moves. But a few bits are wasted, using 4 bits for 10 choices wastes 6 possible choices.

It is possible to do better: reverse the list, and calculate a number based on the possible choices and the choice taken:

n = 0         # last position
n = n*2 + 1   # from [2, 1]   n=1
n = n*10 + 2  # from [10, 2]  n=12
n = n*2 + 0   # from [2, 0]   n=24
n = n*10 + 3  # from [10, 3]  n=243

Now we have the number 243, binary 11110011, which encodes all the above steps in just 8 bits.

To decode, we know that the initial opening position has 10 possible choices. Calculate

n = 243
choice = n % 10  # we know there are 10 moveable pieces. => choice=3
n /= 10          # n=24
choice = n % 2   # we know 2 possible moves for selected pawn => choice=0
n /= 2           # n=12
choice = n % 10  # 10 moveable pieces for black player. => choice=2
n /= 10          # n=1
choice = n % 2   # 2 possible moves for pawn => choice=1
n /= 2           # n=0, finished decoding

Encoding is extremely efficient, especially the endgame because there are not many possible choices left. Also, when you only have one possible move left, you do not need any storage at all for that move.

martinus_481810
Related