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.<p>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%.<p>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.<p>Solver demo: <a href="http://ronzil.github.io/2048-AI/" rel="nofollow">http://ronzil.github.io/2048-AI/</a>
Write up: <a href="https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048/23853848#23853848" rel="nofollow">https://stackoverflow.com/questions/22342854/what-is-the-opt...</a>
Bookmarklet version: <a href="http://ronzil.github.io/2048AI-AllClones/" rel="nofollow">http://ronzil.github.io/2048AI-AllClones/</a>
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].<p>[0] <a href="http://asherv.com/threes/threemails/" rel="nofollow">http://asherv.com/threes/threemails/</a>
Once you know the basic strategy/naive algorithm behind winning it becomes easy to get to much higher than 2048.<p>1) Swipe left until nothing else moves<p>2) Swipe down until nothing else moves<p>3) (If an empty space) Swipe up once<p>4) Repeat from 1.<p>There will only be a few times that you have to stop this process to get "unstuck".
win? you mean people "win"? I've never "won" this game. Its beaten me.<p>you can stop smirking, all three-fifty-hundred of you. I know.<p>(lovely game btw)
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.
Great post!<p>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.
> at least 938.8 moves on average<p>> at least ... on average<p>wat<p>> The main simplification that enabled that calculation was to ignore the structure of the board<p>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.<p>So it's unclear that his previous figure of 938.8 is particularly meaningful since it assumes an inexact model.<p>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<p>- is independent of any potentially inaccurate model of the game dynamics<p>- takes like 1s to calculate, and you could do it in your head