zappz

Articles2048

How Computers Play 2048: Search, Chance and a Board Value

Computers play 2048 by searching a few moves ahead, weighing every new tile by its chance, and giving each board a value. Here is how that works.

Evolved 2048

The 2048 puzzle on a Rubik's cube: slide the front face, twist rows to bring tiles from the other sides, and build tiles past 2048.

If you have ever watched a program clear a 2048 board without a pause, you may wonder what it sees that you miss. The answer to how computers play 2048 is less mysterious than it looks: they try each slide, list every tile the game could drop next, give each resulting board a value, and play the slide with the highest average. The same reasoning carries over to a 2048 puzzle played on a Rubik's cube, where the search simply has more moves to weigh.

Each step of that process is something you can do by hand on a small board. Once you know the steps, the program's moves stop looking like magic and start looking like careful arithmetic.

How computers play 2048 in one sentence

A strong 2048 program looks a few moves ahead, treats each new tile as a chance event, and picks the move whose likely outcomes are worth the most. The 2048 page on Wikipedia) names the method most of them use: expectiminimax search to a variable depth, with transposition tables so the same board is not worked out twice.

Three ideas sit inside that sentence:

  • A search tree. Your moves and the game's tiles alternate, one layer after another.
  • Chance. The game does not choose its tiles to hurt you. It drops them at random, so each one is weighed by how likely it is.
  • A board value. The search cannot run to the end of the game, so it stops after a few layers and judges the boards it reaches.

Your slides and the game's tiles take turns

On a flat board you have at most four slides: up, down, left and right. A slide that changes nothing is not a legal move, so some turns offer fewer. After your slide, the game places one new tile in an empty square. On the classic board that tile is a 2 nine times in ten and a 4 one time in ten.

That gives the search its shape. The first layer holds your four possible slides. Under each slide sits a layer of chance: every empty square, each with a 2 or a 4 in it. Under each of those boards sits your next set of slides, and so on.

The expectiminimax page on Wikipedia describes this kind of tree. It is a variation of minimax, with an extra kind of node for chance. At your own layers the program takes the highest value. At a chance layer it takes a weighted average, where each child counts in proportion to the probability that it happens. The page credits Donald Michie with proposing the method in 1966, and names backgammon, with its dice, as a typical use.

2048 has no opponent, so the "min" part of the name never acts. The program only ever meets two kinds of layer: its own choice and the game's dice roll.

Giving a board a value the search cannot see past

The tree grows fast. With 10 empty squares, each slide leads to 20 possible boards, and each of those leads to up to four more slides. A program has to stop after a few layers and judge what it reaches. The function that judges a board is the heart of any 2048 program.

The Wikipedia page on 2048 lists the features such a function can favour:

  • Empty squares. More room means more slides stay legal and fewer new tiles land where they do harm.
  • Merge chances. Equal tiles side by side are merges waiting to happen.
  • Order. Rows and columns whose tiles only rise, or only fall, toward one side, a property called monotonicity.
  • Large tiles at an edge. A big tile in the middle splits the board; a big tile on an edge does not.

The program adds these features with weights and gets one number per board. The search depth varies with the board: with few empty squares there are few chance children, so the program can afford to look further.

Diagram of one look-ahead step of a 2048 program: try each slide, place every possible new tile, give each board a value, then average by chance and choose
One step of the search, from your slide to the game's tile to a value for each board.

A worked example: one slide weighed by chance

Take a board where only two slides change anything: left and up. Both leave exactly three empty squares. The program looks one layer deep and uses its board value on each result.

Left. Two of the three empty squares sit at the far side of the board, away from the big tiles. Whatever lands there, a 2 or a 4, the board is worth 12. The third empty square sits in the middle of the ordered top row. A 2 there is worth 4 and a 4 there is worth 3, because either one breaks the row.

  • Each square is picked one time in three.
  • Safe squares: 12, whatever the tile.
  • Risky square: 0.9 × 4 + 0.1 × 3 = 3.9.
  • Left as a whole: (12 + 12 + 3.9) ÷ 3 = 9.3.

Up. All three empty squares are in harmless places, but up pulls the second-biggest tile one square away from its partner. Every outcome is worth 8, so up as a whole is worth 8.

The program plays left, because 9.3 is more than 8. Notice what a worst-case search would do instead. It would see left's bad outcome, worth 3, set it against up's worst of 8, and play up. Weighing each tile by its real chance is what lets the program take a small risk when the likely payoff is larger. On the next turn it runs the same sum again from the new board.

