4 ms·
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, becaus
by vikingerik 1y ago
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.
- dooglius 1y agoYou 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.