Hacker News Reader

Comment by eurleif | Hacker News Reader

To me, the impressive part is implementing it in under 200 lines of bash script, not implementing it with only 64 bits of state. Nothing clever is required for 64 bits of state: a cell has 12 possible states (2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, and empty), which can be expressed in 4 bits, and 4*4*4 = 64.

View on HN

The board rotation trick is very nice to achieve the short code length!

        w) squish ;;
        a) rot; squish; rot; rot; rot ;;
        s) rot; rot; squish; rot; rot ;;
        d) rot; rot; rot; squish; rot ;;

thank you i was so proud of it lmao

It's the first code snippet I've read that also works as modernist poetry.

>a cell has 12 possible states

There is 18 states. The final possible board state is 16 increasing power of 2s starting at 4, since it's possible for a tile to spawn in as 4. Then you also need states for 2 and empty making for a total of 18.

That's a special case. You could have a single bit for special case mode and then very few bits to say what happened.

Usually you can encode special states in a more compact form because the type of specialness is additional information meaning the single special bit is all you need to grow by.

A bloated form for the final state would be a bit to indicate specialness, 7 bits for specialness mode. End state mode is encoded as the turn before plus direction. So adding 10 bits in all, there's almost certainly enough in the knowledge that it is an end state to encode the board in 10 bits fewer, eliminating all expansion except for the specialness bit.

It's not a special case, it's a change of the rules to allow numbers greater than 2048. Which are allowed in some implementations, but not this one.

It's the default rules.

This is correct (if cells higher than 2048 are allowed, which varies by implementation.) But the game can still be represented in fewer than 16×18 bits, because not every board state is reachable. There can't be more than one cell with the maximum value. And if that is present, then there can't be more than one cell with the next-highest value, and so on. So you could devise some scheme to enumerate all reachable states and skip unreachable ones, and it would take fewer than 16×18 bits to indicate which one. The upper bound is at least bounded by ignoring representing the maximum value and then using 4 bits to indicate its necessarily singular position. There are also some other unreachable configurations, like if many copies of the same value are touching each other, since at least one pair of them would have been combined on the previous move.

You can have cells with more than one value with the value above 2048 but below 128K, and I don't think your scheme works much in those cases. It seems like an open question as to whether there are more than 2^64 possible states without the 2048 limit.

There are*

13 possible states, because the empty state is important, too. But they fit nicely into 4 bits.

It would be mildly interesting to super-package the state into the theoretically smallest possible amount of bits: 13 * 16 = 665416609183179841 possible states, which is approximately 2 * 59.2, so 60 bits would be enough, with some margin. A whole hex digit shorter!

That's what the code already does. It packs 16 fields into a base 12 representation that takes up 57.36 bits and uses the remaining 6.64 bits to store a random seed between 0 and 99 (exclusive).

I included empty in my count.

Is that really the theoretically smallest?

I think you can prove that some states representable by your proposal are unreachable. E.g. a board with 16 2s. So there might be another bit to spare.

It ought to be possible to generate valid states ordered by total value and lexicographical order or something.

But whether that is practical is a different matter. It does allow you to unambiguously define state #5546335 with the lowest number of bits

Although at that point, your attempts to cut the state will probably resemble a look-up table enumerating every valid board state, which obviously balloons the executable size by a large amount.

yes but there could conceivably be better tricks to discover

It's not quite literally the smallest, but the interesting question is what fraction of all states represent such unreachable states.

Reply on news.ycombinator.com