title: Programmer Puzzle: Encoding a chess board state throughout a game
body: <p>Not strictly a question, more of a puzzle...</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>So I thought I'd throw one of my questions out there for the Stack Overflow audience. </p>
  
  <p>Question: <strong>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.</strong></p>
  
  <p>No code required for the answer, just a description of the algorithm you would use.</p>
  
  <p>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 :)</p>
  
  <p>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.</p>
  
  <p>EDIT3: It's going to be difficult to pick a winner here :) Lots of great answers!</p>