Using patterns as objectives for general video game level generation

Abstract

Automatically generating multiple levels and creating infinite game-play for video games is a complicated task. In this paper, we introduce a pattern-based level generator for general video games. Our generator uses a genetic algorithm to automatically generate levels. The fitness function promotes contiguous patterns and penalizes levels with single or isolated elements. The generator generates levels using two different types of fitness functions; α and β. α levels are generated using the original fitness function and β levels through the inverse of the fitness function. In our experiments, Relative performance profiles indicate that controllers using more advanced techniques achieve better overall performance on α generated levels. The generator finished at the third spot in the 2018 general video game level generation competition.

Keywords

Procedural content generation general video games level generation design patterns

1. Introduction

Procedural Content Generation (PCG) for games is the algorithmic creation of game contents like: music (Jordan et al., 2012), textures (Ebert and Musgrave, 2003), terrains (Preuss et al., 2014), dungeons (Van Der Linden et al., 2014) and levels (Dahlskog and Togelius, 2014). The development of PCG enables the significant and real-time creation of content based on few parameters. It reduces the cost and time of game development and creates a possibility of infinite gameplay for players. One of the first games to use PCG was Elite1

¹
Acornsoft. (1984). Elite. [Digital game]

which used a random generation approach for a game level generation. PCG became popular in the last decade when it was used for generating game graphics (Ebert and Musgrave, 2003). Since then, interest in PCG has gained traction and spread over the years.

Three basic approaches used for automatic content generation are: Constructive techniques (Shaker et al., 2016), Search-based Procedural Content Generation (SBPCG) techniques (Togelius et al., 2011) and Machine Learning approaches (Summerville et al., 2018). Constructive techniques run in linear time and do not re-generate content in order to improve game quality. Search-based PCGs are special types of generate-and-test algorithms where the algorithm does not simply accept or reject the generated content but also grades it using a fitness value. On the other hand, Machine Learning approaches are train models using game samples and generate instances using the trained model.

In the domain of PCG, level generation has been the most challenging problem. However, most of the level generation research has been focused on specific games such as Super Mario Bros (Dahlskog and Togelius, 2014). Generating content suitable for a single type of game is important but it undermines the capability and re-usability of a generator. On the other hand, creating a level generator capable of generating levels for multiple games is a challenging task in itself. An important framework in this area is the General Video Game Level Generation (GVG-LG) framework (Khalifa et al., 2016). The framework uses the Video Game Description Language (VGDL) (Schaul, 2013) to describe games and it is built upon the General Video Game AI (GVG-AI) framework (Perez-Liebana et al., 2016).

A design pattern involves a pattern that describes a recurring problem in an environment and a core solution to that problem which can be reused many times for the same problem. In video games, design patterns can be seen as problems faced by the player posed by the designer. One can view the content in a level as a sequence of patterns. These patterns collectively form challenges. For instance, the player must find a solution in order to progress through the level. In generating levels for Super Mario Bros, PCG played an important role to improve the recurring level design through a concatenation of design patterns (Dahlskog and Togelius, 2013).

In this paper, we present the usage of design patterns for the generation of general video game levels. In an earlier work (Sharif et al., 2017), we identified patterns from a set of 90 games from the GVG-AI framework. In this work, we propose an intelligent search-based level generator that uses design patterns to generate levels for general video games. The generator uses a Feasible Infeasible 2 Population Genetic Algorithm (FI2Pop) (Kimbrough et al., 2005) that handles two distinct populations at the same time; one for the feasible population and the other for the infeasible population. The feasible population tries to improve the fitness of overall chromosomes, while the infeasible population tries to decrease the number of chromosomes, creating difficulties. Our fitness function is based on the hypothesis that isolated patterns would create a level of low quality. Therefore, isolated patterns are assigned a low fitness value. On the other hand, patterns occurring in groups are assigned a high fitness value in order for them to survive in the next generation.

