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.
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.
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?
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.
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.
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/