2048 is played on a 4×4 grid, with numbered tiles that slide smoothly when a player moves them using the four arrow keys. Every turn, a new tile will randomly appear in an empty spot on the board with a value of either 2 or 4. (Probability of 90%: 2, 10%: 4) Tiles slide as far as possible in the chosen direction until they are stopped by either another tile or the edge of the grid. If two tiles of the same number collide while moving, they will merge into a tile with the total value of the two tiles that collided. (https://en.wikipedia.org/wiki/2048_(video_game))

A scoreboard on the upper-right keeps track of the user's score. The user's score starts at zero, and is incremented whenever two tiles combine, by the value of the new tile. (https://en.wikipedia.org/wiki/2048_(video_game))

The game is won when a tile with a value of 2048 appears on the board, hence the name of the game. After reaching the 2048 tile, players can continue to play (beyond the 2048 tile) to reach higher scores. When the player has no legal moves (there are no empty spaces and no adjacent tiles with the same value), the game ends. (https://en.wikipedia.org/wiki/2048_(video_game))

======

Click for Video

The initial brute force recursive approach failed to provide significant results due to a lack of accurate heuristics. Judging which board state was better than another proved to be very difficult. From prior experience with gameplay I tried rating fittness based on:

1. Monotonically increasing or decreasing values on board edges
   

2. Emptiness of board
   

3. Ability to merge tiles
   

4. Keeping high values on edges
   

These failed to perform well even after weighing for tile score and total board score dynamically. Without the ability to rate fitness of board states accurately a more unsupervised appoached seemed in order. By randomly playing multiple games out to termination and tracking starting moves I was able to guess a "good" move.

======

for i < CONGIF.DEPTH
  Clone current game state
  
  while cloned state game not over
    pick random move to play
    Record first move
  
  Record end score
  i++
  
Make starting move with highest average end score

======

100 games were played with different amounts of random games played out at each move (aka game depth). Random game depths included 50, 100, 500 and 1000.

On averege as more random games were played at each move the end score increased and seems to be maximized at a 8192 tile. A control game series of completly random moves resulted in no more then a 256 tile.

Game Depth 50:
42% of games were able to be won at a depth of 50

Game Depth 100:
61% of games were able to be won at a depth of 100

Game Depth 500:
94% of games were able to be won at a depth of 500

Game Depth 1000:
99% of games were able to be won at a depth of 1000

In summary as the depth increased the percentage of game won and score did also. The 8192 tile was also only achieved at the 500 and 1000 depths.

Most interesting was the spread of the random games behind each move.

The steady increase in score as well as the narrowing of score range can be seen graphing predicted final score of each random games against percentage of game completed.

Similarlly observing when the random games cross the next tile threshold shows that each games does so at nearly the same time.

Lastly looking at the predicted moves until game completion the correlation between the highest merged tiles and game length becomes clear. At each merged high tile, predicted game length increases dramatically. The additional jumps I assume to be the merging of other high tiles.

By inceasing the number of random games played the general trend was an increase in score as well as game length. This did seemed to be capped at a 8192 tile.
Running 10 games with a depth of 10,000 seemed to comfirm this. None of the games where able to break 8192 and instead games became more consistent, resulting with 8/10 falling on 4096, 1/10 reaching 8192 and all at least acheiving 2048. Further increases beyond 10,000 while impractically slow to run without optimization are unlikely to yield more results.

======

http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048 - Specifically @ronenz
https://github.com/gabrielecirulli/2048
http://beej.us/blog/data/monte-carlo-method-game-ai/
https://en.wikipedia.org/wiki/2048_(video_game))