In this paper, we demonstrate how to extract strategic knowledge from gaming data collected among players of the popular video game HearthStone. Our methodology is as follows. First we train a series of classi ers to predict the outcome of the game during a match, then we demonstrate how to spot key strategic events by tracking sudden changes in the classi er prediction. This methodology is applied to a large collection of HeathStone matches that we have collected from top ranked European players. Expert analysis shows that the events identied with this approach are both important and easy to interpret with the corresponding data.
HearthStone (HS) is a popular online video game in which players ght one another using virtual playing cards. To defeat their opponent, players have access to a large number of cards, that they can use to trigger a variety of o ensive or defensive moves. The cards in HS have complex synergies which are exploited by most experienced players to set up powerful strategies. Over the time, experienced players have accumulated a large body of strategic knowledge about the combinations of cards and how to use them. However, this knowledge remains mostly inaccessible to novice players.
In this paper we are interested in identifying key strategic events during
matches to help novice players to decode and learn from matches between skillful
players. The problem of extracting interesting strategic insights from game data
has been addressed in many di erent ways which typically compromise between
quality of the knowledge extracted, and the amount of external expert knowledge
that needs to be used to extract them. For example Bosc et al. [
In general, what is truly interesting is a subjective matter. However, many games, including HearthStone, have been designed to promote small events with big impact on the outcome of the game. For example in HS, playing a particular card at a particular time can have a dramatic impact on the rest of the match, and thus it should be considered as a strategic event of the ongoing match.
Building on this observation, we explore the hypothesis that a strategic event in a game is one that impacts the outcome of the game. To validate this hypothesis, we train a series of classi ers at di erent stages of a match and we analyze the events which are associated with a change in the classi er prediction over time.
To identify truly interesting strategic events, it is crucial to obtain reasonable classi er con dence. But predicting the outcome of a match with con dence using only features observed during a match (such as players health points or number of creature) is a di cult task even for experienced human experts, and a fortiori for simple learning algorithms. To overcome this di culty, we focus on the end of the match, where the winner is easy to detect from simple game features such as players healtpoints, and step backward in the match turns, until the classi er con dence is too low. As we will show in our experiment, this technique enables us to spot a number of interesting strategic events up to 8 turns before the nal turn.
We apply this approach on a large collection of match data which we have collected from real players. Our experiments show that this approach can be used to identify events which are particularly relevant and further analysis of the classi ers parameters, such as feature weights, can be used to better understand these events.
In summary, this paper contributes in three di erent ways. First we introduce a new dataset1 which includes over two thousands HearthStone matches played by skillful players (among the top 1% European players). Second we demonstrate how to train classi ers which are su ciently accurate to detect events impacting the outcome of the game. Finally, we demonstrate how to identify strategic events using changes in classi ers prediction and we derive number of strategic insights from the analysis of the classi ers. These results validate our initial hypothesis that events impacting the outcome of the match can provide strategic insights. As we will show, these insights are not speci c to one particular match and provide useful knowledge for novice players. 2
A large body of work have already been dedicated to the problem of sport
analytics for various purposes. For example, predicting the outcome of the match
is a popular problem due to its connections with betting. Match outcome
prediction can be done either o ine, (for example see the work by Goddard et al.
[
Compared to traditional sports, e-sports o er an interesting test-bed for novel
match data analysis techniques because the data is collected in a controled
envi1 The dataset is available at https://bitbucket.org/Valnora/hsdataset
ronment (the game engine) but still re ects actions performed by highly
competitive human players (see [
Finding highlights in match data is another interesting problem which can be
used to build game summaries and to help the analysis of raw match data. Most
work in the literature involve the prior de nition of game events and highlights
by an expert [
Our work di ers from these, as we want to extract key events, solely based on game features, rather than external information, such as expert knowledge or crowd cheering.
E-sports is being more and more studied in the research community, as match
data are usually easily available. Indeed, many popular electronic games have
a replay feature that record game actions. These replays can then be analyzed,
without having to use external websites game summaries, as it is usually the
case for traditional sports. Nevertheless, HearthStone does not have this replay
feature and game data have to be extracted using custom tools, leading to the
fact that there is currently no publicly available detailed data of HS matches.
Our work is interesting as only few work have been conducted on the game
HearthStone, and their main concern is to build an Arti cial Intelligence that
is able to compete with other, scripted or random, arti cial players [
HearthStone, is an online card game with a medieval fantastic avor. Matches in HS involve two players, playing in turns, one at a time. Each turn starts with one player drawing a card from her deck, and then playing a small sequence of actions using the cards in her hand. When the player has performed all the actions that she wants to play, the turn ends, and the other player can start playing. Players in HS are incarnated by a character who has a xed number of health points and a unique ability. In order to win a match, a player has to bring the health points of the opponent's character down to zero.
Cards can be used to perform a variety of actions but the majority of them invoke magic creatures which have attack points and health points (the health points of the creature are independent from the player's health points). The creatures that have been invoked can then be used to attack the opponent creatures, or the opponent character directly.
Before they can play any match, players are required to build a deck, which is a small set of cards they want to play with. Because cards can have important synergies between them, all decks are not equally powerful, and the best decks enable the player to draw powerful combinations of cards during a match with high probability. Furthermore, since each character class has access to an extra set of cards, players have to build decks which can deal with a large spectrum of opponents. As a consequence, creating novel powerful decks requires lots of expertise and has become an important part of the game. 4
To build strategic knowledge about HearthStone and help novice players, we have collected match data from several skilled HearthStone players using a game tracker2. The tracker runs in the game client of one player and records all the data that this player can see. We track three players who have ranks ranging from rank 10 to legend (good players to elite players). The opponents are automatically selected by the game engine at the beginning of each match and since the game engine uses players ranking to ensure balanced matches, the opponent players in our dataset have similar levels as the tracked players.
Each record in the dataset D is a pair (xi; yi) where xi is a list of feature vectors xi1; : : : ; xin describing each one of the n turns of the corresponding match i, and where yi is a boolean label indicating whether the tracked player won the match or not. A feature vector xik describes a turn k using the following features: turn id (integer), cards played during the turn (list of cards), number of cards in player hand (integer), number of cards in the opponent hand (integer), player's creatures on the board (list of cards), opponent's creature on the board (list of cards), player's turn or opponent turn (boolean), player's health (integer) opponent's health (integer) , player's armor (integer), opponent's armor (integer). In the following, we denote Dk the dataset restricted to the feature vector for the turns k only. (i.e. Dk = f(xik; yi) : 8(xi; yi) 2 Dg). In our dataset the turns are numbered backward starting from the nal one (i.e. turn 0 is the nal turn). This choice is discussed in the following section. 5
Our hypothesis is that a strategic event is one that has an important impact on the outcome a match. In other words, if a particular event (such as a playing a card) drastically changes the estimated winner prior to this event, we consider it to be a strategic event.
To validate this hypothesis using the data collected as described in Section 4, we apply the following methodology.
(i) We train a sequence of classi ers hf1; : : : ; fni to estimate the winning player (i.e. the class label y) after each turn of a match. To do so, we train each classi er fk using the match data collected at turn k (i.e. using the restricted dataset Dk as introduced in Section 4). Remark that training a sequence of classi ers is preferred over training a single classi er because features do not 2 Tracker available at https://github.com/HearthSim/Hearthstone-Deck-Tracker have the same importance at di erent turns. (This e ect is demonstrated later in Figure 3.)
(ii) We use the sequence of classi ers to make a sequence of predictions about the winner after each turn. Given a match description x, the sequence of classiers will produce a sequence of predictions hf1(x1); : : : ; fn(xn)i. In our experiments, we use probabilistic classi ers so that fk(xk) is the estimated probability of a win given the game state at turn k (i.e. fk(x) = Pr(y = 1jxk)).
(iii) We select few match descriptions x having the largest di erence between two consecutive predictions jfk(xk) fk+1(xk+1)j.
(iv) We analyze each corresponding match in the light of the feature coe cients, and show that changes in the classi ers predictions are indeed correlated with highly strategic events in the match.
The main di culty is to achieve su cient classi er accuracy to obtain signi cant
results. Several papers have demonstrated how to achieve good accuracy in the
context of game outcome prediction using standard machine learning algorithms
(for example Goddard et al. used regression techniques to forecast football match
result [
To overcome this problem the key observation is that predicting the outcome of the game becomes easier as we approach the end of the game: predicting the winner after the nal round is (almost) trivial and becomes increasingly di cult as we approach the beginning of the game. Building on this observation, we have numbered the turn starting from the nal one (as described in the previous section) and we focus on the nal turns, where the classi er con dence is high enough. As we will show in our experiments we are able to achieve reasonable classi er accuracy up to 8 turns before the nal turn. 6
In this section we demonstrate the applicability of our approach on the HearthStone dataset. In particular, we rst look at the classi er accuracy at di erent stages of the game (Q1). Then, we validate experimentally that changes in the classi er prediction are correlated with key strategic events (Q2). Finally, we demonstrate important strategical insights about the key events that can be derived from the analysis of the corresponding match data (Q3). How reliable are classi ers at predicting the winner n turns before the nal turn (Q1) In our approach, the classi er accuracy is critical to derive useful knowledge, thus we start this experimental section by evaluating the accuracy of the classi ers at predicting the outcome of the game. Only the most accurate classi ers will be used to validate the subsequent experiments (Q2) and (Q3).
We train a series of classi ers (one for each turn) as described in Section 5. The classi ers are trained using three di erent learning algorithms: Naive Bayes (NB) and Logistic Regression Classi cation (LR), which produce easy to interpret models based on linear predictors (required for Q3), and Random Forest Classi cation (RF) which will serve as a comparison for non-linear models.
The classi ers accuracy and f-score for the 10 nal turns are presented in Figure 1 (left). On these plots, the nal turn is labeled 0 on the x-axis. Unsurprisingly, the accuracy tops at the nal turn (where the winner is already set) and decreases as we get closer to the beginning of the match. The predictions remain signi cantly better than the majority class prediction (represented by the horizontal line in Figure 1) up to 8 turns before the end of the game, which is a good result. Remark that the accuracy in the last turn is not 100% because many players choose to concede when they are in a bad shape. In this case, predicting the winner at the last turn remains non-trivial and the classi ers can still make errors.
If we compare the performances of the di erent training algorithms, we can see that classi ers trained with LR achieve the best results overall. RF occasionally does better, but mostly on the last turn which is not important for the reason mentioned in the previous paragraph.
The instability of the classi ers accuracy on the left hand side is an artifact of our decision to number the turns starting from the nal one. Even numbered turns are played by the player that will eventually win the match whereas odd numbered turns are played by the player that will be defeated. At the end of the game, turns played by the winner will often increase the gap between players' health points, thus making the classi er more con dent in its prediction. On the other hand, turns played by the loosing opponent will often reduce the gap (for example, the loosing player can choose to heal himself) making the classi er less con dent in its prediction.
In order to balance this undesirable e ect, we train classi ers on double turns. A double turn include all the actions played by the player at the turn n, and all the actions played by the opponent at turn n + 1. As one can see, on the right hand side in Figure 1, predictions made using this method are both more accurate and more stable over time.
In the light of these results, we based subsequent experiments on classi ers trained with LR on the last 8 turns, using double turns.
Are changes in classi er con dence correlated with important events (Q2) and can we derive strategical moves from classi ers analysis (Q3) Our goal is to validate our main hypothesis, that a strategical event in a match is associated with a change in the classi er con dence. To do this, we rst plot the classi er con dence in predicting the winner at di erent stages of the game for a variety of manually selected matches which exhibit a sudden change in the nal turns. We discuss three of these games and demonstrate how to derive strategical insights from the analysis of the corresponding data (Q3).
The rst game, (Example 1 in Figure 2), is signi cant because the classi er predicts the incorrect winner with relatively high con dence only 4 turns before the nal turn. At this turn, the nal winner does not have any creature on the board. Without creatures players can deal a very limited amount damage to their opponent, and thus the situation looks more favorable to the other player. In this situation, it is more reasonable for the classi ers and for novice players to predict that the player with the most creatures will win. However, this experienced player chose to play a rare combination of three cards which allowed him to put many weak creatures that deal damage to the opponent, whereas dealing damage with a creature usually requires an extra turn. This strategy has lead the player to reverse the course of the match and win within the next turns.
In the second game, the classi er also predicts the wrong winner 6 turns before then end of the match. Nevertheless, the prediction greatly changes during the next turns. Between turn 4 and 5, the player choose to play a particular card called Flamestrike. The community of experienced HearthStone players has identi ed this card as one of the most powerful cards to play with a mage character. This card deals important damages to all creatures, and opponents 0.5 features importance turn n
0.5 features importance turn n-4 should not play their important creatures before this card is played. However, inexperienced players are often tricked by it.
In Figure 2 (right) an important increase of the classi er con dence occurs at turn 4. Further analysis of this match shows that, similarly to the previous example, a powerful card was played. This card is called Savannah Highmane, and has important synergy with the Hunter class. As we can see here, playing this card gave an important edge to the winning player.
The previous analyses were performed on single games and identify precise strategic moves which lead to an important change in the classi er's con dence. By looking at the corresponding match data, we were able to con rm that such events, are strongly correlated with important strategic moves. In some cases, this analysis corroborates expert knowledge.
Important changes in the classi ers con dence can also be analyzed through the changes in features importance of classi ers at di erent stages of the game. For example, in the last turns of Example 1, the future loser's character loses many life points. As one can see, the classi ers for the last turns pays more attention to life points ((features 0 and 1 in Figure 3 left) than classi ers at early stages of the game ((features 0 and 1 in Figure 3 right). The opposite e ect is observed for the number of cards (features 8 and 9 in Figure 3), whose impact on the predicted outcome decreases as the game progresses. This explains the fact that, even though the future winner has less cards than his opponent in the last turns, his higher health leads to a high probability of victory.
To conclude, we are able to identify strategic moves that can corroborate current community knowledge. Moreover, through the analysis of classi ers features, we are able to nd strategic resources (health, cards or creatures) at each stage of the game. 7
In this paper, we have demonstrated how to use standard classi cation techniques to identify key strategical events in HearthStone. Our underlying hypothesis is that strategical events in HearthStone are associated with a change in the classi er prediction. In order to validate this hypothesis, we have collected a large dataset of HearthStone matches from experienced players. Then, we proposed a technique to train accurate classi ers to spot important strategical events in the dataset. We have then shown that the analysis of these events can provide strategical insights which often corroborate expert knowledge available. Such strategical knowledge would have been tedious to derive from the entire dataset.
Although the applicability of our approach was demonstrated on HS only, we have not made use of any speci city of the game. Therefore this method can also be aplied to other e-sports with a similar game structure (i.e. two players, turn based). Extending this approach to traditional sports is also an interesting challenge. Just like HS, many sports are two players games and are also turn-based to some extend. For example, in Tennis | as well as in many other net games | each player is given a limited amount of time to control the ball and take advantage of the situation. Automatic analysis of Tennis matches is signi cantly more challenging than HS matches, since both time and moves are continuous (rather than discrete in HS), but results in this domain would be very valuable for both players, and for spectators. 8
Thanks to Yann Dauxais for sharing its expertise and vast knownledge about the game.