3 ms·
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.
by air7 9y 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/ http://ronzil.github.io/2048-AI/
Write up: https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048/23853848#23853848 https://stackoverflow.com/questions/22342854/what-is-the-opt...
Bookmarklet version: http://ronzil.github.io/2048AI-AllClones/ http://ronzil.github.io/2048AI-AllClones/
- infinity0 9y agoDo 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?
- air7 9y agoMy 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 9y agoYou 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 9y agoI 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.
- kyleschiller 9y agoSort of, it uses Monto Carlo + a bunch of other things. [0] [0] https://medium.com/@karpathy/alphago-in-context-c47718cb95a5 https://medium.com/@karpathy/alphago-in-context-c47718cb95a5
- ecesena 9y agoI 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.
- Lewton 9y ago> reaching the 2048 tile 100% of time Lies! https://i.imgur.com/Mi3lGzG.png https://i.imgur.com/Mi3lGzG.png (I didn't interfere)
- Lewton 9y agoOk 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