How to store a chess game efficiently?

What's the most space efficient way to store an entire chess game in a database? considering an avg game length of 50-70 moves (1 move means 2 player moves once), i hope it takes less than 800 bits.

The initial place of the piece could be stored in 6 bits and the move could take 2-4 bits. is there any way to store it less than that?

You could enumerate all legal moves in a given position, and sort them in an agreed way (like by starting square, then by target square, then by promotion piece -- if it concerns promotion, ...). Then identify each move by its index in this sorted list of legal moves.

The (theoretical) position found with the most legal moves has 218 legal moves. We can be confident there is no position with more than 256 legal moves, so 8 bits are enough to encode a single move.

With this encoding a game of 70 moves would need 560 bits.

Dynamic number of bits

It is however clear that in most positions the number of legal moves is more like 40 and not 218, so we could have the number of bits for the next encoded move depend dynamically on the number of legal moves that are available.

Since the start position only has 20 moves, the first white move would be encoded with just 5 bits; the same for the first black move. As the game continues, there soon will be a position that has more than 32 legal moves, so 6 bits will be used. For instance, after

1. e3 e5
2. Qg4 d6

...white has 46 legal moves, so their move will be encoded using 6 bits. We already saved 3 x 4 = 12 bits (compared to 8 bits per move) for encoding these first four moves.

While encoding, the algorithm will first check how many legal moves there are, and then use the corresponding number of bits to encode the next move. Also the decoder can know the number of legal moves and then consume that number of bits from the encoded stream.

I don't know what would be a worst-case 70-move game in terms of number of needed bits (not feasible to compute in reasonable time), but it will be well below 500 bits.

Minimizing for reasonable games

The above derived limits are applicable to any game, even games where the players make the worst moves. If however you want to focus on reasonable games, you can further optimise the memory footprint:

Use a deterministic chess engine that produces a score for every legal move, and use the score as a probability for that move actually being played. It is important that it will always produce the same score for the same move in the same game state. Use Huffman encoding to encode the move accordingly. This will mean that good moves will take fewer bits than bad moves. For instance, if the Queen can be captured, this could even become a move with just one bit. Stupid moves will need more bits than average, maybe even more than 8 bits (when there are many legal moves and they include very good and very bad moves). A 70-move game where almost all moves are bad could take up more bits than with the non-Huffman encoding algorithm, but reasonable games would use less.

Number the squares 0-63. Count the number of squares reachable by the current side. Use the minimum number of bits to represent which of the reachable squares was moved to in ceiling(log_2(reachable square count)) bits.

When multiple pieces could move to the destination square, use the same approach to select which of the possible source squares for that destination square was used.

Here's an example using the first few moves from Kasparov v Topalov 4/13/13. I'm numbering with 0 on the bottom-left (white's queen rook starts at 0, white's queen knight at 1, and so on).

1. e4d6 1100 encodes that this is the 12th of 16 possible squares (0-indexed so 0000 would record e3); no additional bits are needed since only one piece can move here.

2. d4Nf6 1011 encodes that this is the 11th of 16 possible squares; again no additional bits are needed.

3. Nc3g6 01101 encodes that this is the 13th of 25 possible squares; again, no additional bits are needed.

4. Be3Bg7 10001 encodes that this is the 14th of 17 possible squares. Here, the move could have come from two squares (knight or pawn), so we need 1 bit to distinguish which, for a final encoding of 100011.

The bits-per-move this requires will depend on the game. The destination can never require more than 6 bits, and I believe most moves in most games will require only 5. I don't think we should expect <= 4 except for the opening moves and some endgame situations.

The disambiguation step (which of multiple squares move to the destination) will come up fairly often. My guess is that most moves won't require it, but that some moves with 1-2 bits and rarely 3 will come up in most games.

So, without doing the work to implement this and analyze real chess games, I'd expect this to record games in ballpark 6 bits per move on average. It'll be more efficient in games with a long stretch with limited moves (e.g. a long endgame with no rooks or bishops).

chess with naive encoding needs 2*6 bits per move:

number_of_moves(7 bits)
start_position (6bits) - target_position (6bits)
start_position (6bits) - target_position (6bits)
...

for example:

70
E2 - E4
D7 - D5
...

3 bits for letter A..H and 3 for number 1..8 and each move has 2 positions.

70 moves * 12 bits + 7 bits = 847 bits = 106 Bytes

This is already near your desired 800 bits. Now just apply compression either Huffman or LZW.

Now you can use 10 bits per move encoding by exploiting that there is only 16 (0..15 -> 4 bits) chess piece per side. Each game starts with white (so odd moves are white and even are black) so change the encoding to:

number_of_moves(7 bits)
white_piece_ix (4bits) - target_position (6bits)
black_piece_ix (4bits) - target_position (6bits)
...

this leads to:

70 moves * 10 bits + 7 bits = 707 bits = 89 bytes

Which is below your 800 bits already

If this is not enough you could use variable chess piece index table. So each time some piece is "deleted" from board you shift the value of indexes so the unused chess piece will be used by next index and the gap will be at the end values (so if piece 13 is removed then pieces 14,15 would become 13,14). This way once one side has less than 8 pieces you can use 3 bits per its index, less than 4 use 2 bits and so on you will end up with 7 .. 10 bits per move.

Now you could also apply compression (LZW or Hufman) I would go for LZW as Huffman needs to pass also probabililty distribution table which would be:

16 * ceil(log2(2*70)) bits = ~ 128 bits

Which is relatively large portion of data in comparison to 800 bits limit, while LZW constructs its dictionary on the run and its size can be chosed arbitrarily (so even if there is small RAM it should not be a big problem)

There are 32 pieces and 64 squares. So it requires 11 bits to store a piece and its position: 5 bits for the piece and 6 bits for the position.

The starting position is fixed, so there's no need to store it. After that, you only have to store the positions of the pieces that move: 11 bits per piece. That is, your stored game is just recording the individual piece moves. You know where the piece started, so all you have to store is where the piece ended up.

Most moves, then, can be stored in 11 bits (one piece moves). Oddly enough, a capture can be encoded by updating only the capturing piece's position. Game logic could see that two pieces are occupying the same space, and remove the captured piece from the board. Which is a good thing, because there's no 65th space (i.e. "not on the board") to put it: you don't have bits for it. En passant can be encoded in much the same way: let the game logic understand it.
I had originally thought that castling would require encoding two piece moves, but it really doesn't. The king always moves two spaces, which in any other situation would be an illegal move. Your logic could easily identify the "illegal" move and do the right thing.

Pawn promotions are a problem. The move isn't the problem, but you need some way to refer to the newly-created piece. There are only 5 bits for pieces and those are already used up. Consider moving your Kings Knight Pawn from G7 to G8. Normally, what you'd store is [14,62] (i.e. piece number 14 moves to position 62). You'd need some way to signal that, hey, piece number 14 is now a Queen instead of a pawn. It can be done, but it'd take some extra bits.

So the best case in a 70-move game is 11 bits per move or 770 bits. In a 50-move game it's 550 bits.

It'd be tight, but I think what you're asking just might be possible even before adding any type of compression or complex logic. Certainly you could average 800 bits per game for games of 50 to 70 moves.

Lots of clever answers, but there are at most 16 pieces that could move on each turn, and fewer than 32 moves for each piece (count castling as a king move and promotion as a pawn move).

That's 4 bits for the piece and 5 bits for the move -- 9 bits per turn. Easy peasy.