Programs that learn their own board values

The weights in a board value can be set by hand, but the Wikipedia page on 2048 notes that they are usually tuned by searching for better values, and that some papers used temporal difference reinforcement learning to do it.

The temporal difference learning page describes the idea. The program plays games and, after each move, nudges its value for the earlier board toward its value for the later one. It learns by bootstrapping from its own current estimate, without a model of the game, from the boards it actually meets. The page names TD-Gammon, Gerald Tesauro's backgammon program, which learned this way to play at roughly the level of expert human players.

For 2048 that means a program can start from rough weights and adjust them from its own games, rather than from a person's guesses. The strongest programs combine both halves: learned values to judge a board and a search to look ahead. The 2048 page reports a 2025 result in which expectiminimax search with pre-built tables for boards full of large tiles reached a 16384 tile in 99.9 percent of 1,200 simulated games.

On a cube the same method holds, but the tree is wider. There are six faces of nine squares, 54 squares in all. You still slide the front face in four directions. You can also twist a row of the right face or a column of the top face, a quarter turn that carries its tiles to the next face, and you can turn the whole cube.

Those moves change the search in three ways:

  • More of your own moves. Twists sit beside the four slides at every one of your layers, so each layer has many more branches.
  • A move that adds no tile. Turning the whole cube costs nothing: only a slide or a twist adds a new tile. A turn has no chance layer under it at all.
  • Chance tied to room. Every slide or twist adds a 2 or a 4, on the front face when it has room, and a twist needs one empty square for its tile. A board value would have to count that room, not only the room on the front.

The board value changes too. In the main mode the game ends only when all 54 squares are full and no face has two equal tiles side by side, and a tile you need is often on a side face. A value that only looked at the front face would miss the merges a twist can bring round.

Frequently asked questions

Do 2048 programs cheat by knowing the next tile?

A fair program does not. It treats the next tile as a chance event, a 2 or a 4 in any empty square, and averages over every case.

What is expectimax in 2048?

It is the common short name for expectiminimax with no opponent: the program takes the highest value at its own moves and the chance-weighted average at the game's tile drops.

The depth varies with the board. Fewer empty squares mean fewer chance children, so a program can look further on a crowded board than on an open one.

Can a person use the same method?

Yes, in a small form. Before each slide, count the empty squares it leaves, ask where a new tile would hurt, and prefer the slide whose likely outcomes stay calm.

What a 2048 program shows about the puzzle

Strip away the speed and a 2048 program is doing three plain things: listing its options, admitting it cannot know the next tile, and judging boards by room, order and merges. None of that needs a computer. The program simply does the arithmetic faster and never skips a case.

That is also why the features it values match the habits strong players already keep: a big tile on an edge, rows in order, and squares left open. The search does not invent a new way to play 2048. It shows, in numbers, why the old advice works, and how much one careless tile in the wrong square can cost.

Evolved 2048

The 2048 puzzle on a Rubik's cube, and past 2048. Visit evolved2048.vlvd.net

Evolved 2048 on desktop
Evolved 2048 on tablet
Evolved 2048 on phone

Related articles

More on 2048
  1. 2048Is 2048 a Game of Luck or Skill? Where Chance Stops2048 hands you a random tile every move, but you choose where the room is. Chance picks the square and the number; the slide is yours. · 7 min read
  2. 2048Why Empty Squares Matter in 2048 and How to Keep ThemEvery 2048 move fills one square and every merge frees one. Count the empty squares a slide leaves, and the game gets easier to steer. · 8 min read
  3. 2048Why 2048 Tiles Appear as 2 or 4, and How Often Each ComesNew 2048 tiles are a 2 nine times in ten and a 4 one time in ten. Here is what that split means for your board, your moves and your plans. · 7 min read

Keep reading

All articles
  1. classical musicComposers Who Changed Western Music: Monteverdi to StravinskyMonteverdi, Bach, Beethoven and Stravinsky: what each of these composers who changed Western music did, and how to hear the change for yourself. · 6 min read
  2. is-ought problemIs-Ought Problem: Why Facts Alone Cannot Set AI ValuesWhat is the is-ought problem? Why a fact about what is cannot by itself tell anyone what ought to be, and what that gap means for AI values. · 6 min read
  3. stoic philosophyWhat Is the Stoic Sage? The Ideal No One Has ReachedThe Stoic sage is the perfectly wise person the Stoics doubted had ever lived. What the sage knows, what the sage feels, and one rumor to work through. · 6 min read