Extracting deck archetypes using topic model and its application to game design
Introduction
Hello everyone! I recently worked on a project in which I applied machine learning (ML) methods to user data from a mobile game app to improve user experience. In the gaming industry, the application of AI/ML methods is trending in recent years and a number of companies and researchers around the world are working in this field (See GDC, IEEE CoG for such applications).
In the current project, I used user-constructed deck data from a mobile game called ‘Gyakuten Othellonia’ (You can check the overview of the game with this tutorial video). The game is based on the rule of Reversi (aka Othello) and two players battle against each other using their decks composed of characters having unique status (HP, ATK value etc.) and skills (or status effect such as buff/debuff etc.). Because of the skills associated with each card, players need to consider the effectiveness of the combination of cards to construct a deck rather than merely choosing strong cards in their possession to win a battle. Therefore, decks are constructed according to concepts (often called archetypes) as is often the case in other trading card games.
In this game, we have released a couple of in-game AI/ML applications such as AI-bot using deep learning and deck recommendation using association analysis (GDC presentation). We are also working on ML applications to support game planners (i.e. people who are responsible for adding new cards to the game and balancing the relationship between archetypes), and this is what this article is about.
For Japanese readers, please check this article written in Japanese as well!
Background and motivation
In PvP (player-vs-player) games, especially for the card games, understanding and maintaining the balance of the game environment is critical for the success of the game. Here, understanding the ‘game environment’ refers to obtaining information of archetypes that are present in the user-constructed decks, usage and overall winning probability of each archetype, and winning probability of each archetype against other archetypes. When the archetypes’ strength is not well-balanced, the user experience will be impaired.
For instance in Figure 1, the environment was balanced among the archetype A, B, and C (left). For some reason (e.g. addition of a new strong card that could be used in archetype A), archetype A gets stronger and now has a high winning probability against both archetype B and C. Players using archetype B and C will find the game boring because they lose more often. Also, the increase in the winning probability of archetype A encourages players to use this archetype more frequently. Thus, for those using archetype A, the game is no longer stimulating because they end up facing against similar type of opponents. This impairment of user experience leads to reduction in the number of active users, which is crucial for PvP games to ensure variability in the gaming experience.
Before the big-data era, understanding the game environment was done qualitatively by game planners playing thousands of battles every month using different archetypes. As the game grows and the number of archetypes increases, this approach becomes intractable. Thus, we need a quantitative approach to extract archetypes from the decks used in the battle. A simple method to extract archetypes is to perform rule-based extraction. In this approach, we apply hand-crafted rules to classify decks into archetypes (e.g. if card 1 is in the deck, the deck belongs to archetype A). It performs well for simple games but it was not the case for our game. In our game, each card can be employed in multiple archetypes and writing down exhaustive set of rules was not feasible. Therefore, we turned into ML method to extract archetypes and classify each deck into archetypes automatically.
Data
We used deck data from battles in the game-mode called ‘Class match’. This is the main PvP mode and players are ranked according to the outcome of the battles. Also, we only used data from battles among top-tier players who are proficient in constructing decks. In this game, deck construction is not an easy task especially for beginners because it involves choosing 16 cards from user’s card pool (In total, there are 3,500 cards available) by considering the skills unique to each card. By constraining the data to decks constructed by top-tier players in the ‘serious’ game-mode, we aimed to exclude randomly constructed decks without concepts that will have a negative effect on the performance of ML algorithm to extract deck archetypes. We also queried various statistics associated with each game such as the player who won the battle, the first player to act, the number of turns it took until the game ends.
LDA (Latent Dirichlet Allocation)
To extract deck archetypes, we applied an algorithm called LDA (Latent Dirichlet Allocation), which is probably the most well-known algorithm among various topic models. There are a number of great Medium articles on this topic explaining the math behind it, so we only briefly mention how it works.
The model was developed to classify documents into different topics using words that consist each document. In the model, each topic is represented by a probability distribution over the words existent in the documents (β in Figure 2) and each document is represented by a probability distribution over the topics (θ in Figure 2). By using these two distributions, the model assumes the following generative process for each document. For each word in the document, the model first decides which topic the word is generated from by referencing the probability distribution (θd) associated with the document d. Then, the word is generated according to the probability distribution over words associated with the selected topic (e.g. If a word is determined to be generated from topic 2, the model refers to the corresponding probability distribution β2). Given this generative model, the model assumes Dirichlet distribution as a prior for β and θ. By performing Bayesian inference, the posterior distributions for these distributions are obtained.
Applying LDA to extract deck archetypes
We extract deck archetypes using LDA by considering the following associations (Also, see Figure 3.).
- words = cards
- topics (probability distribution on words)
= archetypes (probability distribution on cards) - documents (probability distribution on topics)
= decks (probability distribution on archetypes)
Therefore, by applying LDA to deck data, we can obtain (i) archetypes as probability distribution over the cards in all the decks, and (ii) classification of each deck as a probability distribution over all the extracted archetypes. Here, an important parameter of the model is the number of archetypes to be extracted and this is where the qualitative domain knowledge is necessary. We started with ‘5’ and increased the number as long as the extracted archetypes are interpretable by game planners.
Pipeline of deck archetype extraction
In this section, I will describe the processes involved in archetype extraction from the deck data used in battles during one-week period (See Figure 4 for the illustration.).
First, we query the battle log and perform preprocessing. The battle log contains all the information regarding battles such as deck information (which cards are contained in the deck of two players), outcome of the battle (which player won the battle), turn information (which player was assigned to act first and the number of turns until the game concluded). Preprocessing steps involve removing illegal data (e.g. battles concluded by either player killing the app) and converting deck information composed of card names to one-hot encoding vector.
Second, we apply rule-based extraction to the preprocessed decks. You may wonder why we are applying rule-based extraction. Although LDA could extract archetypes that can also be extracted by rule-based method, rule-based extraction is better for archetypes that can be extracted by either method because it is deterministic and noise-free. In practice, game planners update Google Spreadsheet specifying the rules and the algorithm reads this spreadsheet to perform the extraction.
Third, we apply LDA algorithm to the remaining decks (i.e. decks that were not extracted in the second step). We then compare each of the extracted archetype to the archetypes extracted in the past. Because the archetypes are represented by a probability distribution over all the cards in the deck, we can utilize any distant metric between probability distributions (e.g. Hellinger distance) to perform this association. For instance in Figure 4, the extracted archetype x is compared to archetype A and B extracted in the previous weeks. The probability distribution associated with archetype x is much closer to the probability distribution associated with archetype B than that of archetype A. Therefore, we rename archetype x to archetype B. When the distance between archetype x and all the archetypes extracted in the previous week is greater than a certain threshold (this is a tunable parameter), we treat archetype x as a new archetype. We iterate this process for all the archetypes extracted in the current week.
Building dashboard using plotly Dash
We now have the information of the archetype that each deck in the battle log belongs to. Therefore, we can compute various statistics associated with each archetype. These include
- usage (the number of unique players, unique decks and battles)
- win rate (overall winning probability, best and worst against stats)
- decks and deck composition (sample decks and frequently included cards)
- turn (average number of turns in a game)
- time series data (usage and win rate).
We visualized these values using plotly Dash, which is a Python web application framework (See Figure 5. Note that we are displaying random numbers.). We prefer this tool because we can build an interactive dashboard that is highly flexible in the layout and the figures that can be displayed (See a collection of beautiful dashboard examples here.) and easy to learn (you only need to know Python). In order to make the dashboard easily accessible to the members of gaming team, we deployed it on Google Cloud Platform (GCP). This enable the dashboard accessed from web browsers on their local machines.
Application to game design
The project has brought a number of benefits listed below to understand the game environment.
- We can obtain quantitative and more objective grasp of archetypes.
- Onboarding process for game planners became easier and faster.
- We can handle a large number of archetypes.
- We can detect new archetypes that are not expected by game planners.
In addition to these, the output has been utilized in the workflow of game planners. First, they examine the dashboard and find problems in the game environment that is impairing user experience. Second, they plan concrete actions to solve the problem by considering the information displayed on the dashboard and combining it with their domain knowledge. Third, the actions are implemented in the game. Finally, the effectiveness of the actions can be monitored on the dashboard by comparing the game environment before and after the actions were taken.
Here, we present one of such examples. First, game planners noticed that archetype A alone is dominating the current game environment (>55% overall win rate and >50% win rate against all the other archetypes; See Figure 6a and Figure 6c.). Second, to maintain the balance, they decided to find archetype B and C such that A is strong against C, C is strong against B and B is strong against A (Figure 6b). After examining the win rate between different archetypes, they found that A has 62% win rate against C, C has 64% win rate against B, B has 50% win rate against A (Figure 6c). Therefore, by increasing the competitiveness of B and C, we could make the triangular relationship more prominent and more users will use decks in archetype B and C as their overall winning rate increase. Third, actions such as adding new cards that are effective in archetype B and C were taken. Finally, we confirmed that the overall winning rate of B and C are increased and the game environment is no longer dominated solely by archetype A (Figure 6d).
Conclusion
In this project, we applied ML algorithm to deck data to extract deck archetypes. Although detecting what archetypes are present in the current environment of the game is crucial, the complexity of modern trading card games makes it impossible to do it with a traditional approach (knowledge of human expert or rule-based extraction). By using LDA algorithm, which is a variant of topic model, we could successfully extract deck archetypes that are consistent with qualitative assessment by an expert. The result was summarized in the dashboard created by plotly Dash and deployed on GCP so that the game environment is now easily accessible even for non-experts. We have applied the information on the dashboard to tackle various challenges the game was facing to improve user experience and the outcomes have been significant.
From PoC to deployment of the dashboard, the project involved not just coding but also (and importantly) coordinating the expectation of the game planners who knew very little about what ML can and cannot do. It is important to constantly communicate with them so that the value of the final product will be maximized. Also, I cannot emphasize enough that consulting with data engineers ahead of time regarding what you would like to achieve system-wise is critical. This enables the value of the final product exerted promptly.
Finally, we will keep developing ML applications for the gamers and game developers for better gaming experience. We hope you enjoyed reading and we will see you in our future articles!
TM&© Othello,Co. and MegaHouse / © 2016 DeNA Co.,Ltd.
