Playing 2048 with Minimax Algorithm — 1

Original article was published by Dorian Lazar on Artificial Intelligence on Medium

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 how they 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 on 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.

Image by Author

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:

Image by Author

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.