Playing 2048 with Minimax Part 1: How to apply Minimax to 2048

2048 — a simple game, but programming a computer to solve it it’s not trivial

Minimax is an algorithm designated for playing adversarial games, that is games that involve an adversary. In this article, we’ll see how we can apply the minimax algorithm to solve the 2048 game. This is the first article from a 3-part sequence. This one will consist of planning our game-playing program at a conceptual level, and in the next 2 articles, we’ll see the actual Python implementation.

Here I assume you already know how the minimax algorithm works in general and only focus on how to apply it to the 2048 game. So, if you don’t already know about the minimax algorithm, take a look at:

The main 4 things that we need to think of when applying minimax to 2048, and really not only to 2048 but to any other game, are as follows:

1. How we can think of 2048 as a 2-player game? Who is Max? Who is Min?

2. How do we decide when a game state is terminal?

3. How do we evaluate the score/utility of a game state?

4. How do we determine the children of a game state?

The first point above is because that’s how minimax works, it needs 2 players: Max and Min. The other 3 things arise from the pseudocode of the algorithm, as they are highlighted below:

When we wrote the general form of the algorithm, we focused only on the outcomes of the highlighted functions/methods (“it should determine if the state is terminal”, “it should return the score”, “it should return the children of this state”) without thinking of howthey are actually done; that’s game-specific.

Now, when we want to apply this algorithm to 2048, we switch our attention to the “how” part: How we actually do these things for our game?

How we can think of 2048 as a 2-player game? Who is Max? Who is Min?

Recall from the minimax algorithm that we need 2 players, one that maximizes the score and one that minimizes it; we call them Max and Min.

When we play in 2048, we want a big score. So, who is Max? We. We want to maximize our score.

And who wants to minimize our score? Well… no one. There is the game itself, the computer, that randomly spawns pieces mostly of 2 and 4. But, it is not really an adversary, as we actually need those pieces to grow our score. And I don’t think the game places those pieces to our disadvantage, it just places them randomly.

But the minimax algorithm requires an adversary. So, we will consider Min to be the game itself that places those tiles, and although in the game the tiles are placed randomly, we will consider our Min player as trying to place tiles in the worst possible way for us.

How do we decide when a game state is terminal?

That’s a simple one: A game state is considered a terminal state when either the game is over, or we reached a certain depth. We will consider the game to be over when the game board is full of tiles and there’s no move we can do.

The depth threshold on the game tree is to limit the computation needed for each move. If we let the algorithm traverse all the game tree it would take too much time. We want to limit this depth such that the algorithm will give us a relatively quick answer for each move that we need to make. For the 2048 game, a depth of 5–6 works well.

How do we evaluate the score/utility of a game state?

The goal of the 2048 game is to merge tiles into bigger ones until you get 2048, or even surpass this number. In the article image above, you can see how our algorithm obtains a 4096 tile. But the exact metric that we should use in minimax is debatable. One can think that a good utility function would be the maximum tile value since this is the main goal. But what if we have more game configurations with the same maximum? How we differentiate between them? I think we should consider if there are also other big pieces so that we can merge them a little later.

So, should we consider the sum of all tile values as our utility? But this sum can also be increased by filling up the board with small tiles until we have no more moves. I think we should penalize the game for taking too much space on the board. So, dividing this sum by the number of non-empty tiles sounds to me like a good idea. We want as much value on our pieces in a space as small as possible.

How do we determine the children of a game state?

In the minimax game tree, the children of a game state S are all the other game states that are reachable from S by only one move. How we determine the children of S depends on what type of player is the one that does the move from S to one of its children.

If the player is Max (who is us — trying to win the game), then it can press one of the arrow keys: up, down, right, left. Depending on the game state, not all of these moves may be possible. So, Max’s possible moves can also be a subset of these 4.

And in this case, the children of S are the game states that can be reached by Max when doing one of these moves.

What moves can do Min? Min’s job is to place tiles on the empty squares of the board. Most of these tiles are of 2 and 4, but it can also use tiles up to what we have on the board. However, we will consider only 2 and 4 as possible tiles; that’s to not have an unnecessary large branching factor and save computational resources. As we said previously, we consider Min as trying to do the worst possible move against us, and that would be to place a small tile (2 / 4).

So, if the player is Min, the possible moves are the cross product between the set of all empty squares and the set {2, 4}. And the children of S are all the game states that can be reached by one of these moves.

Below is a simple example of that:

In the image above, the 2 non-shaded squares are the only empty squares on the game board. And the moves that Min can do is to place a 2 on each one of them or to place a 4, which makes for a total of 4 possible moves.

And that’s it for now. In the next article, we will see how to represent the game board in Python through the Grid class. This class will hold all the game logic that we need for our task.

I hope you found this information useful and thanks for reading!

This article is also posted on Medium here. Feel free to have a look!