I'm not sure how the math works out, but some googling suggests that 32768 is achievable in practice while 65536 and 131072 are theoretically possible but have only been achieved with undos.

edit: Explanation of the 131072 cap: https://puzzling.stackexchange.com/questions/48/what-is-the-...

Also, in one of the answers there someone claims to have achieved 65536 in practice

You need 16^16 for 32768 because 0 is used to represent an empty tile (2^0 = 1 is not used) which is exactly equal to 2^64.

The state in this implementation also stores a random seed (between 0 and 99, exclusive), so using 16^16 for the state would leave nothing for the random seed.

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.

There are*

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.

I included empty in my count.

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

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.

thank you i was so proud of it lmao

Thats a fair point

    curl -fsSL https://raw.githubusercontent.com/izabera/bitwise-challenge-2048/413abf35be0f47c4947a5ebd6d581355383041e1/2048.bash -o "$HOME/bin/2048" && chmod +x "$HOME/bin/2048" && 2048

Doesn't happen for me, i wonder if it's only on certain architectures or certain versions of bash or something

thanks, i fixed it. it was only happening on bash 3.2 and i don't use a mac so i didn't see it. https://github.com/izabera/bitwise-challenge-2048/commit/73f...