For evaluation purposes, we use two different types of fitness functions: α, the original fitness function that increases the chances of multi-line patterns which include all patterns except isolated or single game elements and β, an inverse version of our pattern-based fitness function. It is important to note here that β fitness function is an inverse of α pattern-based fitness function and hence, it penalizes multi-line patterns and promotes isolated patterns. In addition, eight different game-playing controllers are executed on both α and β generated levels and their performances are compared. The relative performance of different general game-playing algorithms supports our hypothesis that good game-playing algorithms have better performance on well-designed games which in our case are the α generated levels. The generator was submitted to the 2018 GVG-LG competition2

http://www.gvgai.net/gvg_rankings_lg.php

and it was ranked third out of six generators.

The paper is structured as five sections. The second section briefly describes the related work. In the third section, we explained our search-based generator. The fourth section of this article describes the evaluation of the proposed generator and in the final section, we conclude our paper.

2. Related work

2.1. Design patterns and games

Alexander et al. (1977) originally developed patterns related to architecture for problem-solving. A pattern consists of two components: challenge and its solution. The challenge refers to a common and recurring design element in object-oriented development (Gamma, 1995). In a software application, the design patterns give insight to designers about architectural knowledge and provide a template for many situations. A collection of possible design choices in a game can explore architectural knowledge for a designer. These design choices are chunks of game design and can help automate game development.

Design patterns have been applied previously for the generation of levels for specific games. Hullett and Whitehead (2010) used design patterns for a first-person shooter game (Halo 3). Similarly, Dahlskog and Togelius (2012) identified patterns of enemies, gaps, valleys, multiple paths, and stairs to generate levels for Mario. Initially, Dahlskog and Togelius (2013) proposed a naive way of combining the discovered design patterns into game levels. In addition, Dahlskog and Togelius (2014) used vertical slices of existing levels as design patterns and generated levels of sufficient quality.

2.2. GVG-LG track

VGDL (Schaul, 2013) was designed to support both general video game playing and video game generation. A VGDL is the game description which consists of four different parts: a sprite set, interaction set, level mapping, and termination set. The sprite set describes all game object types and properties. The interaction set defines how these objects interact with each other. The level mapping describes how game objects are represented in a level file, while the termination set defines the conditions for completing a game.

The GVG-AI (Perez-Liebana et al., 2016) is a framework used for game-playing competition. It provides an opportunity for competitors to create their own general game-playing controllers and to test them against a variety of different games. The GVG-LG track (Khalifa et al., 2016) is built upon the GVG-AI framework and uses VGDL to describe levels. It allows competitors to integrate their level generators and test them against a set of different games. Three different generators, Random level generator, Constructive level generator, and Search-Based level generator are provided as sample level generators within the framework. The Random level generator creates levels by placing sprites on random empty positions and ensures that a generated level has at least one instance of each sprite. The Constructive level generator generates levels using information from the Game Analyzer. The Game Analyzer divides the levels into different sprites. The generator further follows a step-by-step guide for level creation. The third and most prominent generator is the Search-based level generator (SB-LG). The levels are represented as a 2D array of tiles where each tile had an array of strings representing sprites at that tile. The generator uses a genetic algorithm with a one-point crossover operator, which swaps the two chromosomes around a random tile. For mutation, it uses three different operators: create, destroy and swap. The generator uses an altered version of the Adrienctx controller (Perez-Liebana et al., 2016) for simulation-based fitness and constraint evaluation.

2.3. Search-based level generation

