In this paper, we propose a methodology based on reinforcement learning to automate video game testing. In particular, we discuss how the use of game playing agents with hybrid policies that incorporate reinforcement learning nodes alongside manually implemented ows in the context of behavior trees could lead to potentially more generalizable, understandable, and easier to ne-tune testing agents than those implemented via pure reinforcement learning techniques. In addition, we explore di erent strategies and con gurations for training these agents, and describe a simple procedure for detecting signi cant modi cations in selected gameplay metrics of a game level after introducing design changes. This is intended as a road map for future work in the development of automatic game testing and balancing tools.
Quality control in modern video games can be a major challenge. Nowadays it is not only necessary to keep a strict and continuous control of technical failures or bugs that may arise during the development process, but also of new problems in the playability derived from small changes in gameplay code and parameters that are used in di erent parts of the game. These changes can bring about various adverse e ects such as preventing players from being able to complete previously solvable sections, altering the navigability of menus and environments, or modifying the di culty perceived by the user, in dissonance with the experience originally conceived by the designers.
Quality assurance (QA) tasks usually involve an immense testing e ort in which developers and players strive to detect and solve these problems. In light of this situation, in the last few years several research works have emerged with Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). the aim of proposing strategies to improve the QA process in video games and reduce its cost. Many of these methods are aimed primarily at developing agents (usually by using deep reinforcement learning, DRL) that act as synthetic players capable of automating checks that may otherwise require numerous hours of manual testing, in an attempt to redirect the e orts of human testers towards less mechanical and more creative tasks.
The methodology described in this paper can be applied to the design of automatic regression tests for detecting issues when modi cations are made to level layouts, design parameters, or AIs that are reused in multiple sections of the game. The former may be performed during iterations of a speci c level's design process, whereas the latter may be included when ne-tuning the behavior of a NPC in a level without thinking about the implications of those small variations on other levels where the NPC was placed before. Changes as simple as slightly modifying an enemy's movement speed could end up unexpectedly impacting how the player interacts with the game's levels. These changes need not be particularly drastic (such as as sudden violations of the completability of a level), and may boil down to the player taking more or less time to complete a part of the game, or exploiting a new way to beat a level that was not originally contemplated. All of these design alterations should not go unnoticed, but many of them are not usually straightforward to detect in typical testing environments.
In this paper we propose the application of di erent reinforcement learning methods to produce testing agents capable of interacting with a set of levels in a stealth game while collecting interaction statistics representative of the perceived gameplay in each level. The agents are afterwards used to test whether a change in the level or AI design induces signi cant changes in gameplay parameters collected by the agents before applying the modi cation. 2
The following subsections introduce preliminary topics used in this work: RL, BTs, and RL-nodes in BTs. 2.1
Reinforcement learning (RL) is a process where an agent learns by trial and error from experience by interacting with its environment. In an RL problem, a distinction must be made between the agent, which interacts with its environment through actions, and the environment itself, which provides feedback and \rewards", or positive/negative reinforcement to the agent. RL algorithms usually take the formulation and formalism of Markov decision processes (MDPs) as a starting point. If we consider st 2 S as the state of the system at a given instant t, and at 2 Ast the action that the agent executes at that instant, where Ast is a possibly in nite set of admissible actions for the agent under state st, the agent's goal will be to learn a mapping between states and actions : S ! A = [s2S As, that maximizes the expected long-run total reward from each state s: (1) where 2 (0; 1) is a discount factor that gives more weight to rewards earned in the short term, and Ri is the reward the agent receives at the i-th instant. 2.2
A Behavior Tree (BT) is a way of structuring policies or controllers in
autonomous agents, such as robots or non-player characters in a video game (NPCs).
In essence, a BT can be de ned as a rooted tree in which the leaves correspond
to execution nodes, associated to a speci c task or condition check of the agent
to be controlled, and the intermediate nodes take on the role of ow control
nodes. BTs were initially conceived in the eld of video game programming,
with the rst journal paper on BTs appearing in [
The execution of a behavior tree starts at the root node, which generates signals or \ticks" with a given frequency. These signals enable the execution of a node and are propagated from parent to child in the internal hierarchy of the tree following the speci c logic of each type of control node. A node can be executed if and only if it receives a tick. A child node can respond with Running to its parent if it is in the middle of an execution process, Success if it succeeds in completing its task, and Failure in any other case. Every result will eventually be propagated back to the root node, resulting in the generation of a new tick. This generates a cyclic behavior that continuously repeats the execution of the tree. This cyclic nature is precisely what gives BTs a good responsiveness to changes in the environment: since the conditions are rechecked at each iteration, the control ow can be modi ed if the context di ers from that of the last cycle.
Control nodes represent composite behaviors that succeed or fail depending on the results returned from one or more of their children (which can be of any type, control or execution). The most common types of control nodes are Sequence and Fallback. Sequence nodes are used when a set of actions or conditions are intended to be executed sequentially, and will only succeed if all children complete their behaviors successfully. Fallback nodes on the other hand propagate the tick to their children from left to right until nding one that returns a Success or Running state, and then return that same state to their parent, meaning they will only return Failure when all of their children end with a failing state. 2.3
The above two concepts can be combined giving rise to behavior trees containing nodes supported by reinforcement learning. In general, the current literature contemplates two main types of RL nodes, depending on whether the learning is performed on a control or execution node.
{ A RL-control node can be viewed as an extension of the usual control node,
usually of type fallback [
In any of the above cases, the main goal of combining behavior trees with reinforcement learning is the implementation of actions and ows that are complex to program manually, but in speci c regions of the agent's BT whose limited scope allows to dampen the so-called \curse of dimensionality" in learning subproblems. As an example, when designing the behavior of a robotic agent in an environment, it may be complicated to e ciently orchestrate actions that require the coordination of a large number of joints, such as \picking up an object". In this situation, it is possible to train an action node that learns only this task, and incorporate it into the original tree afterwards, with the problem being reduced to local learning in a controlled environment, but the behavior itself supported by the responsive structure of the BT. 3
By testing we refer to the activity undertaken to evaluate the quality of a product
and improve it by identifying its defects and problems [
In [
Moreover, these methods are not always trivial to implement, often
requiring a potentially daunting process of trial and error in the choice of training
algorithm, reward allocation policy, model features, or the hyperparameters of
the underlying neural networks. Fortunately, over the last few years, libraries
for popular game engines have been appearing that greatly facilitate this
process, with ML-Agents [
In [
Lastly, there exist several works focused on facilitating the task of
designing and adjusting the parameters of videogame contents, both in the eld of
playtesting and in level balancing and design. [
In this paper we focus on the description of a preliminary automated testing methodology based on the agents presented in Section 2 for a speci c game environment that will be covered in detail in Section 5.
This methodology starts from a speci c level of our game, which we consider nished from a design and/or development point of view. For this level, we wish to monitor certain gameplay parameters in order to detect any relevant changes induced by a modi cation on the enemy AI or the level design as soon as possible, for instance by tuning its parameters to meet the requirements of a later level. To carry out this tracking, we wish to train a set of \automatic players" using the techniques already described (RL, hybrid BTs) so that they learn to play the game \like humans". This learning process is conceived as a general procedure, which tries to generate agents capable of playing any kind of level, in such a way that the result may be reused for testing not only existing levels, but also new environments. This generality is, however, potentially challenging to achieve depending on the context, so the strategies proposed in this paper will need to be adequately validated in future experimental work.
Once agents with a su ciently acceptable general ability have been obtained (where the concept of acceptability here takes on an admittedly subjective meaning), one can proceed to the generation of benchmark statistics on the parameters of interest at chosen stages after having agents playing at each level a large number of times. Once we have these references, it is possible to automatically perform a new round of gameplay and statistics compilation on the levels already developed to evaluate the possible impacts of the day's changes on their playability. With these statistics, we can verify if our agents are completing the levels with results equivalent to those recorded on the previous day. If this is statistically not the case, chances are that something has occurred, and we can issue a warning so that a member of the team can investigate the origin of this \alarm". 5
In this section, we will focus on concretizing the methodology described above to the proposal of automated tests for a simple demo game that includes some of the most common mechanics found in genres such as stealth games, in which the player navigates through levels patrolled by enemies that must be avoided while actively trying to attain a certain goal (often reaching a given point in the level). The rules of the designed game can be summarized in the following points: 1. The player is represented by a blue circular gure, with a continuous action space given by At = f(x; z); x; z 2 [ 1; 1]g, which determines the possible movement directions at each instant. The player has a xed maximum velocity vp, such that the velocity at each instant is given by vtp = vp jj((xxtt;;yytt))jj . (a) Enemy Avoidance level (b) Enemy Timing level (c) Hiding Areas level 2. The player starts each level placed on a yellow platform, to which he/she returns after being defeated by an enemy. The victory condition is to reach the green platform located at a xed point in the level. A player is defeated when his/her health points (HP) are reduced to 0, these being lowered by 1 each time the player is hit by an enemy bullet and starting at 10 HP initially.
Some sample levels can be found in Fig. 1. 3. The enemies are shaped like red cubes and have an associated \patrol" path (white lines in the gures), which they cycle through until they detect the player in their range of vision, after which they proceed to chase and shoot at their target as long as it is alive or remains within detection range. 4. Some levels contain yellow walls that block the enemies' range of vision, but have no e ect on the player's movement or visibility (e ectively creating hiding areas). Fig. 1c contains an example of this mechanic.
This demo game was developed in the Unity 3D engine, with the BTs of the
enemies implemented using the Behavior Bricks plugin for the engine [
We have already de ned the action space A of our agent, but we still need to specify on the basis of what information these actions should be taken. A rst approach could consider the following features: { Target location (2 features). Components (x; z) of the distance vector between the player and the target platform, scaled to lay in the [ 1; 1] range. { Relative location of the enemies (4 features per enemy). Components (x; z) of the distance vector between the player and each of the enemies in the level as well as the components (x; z) of the normal unit vector of the enemy's front face. The latter data provides information about the orientation of the enemy at any given time.
In addition to these features, we may also incorporate a series of spatial
sensors or raycasts (for instance 12 sensors) that allow us to identify objects close to
the agent in radial directions. Here we consider the objects \goal", \enemy" and
\wall". The number of features derived from the incorporation of these sensors
can be calculated as (number of rays + 1) (number of detectable labels + 2) =
(12 + 1) (3 + 2) = 65 spatial features. This expression corresponds to a one-hot
encoding of sensors and tags, where the +2 term in the number of detectable
tags represents the cases where a ray detects an object with an unconsidered
tag or nothing at all. It is interesting to note here that the length of the
characteristics linked to the enemies can vary depending on the level, and this can be
managed through the use of BufferSensors in ML Agents (which make use of
an underlying attention module [
Another alternative in this situation is to replace or complement the described observations by grid-based observations, taking advantage of the essentially two-dimensional nature of the game under consideration. These inputs, as the name suggests, are based on covering the level space by a grid of cells in which the presence of objects of the di erent categories to be perceived by the agent is detected, so that the observation associated with each cell is given by a one-hot representation of the objects found in it. This type of input is managed in ML Agents by means of GridSensorComponents, which provide what could be seen as a condensed and simpli ed version of a purely visual input. The total size of observations is thus given by GridSize.x GridSize.z number of detectable labels, and in the case of the levels considered for this game we can take x = z = 20, and keep the same tags as in the previous setup, but incorporating an additional one to represent the player. For the resulting agent to be reusable between levels, however, it is required to keep the dimensions of the grids xed, which could hinder the general long-term viability of this method.
As for the reward allocation functions to employ, we can translate the ideas
outlined in [
If, on the other hand, we were to create a bot that gives priority to reaching the goal in the shortest time possible, regardless of the number of life points at the end of the level, we could opt for the following con guration: { Positive rewards: (+2 units) for reaching the goal and nishing the level. { Negative rewards: (-2 units) for dying after being hit by an enemy bullet and nishing the level, (-0.1 units) for being hit by an enemy bullet, and an existential negative reward (-0.01 units) for each step taken by the agent.
This last penalty may be included to encourage agile ows and spur the agent to nish the episode as soon as possible to avoid too much negative reward.
In this situation, it is of particular importance to ensure that we do not
reach a state of over tting on the levels of the original battery of manually
designed environments, trying in particular to avoid learning speci c movement
paths, or enemy dodging patterns conditioned by the structure of the starting
levels. Justesen et al. [
In addition to agents trained purely by reinforcement learning, we consider a second class of agents given by a hybrid model between manually programmed behaviors and ows learned by RL in the context of a behavior tree. The idea here is to de ne a BT with a selector that alternates between xed base ows (for instance \navigate to goal") and learned actions within RL nodes that are triggered upon entering certain states, e.g. when an enemy enters the agent's range of vision (\evade enemy"). In this way it is possible to set certain easily implementable actions, within level-agnostic action nodes and let the reinforcement learning algorithm handle speci c situations, such as evading the enemies, under controlled conditions.
The reinforcement learning nodes in this case may consider the same features for the st states as those already described in the previous subsection, but it is also possible to opt for more limited subsets of these features, or even include new observations of novel types, depending on the particular needs of each action block. On the other hand, reward allocation features can be tailored locally to each RL node to motivate speci c behaviors, and multiple functions that induce di erent play styles within the action can also be considered here.
This structure presents a number of possible expressive and practical advantages over the pure reinforcement learning based modality. Especially when the expected behavior of the game-playing agent is su ciently complex, the division of the general ow into small blocks of localized logic allows on the one hand to easily incorporate manually programmed sections to take a more rigid control over certain functional regions, and on the other hand to generate complex personalities, in the sense that the existence of local reward functions opens the possibility to create \action libraries" with blocks representing the same task to solve, but di erent styles to do so de ned by the reward functions speci ed to train them. Thus, instead of de ning a global personality for an agent, we can construct BTs that behave in di erent ways depending on the task at hand. 5.3
Once we have agents that are able to interact with the game in a satisfactory way, it is possible to proceed to the testing phase. At this stage we will be interested in extracting a sample of relevant execution parameters for a given number of attempts of the agent on the considered level. To do this, we may set a high number of repetitions per agent and level, in each of which we record statistics regarding, for instance, the HP with which the agent nishes each run and the number of steps needed to complete the level. These samples can be stored as references against which to test future changes in the level.
Having selected reference agents for a level and recorded a sample of contrast
statistics, it is possible to perform a series of Student's t-tests (or Welch's t-tests
if we do not assume variance equality) after incorporating any change in the game
in order to check whether any of the statistics considered varies signi cantly (for
the reference agent) after introducing the aforementioned change. To do this,
it is su cient to collect a new execution sample for the agent on the modi ed
level and perform a parameter-by-parameter t-test to assess whether the means
of the reference and test sets are signi cantly di erent from one another after
the change ( = 0:05). In our case, we assume that the variances of the two
groups do not necessarily need to be equal, and therefore we propose the use of
Welch's t-tests [
This paper focused on the problem of creating testing agents to detect signi cant changes in di erent aspects of gameplay on a demo with stealth genre mechanics. We proposed and described two accessible alternatives to obtain agents capable of playing di erent levels of the game, the rst one through pure RL, and the second through hybrid models that combine RL action nodes within handcoded control structures in the form of BTs, both of them with the possibility of introducing di erent reward function based play styles. Hybrid models, however, could potentially be easier to ne-tune and may possess greater expressive capacity than their pure RL counterparts. In this methodology, after obtaining satisfactory agents for each training method, a rst simulation step can be carried out in which the agents play the considered levels repeatedly, recording relevant statistics regarding their perception of the execution, for instance HP remaining at the end of the level and time taken to complete it. Subsequently, after introducing various changes in the behavior of the enemies, the level layouts, and so on, new simulations can be performed with the agents on all levels to recollect performance metrics in the modi ed environments. Lastly, the reference samples may be compared with those of the post-change simulations by applying a means-contrast test or a non-parametric test on each of the parameters of interest to detect statistically signi cant changes in level gameplay.
This work is intended to serve as a road map and basis for future work aimed at analyzing whether the automated tests performed using this methodology can assist in locating and explaining changes of interest in the base of evaluated levels. Under the assumption that this is the case, if the tests after modi cation fail for any of the agents, the designer can analyze the results to check whether they conform to the predicted e ect, if this was intended, or proceed to manually investigate the level where the test failed to search for the origin of the variation in the statistics. This would make it possible to narrow down the search for unexpected e ects to those levels reported by the tests, or to evaluate whether a design change has the desired impact on the monitored parameters. Additionally, the introduction of game styles based on the use of di erent reward functions may allow to analyze the e ect of applying changes not only at a general scale, but for di erent archetypal pro les that may be considered relevant in the design of the level, thus providing a tool to support the tailoring of experiences adapted to the player's pro le.