## How to Beat Threes (and 2048)

**Threes** is a terrifically simple, yet tremendously intriguing game from the creative team of Asher Vollmer and Greg Wohlwend, known for their work on indie games such as Puzzlejuice and Ridiculous Fishing. While each of them have created tons of great indie games, I don’t think it’s an exaggeration to say that *Threes* could well be their best game yet.

The rules are very simple: every time you swipe across the screen, all of the tiles try to move in the direction you swiped. Two tiles can combine if their values add up to 3, or if the tiles are equal and both integer multiples of 3. If you try to combine two tiles (by squishing one against the wall) and they can’t, then they act as a barrier, and that particular column or row doesn’t budge. Finally, there’s the part which makes it tricky: Every time you move the tiles, another tile is introduced. The goal is to reach the elusive 6144 tile, or more realistically, to last as long as you can without running out of possible moves.

For reasons which are yet to be fully understood, this game has attracted a stunningly large audience of players. Perhaps it’s because the game’s aesthetically appealing, or perhaps it’s because it’s apparently (and initially) easy to get past the first few stages, and yet nearly impossible to reach the final goal. It’s also a game which encourages study from just about everyone who’s played it (in the same way as Chess does), but also lacks any sort of threat of failure- a cheerful sound plays, and you get to see how many points you wound up with without losing in any sort of public way. In any case, even though it’s been around for only 2 and one-third months, there’s been an enormous amount of public interest and quite a few successful attempts to work out how the game works internally. Unfortunately, quite a few clones, some of which have offered notable modifications to the game, have also been created.

One of the most notable clones is Gabriel Cirulli’s * 2048*, which is almost identical to

*Threes*, except for a few differences:

- The tiles are the powers of 2 (2,4,8…) instead of three times the powers of two along with 1 and 2 (1,2,3,6,12,24…)
- Only tiles reading 2 and 4 are ever inserted, as opposed to the 1,2,3, and sometimes 6 or more of
*Threes* - The tiles slide as far as possible instead of moving at most one space
- The tiles are placed randomly on the board (in
*Threes*, they only ever enter from the edge you swiped from) - The goal is to get to 2048 instead of 6144, which makes the game a bit easier, since there are two types of tiles you never have to deal with, and
*2048*is free and open-source, and this, more than anything else, has probably led to its popularity and the number of subsequent clones.

If you’ve never played *Threes* or *2048* before, I highly recommend giving them a try, if only so that you can develop your own intuition for these games.

One of the few things that everyone who’s played *Threes* or *2048* agrees about is that these games are *really* difficult. As it turns out, people have discovered quite a few strategies for playing these games which make them a bit easier, but usually not by very much. However, there is a complicated and arcane algorithm for *2048*, known as the Corner Strategy, that will allow you to match or surpass scores you may have spent hours achieving in just a few minutes, using only a few very simple calculations.

## The Corner Strategy

**Tap Right and Down in alternating order until you can’t move. Then press Up. Repeat.**This works *ridiculously* well, given the amount of thought necessary to run this algorithm.

(This isn’t sped up or time-lapsed in any way)

Of course, the standard corner strategy rarely gets you to the 2048 tile, though it sometimes does. There are other methods, such as the so-called Mancini technique (keep the largest number in a corner, construct chains, never press Left), but almost all are versions of the Corner Strategy.

What we’d really like to know, though, is how to play *2048* or *Threes* optimally; that is, what is an algorithm that will play a game so as to gain the highest score? While this is almost certainly extraordinarily computationally intensive, a number of programmers have developed algorithms which play *2048* extraordinarily well. There was actually a bit of a competition on StackExchange not very long ago to design the best AI for the game, and many of the submissions were able to attain the 2048 tile almost all of the time! In particular, the best AI, developed by nneonneo, uses a surprisingly simple technique known as *expectimax optimization*, which works something like this:

- Consider the game tree of
*2048*: We move in one direction, then the computer places a piece randomly, then we move in another direction, the computer places another piece randomly, and so on until we can’t move anymore. - Suppose we can assign a “score” to each state of the board, which tells us roughly how good a position is, without actually looking into the future for possible moves or anything like that. The function used to calculate the score can be as simple as counting the number of empty spaces on the board, to complicated heuristics (such as ovolve’s combination of monotonicity, smoothness, and free tiles) It’s a bit like looking at a chessboard and guessing how much one side is winning.
- That said, we can get a better idea of how good a particular state is if we can look a few moves ahead, and measure the approximate score of each of
*those*positions, assuming we played optimally up to each one. - Now, suppose we’re at a particular state, and we want to determine how good a move such as, say, moving right is. It’s actually fairly easy to compute the expected score of the
*computer**‘s*move- just add up the score times the probability of a particular move for each move the computer could make. For instance, if there were a probability of 0.9 that the computer would place a 2 (say) resulting in a state with a score of 5, and a probability of 0.1 that the computer would place a 4, resulting in a state with a score of 2, then the expected score would be

0.9*5 + 0.1*2 = an expected score of 4.7

- If we know how good each move we could make is, then we should just play the best move (obviously).
- Expectimax optimization starts by asking “What is the best move I can make?” at the current state. To do that, it has to compute the score of each of the moves it could make, which it does by first branching over each of the moves the computer could make, and then measuring the score of each of the resulting positions by asking “What is the score of the best move I can make?” for each of
*those*. Theoretically, this could go on forever, so expectimax just uses the base heuristic once it’s sufficiently far down the game tree (that is, once it’s thinking a particular number of moves ahead). Once it has decided on an accurate score for each of the possible moves it could make, it simply plays the one with the best score.

Not only is this algorithm *very* good at playing the game when equipped with a good base heuristic- nneoneo’s implementation achieved ** 4096** in 97 of 100 trials, and gets to 16384 about once in every eight attempts – it’s also very fast!

(this is *also* not sped up in any way- it really is doing 30 moves per second!)

Of course, if you have an AI that play the game, it’s not difficult to create an AI that can always place the new tile in the worst possible place for the player, making the game more or less impossible. (For instance, see Stephen B. Beevan’s *Hatetris*) This is exactly what Zsolt Sz. Sztupák has done with *2048-Hard*, based off of Matt Overlan’s solver. Interestingly enough, the “Impossible” mode isn’t *entirely* impossible- I actually managed to get the 64 tile, with a final score of 540, while the embedded AI solver often gets to the 128 tile.

## It’s Not Just You; Threes is Difficult for Computers as Well!

Unfortunately, if you try the Corner Strategy on *Threes*, you’ll probably get the *lowest* score you’ve ever gotten. In fact, the designers of *Threes* found out about the corner strategy fairly early on, and modified the game a bit to make braindead strategies like it ineffective. This has the side effect of making the game *much* more difficult. Continue reading