Togelius et al. (2011) introduced the term search-based PCG to describe a set of techniques using search-based methods, such as evolutionary algorithms. These algorithms allow content to be generated and refined towards a predefined set of goals, using a fitness function. In Shaker et al. (2012), the authors introduce a grammatical evolution method to generate player-adapted content for Mario levels. The fitness function captures player experience and learns three emotional states: engagement, frustration and challenge. This method provides the ability to recognize and learn from different playing styles. Ashlock et al. (2011) identifies a variety of representations for encoding mazes and gave a framework for designing fitness functions that give substantial control over the character of the mazes that evolve during the evolution process. The generator generates multiple characters by using three different representations. This technique uses checkpoints within the maze to identify the connectivity and path lengths within a level. The study suggests that varying the numbers and arrangement of these checkpoints should yield an idea for controlling the type of mazes. Sorenson and Pasquier (2010) presents a generic approach for automatic content generation. The generator automatically generates game levels according to a definitive model based on challenges and fun. The model draws a definite connection between the variety of challenge and the enjoyment experienced by a player, which creates a rhythmic structure of patterns with high and low difficulties. Such a rhythmic structure provides an effective way to engage players. In this approach, possible level designs are considered as individuals in a population and individuals with high difficulty are used in further generations.

There are a variety of search-based approaches for the GVG-LG framework. The sample search-based level generator generates levels using the FI2POP genetic algorithm. The feasible population tries to increase the difference between the OLETS agent and one-step look ahead, while the infeasible population tries to decrease the number of chromosomes that violate the constraints. Other generators that follow search-based approaches and were part of the GVG-LG competition includes Jnicho genetic generator, Amy12 genetic generator, and Number13 genetic generator. However, to the best of our knowledge, there are no published studies related to the mentioned generators.

3. Pattern-based level generator

In this section, we explain our pattern-based level generator that utilizes patterns which are extracted using the GVG-LG framework. These patterns are then used as objectives for level generation. The detail of these two steps have been explained in detail in the following subsections.

3.1. Pattern extraction for GVG-LG

In our previous work (Sharif et al., 2017), we identified patterns using rhythmic analysis. The pattern sizes vary from one to five depending upon the game. A rhythmic group is a short and non-overlapping set of components that unfolds an area of challenge in the game. Rhythmic groups help identify challenging areas of a level and understand what makes them difficult. For this purpose, a game level is sub-divided into cells. A cell is a section of non-overlapping, linear game-play connected by portals. For example: In Mario, the pipe in a level is a portal. The player can go into the pipe and appear in a new area in the game. The cells are connected by that pipe because it is possible for the player to choose between the two cells.

A pattern is composed of one or more adjacent sprites. A few example of collectible sprite patterns are shown in Fig. 1. From the rhythmic analysis of the GVG-LG framework, we find that most of the games have similar design patterns. For level generation, these patterns are assigned different frequencies considering our pattern-based fitness function. Sprite types that are a part of our fitness function include: Solid Sprites, Collectible Sprites, Harmful Sprites, Other Sprites and Goal. For each sprite type, different frequencies were assigned. All patterns are assigned low fitness if individual, medium in a pair and high if in groups (greater than two sprites together).

Fig. 1.

Examples of design patterns for collectible sprites. A pattern of size one is labeled as 1 and a pattern of size three is labeled as 2.

3.2. Level generation using patterns as objectives

Our level generator takes as input the game description and has access to all its information set. It uses the game description to generate a level using a Feasible Infeasible two Population genetic algorithm (FI2Pop). Genetic algorithms are generally represented using a binary string; however, a variety of representations are available (Whitley, 1994). In our case, we have used FI2Pop genetic algorithm and levels are represented as the 2D array of tiles. Each tile consists of an array of strings representing all sprites in that tile. The initial population is generated from the sample constructive level generator and the population size of 50.

For crossover, the generator uses one-point crossover operation which swaps two chromosomes at randomly selected tiles. For mutation, three different operators i.e. create, destroy and swap are used. For the simulation-based fitness function, Adrienctx (a well-performing controller that won the 2014 competition) (Khalifa et al., 2016) is used. The fitness function is a combination of the existing sample genetic level generator technique and our proposed pattern based heuristic function. The idea of using the proposed fitness function is inspired by the work done by Dahlskog and Togelius (2013). We modify the fitness function introduced by Khalifa et al. (2016) work to incorporate the idea of design patterns. The fitness function consists of three main parts:

