Creating a bot tester for match-3 games

In the process of working on a match-3 project, sooner or later, the question necessarily arises - how to evaluate the complexity of the created levels and the overall balance of the game?

Even with a large number of testers in a team, collecting detailed statistics for each level (and there are hundreds of them in modern games) is simply unrealistic. Obviously, the testing process needs to be automated somehow.

Below is a story about how we did this in our indie match3 game, which we are now finishing work on. (Caution - footcloth!)

Formulation of the problem

To automate level testing, we decided to program a “bot” that would meet the following requirements:

Binding to the game engine - the bot should “use” the same blocks of code that are used during a standard game. In this case, you can be sure that both the bot and the real player will play the same game (i.e. they will deal with the same logic, mechanics, bugs, etc.).

Scalability - it is necessary that the bot can test not only already existing levels, but also levels that can be created in the future (given that in the future new types of chips, cells, enemies, etc. can be added to the game) . This requirement largely overlaps with the previous one.

Performance- to collect statistics on one level, you need to “play” it at least 1000 times, and there are hundreds of levels, which means the bot must play and collect statistics fast enough so that analysis of one level does not take all day.

Reliability - bot moves should be more or less close to the moves of the average player.

The first three points speak for themselves, but how to make the bot play "humanly"?

Bot strategy. First approach

Before starting work on our project, we went through about 1000 levels of varying difficulty in different match3 games (two or three games even went through as a whole). And having thought over this experience, we decided to stop on the following approach to level creation.

I must say right away that this decision does not claim to be the ultimate truth, and is not without flaws, but it helped us build a bot that meets the requirements described above.

We decided to proceed from the fact that a good level is a kind of task to find the optimal strategy - level designer creating a level “guesses” the optimal sequence of actions, and the player must guess it. If he guesses correctly, then the level is relatively easy. If the player acts “out of order”, then he is very likely to be in a hopeless situation.

For example, let there be given a level in which there are “multiplying” chips (if you do not collect a group of chips next to them, then before the next player’s turn they capture one of the cells adjacent to them). The goal of the level is to lower certain chips in the bottom row of the board. Our game is dedicated to sea adventures (yeah, again!) Therefore it is required to lower the divers to the bottom, and corals act as breeding chips:



If the player does not take the time to destroy the corals from the very beginning, and instead immediately tries to lower the divers, then most likely the corals will grow and make the level impassable. Therefore, in this case, we can say that the strategy that the level designer “thought up” is approximately as follows: “Destroy the corals as soon as possible, and then lower the divers”.

Thus, the strategy of passing the level, both from the side of the level designer, and from the player’s side, consists in prioritizing between various tactical actions (in what follows I will call them simply tactics). The set of these tactics is approximately the same for all games of the genre:

• collect as many chips as possible (points)
• collect chips of a certain type
• destroy "interfering" chips / cells
• create bonus chips
• attack the “boss”
• let down certain chips
• etc…

The ability to set these priorities for each level, we added to our Excel





-based level editor: Level designer creates a level and sets tactical priorities for the bot - the generated XML file will contain all the necessary information about both the level and how to test it. As you can see in the picture, the following prioritization is supposed to solve the level:

1. Destruction of Coral (ANTI-CORAL)
2. Creation of bonuses (COLLECT BONUS)
3. Descent of divers (DIVERS)
4. Choosing the most valuable moves (MAXIMUM POINTS)

When testing a level, the bot should take these priorities into account and choose the appropriate moves. Having decided on the strategy, it is already easy to program the bot.

Bot algorithm

The bot works according to the following simple algorithm:

1. Download priority list for level from XML file
2. Save all currently possible moves to an array
3. Take next priority from the list.
4. Check if there are moves in the array that correspond to the current priority
5. If there is, then choose the best move.
6. If not, GOTO 3.
7. After the move is done, GOTO 2

The task of determining whether the move corresponds to a tactical priority will not be considered in detail here. Briefly, when compiling an array of possible moves, the parameters of each move are saved (how many chips were collected, what type of chips were, whether a bonus chip was “created”, how many points were scored, etc.) and then these parameters are checked for compliance priorities.

After the bot “wins back” the level a specified number of times, it displays statistics on the results: how many times the level was won, how many moves were taken on average, how many points were scored, etc. Based on this information, it will already be possible to decide whether the level of complexity corresponds to the desired balance. Here, for example, part of the printout by the level shown in the pictures above:

LEVEL STATISTICS:
=====================================
STOP LIMIT: 30
NUMBER OF EXCESSIONS: 1000
PER LOSSES : 63% (630 RUNS)
AVERAGE COMPLETION OF THE LOSED LEVEL: 61%
AVERAGE NUMBER OF WAYS AT WINNING: 24
----------------------------- -------
POINTS:
-------------------
MINIMUM ACCOUNT: 2380
MAXIMUM ACCOUNT: 7480
-------------- -----
------------------------------------
RUNNING STATISTICS:
------ -------------
0. LOSS (87.0% COMPLETED)
1. LOSE (12.0% COMPLETED)
2. LOSS (87.0% COMPLETED)
3. LOSS (87.0% COMPLETED)
4. LOSE (87.0% COMPLETED)
5. VICTORY (LEVEL COMPLETED IN 26 STROKES. 2 STARS ASSEMBLED.)
6. LOSE (75.0% COMPLETED)
7. VICTORY (LEVEL COMPLETED IN 26 STROLLES. 3 STARS ASSEMBLED
 
    ...  3.

It can be seen that the level is lost in 63% of cases. This is a quantitative assessment of this level, which you can already rely on when balancing and determining the order of levels in the game.

And who said that the player will act that way?

Above, we suggested that the player, choosing the next move, analyzes the moves available in the given position and selects the one that is best suited for the highest priority tactics at the given moment. And based on this assumption, we set the logic for the bot.

But there are two assumptions here:

• The real player is unlikely to analyze all the moves on the board - rather, he chooses the first found more or less reasonable move. And even if he tries to consider all the moves on the board, he can still simply not notice a good move.
  
• The player is far from always able to determine and correctly prioritize - for this you need good knowledge of a specific game and its mechanics, which means that you can’t expect optimal actions from it on each specific move. (Although this is a lesser problem, because the player will learn from his mistakes and in the end will figure out what is important for passing the level, and what can wait).

It turns out that a bot built on the basis of these assumptions will play not as an average, but as an “optimal” player, well acquainted with all the subtleties of the game. And you can’t rely on the statistics collected by this bot. What to do?

Bot strategy. Second approximation

Obviously, you need to introduce some kind of correction factor that would make the bot’s actions less “ideal”. We decided to stay on a simple option - to make part of the bot's moves simply random.

The coefficient determining the number of random moves is again set by the level designer based on his goals. We called this coefficient “deviation from the strategy” - set it to 0.2 for this level:



A deviation of 0.2 means that with a probability of 0.2 (or in other words in 20% of cases) the bot will simply choose a random move from the ones on the board. Let's see how the statistics on the level changed with such a deviation (the previous statistics were calculated when the deviation is zero - that is, the bot absolutely exactly followed the given priorities):

LEVEL STATISTICS:
=====================================
STOP LIMIT: 30
NUMBER OF EXCESSIONS: 1000
LOSS PERCENT. : 78% (780 RUNS)
AVERAGE COMPLETION OF THE LOSED LEVEL: 56%
AVERAGE NUMBER OF GOALS AT WINNING: 24
----------------------------- -------
POINTS:
-------------------
MINIMUM ACCOUNT: 2130
MAXIMUM ACCOUNT: 7390
-------------- -----
...  
 

The percentage of lost levels expectedly increased by 15% (from 63 to 78). The average completeness of the lost level (the percentage lowered to the bottom of the divers) also fell as expected. But the average number of moves when winning, which is curious, has not changed.

Statistics show that this level is quite complicated: 24 out of 30 moves should be well thought out (30 * 0.2 = 6 moves can be made “in vain”), and even in this case the player will lose in 78% of cases.

The question remains - where did the coefficient 0.2 come from for this level? What are the odds for other levels? We decided to leave it at the discretion of the level designer.

The meaning of this coefficient is very simple: "the number of rash moves that a player can make at this level." If you need a simple level for the initial stage of the game, which should be easily passed by any player, then you can balance the level with this coefficient equal to 0.9 or even 1. If you need a difficult or very difficult level, for the passage of which the player must make maximum efforts and skills , then balancing can be carried out with a small or even zero deviation from the optimal strategy.

Performance

And finally, a few words about the speed of work.

We made the bot a part of the game “engine” - depending on the flag set, the program either waits for a move from the player, or the moves are made by the bot.

The first version of the bot turned out to be quite slow - it took more than an hour to complete 1000 runs of the level in 30 moves, even though all the graphic effects were turned off in the test mode and the chips moved between cells instantly.

Since the entire game logic is tied to a rendering cycle, and it is limited to 60 frames per second, to speed up the tester's work, it was decided to turn off vertical synchronization and “release” FPS. We use the LibGDX framework in which this is done this way (it might come in handy for someone):

cfg.vSyncEnabled = false;
cfg.foregroundFPS = 0; 
cfg.backgroundFPS = 0; 
new LwjglApplication (new YourApp (), cfg);

After that, the bot quickly ran at a speed of almost 1000 frames per second! For most levels, this is enough to make 1000 “runs” of the level in less than 5 minutes. Honestly, I would like even faster, but you can already work with this.

Here you can see the video of the bot (unfortunately, when recording video, FPS drops to about 120):

Summary

As a result, we have a bot tied to the game engine - there is no need to maintain a separate tester code.

If in the future new mechanics are added to the game, then the bot can be easily taught to test them - you only need to add identifiers for new tactics in the level editor and enter additional parameters into the code when analyzing moves.

The hardest thing, of course, is to assess how much the bot’s behavior matches the behavior of the average player. But this will be a weakness of any approach to building an automated tester, so no one canceled testing on living people (especially from the target audience).