Welcome to the second post of my technical blog series on solving Match-3 games with graph algorithms! In the first post, I gave a brief introduction to graphs, and described how graphs can represent scenarios such as how a robot navigates a maze, and the game of chess.
In this and subsequent posts, we will be diving into Match-3 games. We will first focus on a “simplified” Match-3 game for starters, and then add complexity in later posts. We will mainly talk about how to represent the simplified Match-3 game as a graph, since this representation will be used (with some tweaks) in future posts. We will also discuss how to solve the simplified Match-3 game with a greedy algorithm, and conclude with some discussion about the algorithm.
Let’s first define what our simplified Match-3 game will be. We’ll be calling it “Swapless Match-3”, or SM3 for short. As its name suggests, the player will not have to perform any swaps in order to clear blocks from the board. Below is an image of an example board.
The game board is n by m squares, where n is the width of the board, and m is the height of the board. In each square of the game board, it may or may not be occupied by a block, which will be one of K colors. In the image above, the game board is 4 by 5 squares, and there are 3 colors, red, green, and blue.
We’ll also define a coordinate system, which will make it easier for us to refer to particular locations on the board. Let (0, 0) be the bottom-left square, with the x-axis going to the right, and y-axis going up. Using the image above again, the square (3, 2) is occupied with a blue block.
The player is allowed to play one “action” each turn, where an action is a selection of a single (x, y) coordinate. A legal action is one where there is a block at (x, y) with color k, and there are 3 or more blocks in a horizontal line and/or vertical line containing (x, y) that all have blocks with color k. In the image above, (1, 0) is a legal action, since (0, 0), (1, 0), (2, 0) all have the same color blue. Similarly (2, 4) is a legal action since (0, 4), (1, 4), (2, 4), (3, 4) and (2, 2), (2, 3), (2, 4) all have the same color green. In contrast, (3, 1) is not a legal action since the longest vertical line of the same color is (3, 1), (3, 2), and the longest horizontal line is (2, 1), (3, 1). Even though contiguously they form 3 squares, each horizontal or vertical line must consist of 3 of more blocks of the same color.
After the player plays one legal action, blocks in the horizontal line and/or vertical line are removed from the game, and the remaining blocks do not move. In SM3, we will assume that the game does not have gravity, so blocks do not fall downwards if there is empty space below them. We will consider gravity in our next post. Below is the game board after an action at (0, 0) has been played from the image above.
Each legal action that the player plays generates some points. Let V(i) denote the point function, i.e., V(3) is the points from clearing 3 blocks, V(4) is that for 4 blocks, and so on. For example, let’s suppose that in our example V(i) = 0 if i < 3, and V(i) = i – 2 if i ≥ 3, e.g., V(5) = 3.
At the beginning of the game, the player has a maximum of A actions, and 0 points. After taking a legal action, the number of remaining actions decrease by 1, and points increase by V(i). The goal of the game is to attain at least P points before there are no more remaining actions. If there are a actions remaining when the points ≥ P, then the player receives V(n + m) points for each remaining action.
Following on from our example images above, suppose the game starts with 4 actions with a goal of 4 points. The player plays actions (0, 0) (as mentioned above), and then (2, 4). After these 2 actions, the player has 7 points (3 points from the first action, 4 points from the second), and the game is complete. Since there are 2 actions remaining, the player receives a bonus of 2 * V(4 + 5) = 14 points, for a total of 21 points.
There may be multiple ways to represent the SM3 game as a graph (i.e., vertices and edges), and in this article, we will use an approach similar to that of chess, which we described in our previous post. For a recap of graph-related terms and a description of how chess can be represented with graphs, check out my previous post.
We will be using the words state and vertex somewhat interchangeably, although we will generally use the term state when we’re discussing the search algorithm, and vertex when we’re talking about the graph. We will represent a vertex with the current colors and positions of blocks on the board, together with the current number of points and number of actions remaining. Specifically, the state of the game can be represented as a structure containing an n by m array and 2 integers. The array will contain values from 0 to K, where 0 indicates an empty square (i.e., no block is present there). The 2 integers represent the number of points and the number of actions remaining respectively. In terms of notation, we will say that state s = (bs, ps, as), where bs is the n by m array, ps is the number of points, and as is the number of actions remaining. In this representation, the bonus points are not computed, and we will discuss them later when we analyze the proposed algorithm.
From the description above, you can imagine that the number of possible states can be huge: just the n by m array could have (K + 1)^(nm) possibilities! As such, we will not be enumerating all possible vertices in our graph; it will suffice to know our current state, and other reachable states from that.
Edges in a SM3 graph are directed, and an edge represents a legal action that can be taken in the game. Similar to states, it may be challenging to fully enumerate all possible edges, so we will only consider edges from states that are reachable from the current state. In addition, we will consider that every edge has some metadata that contains the coordinate (x, y) that was selected in order to take the action. We will generally omit the metadata when mentioning edges, but we will use it later in the algorithm.
Taking a legal action not only changes the blocks on the board. The points are also increased by V(i), where i is the number of blocks removed, and the number of actions remaining decreases by 1. As an example of vertices and edges in the SM3 graph, the figure below shows an initial state v1, and two child states v2 and v3. There exists edges (v1, v2) and (v1, v3) in the SM3 graph.
In the SM3 graph, we will assume that all edges are unweighted (i.e., all edges have a cost of 1).
In the SM3 game, the game ends when the number of points is greater than or equal to some given value P, and the number of remaining moves is greater than or equal to 0.
Thus, in the SM3 graph, goal states are states s such that ps ≥ P and as ≥ 0. We use the phrase goal states because there may be more than a single state that fulfills the goal of the game.
Before diving into an algorithm that will solve the SM3 game, let us first discuss some functions that will be useful, which we will assume already exists.
The first function is GetActions(s). Conceptually, GetActions returns a list of legal actions that can be taken from a state s. In terms of the graph, GetActions(s) returns the list of edges in the graph that start from s.
The second function that we assume exists is the function TakeAction(a). Conceptually, TakeAction takes a legal action a from the current state s, updates the current state to be s’, and returns s’. In terms of the graph, the action a corresponds to an edge (s, s’), and thus, the function TakeAction((s, s’)) updates the current vertex to be s’ and returns it. TakeAction can only be called on legal actions a that can be taken from the current state s. Otherwise, the function is undefined.
While MakeMove only takes in legal actions from the current state, we will also make use of a third function, HypotheticalAction(s, a). Conceptually, HypotheticalAction is similar to TakeAction, except that it has an additional parameter s. Instead of mutating the current state, HypotheticalAction returns the state s’ that would be achieved if action a is taken in state s. We will use this function HypotheticalAction in the graph search algorithm to consider the next action to be taken, before calling TakeAction on that action.
Now that the SM3 graph and helper functions have been defined, we can dive into an algorithm that solves the SM3 problem. We will be using a greedy algorithm, and later discuss the performance of the greedy algorithm in the SM3 problem.
Here is the pseudocode of the algorithm:
function GreedySolveSM3(s0, P)
actions =  // The actions that are taken
currentState = s0 while currentState.p < P and currentState.a > 0
possibleActions = GetActions(currentState) // Find the best next action greedily
bestAction = null
bestP = currentState.p
for action in possibleActions
possibleNextState = HypotheticalAction(currentState, action)
if possibleNextState.p > bestP
bestAction = action
bestP = possibleNextState.p
end for // If there isn’t a best action, there is no solution
if bestAction == null
end if // Retrieve the coordinates corresponding to bestAction
// Hypothetically take the action and update the current state
currentState = HypotheticalAction(currentState, bestAction)
end while // Return the actions that can be taken to solve SM3
return actionsend function
In the pseudocode above, the function GreedySolveSM3 takes in the initial state s0 and the number of desired points P, and returns a list of coordinates that represent the list of actions that can be taken to achieve the goal. If the algorithm does not find a solution, i.e., there is no way to achieve P points with the number of actions greedily, then null is returned.
The bulk of the algorithm happens in the for-loop over possible actions. The algorithm, being greedy, picks the next action that yields the highest possible points immediately. After finding the highest-point action, it is executed (hypothetically, so the game state doesn’t actually change), and the current considered state advances, until the current state’s points are above the desired threshold P, or we run out of available actions.
The algorithm is greedy because it picks the locally optimal action at each step, where optimal is defined as the next state with the highest points. While typical graph search algorithms tend not to be greedy and explore more of the graph, this greedy algorithm is technically still a graph search algorithm, because it considers all neighbors of the current state as it traverses down a single path in the graph. The figure below illustrates the greedy algorithm traversing a single path in the graph of possibilities from the initial state.
One question that is good to ask about any graph search algorithms is whether it is optimal. Before we can answer whether or not the GreedySolveSM3 algorithm is optimal, we first have to define what we mean by optimality. In the context of the SM3 game, we can define the optimal solution as the solution that ends up with the highest number of points (including bonus points after completing the game).
An interesting feature of the SM3 game is the lack of gravity. Since pieces don’t “fall down” from gravity, the order of actions seems to have little impact, or no impact at all if all the actions clear blocks of different colors. For example, suppose the game board contains one row of all green, one row of all red, and one row of all blue, and empty otherwise. Regardless of what order red, green and blue are cleared, the resultant state is identical — those 3 rows will be cleared, and the points will be the same. The figure below illustrates the progression of different orders of actions over a game board.
Actions can have some impact though. Suppose that the game board consists of a single L-shape made of red blocks, and nothing else. If the first action is the corner of the L-shape, then all the red blocks will be cleared, and a substantial number of points will be achieved. However, if the first action is the top-most or right-most point of the L-shape, then only a row, or a column, would be removed, which may remove the possibility of subsequently removing the column/row if not enough red blocks remain. Even if sufficient blocks remain, the number of points with the 2 actions would be less than the points with a single action at the corner. The figure below illustrates the possibilities and points achieved.
Given that the order of actions has limited to no impact, is it always preferable, given a color, to take an action to remove as many blocks of that color as possible? Would such an action always yield more points than taking multiple actions of removing the same color? Taking it one step further, is it always preferable to take an action to remove as many blocks as possible, over all possible colors, like what the GreedySolveSM3 algorithm does?
Unfortunately, the answer is no, the GreedySolveSM3 algorithm is not optimal. Below is an example board with only one color of blocks to help simplify the explanation. There are multiple possible action paths, but let us only consider two — the actions that the GreedySolveSM3 algorithm would take, and another set of actions that would yield a higher number of points.
In the game board above, the GreedySolveSM3 algorithm would choose to first take the action at (3, 2), which would clear the largest plus-shape on the board, consisting of 11 blocks. Subsequently, the only action remaining would be to clear the column of 3 blocks. Thus, the SM3 Greedy Algorithm would attain V(11) + V(3) = 10 points.
Below is a different sequence of actions. Suppose that the first action is at (4, 5), which would clear an inverted-T of 5 blocks. Subsequently, the plus-shape (which is now 1 block smaller) can be cleared. These two actions would yield V(5) + V(10) = 11 points.
Thus, this counterexample shows that the GreedySolveSM3 algorithm is not optimal. But fear not! We will be exploring other graph algorithms in our future posts, some of which will be optimal algorithms.
In the GreedySolveSM3 algorithm, it does not consider bonus points, because it is greedy and only considers the immediate best next action. If the action doesn’t complete the game, then no other action this turn would complete the game and all subsequent states would not have received the bonus points (yet), so the algorithm doesn’t need to consider the bonus points at all. Conversely, if the action completes the game, then the maximum number of bonus points would be gained from the current state (since only 1 action is taken), and the algorithm doesn’t need to explicitly compute the bonus points.
In the next post of the series, we will be continuing with Swapless Match-3 plus an additional feature — gravity. We will discuss how gravity affects the game, the graph representation, and another graph search algorithm. Stay tuned!