Rigging Match 3 Games
Taking on the Role of an Evil Game Designer

I have always had a sort of a love-hate relationship with Match 3 games. On the one hand, they offer some easy way to pass a couple of minutes of casual gaming on the bus or elsewhere, but they also oftentimes feel like being arbitrarily easy or difficult as the levels progress. Especially when we’re talking about mobile versions of the game, the difficulty jumps seem to be almost purposefully defined, in order to get the player to spend money on in-game upgrades.

There's probably no one with a smart phone who hasn't played this at some point

All of this should come as no surprise. Of course game designers are going to overwhelm you with flashy sounds and congratulatory messages (you’re doing so well!) at first before stepping on the brakes and maybe offering you an exclusive one time discount (only 1 dollar for 5 more moves; only 3 dollars for 10 extra bombs).

What I wanted to play around with a bit here, however, comes from the feeling that these incentives mentioned above not only seem to come at purposefully crafted moments, but also seem to incorporate a dynamic aspect as well. It’s one thing for a designer to determine that levels 1 to 10 will gradually ramp up the difficulty, before really making things hard in level 11. Whilst still being very unfun, you could at least appropriate some fairness to this approach as it treats all players evenly. However, this is exactly what you wouldn’t want to do when you’re a game developer aiming to maximize profits. Not only does this not take into account the spending behavior of different players (some of them might be willing to shell out way earlier, or some prefer to wait a bit longer and will be turned off by this early obstacle), it also ignores the skill level of different players. It might sound surprising, but some players are obscenely good at Match 3 games. They can quickly identify opportunities for combo’s, and are fast at picking a good move. Other players might be slower, don’t quickly spot moves involving more than three pieces, or might simply be playing out of boredom rather than interest, with not too much cognitive involvement (like myself).

Let’s say you’re an evil game designer. How would you design a Match 3 game to take the above into consideration. Which dark gameplay patterns can we add on top of everything else we’re using already? We change the gameplay, of course! This is what I meant by the difficulty and offered incentives hence incorporating a dynamic aspect. I don’t know about you, but if you’ve ever played a more recent Match 3 game, have you noticed, perhaps:

  • Doing very well for a couple of levels and the next level suddenly being a lot harder?
  • Failing a level multiple times with only a few remaining goals left?
  • Not playing the game for a couple of days and noticing how suddenly you’re making a lot more combo’s?

It almost feels uncanny. I’m not claiming that any of what I’ll describe below is being done by any game at this moment. In fact, pulling this off would essentially require an always-connected game where the client requests new pieces from the server as matches are being removed from the board. On the other hand, that’s not too unreasonable of a requirement as some games might implement this anyway nowadays to prevent client-side cheating. I have not reverse engineered any games on the Play Store to take a closer look at this; it’s just a thought exercise.

So, to get back on track, we’re trying to design a Match 3 game which, in a nutshell, can be made easier or harder as the game progresses based on how well the player is doing (or any other parameter, in fact; e.g. we could also give the player a “boost” if they’ve just spend money to emphasize the feel-good effect).

Let us first define the simple rules we will be using here, which are a simplification of Match 3 games found in real life, but good enough to illustrate the point:

  • The game is played on a board with C columns and R rows. Typically, C and R are equal to 8 (an 8x8 grid)
  • Each position p(c,r) → s with c ∈ 1..C, r ∈ 1..R, s ∈ S ⋃ {0} defines the piece s present on each location. Note that positions can be empty, so let’s say 0 is the empty indicator. Typically, |S| is equal to 5, 6, or higher, depending on the difficulty of the game. We’ll use 6 pieces here

The game itself progresses through a simple state machine:

drop ↔ fill → remove → (drop | wait)
  • drop moves columns of gems one row down if an empty tile is found with a non-empty tile above it, working upwards: ∀ c ∈ C : ∀ r ∈ R..1 : p(c,r) = 0 ∧ p(c,r-1) = 0 ⇒ (∀ m ∈ r..1 : p(c,m) := p(c,m-1)) ∧ next c (this assumes that p(c,r) = 0 for out-of-bounds inputs)
  • fill inserts new gems to fill up the board in case the top row is empty: ∀ c ∈ C : p(c,1) = 0 ⇒ p(c,1) := getGem(c,~) with getGem being defined later and ~ referring to any implicit arguments, such as the full board, we might need
  • When the board is fully filled, we check for matches to remove. This is a bit cumbersome to write down in full, so lets say that we ∀ c ∈ C : ∀ r ∈ R..1 : isMatched(c,r) ⇒ p(c,m) := 0 with isMatched determining if a piece is part of a match. A piece is part of a match if it is at least part of three subsequent equal piece types row or column wise. Larger matches than three are hence also allowed, e.g. a row of four equal pieces matches completely
  • We don’t score larger matches any differently, we just assign a point per isMatched(c,r) that we remove. No special gems or anything
  • Once this is done, we move back to drop this continues until nothing needs to be dropped, filled, or removed, at which point we wait for user input
  • User input consists of swapping to neighboring gems (row or columns wise, a Von Neumann neighborhood) for those swaps which lead to a valid match, i.e. either of the positions is involved in a isMatched check for the next board after swapping

