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.
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).
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.
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).
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.
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.
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!
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.
> 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!)
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.
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.
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!
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.
The board rotation trick is very nice to achieve the short code length!
thank you i was so proud of it lmao
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.
>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.
There are*
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).
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.
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.
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!
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.
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.
> 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!)
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.
The LOC are really impressive and the implemention pretty smart. Thanks for sharing!
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!
Encode them in CJK and combining Unicode characters, to keep the visual representation as short as possible.
YOLO install command
You could pin to a commit for safety
Thats a fair point
Wow,I have a bash script that just starts a docker container with some fancy arguments roughly the same LOC...
I too am impressed with his bash script. Simple and concise.
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!