Playing 2048 with Minimax Part 2: How to represent the game state of 2048

And how to do it in an object-oriented fashion

In the last article about solving this game, I have shown at a conceptual level how the minimax algorithm can be applied to solving the 2048 game. But to put those ideas into practice, we need a way of representing the state of the game and do operations on it. I chose to do so in an object-oriented fashion, through a class which I named Grid. This class holds the game state and offers us the methods we need for further implementing the minimax algorithm (in the next article).

In case you missed my previous article, here it is:

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

---

Now, let’s start implementing the Grid class in Python.

Inside the Grid class, we will hold the game state as a matrix with tile numbers in it, and where we have empty squares, we will hold a 0. In Python, we’ll use a list of lists for that and store this into the matrix attribute of the Grid class.

An example of this representation is shown below:

In our implementation, we will need to pass this matrix around a little bit; we will get it from one Grid object, use then to instantiate another Grid object, etc. So, to avoid side effects that can arise from passing it by reference, we will use the deepcopy() function, hence we need to import it. Another thing that we will import is Tuple, and List from typing; that’s because we’ll use type hints.

from copy import deepcopy
from typing import Tuple, List

The simplest thing we can start with is to create methods for setting and getting the matrix attribute of the class. Then we will create a method for placing tiles on the board; for that, we’ll just set the corresponding element of the matrix to the tile’s number. The input row/col params are 1-indexed, so we need to subtract 1; the tile number is assigned as-is.

Then we will define the __init__() method which will be just setting the matrix attribute.

For the minimax algorithm, we’ll need to test Grid objects for equality. We will consider 2 Grid objects to be equal when the 2 object’s matrices are the same, and we’ll use the __eq__() magic method to do so. We iterate through all the elements of the 2 matrices, and as soon as we have a mismatch, we return False, otherwise True is returned at the end.

Next, we create a utility method. This method evaluates “how good” our game grid is. There could be many possible choices for this, but here we use the following metric (as described in the previous article): sum all the elements of the matrix and divide by the number of non-zero elements.

The next piece of code is a little tricky. We need to check if Max can do one of the following moves: up, down, left, right. The code for each of these moves is quite similar, so I will explain only one of these moves: up which is implemented in the .canMoveUp() method.

When we want to do an “up” move, things can change only vertically. There’s no interaction between different columns of the board. So, we can run the code independently for each column.

We can do this in a for loop:

And we don’t necessarily need to check all columns. As soon as we encounter a column that allows something to be changed in the “up” move we return True. If there is no such column, we return False at the end.

For each column, we do the following: we start at the bottom and move upwards until we encounter a non-empty (> 0) element. After we see such an element, how we can know if an “up” move changes something in this column? 2 possible things can produce a change: either there is an empty square where a tile can move, or there are 2 adjacent tiles that are the same.

As an example:

The code highlighted below is responsible for finding the down most non-empty element:

The piece of code highlighted below returns True as soon as it finds either an empty square where a tile can be moved or a possible merge between 2 tiles.

Below is the code with all these methods which work similarly with the .canMoveUp() method.

We will need a method that returns the available moves for Max and Min. For Max that would be a subset of the moves: up, down, left, right. We will represent these moves as integers; each direction will have associated an integer:

• Up = 0
• Down = 1
• Left = 2
• Right = 3

In the .getAvailableMovesForMax() method we check if we can move in each of these directions, using our previously created methods, and in case the result is true for a direction, we append the corresponding integer to a list which we will return at the end of the method.

The .getAvailableMovesForMin() method will return, the cross product between the set of empty places on the grid and the set {2, 4}. This return value will be a list of tuples of the form (row, col, tile), where row and col are 1-indexed coordinates of the empty cells, and tile is one of {2, 4}.

The .getChildren() takes a parameter that can be either “max” or “min” and returns the appropriate moves using one of the 2 previous methods. These are the moves that lead to the children game states in the minimax algorithm’s tree.

For the minimax algorithm, we need a way of establishing if a game state is terminal. As I said in the previous article, we will consider a game state to be terminal if either there are no available moves, or a certain depth is reached. But checking for the depth condition would be easier to do inside the minimax algorithm itself, not inside this class. So, by the .isTerminal() method we will check only if there are available moves for Max or Min. A simple way to do this, is to use .getAvailableMovesForMin() or .getAvailableMovesForMax() to return a list with all the moves and if it is empty return True, otherwise False. But a more efficient way is to return False as soon as we “see” an available move and at the end, if no False was returned, then return True.

The .isGameOver() method is just a shorthand for .isTerminal(who=”max”), and it will be used as an ending condition in our game solving loop (in the next article).

The methods below are for taking one of the moves up, down, left, right. This time we actually do these moves, don’t just check if they can be done. The code for each movement direction is similar, so, I will explain only the up move.

The up move can be done independently for each column. We will have a for loop that iterates over the columns. For each column, we will initialize variables w and k to 0. w holds the location of the next write operation. k stores the tile value of the last encountered non-empty cell.

The algorithm runs as follows:

And here is an example of how it works for a given column:

Below is the code with all 4 methods: .up(), .down(), .left(), .right():

Then we create a wrapper around the above 4 methods and name it .move(), which does a move in the direction given as a parameter.

Another thing that we need is the move’s “inverse” method. .move() takes as a parameter a direction code and then does the move. Now, we want a method that takes as parameter another Grid object, which is assumed to be a direct child by a call to .move() and returns the direction code that generated this parameter. We name this method .getMoveTo().

This method works by creating copies of the current object, then calling in turn .up(), .down(), .left(), .right() on these copies, and tests for equality against the method’s parameter. And where the equality is True, we return the appropriate direction code.

Below is the full code of the Grid class:

And that’s all for this article. In the next one (which is the last about 2048 and minimax) we will see how we can control the game board of a web version of this game, implement the minimax algorithm, and watch it playing better than us (…or at least better than me).

Playing 2048 with Minimax Part 3: How to control the game board of 2048

---

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!