Welcome to my third post on solving Match-3 games with graph algorithms. In my previous post, I described the Swapless Match-3 Game (SM3), where the player does not have to perform any swaps and instead finds contiguous horizontal and/or vertical lines of the same color.
One feature of the SM3 game is that there is no gravity. Hence, after a player takes an action, the blocks are removed, but the other blocks on the game board remain where they are. In this and in subsequent posts, we will be adding more features to the Match-3 game to make it more complex and interesting, and we will also discuss more graph algorithms.
In this post, we will add gravity into the game. The player will continue to not have to perform swaps, but now, the remaining blocks will “fall down” due to gravity. We will describe the game in a little more detail, discuss how to represent it as a graph, walk through a graph algorithm that solves this game, and conclude with some discussion.
Let’s begin with defining our Match-3 game. We will be calling it the “Swapless Match-3 with Gravity” (SM3G) game since it is an extension of the “Swapless Match-3” (SM3) game we discussed in the previous post.
Most of the definitions of SM3 still apply, namely the size of the game board being n by m squares, each block having one of K colors, the player’s actions, the point system, and the goal of the game.
The key difference is that we will now incorporate “gravity” into the game. Specifically, after a block at (x, y) is removed, all blocks (x, y + 1), (x, y + 2), … lower their y coordinate by 1. In other words, the blocks above (x, y) fall down by 1 square. Figure 1 demonstrates the effect of gravity in the game.
At first glance, adding gravity may seem somewhat trivial, since all that happens is that blocks now fall down. However, there are a few questions we must now consider.
Firstly, when a block on the top-most row (i.e, a block at (x, m — 1)) is removed or falls down, what happens to that square? Does it get filled in with a new block? If so, where does the new block come from?
Secondly, after an action is taken and blocks fall down, what happens if new horizontal/vertical lines of the same color are created? Should those lines also be automatically removed? If so, how does that affect the points that are gained from that action?
For the first set of questions, we will assume that in the SM3G game, a much larger “world” exists that is n by M in size, where M ≥ m. In fact, the player always “knows” what blocks will fall into the top-most row after all of the player’s actions. If M is close to m, then it means that no new blocks will appear after blocks are removed. This assumption allows the player to continue to have full knowledge of what happens in the game over time, as compared to a typical Match-3 game where there are unknowns. For example, in Candy Crush, after some candies are removed, it is not always known what candies will enter the game board. We will consider such unknown states in a later post.
For the second set of questions, we will allow “chain” effects in the SM3G game. Specifically, if the player’s action removes blocks in a set of coordinates, e.g., (x, y), (x + 1, y), (x + 2, y), then after the other blocks “fall down”, if new lines are formed that contain one or more of those coordinates, then those lines are also automatically removed, creating a new set of coordinates to be considered (and discarding the first set). Chain effects can occur many times, until no new lines are formed. The points gained from an action with chain effects will be V(i), where i is the total number of blocks that were removed, including all the chain effects.
Figure 2 is an example of an initial game board and how one action creates a chain effect. In total, 6 blocks were removed, so V(6) points are received.
Another effect of chain effects is that the bonus points at the end of the game may no longer be optimal with respect to the total number of points received. Specifically, a player receives V(n + m) points for every unused action when the game is complete, i.e., when the points is greater than or equal to the goal P.
In the SM3 game, it is optimal to complete the game as quickly as possible, since each action can only receive a maximum of V(n + m — 1) points, which is when a row and column of maximum heights and widths are cleared simultaneously. However, in the SM3G game, it may seem that an action can potentially receive an unlimited number of points if the chains never end. But there is a caveat: since the world has a finite height of M, at some point blocks will stop falling and the chains will stop. Even so, receiving V(n + m) points for each remaining action may be less than the points the taking the actions might have caused. Figure 3 shows an example where an action is taken and the game is complete. Figure 4 shows an example of taking two actions to complete the game, which results in more total points, even after including the bonus points that the actions of Figure 3 receives.
Thus, we should take all of the above into account when discussing the graph algorithm to solve SM3G.
Now that we have described the SM3G game, let’s have a look at an online that is very similar to SM3G. Colorpop is a single-player game that you can play. There is another board game for 2 to 5 players with the same name, but in this section, we will be referring to the single player online game.
In Colorpop, the game proceeds with time (not actions), and the goal is to get as many points as possible before time runs out or the board is filled up (explained later). Each turn, a player “pops” one square of the board, where there are at least 3 contiguous colors. Our definition of SM3G also requires 3 or more contiguous colors. However, in Colorpop, the popped region is any 4-connected region, as opposed to a horizontal and/or vertical line of SM3G. This is a small difference that can easily be accommodated for in our SM3G definition.
After a square and its contiguous region are popped, the remaining blocks above it fall down due to gravity. The effect of gravity is identical to our description in SM3G.
The point system of Colorpop is similar to SM3G, where popping a larger number of contiguous squares results in a higher number of points gained. The actual value function is slightly different, but SM3G’s V(i) function can be updated to reflect the change.
A larger difference is that Colorpop is time-based. When time runs out, the game ends. Since we have defined SM3G to be action-based, i.e., the world does not change until/unless an action is taken, the time-based nature of Colorpop is a significant difference. However, we can approximate it by assuming that each action takes up a certain amount of time.
Besides ending the game when time runs out, Colorpop also adds new rows of blocks from the bottom after a pre-determined amount of time. SM3G currently does not have any such feature, although it could be added into the game definition if needed, without affecting the graph representation or the algorithm to solve SM3G.
Finally, Colorpop has a number of special blocks, such as blocks that remove an area of blocks (like the bomb block in Figure 5 above), and blocks that add to the total time remaining. In SM3G, we only consider blocks that are one of K colors, without any special abilities. We will consider special blocks in a later post of this series!
All in all, Colorpop is very similar to SM3G, although modeling Colorpop exactly would require some changes to the definition of SM3G. For the sake of streamlining our explanation of SM3G and the graph algorithm, we will not be making those changes. However, you can make the extension from SM3G to Colorpop if you so wish!
Now that we have defined SM3G and described its similarity to Colorpop, we shall now represent the SM3G game as a graph. Like my previous post, we will discuss the states/vertices, edges and goal states. In the next section, we will discuss the helper functions that the graph algorithm will use.
The states/vertices in SM3G are almost identical as SM3, where each state contains the game board, the number of points, and number of actions remaining. However, a key difference is that the game board is now n by M in size, instead of n by m. Hence, the 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. Again, the bonus points are not computed in the state, but we will compute them in the graph algorithm, which we will discuss later.
The edges in SM3G are identical to SM3, where each edge denotes a legal action in the game. A legal action is one that selects a coordinate (x, y) where 0 ≤ x < n, and 0 ≤ y < m, even though the state contains an array of n by M values.
Also, the next state after taking an action will be the state after all chain effects have occurred. We will assume that the number of chain effects is finite since M is finite, and thus the next state can be computed.
The goal states are also identical to that of 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 SM3G 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.
We will use the same 3 helper functions as the SM3 solver, GetActions(s), TakeAction(a), and HypotheticalAction(s, a). For more details on these functions, please refer to my previous post. Below is a short description of the 3 helper functions.
GetActions(s) returns a list of legal actions from a state s. TakeAction(a) takes a legal action a (i.e., an edge (s, s’)) on the current state s, updates the current state to s’, and returns s’. HypotheticalAction(s, a) takes a state s, and an action a that is a legal action of s, and returns the next state s’ which corresponds to the resultant state if the action a is taken in state s.
Since SM3G has chain effects, TakeAction(a) and HypotheticalAction(s, a) are a little more complex than that in SM3. We will handwave the implementation of these functions, since they are used by the graph algorithm but are not necessarily part of the graph algorithm. However, it will be necessary for these functions to perform the “falling down” of blocks, detecting new lines and removing those, and causing more blocks to “fall down” until the chain effect stops, and finally computing the points received.
To solve SM3G, we can use the greedy algorithm described in my previous post. However, the greedy algorithm was shown to not be optimal for SM3, and will perform worse in SM3G due to the chain effects. In fact, the greedy algorithm may not find a solution for SM3G at all.
Figure 6 is an example SM3G game where the goal is to obtain 8 points or more, using 2 actions or less. In the initial state, there are 2 possible actions, the horizontal blue line, or the horizontal red line. The horizontal red line results in a chain effect while the blue doesn’t, and attains more points immediately. Thus, the greedy algorithm would select that action. However, after selecting the red horizontal line, the only action remaining is to clear the purple horizontal line, which results in a total of 6 points, and is lower than the goal of 8 points. In contrast, selecting the blue horizontal line on the initial board of Figure 6 would receive fewer points immediately, but it would allow for a longer chain effect when clearing the button red blocks, and receiving sufficient total points to complete the game.
In this post, we will be discussing a depth-first search algorithm to find a solution to solve SM3G. We will first provide some pseudocode and describe the flow of the algorithm, and we will analyze and discuss the algorithm in the next section.
function DepthFirstSM3G(s, P, actionsSoFar)
// If the current state s is a goal state, we’re done
if s.p >= P
// Otherwise, recurse on all possible actions
possibleActions = GetActions(currentState)
for action in possibleActions
possibleNextState = HypotheticalAction(currentState, action) // Retrieve the coordinates corresponding to the action
possibleActionsSoFar = actionsSoFar + [metadata(action)]
possibleSolution = DepthFirstSM3G(
possibleNextState.s, P, possibleActionsSoFar) // If we’ve found a solution, break the recursion and
// return that solution
if possibleSolution != null
end for // No solution found
return nullend function
In the pseudocode above, DepthFirstSM3G is a recursive algorithm. Its parameters are s (the current state), P (the point threshold), and actionsSoFar (the list of actions taken so far). The top-level call to retrieve a solution would be to DepthFirstSM3G(s0, P, [ ]), since it starts at the initial state s0 with no actions taken yet.
As a base case to the recursion, if the current state s is a goal state (i.e., the points of that state are greater than or equal to the point threshold P), then actionsSoFar is a solution and the function returns it.
Otherwise, the algorithm loops through all possible actions from the current state, and recurses on the children of the current state (by hypothetically taking the action). If any of the recursive calls returns a solution, then the recursion ends early and the solution is propagated quickly up the call stack to the top-most level and returned as the solution of the algorithm. Figure 7 illustrates the search path of a depth-first search algorithm.
Let’s start with the same question as the greedy algorithm: is the DepthFirstSM3G algorithm optimal? We will define an optimal solution as a sequence of actions that solves the game, and results in the highest possible number of points received, including the chain effects and bonus points at the end. There may be multiple optimal solutions, i.e., multiple sequences of actions from the initial state that result in the same number of points, but is the DepthFirstSM3G algorithm guaranteed to find any of them?
Sadly, the answer is still no. DepthFirstSM3G is not guaranteed to find an optimal solution, since it returns the first solution it finds. In other words, DepthFirstSM3G will return a solution if one exists, but that solution has no guarantees on optimality.
However, that does mean that DepthFirstSM3G is a complete algorithm. In other words, if at least one solution exists in the problem, then DepthFirstSM3G is guaranteed to find and return it, given enough time. From the pseudocode, we can see this happening as the algorithm tries all possible search paths until a solution is found. However, if the problem does not have any solutions, then DepthFirstSM3G would have to search through all possibilities before finally giving up and returning no solution.
As an extension, it is possible to update DepthFirstSM3G to be an optimal algorithm, i.e., an algorithm that finds an optimal solution if one exists. Namely, instead of returning the first solution that it finds, it can save the “best” solution (in terms of the number of points including bonus points) that it has found so far, and keep going. When the top-most call completes, the “best” solution will correspond to an optimal solution. However, such a change, while allowing the algorithm to find an optimal solution, also requires that it finds all solutions, which may be intractably long to execute. Thus, there are other graph algorithms that can be used to find optimal solutions.
In the next post of the series, we will be adding a new feature into the Match-3 game — swaps! We will discuss how swaps affects the game, the graph representation, and a graph search algorithm that is optimal. Stay tuned!