The Mathematics of 2048: Counting States with Combinatorics(jdlm.info)
jdlm.info
The Mathematics of 2048: Counting States with Combinatorics
http://jdlm.info/articles/2017/09/17/counting-states-combinatorics-2048.html
48 comments
I like that you can inject your own moves, and try to make the AI to loose... it's really impressive. As someone else mentioned, it's really cool to see how it seems to "play freely" with no simplified strategy like the left-down-up.
> reaching the 2048 tile 100% of time
Lies!
https://i.imgur.com/Mi3lGzG.png
(I didn't interfere)
Lies!
https://i.imgur.com/Mi3lGzG.png
(I didn't interfere)
Ok I'm guessing you used more than 100 iterations per move because it failed the second time too
If not, my computer is really terrible at 2048 :P
If not, my computer is really terrible at 2048 :P
Do you think you could get it to prefer the left-down-up strategy as described elsewhere in this thread? (Personally, I used left-down-right, but it's all the same). Then it should be possible to increase the chances of reaching 4096. I myself have reached 8192 with that strategy and heard about other people getting to 16384.
One easy way would be to skew the AI evaluation score heavily towards states with lower numbers of tiles. Maybe log(score) - num-tiles?
One easy way would be to skew the AI evaluation score heavily towards states with lower numbers of tiles. Maybe log(score) - num-tiles?
My main goal was to create a player without embedding any human developed strategy (such as left-down-up). This would obviously be less optimal but more general purpose.
If you are interested in domain specific algorithms, the same StackOverflow question I linked features a solution using a min-max variant using an elaborate hand-crafted scoring function. It's best run scored 794076 points and got the "32768" tile.
If you are interested in domain specific algorithms, the same StackOverflow question I linked features a solution using a min-max variant using an elaborate hand-crafted scoring function. It's best run scored 794076 points and got the "32768" tile.
You might be pleased to know this is fairly close to Monte Carlo tree search, the best algorithm for general game solving, until Google's deep learning came along.
I thought AlphaGo was still using Monte Carlo tree search, just with two neural networks: one to estimate the board values, and one to estimate likelihood of moves for sampling.
Sort of, it uses Monto Carlo + a bunch of other things. [0]
[0] https://medium.com/@karpathy/alphago-in-context-c47718cb95a5
[0] https://medium.com/@karpathy/alphago-in-context-c47718cb95a5
Would be nice to see a similar analysis done on Threes given that it came before 2048. By game design standards, 2048 is very poorly designed. 2048 is easily beatable whereas Threes takes a lot longer to master and beat [0].
[0] http://asherv.com/threes/threemails/
[0] http://asherv.com/threes/threemails/
I've seen this before, and it smacks very much of sour grapes. What exactly makes it "better designed"? Is it simply that the goal posts for 2048 are set too low, and the goal posts for Threes is set too high?
If you aim for 4096 or 8192 or 16384 (all achievable) in 2048, it's a much more difficult game that requires careful thought and planning.
I enjoy Threes immensely, and find myself still replaying it (as I replay 2048), but I don't see an argument for it being objectively better. The fact that tiles only move by one allows you a lot more flexibility in repairing places where bad luck (or bad play) has landed you an out-of-order gap.
But Threes has flaws; I think the biggest design flaw in Threes is that the incoming blocks are too varied -- the 1/2 is the central conceit of the game, but higher blocks (and especially the occasional super-large block) make the element of chance way too important. And even the 1/2 thing can get annoying -- when the board is half-full of reds with no blues showing up, what can you do? You're just stuck.
At least 2048 is fairly consistent -- the presence of the occasional 4-block is a bit ugly, but otherwise the game has an element of predictability that puts the onus for progress squarely on the player rather than the random number generator, which mainly serves to make sure that each game is different.
If you aim for 4096 or 8192 or 16384 (all achievable) in 2048, it's a much more difficult game that requires careful thought and planning.
I enjoy Threes immensely, and find myself still replaying it (as I replay 2048), but I don't see an argument for it being objectively better. The fact that tiles only move by one allows you a lot more flexibility in repairing places where bad luck (or bad play) has landed you an out-of-order gap.
But Threes has flaws; I think the biggest design flaw in Threes is that the incoming blocks are too varied -- the 1/2 is the central conceit of the game, but higher blocks (and especially the occasional super-large block) make the element of chance way too important. And even the 1/2 thing can get annoying -- when the board is half-full of reds with no blues showing up, what can you do? You're just stuck.
At least 2048 is fairly consistent -- the presence of the occasional 4-block is a bit ugly, but otherwise the game has an element of predictability that puts the onus for progress squarely on the player rather than the random number generator, which mainly serves to make sure that each game is different.
In case you're not aware, the reds and blues are not random.
The 'deck' of the game has 12 cards in it[1], 4 ones, 4 twos, and 4 threes. These are shuffled and then played one at a time. After all 12 have come out, they are shuffled again.
This means you can plan for which card is to come next. Yes, you will sometimes get 4 (or more!) blues in a row, but developing strategies that allow you to survive those situations is one of the things you have to do if you want to get the 6144 tile.
[1] this isn't quite accurate, as sometimes a large card is inserted into the deck, I think on average 1 every 36 cards, but I don't actually remember.
The 'deck' of the game has 12 cards in it[1], 4 ones, 4 twos, and 4 threes. These are shuffled and then played one at a time. After all 12 have come out, they are shuffled again.
This means you can plan for which card is to come next. Yes, you will sometimes get 4 (or more!) blues in a row, but developing strategies that allow you to survive those situations is one of the things you have to do if you want to get the 6144 tile.
[1] this isn't quite accurate, as sometimes a large card is inserted into the deck, I think on average 1 every 36 cards, but I don't actually remember.
I'd agree that 2048 is quite forgiving --- you can make some pretty serious errors and still recover to win [1]. I wouldn't say that makes it poorly designed, however; harder isn't always better, and making a game too hard can make it less fun, so it's about finding a balance that works.
That said, flappy bird came out at about the same time as 2048 [2], and it was absurdly hard (at least for me) and still very successful.
[1] In my previous post, http://jdlm.info/articles/2017/08/05/markov-chain-2048.html, I managed to win in around the minimum number of moves, 938.8 on average, several times. I think that was often because I was able to recover from blunders, rather than because I never made them.
[2] https://en.wikipedia.org/wiki/Flappy_Bird --- both were very popular in early 2014.
That said, flappy bird came out at about the same time as 2048 [2], and it was absurdly hard (at least for me) and still very successful.
[1] In my previous post, http://jdlm.info/articles/2017/08/05/markov-chain-2048.html, I managed to win in around the minimum number of moves, 938.8 on average, several times. I think that was often because I was able to recover from blunders, rather than because I never made them.
[2] https://en.wikipedia.org/wiki/Flappy_Bird --- both were very popular in early 2014.
Popular does not mean well-designed. Neither was I implying that a difficult game is a well-designed game. But Threes is way better designed than 2048. The super long email chain I linked to earlier really explains why in great detail. I encourage anyone interested in game design and how indie games are made to take some time to read it.
> When an automated script that alternates pressing up and right and left every hundreth (sic) time can beat the game, then well, that's broken. Is Threes a better game? We think so. To this day, only about 6 people in the world have ever seen a 6144 and nobody in the world has yet to “beat” Threes. But that’s what’s better to us as game designers. We worked really hard to create a simple game system with interesting complexity that you can play forever.
To me, it seems the argument of the linked article basically boils down to: their game is too easy so it's bad. Does a game need a really long email chain of back and forth to show that it was well-designed?
To me, it seems the argument of the linked article basically boils down to: their game is too easy so it's bad. Does a game need a really long email chain of back and forth to show that it was well-designed?
The intro post says, paraphrasing, "we wanted to design a game with simple rules that was impossible to beat, we succeeded, therefore our game is better". Perhaps the authors prefer games that are impossible to beat - I think it's very unlikely that the target audience of 2048 and similar games do, or in fact most people.
Perhaps neither Threes nor 2048 are very well designed - Threes because building a game that is impossible to beat is easy but not actually much fun for most people to play, and 2048 because it wound up with overly methodical ways to beat it easily?
Perhaps neither Threes nor 2048 are very well designed - Threes because building a game that is impossible to beat is easy but not actually much fun for most people to play, and 2048 because it wound up with overly methodical ways to beat it easily?
> Popular does not mean well-designed.
Maybe but playing devil's advocate for a moment: given the point of a game is to be enjoyable and popularity is as good a measure of group enjoyment as any, you could then argue that a "better designed" game which fewer people prefer is arguably "over designed" compared to the simpler and more popular game. Ergo one could argue that popularity is a perfectly good measure of how well designed a game is.
Personally what draws me to 2048 is that it required just the right amount of thinking. It doesn't stimulate me so I can play it fatigued, but equally it doesn't bore me. And it is just the right level of difficulty where I can regularly beat it but equally I cannot take winning as an assumption so I still have to try to beat it.
Going back to your Flappy Birds example, that was hard as hell but the mechanics were really really easy to learn and you were only competing against your own personal best (there's no finish goal, no boss, just an infinite number of pipes to navigate through). That means as tough as the game is, it's only as hard as the individual is good at it.
Maybe but playing devil's advocate for a moment: given the point of a game is to be enjoyable and popularity is as good a measure of group enjoyment as any, you could then argue that a "better designed" game which fewer people prefer is arguably "over designed" compared to the simpler and more popular game. Ergo one could argue that popularity is a perfectly good measure of how well designed a game is.
Personally what draws me to 2048 is that it required just the right amount of thinking. It doesn't stimulate me so I can play it fatigued, but equally it doesn't bore me. And it is just the right level of difficulty where I can regularly beat it but equally I cannot take winning as an assumption so I still have to try to beat it.
Going back to your Flappy Birds example, that was hard as hell but the mechanics were really really easy to learn and you were only competing against your own personal best (there's no finish goal, no boss, just an infinite number of pipes to navigate through). That means as tough as the game is, it's only as hard as the individual is good at it.
> popularity is as good a measure of group enjoyment
Popularity can depend on a large number of factors. One that has no (direct) effect on quality is cost: threes wasn't free initially, 2048 was, so far more people played 2048.
This is why "freemium" is such a common model, trying to get the exposure/market-share benefit of being free while still pulling in income from the product or related addons/services.
If you look at "popularity" of similar products of each type as measured by market share or absolute download numbers you most likely see free far outstrips freemium which in turn outstrips any product with an up-front cost.
Popularity can depend on a large number of factors. One that has no (direct) effect on quality is cost: threes wasn't free initially, 2048 was, so far more people played 2048.
This is why "freemium" is such a common model, trying to get the exposure/market-share benefit of being free while still pulling in income from the product or related addons/services.
If you look at "popularity" of similar products of each type as measured by market share or absolute download numbers you most likely see free far outstrips freemium which in turn outstrips any product with an up-front cost.
Yes, 2048 is a blatant rip-off of Threes, and omits everything that makes Threes interesting.
I agree - I'd been an avid Threes player for a while when I decided to give 2048 a try to see what the fus was all about. Got to 2048 on my first try - it is very much easier than Threes.
Once you know the basic strategy/naive algorithm behind winning it becomes easy to get to much higher than 2048.
1) Swipe left until nothing else moves
2) Swipe down until nothing else moves
3) (If an empty space) Swipe up once
4) Repeat from 1.
There will only be a few times that you have to stop this process to get "unstuck".
1) Swipe left until nothing else moves
2) Swipe down until nothing else moves
3) (If an empty space) Swipe up once
4) Repeat from 1.
There will only be a few times that you have to stop this process to get "unstuck".
For what it's worth, that's also what I do. But is it optimal? :)
The source code is leading the blog posts [1], so I think I already have an answer to that question for games on 2x2 and 3x3 boards using Markov Decision Processes, but the approach doesn't scale to the 4x4 board.
[1] https://github.com/jdleesmiller/twenty48
The source code is leading the blog posts [1], so I think I already have an answer to that question for games on 2x2 and 3x3 boards using Markov Decision Processes, but the approach doesn't scale to the 4x4 board.
[1] https://github.com/jdleesmiller/twenty48
Most likely not optimal but it certainly can be done without looking at the screen while watching Netflix :P
I really thought this article was going to be about the state of combinatorics in the year 2048.
would you say you were counting on it? (sorry)
This isn't an estimate, it's an upper bound. Unless I've missed something, a board filled with 2s would be counted as possible by this article, despite being unreachable. There are many unreachable states that they are counting.
I'd say it's both an estimate and an upper bound. :)
The article doesn't even make an argument that it's close to accurate, though. It could be off by several orders of magnitude, and whether it might be or not isn't even discussed!
On the other hand, it is giving an exact upper bound; it's a proof that the actual number couldn't be any larger than 44 quadrillion.
On the other hand, it is giving an exact upper bound; it's a proof that the actual number couldn't be any larger than 44 quadrillion.
Last paragraph in the article: "In the next post, we’ll see that the number of actually reachable states is much lower by actually enumerating them. There will still be a lot of them for the 3x3 and 4x4 boards, so we will need some computer science as well as mathematics."
Great post!
2048 is really an addicting game; at this point it's my go-to activity when I'm e.g. in a boring conference and have brain cycles to spare. I have a copy in my browser, on my phone and inside my Emacs.
2048 is really an addicting game; at this point it's my go-to activity when I'm e.g. in a boring conference and have brain cycles to spare. I have a copy in my browser, on my phone and inside my Emacs.
I really love 2048 when I'm bored in the unemployment line. I'm there because I was playing games on my previous employer's time.
Work for an employer who doesn't really care what you do with your time so long as you get the job done. Or work for one where you spend a lot of time compiling.
Compiling time == Nerf war time.
Compiling time == Nerf war time.
The art is in knowing when you can play, and when you cannot.
Yes. I should have waited until my employer had spent money on travel and fees for me to attend a boring conference.
Well, sarcasm aside, I made a point about having brain cycles to spare.
Don't you ever find yourself in situations in which the task at hand only captures a small fraction of your cognitive resources, and you're otherwise getting bored out of your mind? 2048 is the kind of game that's good at engaging the remaining brain capacity, the part that's not used to focus on a meeting.
Don't you ever find yourself in situations in which the task at hand only captures a small fraction of your cognitive resources, and you're otherwise getting bored out of your mind? 2048 is the kind of game that's good at engaging the remaining brain capacity, the part that's not used to focus on a meeting.
Especially as it's easy to quit the game and recover later in case something other relevant comes up ...
Exactly. I wouldn't really want to touch anything more complicated in situations I described. Even reading HN can be too mentally engaging, risking that I actually miss something relevant that's being talked about.
> at least 938.8 moves on average
> at least ... on average
wat
> The main simplification that enabled that calculation was to ignore the structure of the board
Oh OK so he doesn't mean "minimum", he means "assuming perfect play under his simplified model". Which is neither the minimum, nor the average assuming perfect play under an exact model.
So it's unclear that his previous figure of 938.8 is particularly meaningful since it assumes an inexact model.
Actually, assuming a perfect AI exists (i.e. the constraints imposed by the structure of the board is not a hindrance to a sufficiently-advanced AI) then the average number of moves needed is simply 2048 / mean( (2,0.9), (4,0.1) ) = 2048 / 2.2 ~= 930.91 which is very close to the previously-quoted figure and has the advantage that it
- is independent of any potentially inaccurate model of the game dynamics
- takes like 1s to calculate, and you could do it in your head
> at least ... on average
wat
> The main simplification that enabled that calculation was to ignore the structure of the board
Oh OK so he doesn't mean "minimum", he means "assuming perfect play under his simplified model". Which is neither the minimum, nor the average assuming perfect play under an exact model.
So it's unclear that his previous figure of 938.8 is particularly meaningful since it assumes an inexact model.
Actually, assuming a perfect AI exists (i.e. the constraints imposed by the structure of the board is not a hindrance to a sufficiently-advanced AI) then the average number of moves needed is simply 2048 / mean( (2,0.9), (4,0.1) ) = 2048 / 2.2 ~= 930.91 which is very close to the previously-quoted figure and has the advantage that it
- is independent of any potentially inaccurate model of the game dynamics
- takes like 1s to calculate, and you could do it in your head
That's also a good approach, and indeed much simpler! What I think it doesn't take into account is that you need to have more than just the 2048 tile on the board in order to reach the 2048 tile, because it takes a few moves to merge the tiles, and during those moves the game continues to add new 2 and 4 tiles. That explains why it's a few moves lower than the estimate from the Markov chain analysis.
I take your point that the 'at least 938.8 moves on average' phrasing could be clearer, but it's the best way I've found to express the result in a small number of words. More precisely, I'm claiming in the first post that:
1. The number of moves that it takes to win is a random variable, because it depends on the sequence of 2s and 4s, so we can talk about the 'expected number of moves to win' (i.e. an average).
2. The 'bag' game without the structural constraints imposed by the board always takes fewer moves to win than the game with those constraints.
3. The expected number of moves to win for the bag game is 938.8, so using (1) and (2) this yields a lower bound for the expected number of moves to win the full game. (There are no decisions for the player to make in the bag game, so there isn't really a notion of 'perfect play' for the bag game. It's more like a 'bag process'.)
4. By playing lots of games of 2048, I found that I could get pretty close to this lower bound on average, at least when I played well (no major blunders).
I hope that's clearer!
I take your point that the 'at least 938.8 moves on average' phrasing could be clearer, but it's the best way I've found to express the result in a small number of words. More precisely, I'm claiming in the first post that:
1. The number of moves that it takes to win is a random variable, because it depends on the sequence of 2s and 4s, so we can talk about the 'expected number of moves to win' (i.e. an average).
2. The 'bag' game without the structural constraints imposed by the board always takes fewer moves to win than the game with those constraints.
3. The expected number of moves to win for the bag game is 938.8, so using (1) and (2) this yields a lower bound for the expected number of moves to win the full game. (There are no decisions for the player to make in the bag game, so there isn't really a notion of 'perfect play' for the bag game. It's more like a 'bag process'.)
4. By playing lots of games of 2048, I found that I could get pretty close to this lower bound on average, at least when I played well (no major blunders).
I hope that's clearer!
My point actually was that your (2) is not correct. The game gives you +2.2 (av) every single turn regardless of what move you make, so improving the AI can't possibly increase the speed at which you get these points. Improving the AI only reduces your chance of dying.
However, good point with "it takes a few moves to merge the tiles". Coupled with the fact that the game starts you off with 2 tiles (4 points), my "quick" method gets closer to your value:
2048 (target) - 4 (starting) = 2044
2044 / 2.2 = 929.090909090909
+ 10 moves to merge
~= 939.1 on average to get a 2048 tile on the board.
However, good point with "it takes a few moves to merge the tiles". Coupled with the fact that the game starts you off with 2 tiles (4 points), my "quick" method gets closer to your value:
2048 (target) - 4 (starting) = 2044
2044 / 2.2 = 929.090909090909
+ 10 moves to merge
~= 939.1 on average to get a 2048 tile on the board.
[deleted]
I love the smell of tex equations early in the morning.
It was quite simple: It simulated games from the current position using random moves, and chose the move that resulted in the highest average end-game score. The surprising result was that even though random moves are obviously a terrible game plan (on average, random play from a given starting position lasted 40 extra moves and scored an extra of 340 points before dying), using the least bad move each time led to very good game play over all: An average game had 70000 points and lasted 3000 moves, reaching the 2048 tile 100% of time and the 4096 tile 70%.
Also, perhaps of interested to this crowd, I later noticed that the web version of the game had exposed JS for the board state and controls. This allowed me to write a bookmarklet version of the solver that could play the original web version directly. This was fun because many game variants came out (like Hexagon 2048, and 20Euros) which were all different games, but were based on the same controllers. The solver, being "general purpose" could play many of these variants without any tweaking.
Solver demo: http://ronzil.github.io/2048-AI/ Write up: https://stackoverflow.com/questions/22342854/what-is-the-opt... Bookmarklet version: http://ronzil.github.io/2048AI-AllClones/