8 ms·

The entire game history (all possible moves / state) from the first move to the 9th move can be encoded into 18 bits. This also allows reconstruction of the gam

The entire game history (all possible moves / state) from the first move to the 9th move can be encoded into 18 bits. This also allows reconstruction of the game state after every move. The trick is to use the encoding logic for video compressors, start with a keyframe and encode delta frames. In this case, a delta frame would be to determine the number of available spaces, and store the next move. The number of available spaces decrements after every move, so you need less bits. A further space optimisation can be to reuse unused bit values from subsequent moves. Eg. for the 3rd move, there are 7 available fields. This can be packed into 3 bits, with one value spare. The spare can be borrowed to move 1, which has 9 fields. This allows the following optimisation: 1st / 9 / 3 bits (-1) 2nd / 8 / 3 bits (0) 3rd / 7 / 3 bits (+1) (used to complete 1st) 4th / 6 / 3 bits (+2) 5th / 5 / 2 bits (-1) (use 4th extra) 6th / 4 / 2 bits (0) 7th / 3 / 1 bit (-1) use 4th extra 8th / 2 / 1 bit (0) 9th / 1 / 0 bits Total = 18 bits. This is for the entire game history, from the first to last move, and every board state in between. Decoding this 18 bit mask is not really that challenging, since there are only 3 special cases, and the 9th move requires no bits to store the move (since there is only one possible move). To reconstruct the state at any given time, you need to start from the keyframe and move forward. 18 bits for entire game history.

ufocia 3y ago
I'm thinking that there may be a way to reduce that further if you consider symmetry/rotation or don't care much about the sequence, e.g. selecting any corner or edge on the first move is equivalent and since we know that the first move must happen we only need less than 2 bits (2 at most) to encode the first move i.e. 3 states: corner, edge, or center.
lifthrasiir 3y ago
> Eg. for the 3rd move, there are 7 available fields. This can be packed into 3 bits, with one value spare. The spare can be borrowed to move 1, which has 9 fields. This reasoning is not true. Let's say that the 1st move has 9 possible choices of A through I, while the 3rd move has 7 possible choices of 1 through 7 (which would depend on prior moves). When the 3rd move is made, your choice for the 3rd move has to be fixed and there is no "spare" choice available. If you chose to use that spare choice, you must use 3 bits allocated for the 1st move somehow differently so that both 1st and 3rd moves are uniquely determined. As a concrete example, let's represent A/1 as 000, B/2 as 001, ..., G/7 as 110 and H as 111. Any combination of [A-G][1-7] should be trivial to encode. If the first move is I however, you have to use the spare choice for the 3rd position to represent that fact. The 3rd move itself then has to move into bits originally used by the 1st move. Note that this leaves one unused bit pattern: 111111, which demonstrates why your reasoning is incorrect---this happens because the number of possibilities muliplies, not adds, and 9 * 7 < 8 * 8. In general the optimal packing of 9 moves would need 9 * 8 * ... * 1 = 362 880 possibilities, which exceeds 2^18 = 262 144 possibilities which 18 bits can encode, so you actually need 19 bits. (Or 20 bits if you also account for 623 530 mid-game states.)
- smallstepforman 3y ago
  Regarding the first move, 3 bits store 8 values. However, the spare value on move 3 signals us to ignore any value in the original move 3 bits and treat it as a special case to give the 9th value we need.
- quuxplusone 3y ago
  Right, the logic of "take a spare representation from here and use it to encode an extra state from over there" doesn't work in general, and sinks GP's whole idea. But since 9×7 < 8×8, it does _in practice_ work to encode 9×7 states in 3+3 bits. Where GP's idea breaks down pragmatically (as well as logically) is when he tries to take _two_ spare representations and use them to encode _two_ extra states, for bits 6, 5, and 3. It's true that 6 = 2^3 - 2, 5 = 2^2 + 1, 3 = 2^1 + 1; but you can't represent 6×5×3 = 90 states using only 2^(3+2+1) = 64 representations. In short: If A = 2^a + k and B = 2^b - k, then we can cancel the k when adding A+B, but not when multiplying A×B.
dolmen 3y ago
One could use variable length, as once some player wins the game is done.

ufocia 3y ago

I'm thinking that there may be a way to reduce that further if you consider symmetry/rotation or don't care much about the sequence, e.g. selecting any corner or edge on the first move is equivalent and since we know that the first move must happen we only need less than 2 bits (2 at most) to encode the first move i.e. 3 states: corner, edge, or center.

lifthrasiir 3y ago

> Eg. for the 3rd move, there are 7 available fields. This can be packed into 3 bits, with one value spare. The spare can be borrowed to move 1, which has 9 fields. This reasoning is not true. Let's say that the 1st move has 9 possible choices of A through I, while the 3rd move has 7 possible choices of 1 through 7 (which would depend on prior moves). When the 3rd move is made, your choice for the 3rd move has to be fixed and there is no "spare" choice available. If you chose to use that spare choice, you must use 3 bits allocated for the 1st move somehow differently so that both 1st and 3rd moves are uniquely determined. As a concrete example, let's represent A/1 as 000, B/2 as 001, ..., G/7 as 110 and H as 111. Any combination of [A-G][1-7] should be trivial to encode. If the first move is I however, you have to use the spare choice for the 3rd position to represent that fact. The 3rd move itself then has to move into bits originally used by the 1st move. Note that this leaves one unused bit pattern: 111111, which demonstrates why your reasoning is incorrect---this happens because the number of possibilities muliplies, not adds, and 9 * 7 < 8 * 8. In general the optimal packing of 9 moves would need 9 * 8 * ... * 1 = 362 880 possibilities, which exceeds 2^18 = 262 144 possibilities which 18 bits can encode, so you actually need 19 bits. (Or 20 bits if you also account for 623 530 mid-game states.)

smallstepforman 3y ago
Regarding the first move, 3 bits store 8 values. However, the spare value on move 3 signals us to ignore any value in the original move 3 bits and treat it as a special case to give the 9th value we need.
quuxplusone 3y ago
Right, the logic of "take a spare representation from here and use it to encode an extra state from over there" doesn't work in general, and sinks GP's whole idea. But since 9×7 < 8×8, it does _in practice_ work to encode 9×7 states in 3+3 bits. Where GP's idea breaks down pragmatically (as well as logically) is when he tries to take _two_ spare representations and use them to encode _two_ extra states, for bits 6, 5, and 3. It's true that 6 = 2^3 - 2, 5 = 2^2 + 1, 3 = 2^1 + 1; but you can't represent 6×5×3 = 90 states using only 2^(3+2+1) = 64 representations. In short: If A = 2^a + k and B = 2^b - k, then we can cancel the k when adding A+B, but not when multiplying A×B.

dolmen 3y ago

One could use variable length, as once some player wins the game is done.