If that sounded hard, you can also just play the game for yourself. Note that there’s one component we still need to define here, which is getGem. (You can press r to restart and a to make a move automatically. You might need to click inside the board first to get focus.)

So what’s the getGem definition like here? Well… it’s basically as fair as it can be. Whenever there’s an empty spot to fill up, we simply pick a random tile.

fill(x, y) {
    var tile = floor(random(this.board.nrGemTypes));
    this.board.setTile(x, y, tile);
    return true;
}

This doesn’t feel too bad, right? Some of your moves might feel unlucky — i.e. you don’t get any combo’s. Oh, at this point it’s also a good idea to define a “combo”. When you make a match, a combo happens when subsequent drops lead to more matches being made. This provides a very powerful feedback to the player, even without sounds or flashy effects (although the gems breaking up do look nice, you should admit). The fact that a simple action sets of a chain of cascading events, each with immediate reward, is one of the best dopamine rushes that you can give to a player. (Again, these are well known patterns by themselves. Though writing this, I do wonder where that cascading rush comes from, evolutionary speaking, as most things in nature are action-reaction rather than action-reaction-reaction-…)

Let me take a pause for a small intermezzo at this time, before going further. In fact, this blog post idea has been written down in my notebook for about five, if not ten years for now. This is a YouTube upload I made for a Bejeweled Blitz bot in 2010:

Notice the bad recording and audio quality. Peak 2010. I won’t even mention the amazing VB GUI (I forget wheter it was VB.NET or still VB6, but for posterior’s sake, you can also watch the development timeline — even more of a side point, I’m using Notepad++ and Vista in that video, which today feel nostalgic as well).

That recording was mainly a quick effort to whip up something which was fast enough to beat my friends on Facebook (back when Facebook was hip). A couple of years later, in 2015, I did it again, picking the game HuniePop, but now approaching it from a more mathematical angle:

The mathematical angle here being that the bot optimized from selecting matches which would lead to the highest EV (Expected Value) by assuming that removed matches would lead to fully randomized drops, like the game shown above. This worked well, and I was eager to write about it outlining the full mathematical details. Sadly, once I solve a challenge “for myself” I am eager to share it with others but also very, incredibly lazy to do so. I have an utmost respect for bloggers and even more so YouTube creators who put in the effort to not only do the coding but also the production for the stuff they put out there, but sadly, I seem to alternate between moments of pure concentration and complete laziness. The second issue was the fact that HuniePop is kind of a “risqué” game, so I didn’t want to use it as an example on how to apply expectation-maximizing optimization (as sexy as that topic is, though). I also felt Match 3 games were at the end of their lifetime, but mobile games have proven that this is not the case. Lastly, I also was heavily into hacking Flash-based (yes, Flash) give-aways around the time between 2010-2015. This was in the golden era when Flash was just-about to die out, a few freelance companies were trying to hold on, and Flash was still a viable medium to make fun throw-away games and promotions with on Facebook. It’s another topic I’d like to tell the story about some day, and another one which has been on the todo list for who knows how many years now. (Not that all the todo items are deccenia old, it just indicates what my backlog looks like.) In any case, someone (another hacker, in fact) found out my schemes and used the video’s I’ve mentioned before as evidence I “wasn’t to be trusted”. Fun times and again, a story for another time, but at the time it also disheartened me a bit from putting even more eyes on it.

End of intermezzo. I can in any case now cross two items of my list (“Match 3 rigging” and “EV Match 3”).

So now try playing this incarnation of our game:

This should feel worse after a bit of playing… right? The initial board is still filled randomly, but once you make your first move, the game is biased against you, like so:

