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
— 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.
- 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.