Predicting Cards Using a Fuzzy Multiset Clustering of Decks
- 10.2991/ijcis.d.200805.001How to use a DOI?
- Fuzzy multisets; Clustering; Deck analysis; Hearthstone
Search-based agents have shown to perform well in many game-based applications. In the context of partially-observable scenarios agent's require the state to be fully determinized. Especially in case of collectible cards games, the sheer number of decks constructed by players hinder an agent to reliably estimate the game's current state, and therefore, renders the search ineffective. In this paper, we propose the use of a (fuzzy) multiset representation to describe frequently played decks. Extracted deck prototypes have shown to match human expert labels well and seem to serve as an efficient abstraction of the deck space. We further show that such deck prototypes allow the agent to predict upcoming cards with high accuracy, therefore, allowing more accurate sampling procedures for search-based agents.
- © 2020 The Authors. Published by Atlantis Press B.V.
- Open Access
- This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).
Automated game playing poses many interesting challenges to the development of artificial intelligence (AI) agents. While many studies presented good results on full information games, the agent's performance is often restricted by partial information on the current game state. The online game Hearthstone: Heroes of Warcraft (in short Hearthstone)  is such a partial information game, which is currently very popular among players . Hearthstone is a deck-building card game in which players create their own decks to play against each other. At the time of writing this paper, Hearthstone includes roughly cards of which players choose a deck of cards to face their opponent. While this paper will only discuss rules and characteristics of Hearthstone that influence the deck building, the interested reader is referred to some excellent resources on the web [1,3], which offer comprehensive reviews of the game's mechanics.
During a game, players do not know their opponent's deck nor hand cards, but observe newly played cards every turn. Since the game state is partially unknown, missing information needs to be completed by the agent before it can apply any search-based algorithm to determine its actions. Similar to other games, expert players of Hearthstone are able to predict opponent moves to a certain degree. This ability can be attributed to their knowledge of the current meta-game, which can be understood as the likelihood of decks and strategies an opponent may play. When building a deck, users often combine cards and their effects with a certain strategy in mind. Players of the game often refer to the concept of deck archetypes, when they discuss decks with a common theme and similar card sets. Such a deck archetype may develop due to the popularity of a certain strategy and its accompanied deck. However, many players do not own all the necessary cards of a specific deck they are trying to build, therefore, variants of these deck archetypes can exist.
In the context of research, the annual Hearthstone AI competition compares agents based on their ability to play the game in various game modes . It has motivated many interesting works, which often focus on the agent's ability to optimize its own turn. Nevertheless, winning approaches also attempt to model the opponent's general strategy [5,6].
In regard of the creation of an autonomous agent, estimating the opponent's upcoming actions is crucial in choosing their own actions. However, due to the opponent's cards being hidden, agents are limited in their capability of predicting these moves. Algorithms like Information Set Monte Carlo Tree Search (MCTS) [7,8] try to handle this problem by randomly sampling the opponent's hand cards to create a determinization of the game state. Based on the generated determinization the search process simulates its own and its opponent's actions and chooses the most promising action. Nevertheless, due to the large number of available cards, the accuracy of this sampling strategy is fairly low and can therefore limit the agent's success. To reduce the sampling size, it has been suggested to use a data base of frequently played decks. Agents using this sampling strategy have resulted in agents with very high performance [9,10] when being compared to other game-playing agents. Nevertheless, they require frequent updates of their deck data base in case the decks' popularity changes over time.
Sievers and Helmert  developed an extended version of Information Set MCTS, which does not sample a single determinization, but multiple determinizations of the game state. For each of these determinizations, the algorithm performs a separate run of MCTS. The results of each run are later aggregated to determine the agent's next action. Sievers and Helmert evaluated their approach on the game Doppelkopf, in which player's need to guess their teammates during the first turns of every game. This critical guess can have a high impact on the following actions. Their approach showed to be valuable in estimating the risk of the next action and improved the agent's overall performance. A study by Dockhorn et al.  further extended this approach by using neural networks for guiding the simulation, therefore, improving the quality of simulations during the search process and its result.
In a recent paper, we introduced an autonomous agent for Hearthstone , which implements a similar approach to the one presented in Reference . We observed that the prediction accuracy and the agent's game-playing performance is still limited, which seems to be due to the enormous number of possible game state determinizations. We reduced the game state's sample space by using information of previously played cards to predict likely cards on the opponent's hand . Using card co-occurrences of previously seen cards and the opponent's hand cards we were able to sample game state determinizations with a higher likelihood. We observed an improvement of the agent's game-playing performance in comparison to a uniform sampling. However, agents that were given complete information still outperformed the proposed agent. From this, we infer that further increasing the accuracy of the game state sampling may in turn further improve the agent's performance.
In the pursuit of creating a better agent for Hearthstone, we want to enhance the agent's prediction capabilities by modeling deck archetypes. In Section 2 we review restrictions of the deck-building process and provide a short overview of the theory of (fuzzy) multisets and various clustering approaches. In the subsequent Section 3, these methods will be used to develop a theoretical model of deck archetypes and how to mine them from a database of recent games. Especially the advantages of using fuzzy multisets instead of crisp multisets are highlighted based on some explanatory examples. We further present a case study, which is based on extracting deck archetypes and their centroid representation from actual playing data of the game Hearthstone (Section 4). We compare our result with a hand-labeled data set and show that the developed approach is able to identify deck archetypes of similar quality.
In this extended version of our conference paper  we added a method for predicting upcoming cards based on identified deck archetypes. The proposed sampling approach will be described in Section 5. Finally, we will evaluate the agent's ability to predict upcoming cards in the opponent's deck (Section 6). The paper concludes with a short analysis of the proposed approach and its possible application to the development of game-playing agents.
We begin this section with a short overview of deck archetypes and how they are defined in Hearthstone. A complete description of the game Hearthstone will be beyond the scope of this paper. For this reason, we would like to refer the interested reader to some excellent web sources maintained by developer  and the community . We further provide detailed explanations on (fuzzy) multisets and selected clustering algorithms, which will be used to model and mine deck archetypes in Section 3.
2.1. Deck Building and Deck Archetypes
In Hearthstone a deck is a set of cards, which can be chosen out of the roughly cards currently available in the game. Each card offers certain effects, which can be used to affect the current game state. Some of these effects create useful synergies that players try to exploit during the game, e.g., attack with a minion card, which will get damaged during the fight, and follow up by healing this minion using a spell card. The choice of cards to be put in the deck is restricted by a small set of rules:
players can only include cards they currently own (which are unlocked on their player's account)
a deck belongs to one out of 9 hero classes who are limited to a subset of about 400 cards each
a deck can only include cards that are either neutral or specific to the chosen hero class
depending on its rarity, a card can be included either once or twice
a deck can be made for a specific game mode that adds additional restrictions, e.g., standard or arena.
While players can create a large number of different decks not all of them are equally successful. The most successful decks define the meta and get known as meta-decks. Often these meta-decks will spawn multiple variants in which players replace just a few cards without changing the main theme of the deck.
A deck archetype describes the resulting cluster of decks with common card subsets. In this work, we will distinguish included cards into two groups, namely core and variant cards. While the core of a deck archetype contains cards that are included in all instances of this archetype, the inclusion of variant cards depends on the given instance. Core cards often define the main building blocks of the archetype and its accompanying strategy. In contrast, variant cards are often included to compensate for cards that the player does not own or to reflect the player's personal preferences. The following subsection will introduce (fuzzy) multisets, which will later be used to model deck archetypes.
2.2. (Fuzzy) Multisets/Bags
Multisets (also called bags) are collections of objects in which an object can be represented multiple times. In this paper, we will closely follow the notation introduced by Miyamoto  and Yager . We denote a multiset by
The collection of all possible multisets of a universal set X is denoted by .
For comparing two multisets and inclusion is defined by
Union, intersection, and addition are defined pointwise for all by
A fuzzy extension of multisets was first introduced by Yager (using the term fuzzy bags) . Here, the sample fuzzy multisetdenotes the occurrence of each object and its membership degree.
For simplicity we group objects of the same kind and their membership degrees, such as inin which the memberships and correspond to the objects and , respectively. Therefore, in fuzzy multisets is a finite multiset of the unit interval .
For each object we further define the membership sequence to be the decreasingly-ordered sequence of elements in . We will make use of the standard form introduced by Miyamoto :
Let be the length of the membership sequence of multiset be denoted by
Any operation between two multisets and requires the membership sequences of each object to be of equal length. We define the length of the resulting membership sequence to be
For the sake of simplicity we assume a membership degree of
Similar to crisp multisets we can define inclusion, equality, union, and intersection based on the membership sequences of each element. Let and be two fuzzy multisets.
Similarly, union and intersection are defined pointwise for all by
To clarify the notation we provide the following short example. Consider the two fuzzy multisets and over the set of objects :
The length per object is
For simplicity we extend the membership sequences for both multisets according to the maximal observed length:
Based on the extended membership sequences we can determine union and intersection of both multisets:
2.3. Clustering Algorithms
In this work, we are going to present the results of our deck archetype clustering process. The interested reader is referred to specialized literature on the topics of data mining and (fuzzy) cluster analysis, which provide a more comprehensive review of alternative approaches than this paper could offer [17–21].
2.3.1. Partitional clustering
The clustering algorithm k-means  is the most common representative of partitional clustering algorithms. During initialization, cluster prototypes are randomly generated or selected from the set of available data points. The cluster prototypes are iteratively updated to better represent and partition the points in the data set. For this purpose, each data point is assigned to its closest prototype. In a second step, the prototypes are moved to the center of all assigned points to minimize the sum of squared errors between a prototype and all its assigned data points. Given a clustering , let the sum of squared error be calculated by
2.3.2. Hierarchical agglomerative clustering
Hierarchical agglomerative clustering is a class of bottom-up clustering algorithms, in which each data point is assigned to a unique cluster during initialization. These clusters are iteratively merged according to a linkage criterion. The merge process is repeated until a minimum number of clusters is reached or all data points belong to a common cluster.
In this work we will make use of the following linkage criteria, which both determine the distance of two clusters based on the distances of points contained in differing clusters:
single linkage  reports the minimal distance between two points of different clusters(17)
complete linkage  reports the maximal distance between two points of different clusters(18)
Similar to k-means, the complete linkage favors compact and well-separated clusters. In contrast, the single linkage criterion may exhibit a phenomenoncalled chaining in which existing clusters are merged due to having two points, which are close to each other, even though other points are far apart.
2.3.3. Density-based clustering
The Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm proposed by Ester et al. , forms clusters by searching for dense regions of points. The -neighborhood of a point consists of all points with a maximal distance of :
The region around a point is considered to be dense in case the number of points in its –neighborhood exceeds the threshold . Points that satisfy this condition are called core points. A point is directly density-reachable from point , if and is a core-point. The transitive closure of directly density-reachable points is called density-reachable. Finally, two points are density-connected when a point exists from which both are density-reachable. A cluster is described by the maximal set of points that are density-connected to each other.
3. (FUZZY) MULTISET ANALYSIS OF DECK ARCHETYPES
In the previous section, we discussed various building components for the deck archetype mining algorithm we are proposing in this section. We will first define how a deck archetype can be represented in terms of fuzzy multisets and further describe a mining routine based on the clustering algorithms presented above.
A natural representation of a deck is a multiset of cards.
3.1. Modelling Deck Archetypes
The Hearthstone community defines a deck archetype to be a collection of decks with a common set of cards. In the following, we are going to model a deck archetype to be the representative of a cluster of decks.
Let's consider two crisp decks and over the set of elements of the form
The intersection of these two decks is the multiset:
While the resulting set describes the core of these two decks, the information of possible variants is lost during the generation of the common subset. A similar problem occurs if we generate the union of both decks:
While the union operator preserves information on the inclusion of and we misleadingly represent these variants, i.e., based on its count in variant object is indistinguishable from the core objects and (similar observations can be made for the objects and ). Hence, objects with different inclusion patterns in and are equally represented in the merged multiset. Replacing the union with the addition operation would yield similar problems and also increase the cardinality of the resulting multiset.
For the crisp multiset we define the average multiset of two multisets and to include the average number of occurrences per object in these multisets and denote it by
Hence, the average of clusters and is
While the average operator already clearly distinguishes the inclusion patterns for , and , we can still observe problems with varying numbers of inclusion, e.g., and . However, extending the representation to fuzzy multisets can help to solve this problem.
For this purpose, we transfer the average operator for crisp multisets to fuzzy multisets by calculating the average of every element of an object's grade sequence. Thus, the average operator for two fuzzy multisets and can be denoted by
Representing both decks as fuzzy multisets results in the following centroid:
To ensure a stable clustering process we want to adjust the definition of the (fuzzy) multiset centroid to fulfill the associative property, since the result of merging multiple multisets should be independent of their merging order, specifically we want the following properties to be fulfilled:
Let a cluster be a multiset over the set of multisets over the set of objects . The centroid of cluster , which is itself a multiset over the set of objects , should be independent of the order of inclusion of said multisets, thus fulfilling the associative property of the order of merges. For this purpose, we generalize the average operator of two multisets (Equation 21) to take the number of inclusions per multiset into account:
The same can be done for a cluster of fuzzy multisets
We will use the cluster centroid to represent the cluster and all its contained decks in a single (fuzzy) multiset.
3.2. Clustering of (Fuzzy) Multisets
For mining deck archetypes we are going to apply the clustering algorithms introduced in Section 2.3 to a data set of recently played decks. Since these clustering methods are distance-based we need a suitable distance measure to group data points into clusters of similar objects.
To measure the distance of two multisets and we define their Euclidean distance by
In our work, we will compare results based on the Euclidean distance with results obtained from applying the Jaccard distance measure. Here we use the general Jaccard distance :
Similar to the Euclidean distance we transfer the equation to measure the distance of two fuzzy multisets and :
4. CLUSTERING EVALUATION
All project files for the following evaluation are available at Github (see Ref. ). We evaluated our clustering approach using deck data of the HSReplay website . The website offers easy access to a large collection of recently played games. Players can choose to use the Hearthstone Deck Tracker plugin, which automatically records played games and uploads them to the HSReplay servers. In return, players can access information on the probability of their opponent's cards while playing the game.
We have extracted a deck data set that contains data from February 5th to 20th 2019. Each deck entry stores the deck's cards, the total amount of games recorded during the two weeks, its average win-rate, average game-length, and average turn count. Additionally, each deck entry provides information on the suggested deck archetype, which was labeled by expert players. The deck data set consists of a total of 956 distributed over 9 hero classes (cf. Table 1).
|Hero||nr Games in
|Class||Deck Data Set||Replay Data Set|
Distribution of hero classes in used data sets.
We will compare the result of each clustering method with the labeling provided in the data set. For this purpose, we use the external validation measures homogeneity, completeness, and v-measure . While homogeneity is satisfied in case the clusters contain only data points that are members of a single class (as labeled in the ground truth), completeness is satisfied if all the data points that are members of a given class are elements of the same cluster. The v-measure is the harmonic mean of homogeneity and completeness. All three measures provide values between and , where larger values are desirable.
We first calculated the distance matrix of decks of the same hero class for each of the nine heroes. Figure 1 shows the heat map plot of the Jaccard distance of all Druid decks (70) contained in the data set encoded as fuzzy multisets. Clusters of similar groups are clearly distinguishable. Euclidean distance looks similar but is not limited to a range of to , which makes it harder to define a cutoff threshold for stopping the clustering process.
For each clustering algorithm we perform a parameter search. For k-means we varied the number of clusters and repeated the clustering times with varying initializations. The best-performing clustering in terms of SSE will be reported as the final clustering result. In case of the hierarchical clusterings, we first create a full hierarchy and horizontally cut it at each layer of the hierarchy. Finally, for DBSCAN we use the -DBSCAN algorithm  to quickly generate a hierarchy of clusters for all relevant parameterizations of the -radius. We repeat this process for , , and . For each retrieved clustering we report homogeneity, completeness, and the v-measure in Figure 2. Additionally, the best-performing parameterization per clustering in terms of the v-measure is reported in Table 2. Presented results are calculated using the Jaccard distance. Using the Euclidean distance yielded similar results and will therefore be omitted.
|HAC single linkage|
|HAC complete linkage|
Best-performing parameter configuration per clustering algorithm.
The results show that the best clustering result in terms of the v-measure was achieved by single linkage () closely followed by complete linkage (). Both hierarchical methods, achieve result in relatively stable v-measures for in the range of clusters. Since Hearthstone's meta-game is dynamic, the number of played deck archetypes will be varying over time. Their stable clustering performance makes these two methods relatively robust against these changes in the meta-game. In comparison, -means achieves a peak performance for clusters. Finally, DBSCAN with performs similar, but is very sensitive to the chosen value and its resulting number clusters. This problem gets worse for higher values and is likely to be a result of the high dimnensionality of the input space.
5. PREDICTING UPCOMING CARDS
In the previous sections we have shown how a clustering of decks that resembles a human labeling can be extracted from a data set of played games. In the following, we will propose a method to predict upcoming cards based on a given clustering. Knowing the cluster centroids, a prediction of the opponent's cards can be made using the multi-process described in the following subsections.
5.1. Keeping Track of Observed Cards
At the beginning of the game the agent starts with an empty fuzzy multiset. During the opponent's turn, the agent keeps track of all the opponent's actions. Each card played is added to the agent's fuzzy multiset with a membership grade of . In case the card has previously been played the membership sequence of this card is extended by another entry of .
5.2. Determine the Most-Likely Deck Archetype
During the agent's turn, the agent first needs to determine the most-likely deck archetype. This can be done by calculating the pair-wise distance between the fuzzy multiset of observed cards and all the cluster centroids, which represent the deck archetypes of the current meta-game. The closest centroid is assumed to be the most-likely deck archetype and will be considered for the card prediction of upcoming cards. In case the agent can handle multiple state determinizations, a distance-weighted sampling can be applied to select one deck archetype per requested determinization. For this purpose, all distances between the observation and the fuzzy centroids of the -th cluster are first transformed into a similarity value by
The resulting similarity values are further transformed into a probability distribution by
In the upcoming evaluation of the agent's prediction accuracy, we will only consider the most-likely deck archetype during the prediction process. However, in the context of a game-playing agent which uses a search process that can handle an ensemble of state determinizations  it may be advantageous to extract cards from a variety of possible archetypes to find a more robust sequence of actions.
5.3. Sample Cards
The final step of the prediction process is the sampling of cards. For this purpose, the agent first removes previously observed cards from the centroids membership sequence. For each observed card, the agent removes the highest value from the centroids membership sequence of this card. The remaining entries in the centroid are ranked according to the sum of their membership sequence. Similar to the bigram-based prediction each card receives a sampling probability based on the determined sum. The resulting probability distribution can be used to sample cards based on their likelihood to appear in the remaining cluster. Sampled cards are temporarily removed from the decks centroid before the next cards are sampled. This process will be repeated until a set of opponent cards has been determined to fully determinize the current game state.
6. EVALUATING THE PREDICTION ACCURACY
Given the prediction process proposed in the previous section, we evaluate the resulting prediction accuracy in two prediction tasks. First, we are testing the agent's ability to predict cards of the remaining game (Section 6.1), and second, we evaluate its accuracy to predict cards of the upcoming turn (Section 6.2). While the former gives us an understanding how well the considered deck archetype matches the opponent's deck, the second scenario is especially relevant when selecting the agent's next actions.
In this evaluation, we will be using a second data set that consists of human player replay data. Each record includes all observed cards that have been played per match but does not contain any information on the remaining cards of both players' decks. Only records that cover games of the standard game mode played during the same patch period (21 February 2019 to 3 April 2019) will be used for evaluating the proposed methods' prediction performance. Used data sets, the source code for the following evaluations, and the raw results can be found in the public git-repository .
6.1. Card Prediction for the Remaining Game
In this first evaluation, the accuracy of predicting upcoming cards of the remaining game will be measured. Since the number of observed cards and the complexity of turns changes over time, results will be reported bucketed by turn. Each algorithm is used to predict the 10 most-likely cards after each of the first 10 turns. To assure that the prediction of the last turns can be reasonably tested, only games that lasted at least 15 turns have been selected for this evaluation which resulted in a total of 3062 games. The hero class distribution is shown in (cf. Table 1).
Figure 3 shows the prediction accuracy for the best clustering per algorithm (see Table 2) bucketed by turn. Rank 1 represents the card that is believed to be the most-likely card to be played by the opponent during the remaining game. Vice versa rank 10 is believed to be the 10th most-likely card. Additionally, we report the average accuracy of the 10 cards to be believed the most likely to appear. Since the opponent is not able to play many cards per turn, we also report the aggregated prediction accuracy in Figure 4. This value represents the accuracy of any of the top -ranked cards being correct.
For all algorithms, the peak performance of predicting the highest-ranked card is achieved in turns 6 or 7. This is likely to be a result of the information gained until this turn, which helps the agent to identify the deck. Since the replay length is limited, we do not know all cards of the opponent's deck. Even in case cards are correctly predicted, chances are that the agent will not be able to observe them due to winning or losing the game before the card can be played. This is likely to be the cause of the steady decline of the prediction accuracy from turn 8 on.
Since multiple cards need to be sampled to create a state determinization of the opponent's hand cards, we also compared the aggregated prediction accuracy of the top ranks. Values indicate that there is more than a 50% chance that any of the top 2 ranked cards will be seen througout the remainder of the game. Increasing the number of considered cards increases this chance with diminishing returns for higher values of . Overall, the aggregated top- cards prediction achieves an accuracy of about 80% for all clustering algorithms from the 5th turn onward.
6.2. Card Prediction of the Next Turn
In a similar manner we evaluate the agent's accuracy in predicting cards of the next turn. Naturally, the accuracy will be much lower, since the number of cards that can be played during the next turn is limited.
Figure 5 reports the prediction accuracies of the highest-ranked card, the card with rank 10 and the average of the first 10 ranked cards. While the accuracy during all turns is very low, the aggregated values shown in Figure 6 look more promising. The prediction accuracy of upcoming cards steadily increases until the 9th turn at which it peaks at a value in between 40% and 50% depending on the clustering algorithm used. As a result the agent has a 40%–50% chance to correctly sample a card to be played during the next turn when only considering the most-likely deck.
It needs to be noted that the sampling approach does not consider if a card is playable during the next turn. Using an opponent model, the agent still needs to determine which of the sampled cards is likely to be played next.
In this paper we reviewed our automatic clustering process for deck archetypes and evaluated it in the context of the collectible card game Hearthstone. We chose to represent decks in the form of (fuzzy) multisets and define a centroid of clusters of such multisets. On the basis of fuzzy multisets, we clustered real player deck data using multiple clustering algorithms. The result of each algorithm was evaluated in context of real player data and has shown to match human expert player labels of deck archetypes reasonably well. Based on the extracted deck archetypes we proposed a sampling algorithm, which can be used to determinate a state. Predicted state determinizations have been evaluated regarding the prediction accuracy of upcoming cards of the whole game and the opponent's next turn. Results show that the process is able to identify upcoming cards with high accuracy. This forms an excellent basis for applying the proposed approach to state-determinizing search agents and may allow agents to play complex games such as Hearthstone on a higher level than they can currently achieve. Our next step will be to compare state-determinization methods and their effects on an agent's game-playing performance.
While our process currently assumes a static meta-game, we are eager to explore dynamic clustering and prediction schemes in the future. Since web sources frequently update their databases, it may be interesting to capture the dynamic evolvement of new strategies and decks among human players. At the same time, it would allow the agent to keep track of popular strategies to play accordingly. A better understanding of the process in which decks emerge may even help to construct new decks or to further balance the game. However, much work needs to be done until these challenges can be solved.
CONFLICT OF INTEREST
The authors declare they have no conflicts of interest.
We would not like to explicitely state the authors contributions.
No funding to be reported.
Cite this article
TY - JOUR AU - Alexander Dockhorn AU - Rudolf Kruse PY - 2020 DA - 2020/08/18 TI - Predicting Cards Using a Fuzzy Multiset Clustering of Decks JO - International Journal of Computational Intelligence Systems SP - 1207 EP - 1217 VL - 13 IS - 1 SN - 1875-6883 UR - https://doi.org/10.2991/ijcis.d.200805.001 DO - 10.2991/ijcis.d.200805.001 ID - Dockhorn2020 ER -