The Mathematics of 2048: Counting States with Combinatorics
jdlm.info
jdlm.info
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/
[0] https://medium.com/@karpathy/alphago-in-context-c47718cb95a5
One easy way would be to skew the AI evaluation score heavily towards states with lower numbers of tiles. Maybe log(score) - num-tiles?
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 not, my computer is really terrible at 2048 :P
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.
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.
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.
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 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.
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?
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?
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".
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.
you can stop smirking, all three-fifty-hundred of you. I know.
(lovely game btw)
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.
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.
Compiling time == Nerf war time.
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.
> 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
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!
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.