Min: 0 bits
Max: 1734 243 bits (4.335 4.401 bits/board amortized)
Expected: 351 177 bits (4.376 4.430 bits/board amortized)
Since I can determine the input and output however I want I decided to go with encoding the history of the game up until this point. One advantage is that the additional information of who's turn it is, en-passant, and who has the ability to castle where can be derived and not encoded.
Attempt 1:
Naively I thought that I can encode each move in 12 bits, 4 triplets of the form (start x, start y, end x, end y) where each is 3 bits.
We would assume the starting position and move pieces from there with white going first. The board is arranged such that
(
0
,
0
)
is white's lower left corner.
For example the game:
e4 e5
Nf3 f6
Nxe5 fxe5
... ...
Would be encoded as:
100001 100010 100110 100100
110000 101010 101110 101101
101010 100100 101101 100100
...
This leads to an encoding of 12 m bits where m is the number of moves made
On one hand this could get really big, on the other hand you can consider each move to be it's own game so each encoding really encodes m "chess boards". If you amortized this you get that each "chess board" is 12 bits. But I feel this is a bit cheating...
Attempt 2:
I realized that each move in the previous attempt encodes many illegal moves. So I decided to only encode legal moves. We enumerate possible moves as follows, number each square such that
(
0
,
0
)
→
0
,
(
1
,
0
)
→
1
,
(
x
,
y
)
→
x
+
8
y
. Iterate through the tiles and check if a piece is there and if it can move. If so add the positions it can go to to a list. Choose the list index that is the move you want to make. Add that number to the running total of moves weighted by 1 plus the number of possible moves.
Example as above:
From the starting position the first piece that can move is the knight on square 1, it can move to square 16 or 18, so add those to the list [(1,16),(1,18)]. Next is the knight on square 6, add it's moves. Overall we get:
[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Since we want the move
(
12
,
28
)
, we encode this as 13 in base 20 since there are 20 possible moves.
So now we get the game number
g0
=
13
Next we do the same for black except we number the tiles in reverse (to make it easier, not required) to get the list of moves:
[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Since we want the move
(
11
,
27
)
, we encode this as 11 in base 20 since there are 20 possible moves.
So now we get the game number
g1
=
(
11
⋅
20
)
+
13
=
233
Next we get the following list of moves for white:
[(1,16),(1,18),(3,12),(3,21),(3,30),(3,39),(4,12),(5,12),(5,19),(5,26),(5,33),(5,40),(6,12),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27)(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Since we want the move
(
6
,
21
)
, we encode this as 13 in base 29 since there are 29 possible moves.
So now we get the game number
g2
=
(
(
13
⋅
20
)
+
11
)
20
+
13
=
5433
Next we get the following list of moves for black:
[(1,11),(1,16),(1,18),(2,11),(2,20),(2,29),(2,38),(2,47),(3,11),(4,11),(4,18),(4,25),(4,32),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Since we want the move $(10, 18)$
(
10
,
18
)
So now we get the game number
g3
=
(
(
(
19
⋅
29
+
13
)
20
)
+
11
)
20
+
13
=
225833
And continue this process for all the remaining moves. You can think of g as the function
g
(
x
,
y
,
z
)
=
x
y
+
z
. Thus
g0
=
g
(
1
,
1
,
13
)
,
g1
=
g
(
g
(
1
,
1
,
11
)
,
20
,
13
)
,
g2
=
g
(
g
(
g
(
1
,
1
,
13
)
,
20
,
11
)
,
20
,
13
)
,
g3
=
g
(
g
(
g
(
g
(
1
,
1
,
19
)
,
29
,
13
)
,
20
,
11
)
,
20
,
13
)
To decode a game number g0, we start at the initial position and enumerate all possible moves. Then we compute g1 = g0 // l, m0 = g0 % l, where l is the number of possible moves, '//' is the integer division operator and '%' is the modulus operator. It should hold that g0 = g1 + m0. Next we make the move m0 and repeat.
From the example above if g0 = 225833 then g1 = 225833 // 20 = 11291 and m0 = 225833 % 20= 13. Next g2 = 11291 // 20 = 564 and m1 = 11291 % 20 = 11. Then g3 = 11291 // 20 = 564 and m2 = 11291 % 20 = 11. Therefore g4 = 564 // 29 = 19 and_m_3 = 564 % 29 = 13. Finally g5= 19 // 29 = 0 and m4 = 19 % 29 = 19.
So how many bits are used to encode a game this way?
For simplicity, let's say there are always 20 moves each turn and for the worst case scenario we always pick the biggest one, 19. The number we will get is
19
⋅
20m
+
19
⋅
20m-1
+
19
⋅
20m-2
+
⋯
+
19
⋅
20
+
19
=
20m+1
−
1
where _m is the number of moves. To encode
20m+1
−
1
we need about
log2
(
20m+1
)
bits which is about
(
m
+
1
)
∗
log2
(
20
)
=
4.3219
∗
(
m
+
1
)
On average m = 80 (40 moves per player) so this would take 351 bits to encode. If we were recording many games we would need a universal encoding since we don't know how many bits each number will need
Worst case when m = 400 (200 moves per player) so this would take 1734 bits to encode.
Note that the position we want to encode must be given to us via the shortest path to get there by following the rules. For example the game theorized here doesn't need m = 11741 to encode the final position. Instead we run a Breadth-First search to find the shortest path to that position and encode that instead. I don't know how deep we would need to go to enumerate all chess positions, but I suspect that 400 is an overestimate.
Quick calculation:
There are 12 unique pieces or the square can be empty so to position them on a chessboard is 1364. This is a vast overestimate since it includes many invalid positions. When we are m moves into the game we have created about 20m positions. So we are looking for when 20m =
1364. Log both sides to get m = 64 * log20(13) = 54.797. This shows that we should be able to get to any position in 55 moves.
Now that I calculated the worst case to be m = 55 not m = 400 I will edit my results. To encode a position where m = 55 takes 243 bits. I'm going to also say that the average case is around m = 40 which takes 177 bits to encode.
If we use the amortization argument from earlier we are encoding 400 "chess boards" in 1734 bits so we get that each "chess board" takes up 4.335 bits in the worst case.
Note that g = 0 denotes a valid game, the one where the piece on the lowest square moves to the lowest square it can.
Additional Notes:
If you want to refer to a specific position in the game you may need to encode the index. This can be added either manually e.g concatenate the index to the game, or add an additional "end" move as the last possible move each turn. This can now account for players conceding, or 2 in a row to denote the players agreed to a draw. This is only necessary if the game did not end in a checkmate or stalemate based on the position, in this case it is implied. In this case it brings the number of bits needed on average to 356 and in the worst case 1762.
