[HN Gopher] 2048 with only 64 bits of state
___________________________________________________________________
2048 with only 64 bits of state
Author : todsacerdoti
Score : 83 points
Date : 2025-06-19 16:43 UTC (3 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| meta-level wrote:
| Wow,I have a bash script that just starts a docker container with
| some fancy arguments roughly the same LOC...
| JoeOfTexas wrote:
| I too am impressed with his bash script. Simple and concise.
| kinduff wrote:
| The LOC are really impressive and the implemention pretty smart.
| Thanks for sharing!
| lotyrin wrote:
| I was thinking "wow, how do you do that?" but then I forgot
| you're not dealing with any possible value between 1 and 2048 in
| a cell, only the powers of 2, so significantly fewer possible
| board states. Very cool.
|
| I feel people often miss opportunities to map between
| (potentially complex, high entropy) state spaces into simple
| linear sequences of possible states and then either use those
| sequences to store the complex state data as a simple number or
| use the state of a system to encode data of some kind.
|
| Like, if you use a limited 7-bit character set encoding for text
| and map that to a number in a sequence of possible orderings of a
| deck of 52 cards, you can store 32 characters (conveniently sized
| for passwords you might not want people to know are passwords).
| carra wrote:
| It is worth mentioning that in the original game you can choose
| to keep going after you reach 2048. This game had to remove that
| option to achieve a 64bit state. Still, a clever implementation.
| enriquto wrote:
| > keep going after you reach 2048. This game had to remove that
| option to achieve a 64bit state.
|
| Since 15^16 < 2^64, you can still use a 64 bit state to reach
| 2^15=32768, which does not seem to be reachable in practice
| (the previous state would fill the whole board!)
| ToValueFunfetti wrote:
| 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
| sltkr wrote:
| 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.
| nneonneo wrote:
| Cool! I used a similar trick in my 2048 AI:
| https://github.com/nneonneo/2048-ai. In my case I allow the tiles
| to go all the way up to 32768, so I just have one tile per
| nybble.
|
| Using this representation is great: it lets me pack a whole
| gameboard into a single machine register, which makes it super
| efficient. In this case I see that you're able to pack in a seed
| value to enable replayability - neat!
| enriquto wrote:
| Total number of states = 11^16, assuming you don't reach 2048,
| just like you don't actually kill the king in chess.
|
| Now log_2(11^16)=55.34, thus 56 bits are sufficient. That's
| _tight_!
| nine_k wrote:
| Encode them in CJK and combining Unicode characters, to keep
| the visual representation as short as possible.
| eurleif wrote:
| 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.
| charcircuit wrote:
| >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.
| Lerc wrote:
| 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.
| pixelpoet wrote:
| There are*
| nine_k wrote:
| 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!
| eurleif wrote:
| I included empty in my count.
| sltkr wrote:
| 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).
| mark_undoio wrote:
| Always fun to see what izabera has come up with - every single
| time I'm somewhere between delighted and terrified to see what
| she's made the computer do this time!
| Normal_gaussian wrote:
| YOLO install command curl -fsSL
| https://raw.githubusercontent.com/izabera/bitwise-
| challenge-2048/develop/2048.bash -o "$HOME/bin/2048" && chmod +x
| "$HOME/bin/2048" && 2048
___________________________________________________________________
(page generated 2025-06-22 23:00 UTC)