fill(x, y) {
    var correctY = this.getCorrectY(x, y);
    var bestTile = floor(random(this.board.nrGemTypes));
    var bestMoves = -1;
    var tileIdx = [];
    for (var tile = 0; tile < this.board.nrGemTypes; tile++) tileIdx.push(tile);
    while (tileIdx.length) {
        var tile = tileIdx.splice(floor(random(tileIdx.length)), 1)[0];
        this.board.setTile(x, correctY, tile);
        var nrMatches = this.board.getMatches().length;
        var nrMoves = this.board.getPossibleMoves(false).length;
        this.board.setTile(x, correctY, -1);
        if (nrMatches) {
            continue;
        }
        if (bestMoves == -1 || nrMoves < bestMoves) {
            bestMoves = nrMoves;
            bestTile = tile;
        }
    }
    this.board.setTile(x, y, bestTile);
    return false;
}

Put shortly, we try to minimize the number of moves you can make, albeit in a greedy fashion. Meaning that if there are multiple columns to be filled up, we decide on a piece for the first column, and then move to the next one, without backtracking. We hence don’t guarantee that our fills will lead to a global minimum of possible moves, especially for columns where multiple spots need to be filled (this is also due to the quick and dirty JavaScript implementation and the state machine defined above, fill filles the top row, then moves back to drop and then looks whether it needs to fill again).

In any case, this is not too bad yet, as minimizing the number of moves does not take into account the combo-effect described above. Well, it kind of does, as moving two pieces of the same type in a row of three is technically a valid move when calculating getPossibleMoves, but these will be immediately removed.

Let’s take a look at these issues one by one. Starting with the greedy problem. Let’s replace this with a recursive calculation to find the outcome which leads to the global minimum of moves (again, we keep the initial board randomly filled, otherwise there won’t be any moves at all to make; it also would take a long time to calculate — the implementation is not fast to begin with):

Note that this again feels much worse to play. Now it’s not a full worst-possible recursion yet, as the global solution might still involve filling the board with pieces which do lead to an additional combo, which again would lead to a removal step and filling the board up again. We only look at the current board but not at the next boards which might arise from followup-removals. Doing so would be more in line with the full-recursive EV approach mentioned above, now using is as an EV minimization procedure to work against the player. However, this is not easily implemented without a system which allows for setting up a tree of game boards and searching through those, something I didn’t feel like doing in JavaScript. It’s a hard problem in any case as Match 3 games are NP-hard.

We can also see what happens if we focus on combo’s in a greedy fashion, e.g. using nrMatches rather than nrMoves in the greedy code fragment above. In fact, to switch things around, let’s now go towards optimizing the highest number instead of lowest:

Okay, this perhaps does feel too good too play, but it does reveal something interesting, namely the fact that the combo-aspect is more directly related to difficulty and game-feel (in terms of “how well am I doing?”) then number of remaining moves. The reason for this being that — especially with a randomly filled initial board — their will typically be enough possible moves present so that players do not immediately feel like they’re being punished on this. We do feel that we’re not making as many long-string combo’s.

With this in mind, we can figure out a version which works greedily (which is fine), but allows to tune the amount of the game favoring you:

fill(x, y) {
    var correctY = this.getCorrectY(x, y);
    var bestTile = floor(random(this.board.nrGemTypes));
    var bestMatches = -1;
    var tileIdx = [];
    for (var tile = 0; tile < this.board.nrGemTypes; tile++) tileIdx.push(tile);
    while (tileIdx.length) {
        var tile = tileIdx.splice(floor(random(tileIdx.length)), 1)[0];
        this.board.setTile(x, correctY, tile);
        var nrMatches = this.board.getMatches().length;
        this.board.setTile(x, correctY, -1);
        // Consider better matches as long as the dice falls below a set value
        if ((bestMatches == -1 || nrMatches >= bestMatches) &&
            (random() < this.slider.value())) {
            bestMatches = nrMatches;
            bestTile = tile;
            console.log(x, y, bestMatches, bestTile)
        }
    }
    this.board.setTile(x, y, bestTile);
    return false;
}

There are better ways to do this, like a biased weighted random choice, but again this is enough to make the point:

Drag the slider to increase our decrease the chance of more combo’s. The higher, the better you’re chances.

To conclude, it is of course very doable to create a dynamic version of a Match 3 game which dynamically adjusts itself to make things harder or easier. This should come as no surprise of course, and a full implementation would be even better at allowing to determine which tiles should be dropped (i.e. do a full tree search) then what I did here. Obviously, the main challenge when implementing something like this is e.g. a mobile game would lie in figuring out how exactly this bias should be changed and based on which inputs. Performance over the game so far, performance over the last n games played, time the game was last opened, time the last purchase was made, amount spend so far? No doubt there are gacha game designers thinking about exactly these questions.