Score Difference Fitness: Score difference of Adrienctx and OneStepLookAhead.

Unique Rule Fitness: The number of unique events that happened in the level due to avatar or any sprite spawned by it.

FPattern Fitness: Sum value of amount of individual patterns multiplied by their fitness frequency value.

The fitness function is computed as an average value of these three; Score Difference Fitness, Unique Rule Fitness and FPattern Fitness. Note that Score Difference Fitness and Unique Rule Fitness were introduced in Khalifa’s work (Khalifa et al., 2016). The fitness function now includes the following:

\begin{matrix} (1) & FitnessFunction = \frac{Fscore + Frule + FPattern}{3} \end{matrix}

where Fscore is the Score Difference Fitness, Frule is the Unique Rule Fitness and FPattern is the Pattern-based fitness function which is defined as:

\begin{matrix} (2) & FPattern = \sum_{i = 1}^{n} Pi * Wi \end{matrix}

In Equation (2), P of i represents the ith pattern and W of i represents its assigned frequency. The Infeasible population is subject to different constraints. The constraints are kept the same with no change from the original generator.

The pattern-based generator finds the set of combination of patterns; e.g. a single sprite, collection of two sprites or group of sprites. The detailed explanation of sprite identification has been reported in our previous work (Sharif et al., 2017). After identifying the patterns, the generator assigns the fitness values such as low, medium and high based on the occurrence of a pattern. Single sprite is assigned by low fitness value in contrast to our assumption on their impact in level design. Two sprites at a position are assigned by medium fitness value as they have an intermediate impact accordingly, while sprites in a group are assigned by high fitness value.

For each generation, these patterns are evaluated on the basis of assigned values. The fitness function decides which iteration is best suited to generate the offspring. Two different fitness functions were tested i.e. α for actual fitness function and β that reverses the FPattern-based fitness. In the reverse process, fitness function changes the assigned values of the patterns. For example, the patterns that were given a high percentage for α fitness function such as rooms were given a lower percentage for β fitness function. Fig. 2 depicts the hand-designed levels for three games including Zelda, Angels and Demons and Survive Zombies.

Fig. 2.

Examples of hand-designed levels for three games (Zelda, Angels and Demons and Survive Zombies). Note that the background is just another sprite, that our generator does not add to all tiles. However, the generator has access to all the properties of game description object.

Fig. 3.

An example of α levels generated for three games (Zelda, Survive Zombies and Angels and Demons).

4. Experimentation and evaluation

We perform an experiment using the GVG-LG framework to evaluate the effectiveness of our proposed level generation technique.

4.1. Experimental setup and game selection

For our experimentation, we use the two fitness functions, α and β, for three different games (Zelda, Survive Zombies and Angels and Demons). These mentioned games are part of GVG-AI track and their selection is random. However, our generator works reasonably well for other games as well. Following is a brief description of the games used in the experimentation.

Zelda: In Zelda, the avatar must find a key to open a door and to exit. The player is armed with a sword to kill enemies existing in the maze. The player wins if it exits the maze, and loses if an enemy hits it.

Survive Zombies: The avatar must stay alive while being attacked by sudden zombies. It may collect rewards, in order to avoid being killed by zombies. The player wins if the timer runs out, and loses if hit by a zombie.

Angels and Demons: The player controls an avatar that must avoid bolts shot by demons at the top of the level hitting citizens at the bottom. There are also angels whose bolts bless citizens, giving a bunch of points. These bolts can be stopped with clouds that the avatar can move around, or by the avatar itself. The game ends, if a citizen is hit by a demon’s bolt.

The Fig. 3 and Fig. 4 explain the example levels generated for three games. In the figures, we can see that the α levels of all three games steadily increase the multiple elements and subdue the isolated elements while the β levels do the exact contrary.

Fig. 4.

An example of β levels generated for three games (Zelda, Survive Zombies and Angels and Demons).

4.2. Evaluation

