3 ms·

> 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 fie

> 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.

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.