[HN Gopher] 2048 with only 64 bits of state
___________________________________________________________________
2048 with only 64 bits of state
Author : todsacerdoti
Score : 167 points
Date : 2025-06-19 16:43 UTC (4 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
| ghghgfdfgh wrote:
| 65536 has been achieved by 2 people without undos. However,
| it is very difficult as it's only around a 7% chance with
| optimal play.
|
| This is a partial video of one of them:
| https://youtube.com/watch?v=QQSLjPHg5P8
| 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!
| kccqzy wrote:
| Love the fact that you refer to your program as AI. We need
| more people to use AI to refer to non-LLM technologies lest the
| term be redefined.
| 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.
| dmurray wrote:
| 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.
| charcircuit wrote:
| It's the default rules.
| pixelpoet wrote:
| There are*
| vikingerik wrote:
| This is correct (if cells higher than 2048 are allowed, which
| varies by implementation.) But the game can still be
| represented in fewer than 16x18 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 16x18 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 wrote:
| 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.
| 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).
| dmurray wrote:
| 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.
| YurgenJurgensen wrote:
| 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.
| whereismyacc wrote:
| yes but there could conceivably be better tricks to
| discover
| shiandow wrote:
| 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
| sltkr wrote:
| It's not quite literally the smallest, but the interesting
| question is what fraction of all states represent such
| unreachable states.
| kccqzy wrote:
| 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 ;;
| izabera wrote:
| thank you i was so proud of it lmao
| retsibsi wrote:
| It's the first code snippet I've read that also works as
| modernist poetry.
| 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
| teaearlgraycold wrote:
| You could pin to a commit for safety
| Normal_gaussian wrote:
| Thats a fair point curl -fsSL
| https://raw.githubusercontent.com/izabera/bitwise-challenge-2
| 048/413abf35be0f47c4947a5ebd6d581355383041e1/2048.bash -o
| "$HOME/bin/2048" && chmod +x "$HOME/bin/2048" && 2048
| hofrogs wrote:
| Why not $HOME/.local/bin
| bvanderveen wrote:
| Like others I found the concise implementation to be impressive!
| I have noticed a bug though. Using the "drive into the corner"
| strategy (I keep the high tile in the bottom left) sometimes the
| top left tile randomly gets a smaller value (e.g., goes from 16
| -> 4) when I slide to the left.
| chadrs wrote:
| Yeah, the first few times I thought maybe I was just imagining
| it; but I went from STATE=7280398215952, tried to merge my 64s
| into the left corner and instead ended up in
| STATE=7280398025476; my 64s have become 4s.
|
| Can't reproduce it exactly as it happened, but if I run
| `STATE=7280398215952 bash 2048.bash` and press a 8 times, the
| 128 always becomes a 2.
| shawabawa3 wrote:
| Doesn't happen for me, i wonder if it's only on certain
| architectures or certain versions of bash or something
| izabera wrote:
| 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...
| rossant wrote:
| I'd love to see a minimal C program or similar, implemented as a
| single function `int64 run_2048(int64 state, int input)`, which
| takes the current state and an input (left, right, up, down), and
| returns the next state. Could be an interesting code golf
| exercise.
___________________________________________________________________
(page generated 2025-06-23 23:02 UTC)