It is noteworthy to mention here that the evaluation of general games is a challenging and complex task and literature is still scarce in this regard. The main obstacle is the generality of the generators, which makes it tough to evaluate the content. The techniques that are frequently used for evaluation are user based studies (Khalifa et al., 2016) and agent-based testing/relative performance profiles (Nielsen et al., 2015). We evaluate the results using relative performance profiles. In this approach quality of games is classified according to the performance of different game-playing controllers. Eight different controllers are executed on three levels of three different games for each fitness function. The controllers explained below are listed from naive to advanced. Note that the ranking of controllers is taken from the GVG-AI competition results. Following is a brief description of the controllers (Perez-Liebana et al., 2018):

doNothingController: Literally does nothing.

sampleRandomController: It just returns a random action to be executed in the next game cycle.

sampleOneStepController: The Sample One Step Look-Ahead controller implements a simple controller that evaluates the states reached within one move from the current state. The controller tries all available actions in the current state, and evaluates the states found after applying each one of these actions.

sampleRSController: The sample RS controller implements a Random Search method to decide the next move to make. At every game step, a (new) small population of individuals is created and evaluated, including as many individuals during the 40 ms given as possible. Each individual represents a sequence of actions, and its fitness is calculated with a heuristic that evaluates the state reached after applying all these actions

sampleFlatMCTSController: Implements a Monte Carlo Tree Search controller, but in an open loop fashion.

sampleMCTSController: Implements a Monte Carlo Tree Search controller using vanilla MCTS search.

sampleRHEAController: The sample RHEA controller implements an online rolling horizon evolutionary algorithm to decide the next move to make.

sampleOLETSController: Open Loop Expectimax Tree Search (OLETS) uses an algorithm inspired by Hierarchical Open-Loop Optimistic Planning. OLETS does not store the states in memory, but uses the sampled sequences to build a tree.

In our experiment, we expected that our α-generated levels would be of a significantly better quality than the β levels. Acknowledging this, we also hypothesize that intelligent algorithms perform better on well-designed games in contrast to poorly designed games. Table 1 shows that the performance of intelligent algorithms (sampleFlatMCTSController, sampleMCTSController, sampleRHEAController, sampleOLETSController) is significantly better at α levels as compared to β levels. However, note that in the case of sampleRSController, the results are better for β levels. This is probably the result of a random search method that sampleRSController performs upon initialization.

Table 1
Performance of controllers for α and β levels

Controllers Performance

Controllers Mean score α Mean score β Win rate α Win rate β

sampleRandomController 3 61.3 0.0 0.0

doNothingController 32.3 0.66 0.34 0.0

sampleOneStepController 3.0 6.7 0.34 0.0

sampleFlatMCTSController 2502 5.0 0.66 0.34

sampleMCTSController 474.2 4.0 0.34 0.34

sampleRSController 5.4 1113 0.34 0.64

sampleRHEAController 691 163 1.0 0.64

sampleOLETSController 2216 292 1.0 0.64

Controllers Performance
sampleRandomController	3	61.3	0.0	0.0
doNothingController	32.3	0.66	0.34	0.0
sampleOneStepController	3.0	6.7	0.34	0.0
sampleFlatMCTSController	2502	5.0	0.66	0.34
sampleMCTSController	474.2	4.0	0.34	0.34
sampleRSController	5.4	1113	0.34	0.64
sampleRHEAController	691	163	1.0	0.64
sampleOLETSController	2216	292	1.0	0.64

Each controller is applied to multiple generated levels for all the three games. The overall results are averaged based on the levels played by each controller. The results given in Table 1 show the importance of patterns that are used in combination. Table 1 also presents normalized scores and win rates for eight different controllers. The average score rate and win rate show that the proposed generator generates better game-levels for the original α-fitness function and hence validates our hypothesis.

