Entity Embedding as Game Representation Nazanin Yousefzadeh Khameneh and Matthew Guzdial Department of Computing Science, Alberta Machine Intelligence Institute (Amii) University of Alberta, Canada {nyousefz, guzdial}@ualberta.ca Abstract Riedl presented a method in which a new graph-like game Procedural content generation via machine learning representation is learned in order to generate new games by (PCGML) has shown success at producing new video game recombining existing ones (Guzdial and Riedl 2018). How- content with machine learning. However, the majority of the ever, the graph-like representation is not well-suited to sta- work has focused on the production of static game content, tistical machine learning methods. Osborn et al. proposed including game levels and visual elements. There has been a system to derive a complete model of game structure much less work on dynamic game content, such as game and rules as a new representation for games (Osborn, Sum- mechanics. One reason for this is the lack of a consistent merville, and Mateas 2017). This approach has only been representation for dynamic game content, which is key for proposed, not yet implemented. Recently, there have been a number of statistical machine learning approaches. We some projects on game generation with PCGML using the present an autoencoder for deriving what we call “entity embeddings”, a consistent way to represent different dynamic Video Game Description Language (VGDL) (Machado et al. entities across multiple games in the same representation. 2019), however we note that all of the dynamic knowledge In this paper we introduce the learned representation, along had to be hand-authored, rather than learned from existing with some evidence towards its quality and future utility. games. Ideally, we would like to have a representation that would Introduction allow us to represent machine-learned knowledge of dy- namic game elements that is suitable to statistical machine Generating game content using Machine Learning (ML) learning tasks. In this paper we aim to learn such a represen- models trained on existing data is referred to as Procedu- tation of dynamic game entities as low dimensional vectors ral Content Generation via Machine Learning (PCGML). in which mechanical information is preserved. We call this PCGML has shown success in both game development and approach entity embedding. This entity embedding attempts technical games research (Karth and Smith 2017; Sum- to obtain the functional (mechanics) similarities between en- merville et al. 2018). Most of the prior work has focused on tities not the aesthetic (appearance) ones. level generation and not mechanic generation or entire game In this paper, we use a Variational AutoEncoder (VAE) generation. One reason is that there are few available shared to re-represent Atari Games with an entity embedding in a representation frameworks across games. Games vary sig- lower dimension representation. We evaluate our approach nificantly from one another, across multiple game systems, with some similarity measures in comparison to a K-nearest game genres, and particular instances of a genre. We also neighbors-inspired baseline. In addition, we demonstrate cannot use the mechanics of just one individual game, as some qualitative examples of the potential applications of modern machine learning approaches rely on training data this representation. sizes that far surpass what a single game could provide. Given all of this, it is difficult to represent functional pieces of different games in the same representation. A suitable Related Work shared data representation for different games would make In this section we focus on related PCGML approaches, and it possible to do different PCGML-related tasks more eas- related deep neural network (DNN) based approaches for ily like novel game generation, novel game mechanic gen- modeling the dynamic elements of games. eration, transferring knowledge between games, automated In the introduction we identified that the majority of reasoning over games, and so on. PCGML approaches have been applied to level generation There is not a large body of prior work in data represen- or the generation of other static content. However, there are tation for dynamic game content in PCGML. Guzdial and some prior examples that touched on the generation of dy- Copyright c 2020 for this paper by its authors. Use permitted un- namic game entities. Guzdial et al. (Guzdial, Li, and Riedl der Creative Commons License Attribution 4.0 International (CC 2017) introduced an approach to learning the rules of a BY 4.0). game from gameplay video and then applied these learned rules to rule generation (Guzdial and Riedl 2018). Similarly, information for each entity based on the learned ruleset by Summerville et al. employed a causal learning framework vectorizing the learned rule information for each entity. Fi- to learn certain semantic properties of various game enti- nally, we train our VAE with this vectorized representation ties (Summerville et al. 2017). They later proposed apply- to obtain the latent space. ing this as part of a pipeline to generate new games (Os- Our trained VAE gives us our entity embedding as points born, Summerville, and Mateas 2017). Recently, Bentley in a learned 25-dimensional latent space. We In this repre- and Osborn (Bentley and Osborn 2019) presented a corpus sentation we can represent changes over entities as vectors of such semantic game properties, which could be employed (one entity at one point becoming another entity at another in PCGML. However, this dynamic information would have point), and whole games as graphs or point clouds (where to be hand-authored and then applied to a PCGML prob- each point is an entity in the game). We anticipate that these lem as in the work of Machado et al. (Machado et al. 2019). compact representations will make PCGML work that in- Comparatively, we seek to re-represent learned dynamic volves mechanical, dynamic, or semantic information far game information in a smaller, latent representation which easier. can then be used for PCGML tasks. In this work we rely on a Variational AutoEncoder (VAE). Ruleset Learning VAE’s have been applied to many other PCGML level gen- Since our goal is to have our representation reflect the se- eration tasks. They have been used to generate levels for Su- mantics (mechanics) of the entities, we decided to obtain per Mario Bros. (Jain et al. 2016; Guzdial et al. 2018) and game rules to collect this information. Thus we make use Lode Runner (Thakkar et al. 2019). Sarkar et al. employed a of the game engine learning algorithm from Guzdial et al. VAE to learn two different game level distributions and then (Guzdial, Li, and Riedl 2017) to learn rulesets for each generate content from in-between these learned distributions game. The algorithm tries to predict the next frame with a (Sarkar, Yang, and Cooper 2020). We also rely on learning current engine (sequence of rules), if the predicted frame is content from multiple games, however our content is a rep- sufficiently similar to the original one the engine remains the resentation of dynamic game entities instead of structural same, otherwise it optimizes the current engine via search. information. Each rule consists of conditional facts and effect facts. The Outside of PCGML, there exists work in learning to facts are percept-like representations that denote individual model dynamic elements of games to help automated game atomic units of knowledge about the game (Ugur, Sahin, playing tasks. Ha and Schmidhuber presented their approach and Öztop 2009). For each rule to fire all the conditional “World Models” that used a VAE as part of its pipeline to facts must be true. Upon firing, the rule replaces one fact learn a forward model, a way of predicting what will happen (the preffect) with another fact (the posteffect). This allows next according to the mechanics of a world (Ha and Schmid- the rules to model changes in a game, like movement, enti- huber 2018). These “World Models” were helpful in improv- ties appearing and disappearing, and changes in entity states. ing agent performance on playing the modelled games, but that represents the mechanics of the game and from which it the learned representation of dynamic elements was far too is possible to simulate the whole game (Guzdial and Riedl large to use as input in a PCGML process. Similarly, Go- 2018). Below is the list of the types of facts we use in this Explore uses a VAE-like model for determining whether it paper: has been to a particular state (Ecoffet et al. 2019). However, • Animation contains SizeX SizeY of the entity. the goal is simply to use the latent embedding as a distance function comparing game states, not as a representation for • VelocityX indicates the velocity of the entity horizontally. PCGML. Most recently, Kim et al. (Kim et al. 2020) pre- • VelocityY indicates the velocity of the entity vertically. sented an approach to use an augmented Generative Adver- • PositionX this fact is the value of an entity in the x dimen- sarial Neural Network (GAN) to model an entire game by sion of a frame. separately modeling dynamic and static entities. We simi- larly seek to model dynamic entities with a DNN, but we • PositionY this fact is the value of an entity in the y dimen- focus on modeling the entities of multiple games instead of sion of a frame. having a model trained to recreate one specific game. Fur- For example, in the following rule (Rule X), entity ther, just as with the World Models approach, the represen- A’s speed in X direction will change from 0 to 5 as its tation is too large to apply a PCGML approach on it. conditional facts match the current game state RULE X: System Overview VelocityXFact: [A, 0]→VelocityXFact: [A, 5] In this paper, we develop a method for embedding entities VelocityXFact: [A, 0] from multiple games in a 25-dimension latent vector. We fo- VelocityYFact: [A, 0] cus on the domain of Atari games to test this approach, as AnimationFact: [A, (8, 4, 3)] the games are relatively simple while still being more com- PositionXFact: [A, 79] plex than hand-authored games in the VGDL, which makes PositionYFact: [A, 17] hand-authoring knowledge from them non-viable. We iden- tify this dynamic information automatically from these Atari VelocityXFact: [B, 0] games by running the rule learning algorithm introduced by VelocityYFact: [B, 0] Guzdial et al. (Guzdial, Li, and Riedl 2017). We then collect AnimationFact: [B, (5, 6, 3)] Figure 1: Architecture of our VAE PositionXFact: [B, 93] ityX and VelocityY which can be negative. We convert each PositionYFact: [B, 42] entity to a vector of shape 1x1600 (8x200). Due to the fact etc. that all the absolute values of the features are always less For more information on the Engine learning process please than 100, we chose 200 as one-hot encoding size (to repre- see (Guzdial, Li, and Riedl 2017). sent positive and negative values). We found that the second representation results far exceeded the first for our evalua- Dataset tions and so we only report those. In this paper, we made use of two Atari games, Centipede Training and Space-invaders, as represented in the Arcade Learning Environment (ALE) (Bellemare et al. 2013). We chose these Autoencoders are efficient tools for dimensionality reduc- two Atari games since both games have similar mechan- tion. These tools approximate a latent structure of a fea- ics in which the player is a fighter who shoots at enemies. ture set. We need to reduce the dimensionality of the enti- We ran the Game Engine Algorithm on roughly 100 frames ties in order to learn an entity representation with less vari- of each game to obtain the game rules. Each rule consists ance. We decided to make use of a Variational AutoEncoder of some conditional facts and an effect. These conditional (VAE), as it would allow us to learn a more consistent latent facts describe mechanical features of entities like size, ve- space and sample novel entities from this learned distribu- locity, position and so on. The effect is made up of a pre- tion. We applied VAE to our dataset to learn the parameters effect and post-effect, also describing mechanical features. of a probability distribution to represent our entities. Thus it In frames where they are true (i.e. the mechanical features makes it possible to sample from this distribution and gener- exactly match) that rule fires meaning that the post-effect re- ate new entities. Since it is a generative model, we can apply places the pre-effect (e.g. the velocity of an entity changes). this feature to PCGML tasks like generating entities simi- After obtaining the game rules we ran a parser through lar to the input, blending the entities in the latent space and each rule to save the mechanical information of each game so on. We tried various VAE architectures for training. We entity as an integer in an individual vector of shape (1x8). obtained the final model empirically, which we visualize in For example, entity ’A’ in game ’B’ is represented as a vec- Figure 1. As the Figure demonstrates, our architecture has tor which contains, EntityID: A, SizeX, SizeY, VelocityX, Ve- one fully connected hidden layer with Relu activation in the locityY, PositionX, PositionY and GameID: B. We note that encoder, which then feeds into a 25-dimensional embedding different in-game entities would generate multiple instances layer with Relu activation. The decoder section architecture of this representation. Further, velocity and position values is an inverse of the encoder section, starting with a Sigmoid had to be integers as they were measured over the space of activation fully connected layer. We implemented this model pixels. Our goal was to represent each mechanical state that with the Adam optimizer with a learning rate of 0.001 and each game entity (EntityID) could legally be in according to binary cross-entropy as our loss function. We implemented the game rules. this model in Keras. During development we used two different representa- tions of our dataset. First we used a one-hot encoding for Generation GameID and EntityID while all other features remained in- The decoder generates 1x1600 vectors. We then use tegers. However we have less than 100 EntityIDs and only 2 our one-hot representation for the decoder’s output, by GameIDs, we choose 100 and 10 as one-hot encoding sizes querying the generated outputs and finding the largest for EntityIDs and GameIDs, respectively. This is because of value in each ([[0-200][201-400][401-600][601-800][801- potential future studies with more entities or games. In the 1000][1001-1200][1201-1400][1401-1600]]) segments and second representation we apply one-hot encoding to all fea- replacing it with 1 and others with 0. Thus, we can generate tures. All of the features are greater than zero except Veloc- entirely novel outputs not previously seen during training. Figure 2: Visualization of 20% of our test entities comparisons to our VAE output and our baselines. Evaluation Metric Jaccard Distance Euclidean Distance The entire purpose of this new entity embedding representa- VAE 0.0937 5.6364 tion is to accurately represent the semantic information in a PCA 0.2291 18.0278 more compact representation. Therefore, accuracy is key. In SE Euclidean 0.2013 2.8881 order to evaluate the accuracy of our VAE we ran an evalu- SE Jaccard 0.1388 6.0629 ation to compare the performance of our VAE on a held out testset of 10% of our available data. As a baseline, we were Table 1: Comparison of our two distance functions over our inspired by K-Nearest Neighbors and so selected the most test data, comparing the output of our VAE to our baselines similar entity from the training dataset to each entity in the of the most similar training entity (SE) and PCA according testset. To determine the most similar entity we applied two to the two different distance functions. different similarity measures as below: • Jaccard Similarity that is the measure of similarity for the two sets of data based on their overlap. and test sets have substantial overlap. We also compare the • Euclidean distance that computes the square root of the VAE with Principal Component Analysis (PCA) which is an sum of squared differences between elements of the two unsupervised, non-parametric statistical technique used for vectors. dimensionality reduction in machine learning. If the VAE is able to perform similarly or better than the closest training We found the most similar training entity to the test entity instance, on a test instance it has never seen before, this will with these two methods. We then compare the VAE recon- indicate that the VAE has learned an accurate entity repre- struction of the test entity and the selected training entity sentation. with the original entity. To do this we consider (A) the num- ber of equal values and (B) the difference of unequal val- ues between original and predicted entity vectors. We em- Results ploy the Euclidean and Jaccard distance functions again as The mean values across our test set for our distance scores comparison metrics. Lower values are better for both met- are in Table 1. In the table we refer to the most similar en- rics as it indicates fewer differences. This is notably quite tity in the training set to the test set as “SE”. Thus “SE a strong baseline, given that many entities in the training Euclidean” is the most similar entity in the training set to Figure 3: Eight random variations made to entity (center) in the latent space. Figure 5: Comparing the average entity between two existing entities in terms of the vector representation and in the latent space. Figure 4: t-SNE Visualization of our latent space. to note that the VAE generates the exact same entity roughly 50% of the time for the testset. a particular test set using the Euclidean distance function. Qualitative Examples As is shown in the table, our VAE outperforms the other In this section we display the distribution of entities in the methods when we use the Jaccard distance. However, the latent space using the t-Distributed Stochastic Neighbor Em- SE Euclidean performs better when we use Euclidean dis- bedding (t-SNE) technique. This technique is for dimension- tance, though notably we outperform the SE Jaccard base- ality reduction and is well suited for the visualization of line even with the Euclidean distance function. This indi- high-dimensional datasets (Maaten and Hinton 2008). In ad- cates that the VAE outputs and the original entities share dition, we explore the latent space by presenting some qual- more equal feature values but the individual feature values itative examples. at times have larger variation compared to the closest entity We provide a t-SNE visualization in Figure 4. The repre- in the training data. Furthermore, our proposed VAE out- sentation depicts the distribution of entities in the projected performs PCA which is another dimensionality reduction 2D space. Note that clusters correspond to the two games method. We demonstrate distance score for individual ran- in our dataset, verifying the power of the model in discrim- domly selected entities from our testset in Figure 2. As is inating the entities based on the GameID feature. We also shown, the majority of the values of the VAE are lower com- note that this indicates that we can represent games as clus- pared with the baselines except a few outliers. It is important ters of points in this space. We hope to explore the possible Figure 6: Two randomly selected frames of the games Centipede and Space invaders. Entities in blue circles are the Alien and Mushroom from Space invaders and Centipede respectively, both destroyable entities. Entities with red circles are player entities. The tables indicates the Euclidean distance of these entities in the latent space. research direction of this feature in future. tion. We plan to run another study to analyze if we can use We also examine some qualitative examples to explore generated entities to generate new types of rules or levels entities interpolation in the latent space. To do this, we ran- of an existing game, or entirely new games. domly chose a pair of entities. We then calculate the average of both the vector and latent representations of the pair. As • Transfer Learning: As we discussed in the Ruleset sec- is shown in Figure 5, the latent average is more like taking tion, the embedding is based on mechanical features of features from each entity while the original average is just entities in each rule of a game. Each rule references a set the mean of two entity vectors (all numbers rounded down of entities (group of conditional facts) together in a frame for the average). This indicates that our latent space is not which causes an effect. We might expect similar mechani- replicating the geometric information presented in the vec- cal effects if we have entities from another different game tor representation. with a similar latent representation. We anticipate a need Our second qualitative example is to analyze the sur- for another study to investigate this. roundings of an entity inside the latent space. We first add various normal random vectors in the range (-0.2 to 0.2) to a • Extending the Dataset: We trained this model on around randomly selected entity’s embedding. We choose this range 100 frames of two Atari games with similar mechanics. since the entity does not change perceptively with lower Extending our dataset by adding extracted rules of other ranges. Figure3 displays the randomly selected original en- similar and dissimilar games is another potential future tity and 8 random neighbor entities around it. The random direction. variations seem quite consistent in terms of sizes and IDs. This indicates that similarly shaped entities with similar IDs Conclusions are closer together inside the latent space. This also applies to velocity and position features. In this paper we presented an approach to derive an en- Our third qualitative example indicates that entities with tity embedding, a latent representation of in-game entities similar mechanical features from different games are more based on their mechanical information, via a Variational Au- similar in the latent space compared to entities with different toEncoder (VAE). We discussed how we trained this VAE, mechanical features from the same game. This indicates that and evaluated the entity embedding in terms of its accu- our latent space places mechanically similar entities closer racy at representing unseen test entities. We found that the to one another in its learned latent space. VAE outperformed our K-Nearest Neighbor inspired base- lines in most cases, indicating a general learned embedding. Future Work We hope that this representation will lead to new applica- We trained a VAE on mechanical features of entities in order tions of PCGML involving game mechanics. to derive an entity embedding. We argue that this entity em- bedding can be a shared representation that enables various PCGML-related tasks. We list potential directions for future Acknowledgements work below. We acknowledge the support of the Natural Sciences and • Entity Blending: We can generate new entities based on Engineering Research Council of Canada (NSERC), and the existing ones as is shown in the Qualitative Examples sec- Alberta Machine Intelligence Institute (Amii). References Thakkar, S.; Cao, C.; Wang, L.; Choi, T. J.; and Togelius, Bellemare, M. G.; Naddaf, Y.; Veness, J.; and Bowling, M. J. 2019. Autoencoder and evolutionary algorithm for level 2013. The arcade learning environment: An evaluation plat- generation in lode runner. In 2019 IEEE Conference on form for general agents. Journal of Artificial Intelligence Games (CoG), 1–4. IEEE. Research 47:253–279. Ugur, E.; Sahin, E.; and Öztop, E. 2009. Affordance learning Bentley, G. R., and Osborn, J. C. 2019. The videogame af- from range data for multi-step planning. In EpiRob. fordances corpus. In 2019 Experimental AI in Games Work- shop. Ecoffet, A.; Huizinga, J.; Lehman, J.; Stanley, K. O.; and Clune, J. 2019. Go-explore: a new approach for hard- exploration problems. arXiv preprint arXiv:1901.10995. Guzdial, M., and Riedl, M. 2018. Automated game design via conceptual expansion. In Fourteenth Artificial Intelli- gence and Interactive Digital Entertainment Conference. Guzdial, M.; Reno, J.; Chen, J.; Smith, G.; and Riedl, M. 2018. Explainable pcgml via game design patterns. arXiv preprint arXiv:1809.09419. Guzdial, M.; Li, B.; and Riedl, M. O. 2017. Game engine learning from video. In IJCAI, 3707–3713. Ha, D., and Schmidhuber, J. 2018. World models. arXiv preprint arXiv:1803.10122. Jain, R.; Isaksen, A.; Holmgård, C.; and Togelius, J. 2016. Autoencoders for level generation, repair, and recognition. In Proceedings of the ICCC Workshop on Computational Creativity and Games. Karth, I., and Smith, A. M. 2017. Wavefunctioncollapse is constraint solving in the wild. In Proceedings of the 12th International Conference on the Foundations of Dig- ital Games, 1–10. Kim, S. W.; Zhou, Y.; Philion, J.; Torralba, A.; and Fidler, S. 2020. Learning to simulate dynamic environments with gamegan. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1231–1240. Maaten, L. v. d., and Hinton, G. 2008. Visualizing data using t-sne. Journal of machine learning research 9(Nov):2579– 2605. Machado, T.; Gopstein, D.; Nealen, A.; and Togelius, J. 2019. Pitako-recommending game design elements in ci- cero. In 2019 IEEE Conference on Games (CoG), 1–8. IEEE. Osborn, J. C.; Summerville, A.; and Mateas, M. 2017. Au- tomated game design learning. In 2017 IEEE Conference on Computational Intelligence and Games (CIG), 240–247. IEEE. Sarkar, A.; Yang, Z.; and Cooper, S. 2020. Control- lable level blending between games using variational au- toencoders. arXiv preprint arXiv:2002.11869. Summerville, A.; Behrooz, M.; Mateas, M.; and Jhala, A. 2017. What does that?-block do? learning latent causal affordances from mario play traces. In Workshops at the Thirty-First AAAI Conference on Artificial Intelligence. Summerville, A.; Snodgrass, S.; Guzdial, M.; Holmgård, C.; Hoover, A. K.; Isaksen, A.; Nealen, A.; and Togelius, J. 2018. Procedural content generation via machine learning (pcgml). IEEE Transactions on Games 10(3):257–270.