Alex Rivera | Logout

Programmer Puzzle: Encoding a chess board state throughout a game

Asked 2009-12-02T08:16:13.003
101

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!

algorithm language-agnostic puzzle chess
Edit
Report

6 Answers

4

I saw this question last night and it intrigued me so I sat in bed thinking up solutions. My final answer is pretty similar to int3's actually.

Basic solution

Assuming a standard chess game and that you don't encode the rules (like White always goes first), then you can save a lot by encoding just the moves each piece makes.

There are 32 pieces total but on each move you know what colour is moving so there's only 16 squares to worry about, which is 4 bits for which piece moves this turn.

Each piece only has a limited moveset, which you would enumerate in some way.

  • Pawn: 4 options, 2 bits (1 step forward, 2 steps forward, 1 each diagonal)
  • Rook: 14 options, 4 bits (max of 7 in each direction)
  • Bishop: 13 options, 4 bits (if you have 7 in one diagonal, you only have 6 in the other)
  • Knight: 8 options, 3 bits
  • Queen: 27 options, 5 bits (Rook+Bishop)
  • King: 9 options, 4 bits (8 one-step moves, plus the castling option)

For promotion, there are 4 pieces to choose from (Rook, Bishop, Knight, Queen) so on that move we would add 2 bits to specify that. I think all the other rules are covered automatically (e.g. en passant).

Further optimizations

First, after 8 pieces of one colour have been captured, you could reduce the piece encoding to 3 bits, then 2 bits for 4 pieces and so on.

The main optimization though is to enumerate only the possible moves at each point in the game. Assume we store a Pawn's moves as {00, 01, 10, 11} for 1 step forward, 2 steps forward, diagonal left and diagonal right respectively. If some moves are not possible we can remove them from the encoding for this turn.

We know the game state at every stage (from following all the moves), so after reading which

answered 2009-12-04T13:42:26.660
2

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
answered 2009-12-27T15:31:33.427
1

As several others have mentioned you could for each of the 32 pieces you could store which square they're on and if they're on the board or not, this gives 32 * (log2(64) + 1) = 224 bits.

However the bishops can only occupy either the black or white squares so for these you only need log2(32) bits for the position, which give 28 * 7 + 4 * 6 = 220 bits.

And since the pawns don't start at the back and can only move forward, they can only be on 56, it should be possible to use this limitation to reduce the number of bits needed for the pawns.

answered 2009-12-02T08:40:16.553
1

Each piece can be represented by 4 bits (pawn to king, 6 types), black/white = 12 values

Each square on the board can be represented by 6 bits (x coord, y coord).

Initial positions require maximum of 320 bits (32 pieces, 4 + 6 bits)

Each subsequent move can be represented by 16 bits (from-position, to-position, piece).

Castling would require an extra 16 bits, as it's a dual move.

Queened pawns could be represented by one of the 4 spare values out of 4 bits.

Without doing the maths in detail, this starts to save space after the first move compared to storing 32 * 7 bits (predefined array of pieces) or 64 * 4 bits (predefined assignment of squares)

After 10 moves on both sides, the maximum space required is 640 bits

...but then again, if we identify each piece uniquely (5 bits) and add a sixth bit for flagging queened pawns, then we only need piece-id + to-position for each move. This changes the calculation to...

Initial positions = max 384 bits (32 pieces, 6 + 6 bits) Each move = 12 bits (to-position, piece-id)

Then after 10 moves on each side the maximum space required is 624 bits

answered 2009-12-02T09:00:48.523
1

Like Robert G, I'd tend to use PGN since it's standard and can be used by a wide range of tools.

If, however, I'm playing a chess AI that's on a distant space probe, and thus every bit is precious, this is what I'd do for the moves. I'll come bock to encoding the initial state later.

The moves don't need to record state; the decoder can take keep track of state as well as what moves are legal at any given point. All the moves need to record is which of the various legal alternatives is chosen. Since players alternate, a move doesn't need to record player color. Since a player can only move their own color pieces, the first choice is which piece the player moves (I'll come back to an alternative that uses another choice later). With at most 16 pieces, this requires at most 4 bits. As a player loses pieces, the number of choices decreases. Also, a particular game state may limit the choice of pieces. If a king can't move without placing itself in check, the number of choices is reduced by one. If a king is in check, any piece that can't get the king out of check isn't a viable choice. Number the pieces in row major order starting at a1 (h1 comes before a2).

Once the piece is specified, it will only have a certain number of legal destinations. The exact number is highly dependent on board layout and game history, but we can figure out certain maximums and expected values. For all but the knight and during castling, a piece can't move through another piece. This will be a big source of move-limits, but it's hard to quantify. A piece can't move off of the board, which will also largely limit the number of destinations.

We encode the destination of most pieces by numbering squares along lines in the following order: W, NW, N, NE (black side is N). A line starts in the square furthest in the given direction that's legal to move to and proceeds towards the. For an unencumbered king, the list of moves is W, E, NW, SE, N, S, NE, SW. For the

answered 2009-12-02T11:50:24.273
1

Algorithm should deterministically enumerate all possible destinations at each move. Number of destinations:

  • 2 bishops, 13 destinations each = 26
  • 2 rooks, 14 destinations each = 28
  • 2 knights, 8 destinations each = 16
  • queen, 27 destinations
  • king , 8 destinations

8 paws could all become queens in worst (enumeration-wise) case, thus making largest number of possible destinations 9*27+26+28+16+8=321. Thus, all destinations for any move can be enumerated by a 9 bit number.

Maximum number of moves of both parties is 100 (if i'm not wrong, not a chess player). Thus any game could be recorded in 900 bits. Plus initial position each piece can be recorded using 6 bit numbers, which totals to 32*6 =192 bits. Plus one bit for "who moves first" record. Thus, any game can be recorded using 900+192+1=1093 bits.

answered 2009-12-03T08:00:14.443

Your Answer