In addition to the aforementioned evaluation, the generator was also submitted to the 2018 GVG-LG competition. The competition took place at The Genetic and Evolutionary Computation Conference. For the competition, three levels were generated for four different games per generator (added to the mix Easablade (winner from the first competition) and random generator). Easablade and random were used as the default generators for testing and were not included in the final ranking. Subsequently, a user based study was performed where the players were asked to chose a level of their liking (or none or both are equally good). Our pattern-based level generator was ranked third from a total of six entries.

Fig. 5.

Competition results 2018.

Other entries included: Architect, Jripperda, luukgvgai, tcru and FrankfurtStudents. Architect generator used sampleGeneticGenerator and used a variant of the Constructive Generator as input for the initial set of chromosomes. Jripperda, luukgvgai and tcru generators modify the cross-over and selection procedure using sampleGeneticGenerator. FrankfurtStudents generator mimicked the random generator, with additional settings for specific sprites. However, the complete details of each generator submitted to the competition were not mentioned in detail and to the best of our knowledge, there are no published studies related to these generators. Figure 5 depicts the competition results. As we can see from the figure that our pattern-based generator (ADEELZAFAR) is placed at the third spot.

5. Conclusion

The primary goal of this research is to use design patterns as objectives for the GVG-LG track. Existing literature on the use of design patterns in video games is relatively scarce. This paper highlights the importance of design patterns and how design patterns can play a significant role in the general video games level generation. In our previous effort, we discuss distinct design patterns for this purpose. In this work, we propose a search-based generator, which takes game design patterns as input and generates levels for general video games. The generator selects patterns from the available array and creates levels for a game using crossover and mutation operator. Our generator generates α levels using the original fitness function and β levels through the inversal of the pattern-based fitness function. We evaluate our generator using its relative performance with several well-known controllers. Our evaluation is based on the hypothesis that the performance of intelligent playing algorithms is better on well-designed games as compared to poorly designed games. The average score value and win rate of controllers validates our hypothesis. In conclusion, design patterns can effectively be used as objectives for general video game level generation.

Footnotes

Acknowledgements

We acknowledge Riphah International University Islamabad for support of this research.

References

Alexander, C., Ishikawa, S., Silverstein, M., Jacobson, M., Fiksdahl-King, I. & Angel, S. (1977). A Pattern Language: Towns, Buildings, Construction (Center for Environmental Structure). Oxford University Press.

Ashlock, D., Lee, C. & McGuinness, C. (2011). Search-based procedural generation of maze-like levels. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 260–273. doi:10.1109/TCIAIG.2011.2138707.

Dahlskog, S. & Togelius, J. (2012). Patterns and procedural content generation: Revisiting Mario in world 1 level 1. In Proceedings of the First Workshop on Design Patterns in Games (pp. 1–8). ACM.

Dahlskog, S. & Togelius, J. (2013). Patterns as objectives for level generation. In Proceedings of the Second Workshop on Design Patterns in Games. ACM.

Dahlskog, S. & Togelius, J. (2014). A multi-level level generator. In 2014 IEEE Conference on Computational Intelligence and Games (pp. 1–8). IEEE.

Ebert, D.S. & Musgrave, F.K. (2003). Texturing & Modeling: A Procedural Approach. Morgan Kaufmann.

Gamma, E. (1995). Design Patterns: Elements of Reusable Object-Oriented Software. Pearson Education India.

Hullett, K. & Whitehead, J. (2010). Design patterns in FPS levels. In Proceedings of the Fifth International Conference on the Foundations of Digital Games (pp. 78–85). ACM.

Jordan, A., Scheftelowitsch, D., Lahni, J., Hartwecker, J., Kuchem, M., Walter-Huber, M. & Preuss, M. (2012). Beatthebeat music-based procedural content generation in a mobile game. In 2012 IEEE Conference on Computational Intelligence and Games (CIG) (pp. 320–327). IEEE.

10.

Khalifa, A., Perez-Liebana, D., Lucas, S.M. & Togelius, J. (2016). General video game level generation. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (pp. 253–259). ACM. doi:10.1145/2908812.2908920.

