I spent a good chunk of Saturday and Sunday ignoring the NCAAs and spent my time on something only slightly less frivolous: crafting an algorithm to beat the awesomely addicting game 2048. Spoilers below

@aaron_strauss somewhat?

— byuhas (@byuhas) March 23, 2014

Wednesday update: I’ve updated this post to reflect recent improvements in the algorithm.

I learned of 2048 from this xkcd cartoon. I played a few times, and then on Thursday it struck me that the game is similar to the Towers of Hanoi problem. That night I spent way too many hours crafting the outlines of a winning strategy, proving to myself that I could beat the game. The basic idea is to align the tiles in a snakelike pattern from highest to lowest (from the upper-left, down, then over one, then up, etc) as shown below:

It’s especially crucial to keep your highest-numbered tile in a corner (e.g., the upper-left).

The computer scientist in me wasn’t satisfied with solving the puzzle by hand. Rather, I felt the need to develop an algorithm, thus allowing a computer to win the game for me. Overall, I did an adequate job — the computer wins the game, but I notice that it still makes small mistakes. You can check it out here. (On my personal machine, each move takes about a second, which provides a pleasant viewing experience — hopefully the same is true for you.)

Some notes on the algorithm:

• It looks four moves ahead and does not prune the game tree. (Speed options: Blazing = 3 moves ahead; Plodding = 5 moves ahead.)
• Grids are scored on:
  • Better score if tiles are in exactly the right place for the “perfect” grid (accounting for gaps in the numbers available).
  • Even if the tiles on the “snake path” aren’t perfect, it’s better if they are monotonic
  • Points for having at most two of the same tile number.
  • Points for having more blank spaces.
  • Points for having a higher maximum tile number.
  • End game: once there are enough points to win on the board: the snake path and monotonicity become less important, adjacent pairs are worth works, and blank spaces are worth more.
• Besides scoring a grid (and figuring out how to clone an object in javascript), the most challenging aspect of coding up the solution was the nondeterministic nature of 2048. The fact that 2s (and sometimes 4s) pop up randomly in blank spaces means that some moves (e.g., abandoning the high-number corner) can be extremely risky: a low-probability event can cause catastrophe. Averaging over several (e.g., 10) random spots for the new number is way too computational costly given that I want to traverse 5 levels of the tree each move. Instead I evaluate a move under two options: random and bad luck (deterministicly based on what is “lucky” for the algorithm). The minimum score between these two options is used as the overall evaluation of the move.
• I’m not sure what percent of the time it wins, especially since there are three speeds. It does make mistakes — likely a combination of deterministic new-number pop up, poor coding of a grid-score function, and not looking that far down the tree.
• It take about 1000 moves to win.
• Aside: finding end-game bugs is annoying. I had a build methods to test arbitrary boards. Cost of doing business I guess.

Comments welcome. I respond fairly quickly to tweets.