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.
What do you mean by "bitwise"? – Peter Taylor – 2014-01-25T23:16:45.990
Is this smallest code or most-compressed? Most-compressed is more interesting. – Justin – 2014-01-26T00:15:29.007
Sorry for not clarifying. Bitwise in the sense that you can only compress it if you start representing it as bits, which will require some bitwise operation. Poor use on my part. Also most-compressed, not smallest code. – Seltzer – 2014-01-26T01:59:40.913
How are you planning to handle submissions with variable length? Rate by average size? Maximum size? – Kendall Frey – 2014-01-26T02:05:42.800
@KendallFrey My bad. I'd measure it by maximum size (in bits). Most good compressions will end up getting smaller as fewer pieces are on the board, and there can't be more than 32 total pieces (but if you end up doing a quasi-Huffman thing for pieces where pawn promotion could change things, you'll need to figure out the maximum number of pawns that could be promoted at any given time in a game. I don't have the wherewithal to say what that is, but I think it's possible (under ridiculous circumstances) to have all of them promoted by moving them into 4 single-file lines on each site. – Seltzer – 2014-01-26T02:21:58.880
2
@GeekWithALife Yes, it's possible to have 18 queens on the board at the same time. Follow this link and click the playback button for an example.
– r3mainer – 2014-01-26T09:19:23.283You probably want to impose a sensible time limit to exclude solutions which work by enumerating all possible board positions via move sequences and then indexing them. The combinatorics to justify the claimed score could be quite interesting, particularly if it's less than 170, but start to get a bit off-topic for this site. – Peter Taylor – 2014-01-26T15:21:25.607
@PeterTaylor What would be a good time limit for something like this? I'm new around here. – Seltzer – 2014-01-26T18:27:54.607
A minute or two should be ample for most reasonable answers, I would say. – Peter Taylor – 2014-01-26T22:26:36.733
If an identical position is reached three times with it being the same player's turn, then the game is a draw. Thus, you need to encode how many times the position has been reached. – Carl Love – 2014-01-27T02:16:46.267
An idea which I might not investigate fully, so I throw it out for other people to consider: if all 32 men are on the board, there are 15^8 possible configurations of the pawns, and the remaining 16 men fit into the remaining 48 squares. An encoding for which all 32 men on the board is the worst case can probably be improved by having one bit to switch between 32 men vs fewer. – Peter Taylor – 2014-01-27T09:33:42.957
@PeterTaylor Keep in mind that each bishop can only ever be on one color, so you can easily save a few bits there. – AJMansfield – 2014-01-28T01:11:38.567
1@AJMansfield, that might be useful for boards with about 28 men, but I calculate that 117 bits is plenty for boards with all 32 men, which is about 50 bits less than the target. The complication is that once you go below 32 men, promotion can give a player more bishops. – Peter Taylor – 2014-01-28T07:39:58.580
@PeterTaylor why would anyone promote to anything other than a queen or knight? – AJMansfield – 2014-01-28T13:30:17.360
An interesting variant of this problem, inspired by some of the wording earlier in this one, is to write a program that does compression like this, but only has to compress it for use by some type of AI program, allowing parts that the AI ignores anyway to be left out. – AJMansfield – 2014-01-28T13:32:23.573
@AJMansfield, usually for reasons to do with stalemate, but the motivation is irrelevant. The question is whether a position is reachable by legal moves, not whether it is reachable by competent players. – Peter Taylor – 2014-01-28T14:05:14.233
Speaking of legal moves: Is it a legal move to "promote" a pawn into a pawn (i.e. not to promote it at all)? That is, does there exist a legal position where a white pawn is on row 8, or a black pawn is on row 0? (Of course no one in his right mind would do that, but it certainly affects the achievable compression). – celtschk – 2014-03-24T22:41:35.647
OK, I've now found out myself: It must be promoted to another piece. – celtschk – 2014-03-24T22:59:34.497
FYI, this is the http://wismuth.com/chess/statistics-positions.html definition of a "position"
– William Entriken – 2014-04-19T15:36:19.927See also: minimum encodings of chess games: http://phor.net/apps/ign/
– William Entriken – 2014-04-19T15:36:50.483@GeekWithALife Will you review answers here? – William Entriken – 2014-05-14T19:48:48.227