11.

Kimbrough, S.O., Koehler, G.J., Lu, M. & Wood, D.H. (2005). Introducing a feasible-infeasible two-population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch. March 14, 2005, (Working Paper).

12.

Nielsen, T.S., Barros, G.A., Togelius, J. & Nelson, M.J. (2015). General video game evaluation using relative algorithm performance profiles. In European Conference on the Applications of Evolutionary Computation (pp. 369–380). Cham: Springer.

13.

Perez-Liebana, D., Liu, J., Khalifa, A., Gaina, R.D., Togelius, J. & Lucas, S.M. (2018). General video game AI: A multi-track framework for evaluating agents, games and content generation algorithms. arXiv preprint. arXiv:1802.10363.

14.

Perez-Liebana, D., Samothrakis, S., Togelius, J., Schaul, T., Lucas, S.M., Couëtoux, A., Lee, J., Lim, C.-U. & Thompson, T. (2016). The 2014 general video game playing competition. IEEE Transactions on Computational Intelligence and AI in Games, 8(3), 229–243. doi:10.1109/TCIAIG.2015.2402393.

15.

Preuss, M., Liapis, A. & Togelius, J. (2014). Searching for good and diverse game levels. In 2014 IEEE Conference on Computational Intelligence and Games (pp. 1–8). IEEE.

16.

Schaul, T. (2013). A video game description language for model-based or interactive learning. In 2013 IEEE Conference on Computational Inteligence in Games (CIG) (pp. 1–8). IEEE.

17.

Shaker, N., Liapis, A., Togelius, J., Lopes, R. & Bidarra, R. (2016). Constructive generation methods for dungeons and levels. In Procedural Content Generation in Games (pp. 31–55). Cham: Springer. doi:10.1007/978-3-319-42716-4_3.

18.

Shaker, N., Nicolau, M., Yannakakis, G.N., Togelius, J. & O’neill, M. (2012). Evolving levels for super mario bros using grammatical evolution. In 2012 IEEE Conference on Computational Intelligence and Games (CIG) (pp. 304–311). IEEE.

19.

Sharif, M., Zafar, A. & Muhammad, U. (2017). Design patterns and general video game level generation. International Journal of Advanced Computer Science and Applications, 8(9). doi:10.14569/IJACSA.2017.080952.

20.

Sorenson, N. & Pasquier, P. (2010). Towards a generic framework for automated video game level creation. In European Conference on the Applications of Evolutionary Computation (pp. 131–140). Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-12239-2_14.

21.

Summerville, A., Snodgrass, S., Guzdial, M., Holmgard, C., Hoover, A.K., Isaksen, A., Nealen, A. & Togelius, J. (2018). Procedural content generation via machine learning (pcgml). IEEE Transactions on Games, 10(3), 257–270. doi:10.1109/TG.2018.2846639.

22.

Togelius, J., Yannakakis, G.N., Stanley, K.O. & Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 172–186. doi:10.1109/TCIAIG.2011.2148116.

23.

Van Der Linden, R., Lopes, R. & Bidarra, R. (2014). Procedural generation of dungeons. IEEE Transactions on Computational Intelligence and AI in Games, 6(1), 78–89. doi:10.1109/TCIAIG.2013.2290371.

24.

Whitley, D. (1994). A genetic algorithm tutorial. Statistics and computing, 4(2), 65–85. doi:10.1007/BF00175354.

Controllers Performance

Controllers	Mean score α	Mean score β	Win rate α	Win rate β
sampleRandomController	3	61.3	0.0	0.0
doNothingController	32.3	0.66	0.34	0.0
sampleOneStepController	3.0	6.7	0.34	0.0
sampleFlatMCTSController	2502	5.0	0.66	0.34
sampleMCTSController	474.2	4.0	0.34	0.34
sampleRSController	5.4	1113	0.34	0.64
sampleRHEAController	691	163	1.0	0.64
sampleOLETSController	2216	292	1.0	0.64