Computer games have become a very interesting environment or testbed to develop new algorithms in many of the branches of Arti cial Intelligence. In fact, collectible card games, such as Hearthstone, have recently attracted the attention of researchers because of their characteristics: uncertainty, randomness, or the in nite and unpredictable interactions that can occur in a game. In this game each player composes decks to face other players from a pool of more than 3,000 cards, each one with its own rules and statistics. This implies a great variability of decks and card combinations with rich e ects. This paper proposes the use of clustering techniques to extract information from data provided by Hearthstone players, i.e. a Game Mining approach. To do so, more than 500,000 decks created by game players (both experts and just enthusiasts) have been downloaded from Hearthpwn website. Thus, a descriptive analysis of this dataset, along with Data Mining techniques, have been carried out in order to understand which archetypes (or deck types) are the favourites among the community of players, and what relationships can be identi ed between them. The results show that it is possible to use clustering algorithms such as K-Means to automatically detect the archetypes used by the players.
? This work has been supported in part by projects B-TIC-402-UGR18 (FEDER and Junta de Andaluc a), RTI2018-102002-A-I00 (Ministerio Espan~ol de Ciencia, Innovacion y Universidades), projects TIN2017-85727-C4-1-2-P (Ministerio Espan~ol de Econom a y Competitividad), and TEC2015-68752 (also funded by FEDER)
However, a very interesting area of application is the modeling of players. That is, starting from information related to how the human player interacts with the game to obtain useful knowledge. Furthermore, understanding and modelling the interaction between the player and the game can be considered a holy grail for game developers and designers [22].
The interaction between players and games is particularly challenging in the area of Collectible Card Games (CCGs), such as Magic The Gathering. This type of games involves a lot of human interaction not only during the game, but also during the creation of the decks to be used from a pool of thousands of cards. These decks are usually shared and commented on the internet, so many players use them as a basis to create their own versions. In addition, the appearance of new cards and expansions makes players have to adapt their decks to the current meta-game, that is, to the players' behavior at a given time.
One of the most popular Digital CCGs (DCCGs) nowadays is HearthStone,
Heroes of Warcraft (HS), with over 40 million players. In addition, this game is
becoming a de facto benchmark for researchers in arti cial intelligence branches,
due to the enormous amount of combinations when creating decks, along with
the randomness of the e ects of the cards, and the hidden information [
In HS, players build a deck of 30 cards from a card pool (that can be expanded buying random packs). To win, players must reduce the health of the opponent's Hero from 30 to 0, using the two types of cards available: spells, that a ect the battleground and are then discarded, and minions, that stay in play and can attack the enemy's Hero or other minions. There are also, weapons, a sub-set of spells that allow the hero to attack other characters during several turns using special abilities. Each card has an associated cost (in number of mana crystals), that is reduced from the player's bunch after a card is played. This amount of crystals of each player is replenished at the beginning of the turn and increased in one up to a maximum of 10.
In HS, deckbuilding is limited to the neutral card pool and the cards that belong to the class of the Hero chosen for the game: Druid, Mage, Hunter, Paladin, Priest, Rogue, Shaman, Warlock, or Warrior. Every Hero class comes with a di erent Hero Power (costing 2 crystals to use), that in conjunction with their card set, matches every Hero to di erent deck archetypes. For example, Priest's healing abilities are a very powerful choice for decks that attempt to control the board, but not so convenient for aggressive ones, that aim to quickly end the game.
Due to its popularity, players share the list of cards they use in their decks publicly on websites such as Hearthpwn4, where users and game enthusiasts vote for, copy and comment on the most popular decks. Currently, this website has a huge amount of data: over 600,000 decks in total for all Hero classes, and game modes. The data obtained by crowdsourcing, like those on this website, allows for a dynamic, extensive and organic study of user-generated data [16]. The created decks can be entered into archetypes: that is, decks with a speci c behavior and use. For example, the Jade Druid archetype is one in which the 4 https://www.hearthpwn.com/ Druid class uses Jade Idols and other cards with the Jade keyword to obtain stronger and stronger e ects. Players are familiar with these archetypes and often create other archetypes to counteract them.
The aim of this paper is to demonstrate whether it is possible to extract
information from large user-created datasets within the scope of the DCCGs, i.e.
conduct a Game Data Mining [
The process that we are going to follow in this work consists of downloading the dataset and pre-processing to remove unnecessary information. Next, a descriptive analysis of the dataset will be performed to obtain relevant information before applying clustering algorithms. An expert player will analyze the di erent clusters to con rm that they correspond to di erent decks archetypes.
The rest of the paper is structured as follows. After the state of the art in section 2, Section 3 describes the methodology used to obtain the dataset, preprocess and analyze it. In the following section a descriptive analysis of the dataset is made and the results of the clustering method are discussed. Finally, in Section 5 the conclusions and future lines of work are presented. 2
Game Data Mining [
Obtaining the dataset is the main bottleneck, thus, even if this research line has been widely studied in several papers, the games analysed are just a few those for which there are available data -.
For instance, Thurau and Bauckhage [18] analysed more than 190 million records (from 4 years) of World of Warcraft game and found di erent tendencies in the evolution of guilds. Weber and Mateas [19] applied classi cation techniques in order to forecast enemy behaviour in StarCraft. Also Madden NFL [21] and (In nite) Super Mario [20] have been studied from this perspective.
However the most proli c game so far has been Tomb Raider: Underworld,
which has been deeply analysed in many papers. Drachen et al. have several
works applying di erent data mining and machine learning techniques to more
than 1300 records of players that have nished the game, such as [
The objective of the present paper is also to analyze data to nd archetypes, but we are considering Hearthstone, which, to our knowledge, has not been analyzed with this purpose yet.
This DCCG, anyway, has been one of the most proli c games/environments
for research in the last years. The studies have been mainly focused on the
creation of competitive agents to play autonomously the game [
Data mining has also been applied to HS. Indeed there have been two Data
Mining Challenges (AAIA'175 and AAIA'186) using this game as a testbed.
However, the 2017 Challenge and the derived papers [
Thus, in this study we will apply clustering methods to a big dataset, but
instead of trying to model player behaviour as in [
As the objective of this work is to analyze the decks that players create, it is necessary to obtain a large amount of data. In our case we have used the data available on a repository: the HearthPwn website (https://www.hearthpwn. com/). This database contains information about all the cards available in the game, and o ers to its users the possibility to create and share decks built from those cards. Currently there are more than 600,000 decks created, allowing ltering by expansion, hero class, or type of game, among others. Users can view other users' decks and copy them into the game to use against other players. 5 https://knowledgepit.ml/aaia17-data-mining-challenge/ 6 https://knowledgepit.ml/aaia18-data-mining-challenge/ Typically, the most popular and proven powerful decks are copied, or variations are created from them.
To download the data we have made a script in Python that allows to iterate by deck id to get the URL of that deck and download the speci c deck webpage. That web in HTML format is parsed using the BeautifulSoup 7 library to obtain the list of cards, the date, the class and the game type of deck (Game types in Hearthstone are: Ranked, Tavern Brawl, Arena and Adventures). With the name of the cards it would also be possible to access to more information, such as the cost of making the complete deck with Arcane Dust (the virtual currency of the game), the mana cost of each card, or the card type: Spell, Minion or Weapon. Other information such as the Rarity of cards, can als be extracted.
We have limited the decks to those belonging to the \Ranked" category. This game mode is the one where players prepare their decks in order to compete against other players, because it is the most popular game mode. It also is the most common in the whole dataset, with a proportion of 62%.
Each sample (row) will be a deck identi er, and each feature (columns) will be a card from the entire collection. A 1 in a position indicates that the deck has that card, a 2 indicates that it has 2 copies (the maximum for non legendary cards) and a 0 indicates that it is not included in the deck. 3.2
Method of analysis Initially we will perform a descriptive analysis of the dataset, to see the number of decks per Hero Class, the date of creation, or the most common cards of each class. This can be useful as an initial overview of the whole dataset, and will help to understand further analyses.
Then, a clustering analysis have been conducted using two techniques:
{ K-Means [
The rst technique has been applied because it is very fast but also very e ective, as it has been proved in hundreds of studies with all kinds of data. On the other side, Hierarchical clustering o ers a very simple visual output, that could be interpreted easily by a human expert, as this is the case in this work.
The input of both algorithms is the dataset. While in K-Means we want to detect if we can extract archetypes (clustering decks), in the AHC we want to extract information about how cards are related (clustering cards). That is the reason in the AHC the input is the transpose of the array: now each card is a row, and each feature (column name) is the ID of the deck the card belongs.
Since each hero has a subset of speci c cards that only that class can use, it does not make sense to do the clustering analysis with all the cards/decks, 7 https://pypi.org/project/beautifulsoup4/ as the clusters obtained would be the classes themselves, considering they have disjoint features - their exclusive cards -.
In the case of K-Means we have focused on three classes: Druid, Mage and Warrior, as they have a very wide range of archetypes to play.
The obtained results of the analysis are presented and discussed in the following section. 4 4.1 60000 s k c e fd40000 o r e b m uN20000 0
Figure 1 shows the distribution of dataset decks by hero class. Although they have a similar number, there is a 32% di erence between the class with the highest number of decks (Priest) and the one with the least (Warrior). The most common classes (Priest, Mage and Druid) are also more oriented to control and long-term strategy, so it can explain the variability of user-created decks. 65379 57961 62418 70083 66306 57184 53435 54129 52885 MAGE
WARLOCK
PALADIN
PRIEST
ROGUE
SHAMAN
HUNTER
WARRIOR DRUID
Class K-Means algorithm has been applied to the decks in order to see how they are related. We have set to 10 the number of clusters for each class, a value expected 2000 t coun 1000 0 2014 2015 2016 2017 2018
2019 Date to produce enough variety of archetypes, while delivering a reasonable amount of data to be analyzed.
After applying K-Means, we extracted the 15 most common cards from the decks of each cluster. Figure 4 show the percentage of each one for each cluster.
One of the authors, a HearthStone player that reached the highest rank (Legend) in the competitive ladder, manually inspected the clusters and provided an expert analysis for three classes, selected because of an anticipated larger variety of deck archetypes: Druid, Mage, and Warrior. In the following, the notation used for clusters is the initial of the hero class, plus the cluster id (e.g. M2 indicates the second cluster for the Mage class). Also, Figure 4 shows the ten most common cards in each cluster.
Druid Clusters D1, D5, D7 all present cards that provide advantages in the late game (such as Wild Growth and Nourish); but while D1 and D7 have control cards (such as Starfall ), D5 exploits the late-game advantage to close combos, using potentially one-turn-kills like Malygos or Aviana. Clusters D2 and D6, on the contrary, have none of these cards, but feature weak, cheap creatures such as Arcane Raven and Fire Fly, plus cards that enhance all friendly creatures on the board, such as Savage Roar, thus grouping decisively Aggressive archetypes. D3 and D9 show a preponderance of Jade cards (Jade Idol, Jade Spirit, Jade Behemoth), thus placing these decks in the category of Jade Druid, a specialized midrange archetype. Cluster D10 presents mostly cards with the C'Thun keyword, identifying the decks belonging to this cluster as variants of the combo C'Thun Druid archetype. Clusters D4 and D8 are harder to categorize, as they seem to either be mid-range variations of aggressive decks, or present poor cohesion, possibly representing outliers.
Mage Clusters M3, M4, M6, and M9 all represent aggressive archetypes, featuring cards such as Fireball and Frostbolt. M3 exploits synergies with secrets (Arcanologist, Counterspell, Medivh's Vallet ), M4 relies upon Flamewaker and cheap spells to damage to opponent, M6 shows a strong presence of Mech minions
28.62% 38.69% 39.27% 39.65% 41.7% 44.96%57.35% Frost Nova Blizzard
Ice Block Sorcerer's Apprentice
Polymorph Mana Wyrm Flamestrike
Firebal Arcane Intelect
Frostbolt 43.35% 51.92% 53.95% 57.71% 25% 5607%.74% 75% 100% 0%Percentage of DRUID decks using the card SUaAnvlnaeinamEnEsHKaaFHhaxlgiurDhlpoetClnheleuCeHotoehanezsoimogddriiHmn'vrlhmspynegommaMauSBTTnsaanrrahiotannoaderowpednpksrt 0% 30.9433842%9.0.552.1%87466%%.%47%5568.8.256954%.0%16%29.%5765%.82% 75% 100%
Percentage of HUNTER decks using the card
Vilespine Slayer Edwin VanCleef Deadly Poison Shadowstep SI:7 Agent Preparation
Sap Fan of Knives Eviscerate
Backstab
Warrior Clusters W1, W2, W3, and W4 all represent variations of Warrior Control archetypes. Decks in W1 rely upon Dead Man's Hand to try and nish the game through fatigue damage, W2 groups both Mech synergy (Dr. Boom, Mad Genius, Zilliax ) and Odd Warrior (Baku, the Mooneater ), W3 decks seem to exploit older cards (Sylvanas, Justicar Trueheart ) possibly representing Wild decks, W3 is a Control version of C'Thun Warrior, with the C'Thun cards and several other synergies. W8 is a set of decisively aggressive decks, with cards such as Leeroy Jenkins, Patches the Pirate, Southsea Deckhand. W6, W7, and W10 all represent combo decks: W6 includes cards that can damage all minions on the board (Whirlwind, Death's Bite) plus minions that bene t from being damaged (Grim Patron, Frothing Berserker ); W7 and W10 are variations of C'Thun Warrior, with less control elements with respect to W3, and cards such as Brann Bronzebeard to try and nish the game using a colossal amount of damage from C'Thun. Cluster W5 groups together Quest Warrior archetypes based on Fire Plume's Heart, and more generic mid-range decks still based on Taunt minions (Stonehill Defender, Direhorn Hatchling ). Finally, cluster W9 shows relatively few points in common between its decks, with the most common card being Fiery War Axe appearing in only 68% of cases, and might thus represent a collection of outliers, or very di erent mid-range decks.
Once the clusters generated by K-Means have been analyzed, Agglomerative Hierarhical Clustering has been applied. AHC can show also interesting information about the in uence of the cards. We have run the method for the three heroes, but due to space limitations we are showing and analyzing here only the results of the Warrior class, as they are somehow representative and interesting.
Figure 5 show the complete generated dendrogram of the Warrior cards, and more detail of the subtrees with height=4 is shown in Figure 6. The height of the fusion, provided on the vertical axis, indicates the similarity/distance between two cards. The higher the height of the fusion, the less similar the cards are. This height is known as the cophenetic distance between the two cards. Most of the cards are in a big cluster (subtree 4), but there exist several relevant cards (single cards) that have enough weight to appear in their own subtree, even at level 1. Several pair of cards shown are usually used in combos, have some kind of synergies or belong to the same expansion. For example: N'Zoth and Bloodsail Cultist. 5
Understanding how players play a game is a major concern for developers, as
they can adapt elements of the game, such as the rules and content, to facilitate
the balance or fun it can provide. In this paper we propose to use Game Data
Mining [
After expert analysis of the results, we have provided information on how the cards are related to each other, and how it is possible to detect di erent archetypes from the data created by the users. However, the proposed automatic clustering approach also showed a few limitations: 3 out of the 30 clusters analyzed seems to be composed of mostly outlier decks, identifying no clear archetype (D4, D8, W9); moreover, distinct clusters in the same hero class seem to present very similar archetypes (W7, W10); and nally, it is sometimes pos
Wrath
Wild.Growth Ultimate.Infestation
The.Lich.King
Swipe Spreading.Plague
Primordial.Drake radC Nourish
Mire.Keeper Malfurion.the.Pestilent
Jungle.Giants
Innervate Fandral.Staghelm Elder.Longneck Earthen.Scales
DRUID − Cluster 1 ( 5340 decks) 70.58% 75.71% the set, or the amount of beast cards, weapon cards, or combo cards, to cite some examples. This information could better describe the decks for their analysis.
Moreover, other clustering algorithms such as Density-Based Spatial
Clustering of Applications with Noise [
In: FDG Workshop on Evaluating Player Experience in Games. ACM Press (2011) 21. Weber, B.G., John, M., Mateas, M., Jhala, A.: Modeling player retention in madden n 11. In: Twenty-Third IAAI Conference (2011) 22. Yannakakis, G.N., Togelius, J.: Modeling Players, pp. 203{255. Springer International Publishing, Cham (2018)