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

bynsquares, wheremnis the width of the board, andmis 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 ofcolors. In the image above, the game board is 4 by 5 squares, and there are 3 colors, red, green, and blue.KWe’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

coordinate. A(x, y)legalaction is one where there is a block atwith color(x, y), and there are 3 or more blocks in a horizontal line and/or vertical line containingkthat all have blocks with color(x, y). 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) isknota 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 notmove. 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

denote the point function, i.e.,V(i)is the points from clearing 3 blocks,V(3)is that for 4 blocks, and so on. For example, let’s suppose that in our exampleV(4)ifV(i) = 0, andi < 3ifV(i) = i – 2, e.g.,i ≥ 3.V(5) = 3At the beginning of the game, the player has a maximum of

actions, and 0 points. After taking a legal action, the number of remaining actions decrease by 1, and points increase byA. The goal of the game is to attain at leastV(i)points before there are no more remaining actions. If there arePactions remaining when the pointsa, then the player receives≥ Ppoints for each remaining action.V(n + m)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

points, for a total of 21 points.2 * V(4 + 5) = 14There 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

stateandvertexsomewhat interchangeably, although we will generally use the termstatewhen we’re discussing the search algorithm, andvertexwhen 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, thestateof the game can be represented as a structure containing anbynarray and 2 integers. The array will contain values from 0 tom, 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 stateK, wheres = (bs, ps, as)is thebsbynarray,mis the number of points, andpsis the number of actions remaining. In this representation, the bonus points areasnotcomputed, 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

bynarray could havempossibilities! As such, we will not be enumerating all possible vertices in our graph; it will suffice to know our current state, and other(K + 1)^(nm)reachablestates 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

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.(x, y)Taking a legal action not only changes the blocks on the board. The points are also increased by

, whereV(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 statei, and two child statesv1andv2. There exists edgesv3and(v1, v2)in the SM3 graph.(v1, v3)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

, and the number of remaining moves is greater than or equal to 0.PThus, in the SM3 graph, goal states are states

such thatsandps ≥ P. We use the phrase goalas ≥ 0statesbecause 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,GetActionsreturns a list of legal actions that can be taken from a state. In terms of the graph,sGetActions(s)returns the list of edges in the graph that start from.sThe second function that we assume exists is the function

TakeAction(a). Conceptually,TakeActiontakes a legal actionfrom the current statea, updates the current state to bes, and returnss’. In terms of the graph, the actions’corresponds to an edgea, and thus, the function(s, s’)TakeAction((s, s’))updates the current vertex to beand returns it.s’TakeActioncan only be called on legal actionsthat can be taken from the current statea. Otherwise, the function is undefined.sWhile

MakeMoveonly takes in legal actions from the current state, we will also make use of a third function,HypotheticalAction(s,a). Conceptually,HypotheticalActionis similar toTakeAction, except that it has an additional parameterInstead of mutating the current state,s.HypotheticalActionreturns the statethat would be achieved if actions’is taken in statea. We will use this functionsHypotheticalActionin the graph search algorithm to consider the next action to be taken, before callingTakeActionon 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 if

end for // If there isn’t a best action, there is no solution

if bestAction == null

return null

end if // Retrieve the coordinates corresponding to bestAction

actions.append(metadata(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 functionIn the pseudocode above, the function

GreedySolveSM3takes in the initial stateand the number of desired pointss0, 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 achievePpoints with the number of actions greedily, thenPis returned.nullThe 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

, or we run out of available actions.PThe 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

someimpact 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

notoptimal. 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

points.V(11) + V(3) = 10Below 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

points.V(5) + V(10) = 11Thus, this counterexample shows that the GreedySolveSM3 algorithm is

notoptimal. 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!

Credit: BecomingHuman By: Allison Liemhetcharat