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!