The Mathematics of 2048: Counting States with Combinatorics

http://jdlm.info/articles/2017/09/17/counting-states-combinatorics-2048.html

by jdleesmiller • 9 years ago

159 46 9 years ago

doppp2• 9 years ago

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/

jdleesmiller3• 9 years ago

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.

doppp2• 9 years ago

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.

iainmerrick• 9 years ago

Yes, 2048 is a blatant rip-off of Threes, and omits everything that makes Threes interesting.

maaaats2• 9 years ago

How is it a rip-off if it omits everything?

m12k• 9 years ago

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.

andrewla• 9 years ago

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.

Cogito• 9 years ago

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.

ggm• 9 years ago

win? you mean people "win"? I've never "won" this game. Its beaten me.

you can stop smirking, all three-fifty-hundred of you. I know.

(lovely game btw)

pcurve• 9 years ago

I think it's beatable if you play it a dozen times and get the hang of it. 4096 version is quite tough I have to say.

TeMPOraL4• 9 years ago

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.

KC8ZKF2• 9 years ago

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.

TeMPOraL4• 9 years ago

The art is in knowing when you can play, and when you cannot.

KGIII• 9 years ago

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.

Hbthegreat2• 9 years ago

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".

jdleesmiller3• 9 years ago

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

Hbthegreat2• 9 years ago

Most likely not optimal but it certainly can be done without looking at the screen while watching Netflix :P

air72• 9 years ago

2048! Towards the end of the 2048-craze era, I wrote a solver for the game that unlike other solvers that came out, had no built-in algorithm about how to play.

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/

infinity03• 9 years ago

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?

air72• 9 years ago

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.

CJefferson• 9 years ago

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.

zellyn• 9 years ago

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.

ecesena• 9 years ago

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.

Lewton2• 9 years ago

reaching the 2048 tile 100% of time

Lies!

https://i.imgur.com/Mi3lGzG.png

(I didn't interfere)

Lewton2• 9 years ago

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

infinity03• 9 years ago

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

jdleesmiller3• 9 years ago

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!

infinity03• 9 years ago

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.

popcorncolonel• 9 years ago

I really thought this article was going to be about the state of combinatorics in the year 2048.

vinchuco• 9 years ago

would you say you were counting on it? (sorry)

justinpombrio2• 9 years ago

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.

omaranto• 9 years ago

I'd say it's both an estimate and an upper bound. :)

justinpombrio2• 9 years ago

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.

feborges• 9 years ago

I love the smell of tex equations early in the morning.

The Mathematics of 2048: Counting States with Combinatorics

Related Stories