Decision-Making in Hearthstone Based on Evolutionary Algorithm
Eiji Sakurai, Koji Hasebe
Department of Computer Science, University of Tsukuba, Japans2120594@s.tsukuba.ac.jp, hasebe@cs.tsukuba.ac.jp

Keywords:

Game AI, Hearthstone, Decision-Making, Rolling Horizon Evolutionary Algorithm.

Abstract:

Hearthstone is a two-player turn-based collectible card game with hidden information and randomness. Generally, the search space for actions of this game grows exponentially because the players must perform a seriesof actions by selecting each action from many options in each turn. When playing such a game, it is often
difﬁcult to use a game tree search technique to ﬁnd the optimal sequence of actions up until the end of a turn.
To solve this problem, we propose a method to determine a series of actions in Hearthstone based on an evolutionary algorithm called the rolling horizon evolutionary algorithm (RHEA). To apply RHEA to this game, we
modify the genetic operators and add techniques for selecting actions based on previous search results and forﬁltering (pruning) some of the action options. To evaluate the effectiveness of these improvements, we implemented an agent based on the proposed method and played it against an agent based on the original RHEA for
several decks. The result showed a maximum winning rate of over 97.5%. Further, our agent played against
the top-performing agents in previous competitions and outperformed most of them.

1 INTRODUCTION
With the rapid advance in artiﬁcial intelligence technologies, many studies have been made on the development of agents playing games. In particular, many
researchers have paid attention to games with hidden
information and randomness, such as poker, mahjong,
and collectible card games.
Hearthstone (Blizzard Entertainment, nd) is a collectible card game classiﬁed into a two-player turnbased imperfect information game. In this game, eachplayer composes a bunch (called a deck) of 30 cardsof more than 1,000 different types of cards and playswith them. The game progresses while alternatingturns between two players, and the player who uses
the deck on hand in their turn and eventually reduces
the opponent’s health to 0 wins.
Typically, in collectible card games, the search
space grows exponentially because players select asequence of actions from numerous options at eachturn. Many previous studies, such as (Zhang andBuro, 2017; Świechowski et al., 2018; Choe and Kim,
2019), have used tree search techniques for collectible
card games. However, ﬁnding the optimal sequenceof actions to take to the end of the turn using a tree
search within time constraints is often difﬁcult.
To solve this problem, in this study, we propose a method for determining a sequence of ac-

tions in Hearthstone based on the evolutionary algorithm called the rolling horizon evolutionary algorithm (RHEA) (Perez et al., 2013). In RHEA, eachindividual has a sequence of genes that represents a
series of behaviors in a certain interval. Furthermore,each individual is given a ﬁtness value obtained byevaluating the state reached through its series of actions. From a set of individuals, those with high ﬁtness are selected, and a new generation is generated
by crossover and mutation. The optimal sequence ofactions is eventually determined by repeating this process.
Despite being a versatile genetic algorithm, applying the RHEA directly to decision-making in Hearthstone is difﬁcult. Therefore, our proposed method has
the following three improvements. The ﬁrst improvement is to modify the genetic operators to account for
subsequent actions. The second improvement is touse a tree structure based on the study of Perez et al.
(Perez Liebana et al., 2015) to store and reuse statistical information obtained from previously generated
individuals. Finally, the third improvement is to ﬁlter action options (i.e., pruning) so that the series ofactions in a turn is consistent.
In this study, we evaluated the effectiveness ofthese improvements by playing game against an agent
based on the original RHEA. The result showed thatthe maximum winning rate of the proposed method

was 97.5% when using a deck called MidrangeJadeShaman.
Furthermore, to evaluate the performance of our
proposed method, we played our agent against several agents that achieved high performance in thepast Hearthstone AI Competitions (Dockhorn andMostaghim, 2019). According to the results, ouragent outperformed most of them for several decks.
The remainder of this paper is organized as follows. Section 2 explains the related work. In Section 3, we provide an overview of the background of
this study. Section 4 describes our proposed methodfor determining the optimal sequence of actions inHearthstone based on RHEA. In Section 5, we present
the results of the evaluation by experiments. Finally,
Section 6 concludes the paper and presents futurework.

2 RELATED WORKIn research on decision-making in Hearthstone, many
attempts based on Monte Carlo Tree Search (MCTS)(Browne et al., 2012) have been proposed. Choe etal.’s study (Choe and Kim, 2019) suppressed the expansion of search trees by abstraction and sampling.
Some studies (Zhang and Buro, 2017; Świechowski
et al., 2018; Wang and Moh, 2019) have improved
the accuracy of state evaluation by combining neuralnetworks. A study (Dockhorn et al., 2018) presented
a method for estimating the opponent’s hand basedon the cards used by the opponent immediately before. Furthermore, a study (Dockhorn et al., 2018)
extended the method of (Bursztein, 2016) to improve
MCTS by estimating the opponent’s deck.
Furthermore, studies have been conducted on theapplication of the RHEA to game-solving. In particular, there were many attempts at utilizing past search
information in research (Perez Liebana et al., 2015;
Gaina et al., 2017) that applied the RHEA to a framework called general video game AI (GVGAI). GVGAI is a framework for handling relatively simple
games, such as Space Invaders and puzzle games.
A study (Justesen et al., 2016) proposed a method
called online evolutionary planning (OEP) to apply
RHEA to a turn-based strategy game, which determined a series of actions based on an action planrather than a single action decision. In a study(Dockhorn et al., 2021) that applied the RHEA to areal-time strategy game, the RHEA was not used tosearch the action space but to search the script space,
where actions were abstracted. In each of (Justesen
et al., 2016) and (Dockhorn et al., 2021), experiments
showed that the RHEA-based agents were superior to

MCTS in several cases.
Generally, for collectible card games with many
options, it is often difﬁcult for the MCTS to ﬁnd the
optimal series of actions until the end of a turn withina time limit. On the other hand, RHEA is expected toperform decision-making for actions considering thegoal of the turn because it searches based on the stateevaluation after executing a series of actions.

3

BACKGROUNDThis section outlines the rules of Hearthstone (in Section 3.1) and RHEA (in Section 3.2), which are prerequisites for this study.

3.1

Rules of Hearthstone

A match in Hearthstone consists of two phases,
namely, deck-building and battle, as described below.
3.1.1

Deck-Building Phase

A player selects 30 cards from among the cards thatcan be used by the selected hero and bundles them
together to complete the deck.
The cards used in Hearthstone are classiﬁed into
the following three types.
Minion: This can be summoned to the battleﬁeld byplaying from hand. A minion consists of healthand attack, and they are removed when the healthof a minion on the battleﬁeld reaches 0.
Spell: Players can use the effect of a card by playing
it from their hand.
Weapon: This can be equipped on heroes. A
hero equipped with a weapon acquires the attack
power.
Each card has a cost, and when a card is used, a player
needs to pay the card’s cost from the resource called
mana crystal.
3.1.2

Battle Phase

A hero’s health is set to 30 at the start of a battle,
and the ﬁrst player draws cards from their deck tomake a hand of three cards. The second player draws
one more card from their deck and add a special card
called a coin, to make their hand ﬁve cards. After
that, each player aims to reduce the opponent’s hero’s
health to 0 while taking turns. Here, we note that,for each player, the state of the game is only partiallyvisible, and some information is hidden.

The player who takes the ﬁrst turn adds one cardfrom the shufﬂed deck to the hand. At this time, theupper limit of mana crystal is increased by 1. Mana
crystal increases up to its capacity of 10 as the turnprogresses. Then, the player can perform multiple actions, such as paying mana crystal to play cards orattacking minions if they are on the battleﬁeld.

3.2 Rolling Horizon Evolutionary
Algorithm (RHEA)

A

B

C

D

?

E

F

G

H

?

I

J

K

L

?

2

A

B

C

D

0.6

E

F

G

H

0.8

I

J

K

L

0.7

3

M

N

O

P

0.9

E

F

G

H

0.8

I

J

K

L

0.7

4

Crossover

5

M

7

F

O

6

Mutation

H

0.7

Q

R

E

S

N

G

T

1.0

Best individual

P

0.6

I

J

C

L

0.8

Q

Execution

5. Evaluate the generated new individuals.
6. Repeat Steps 2-5 until the time limit is reached.
7. The ﬁrst action of the individual with the highest
ﬁtness value is selected when determining an action.
8. Transition to the next state and search for the second action, which is the next action from Step 1.

RHEA (Perez et al., 2013) is a type of evolutionary algorithm for decision-making that replaces tree searchin games with real-time state transitions. Each individual comprises a sequence of genes and a ﬁtness
value. The former represents a series of actions, while
the latter indicates the evaluation of the state obtained
when performing a series of actions. Similar to othergenetic algorithms, RHEA searches for the optimal
sequence of actions by repeatedly changing generations through genetic manipulations.
Figure 1 shows the optimization procedure by
RHEA. Here, the numbers in the ﬁgure correspond to
the step numbers in the following description. Also,
each alphabet surrounded by a square represents an
individual action, and a mass consisting of them represents a sequence of actions.
1and actions are randomly selected. This generates
an individual with a new set of behaviors.

8

Figure 1: Steps for action decision based on RHEA.

1. Perform a series of actions at random, generate
multiple individuals, and form an initial population.
2. Evaluate each individual. The ﬁtness of an individual is the evaluation value of the state after performing a series of actions.
3. Select individuals with high ﬁtness through tournament or elitism selection.
4. Generate new individuals from selected individuals through genetic operators. In a crossover,the behavior of two individuals is randomly exchanged through a uniform crossover. In mutation, the mutation point is determined at random,

As shown above, RHEA searches solely on the evaluation value of the state after executing a series of actions, thereby allows for action decisions to be madein anticipation of the ﬁnal state of the turn.

4

DECISION-MAKING WITH
RHEA

Our method for decision-making in Hearthstone isbased on the idea of RHEA. A more speciﬁc search
procedure is as follows. First, an initial population is
generated. Second, crossover and mutation are performed for each individual contained in the population. At this time, a statistical tree constructed on thebasis of the ﬁtness possessed by the generated individuals is used. In the initialization and mutation, options are pruned by a ﬁlter that encourages consistentaction decisions. The game transitions to the next stepby selecting and executing the ﬁrst action of the bestindividual in the last generation when deciding on anaction. Then, the initial population is generated again
to search for the next action, and new individuals are
generated through genetic operators. The above procedure is repeated until the end of turn.
A more detailed description is provided below.
Section 4.1 ﬁrst explains the statistical tree. Section
4.2 describes the new genetic operators. Section 4.3
describes how to evaluate the ﬁtness of each individual. Finally, Section 4.4 describes ﬁltering for action
selection.

4.1

Statistical Tree
Search tree

Population
A

C

H 0.7

B

E

I

A

D

Store the fitness

A
0.8

B

+0.7

C

0.3

D

E

F

+0.7

G

H

I

+0.7

Figure 2: Store the ﬁtness in a statistical tree.

In the proposed method, to reuse the information
obtained by searching during evolution, the information is stored in a tree structure using the techniques of(Perez Liebana et al., 2015) and (Gaina et al., 2017).
Figure 2 shows how the ﬁtness value of individuals
is stored in a statistical tree. Here, the value storedin each node is a pair of the evaluation value and thenumber of visits at a node. Because this search tree
does not store the state of the game, nodes are determined only by actions. Therefore, the expansion of
the search tree can be suppressed, even if an action
or state transition, including randomness, occurs. In
addition, this statistical tree can construct another tree
whose root is the node that can be reached by that action when a certain action is determined and executed.
In the proposed method, the Upper Conﬁdence
Bound (UCB) (Kocsis and Szepesvári, 2006), deﬁned
by the following equation, is used for crossover andmutation.
√
{
}
V
(s,
a)
ln N(s)∗a = arg max+C.
(1)
N(s, a)N(s, a)aMeanwhile, elitism selection is a selection methodthat selects and retains n individuals with high evaluation values from the population. Tournament selection may lead to a more diverse selection of individuals than elitism selection, which simply selects only
individuals with high evaluation values, but may omit
the best individuals of the current generation. Therefore, it is supplemented by elitism selection, which
selects individuals with high ﬁtness values.
4.2.2

Crossover
Population
Parents

1

A

B

C

D

E

A C H 0.7

F

G

E

B

E

A D

I

0.8
0.3

UCB or random
selection

2Children

3

G

Repeat

C

G

B

F

E

0.8

C

G

D

E

0.6

Evaluation

Figure 4: Crossover based on the search information.

Here, s represents the current node, N(s) represents
the number of visits to the current node, V (s, a) denotes the cumulative evaluation value of the next
nodes reached by action a, N(s, a) represents the number of visits to the next node that selected the actiona, and C denotes the search coefﬁcient. It is possible
to prioritize and search for promising actions while
maintaining a balance between exploration and exploitation, because this formula selects actions withhigh evaluation values and actions with low visit
counts.

4.2 Genetic Operators
4.2.1 Selection&'(()*+,-)*)(.+/0*8)9+,-)*)(.+/0*
23/+/45,4)3)6+/0*

!

"

# !"#

!

"

# !"#

$

%

&

!"$

!

'

!"%

!

'

!"%

$

(

!"1

70'(*.5)*+,4)3)6+/0*

Figure 3: Tournament selection and elitism selection.

Tournament selection and elitism selection are
combined to generate a population to choose for the
next generation. Figure 3 shows the selection of individuals by tournament and elitism selection. Tournament selection is a selection method that randomly selects n individuals from the population of the current
generation and chooses the individuals with the highest evaluation value among the selected individuals.

Figure 4 shows an example of individual generation by crossover. The procedure for crossover isshown below, where the numbers in the ﬁgure correspond to the numbers in the following description:
1. Sequentially select one individual from the population of the current generation and select anotherrandomly.
2. Select one individual with a probability of 50%,and select the feasible action using the UCB. At
this time, if an executable action does not exist
in the search tree, that action is selected with acertain probability. Thereafter, one individual isselected again with a probability of 50%, and theaction is selected in the same manner. Repeat thisoperation until the end of the turn to generate aseries of actions.
3. The evaluation value of the state after executing a
new series of actions is the ﬁtness of the individual.
Our method probabilistically select a parent to inherit the behavior and generate a new individual byinheriting good behavior from the parent’s series of
behaviors by random selection or selection based on
the UCB. Thus, it is possible to generate a series ofactions that tend to be highly evaluated without generating unfeasible actions.
Either random selection or selection based on the
UCB is performed by γ N(s) when inheriting the parent’s behavior. Here, γ (0 ≤ γ ≦ 1) represents the attenuation rate, and N(s) represents the number of vis-

its to the current node s that can be reached by actions
thus far. According to this value, if the search information is sufﬁcient, the search is performed by selection based on the UCB with a high probability; otherwise, the search is performed by random selection.
Random selection is also performed when search information about the current node does not exist.
4.2.3 Mutation:%96-'/0%(

!

!

"

#

$

! "

# $%&

'

)

(

$%*

%
! +

"

!

"

#

$

%

#

!

"

'

&

(

%

$

!

"

'

&

(

%

$%,

7'()%*$+,-,./0%($%8$*6/'/,)$9%0(/!"#$%&$&'()%*$+,-,./0%(

12345'-6'/0%(

Figure 5: Mutation based on search information.

Figure 5 shows an example of generating an individual by mutation. The mutation procedures areshown below, where the numbers in the ﬁgure correspond to those in the following description:
1. Select one individual from the population of thecurrent generation.
2. Randomly determine mutation points.
3. For each subsequent action, choose an action either randomly with a rate γ N(s) or based on the
UCB. Repeat this until the end of the turn to generate a series of actions.
4. The evaluation value of the state after executing a
new series of actions is the ﬁtness of the individual.
Therefore, in our method, after randomly determining the mutation point, all subsequent behaviors
are mutated. For each behavioral mutation, two mutations are used: random mutation and mutation basedon search information. The former selects randomly
from the current viable options, whereas the latterselects the action using UCB. Similar to crossover,in mutation, the selection method is determined by
γ N(s) , and as the number of visits to nodes that canbe reached by actions increases, the ratio of random
mutations decreases, and the ratio of mutations basedon search information increases.

4.3 Evaluation of Individuals
Evaluating the state after executing a series of actions
is necessary to evaluate an individual. Our method

uses random playouts often used in MCTS. In addition, to determine the opponent’s deck and hand forthe simulation of the opponent’s actions, our method
randomly determines the cards included in the opponent’s deck from the observable information of the
opponent’s hero class. Furthermore, the opponent’s
hand is determined by taking it out from the generated
deck so that it matches the actual number of cards inthe hand.
In addition, our method abstracts card locationand other information, and keeps the abstracted stateand evaluation values. Therefore, evaluation can bedone without playouts.

4.4

Filtering for Consistent Action
Selection

In Hearthstone, consistent action decisions are required to execute a series of actions in one turn.
Therefore, eliminating unnecessary options from theimmediately preceding action and the current state
would allow for consistent action selection.
In the proposed method, a ﬁlter is used when initialization and during mutation, and a ﬁlter is randomly applied from ﬁve ﬁlters other than the turn end
when selecting actions. Moreover, the same ﬁlter isapplied to subsequent action selections until the ﬁlter
becomes inapplicable. Here, a ﬁlter cannot be applied
if all options are blocked, in which case another ﬁlter
is applied. If there is no applicable ﬁlter, a ﬁlter otherthan the turn end is applied only for one action, andin subsequent action selections, it is once more randomly applied from among the ﬁve types of ﬁlters.
Direct Attack: This ﬁlter keeps the action of attacking the opponent’s hero.
Destroy minion: This ﬁlter keeps actions that damage destructible minions. Here, a certain minion isdestructible if the health of the minion is less thanor equal to the total attack value of its minion.
Deploy minion: This ﬁlter keeps the action of summoning minions. In addition, this ﬁlter keep spells
and hero powers that summon effect.
Protection: This ﬁlter keeps the summoning of minions with taunts and actions that block opponent
attacks to mitigate health loss.
Keep hand: This ﬁlter calculates the average cost of
the cards in player’s hand and keeps actions thatplay card below that value.
Except turn end: This ﬁlter is applied when none of
the above ﬁve ﬁlters is left with any options left.
This ﬁlter keeps the action except for the end of
the turn.

5 EXPERIMENTS
To evaluate the effectiveness of the proposed method,
we conducted the following two experiments. First,
to evaluate the effectiveness of the improvements
explained in the previous section, we performed
matches against an agent based on the original RHEA
(called Vanilla RHEA) and measured the winning
rate Second, we measured the winning rate of ouragent against conventional agents submitted in past
Hearthstone AI Competitions to demonstrate the performance of our method.

5.1 Experimental Settings
As the environment of the experiments, we used SabberStone (Dockhorn and Mostaghim, 2019), which
was used in Hearthstone AI Competitions. In our experiments, there is no re-drawing of cards, and thetime limit per turn is set to 30 s to conform to therules of the competition. The turn end is forcibly selected if the time limit is exceeded when deciding onan action. Furthermore, the match may be prolonged
depending on the deck and will be treated as a draw
if it exceeds 25 turns. In the experiments, three decks
were used: MidrangeJadeShaman, AggroPirateWarrior, and CubeWarlock, which are deﬁned in a website(Hearthstone Top Decks, nd).
In addition, during action search, our method assumed a population size of 50 with a tournament sizeof 2 and an elite size of 1. During state evaluation,
our method generates 20 game states, and performs
20 random playouts for each state.

AlvaroAgent: This agent searches for actions iteratively based on the UCB using the optimized evaluation functions.
Monte Carlo graph search (MCGS): It is possible
to search for actions even after the end of the turnby suppressing the expansion of the search tree
used in the MCTS by abstracting, sampling, andpruning the state and assuming that the opponent’s
actions are random.
TycheAgent: This agent uses a random search, andonly the ﬁrst action with a high evaluation value
is selected after a certain number of iterations. It
uses a complex evaluation function for the stateevaluation.

5.3

Search Performance Evaluation

5.3.1

Impact of genetic operators and statisticaltree on performance

We measured the winning rate against Vanilla RHEA
to evaluate the effectiveness of the proposed genetic
manipulation and the statistical trees. The results areshown in Figure 6. Here, the genetic manipulation
rate is set to 50% in both cases, and the ﬁlter describedin Section 4.4 is not used. Combinations of methods
and settings that constitute each method are expressedusing the following abbreviations.
• VC: uniform crossover.
• VM: point mutation.
• PC: crossover by the proposed method (see Section 4.2.2).

5.2 Opponent Agents• PM: mutation by the proposed method (see Section 4.2.3).

The opponents used in the experiments were as follows. Here, except for vanilla RHEA and MCTS, theagents who have excelled in previous Hearthstone AI
Competitions.

• γ : ratio of random selection (see Section 4.2.2).

Vanilla RHEA: This is an agent developed for comparative experiments to evaluate the effectivenessof our improvements. This agent is based on theoriginal RHEA algorithm, which searches by genetic operators based on point mutation and uniform crossover.
Vanilla MCTS: This is a general MCTS-based agent
implemented for comparison of the search aspectwith the proposed method.
DynamicLookAhead (DLA): This agent uses simple evaluation function to evaluate the state, andsearches actions through depth-ﬁrst search with adynamically limited depth.

In Figure 6, the vertical axis presents the list ofagents, each of which represents a possible combination of the components, whereas the horizontal
axis indicates the winning rate against Vanilla RHEA.
Here, the orange, green, and gray graphs show thewinning rates when using the decks called MidrangeJadeShaman, AggroPirateWarrior, and CubeWarlock,respectively.
The results show that there was no signiﬁcant difference between the proposed method and Vanilla
RHEA when search information was not used (i.e.,γ = 1.0). However, it was observed that the winning rate of the proposed method was signiﬁcantly
improved compared with Vanilla RHEA when search
information was used (i.e., γ ̸= 1.0). In particular,
the winning rate of the agent with PC, PM, and γ =0.0 when using MidrangeJadeShaman improved to aMidrangeJadeShaman

PC, VM, γ = 1.0
VC, PM, γ = 1.0
PC, PM, γ = 1.0
PC, VM, γ = 0.8
VC, PM, γ = 0.8
PC, PM, γ = 0.8
VC, VM, γ = 0.8
PC, VM, γ = 0.6
VC, PM, γ = 0.6
PC, PM, γ = 0.6
VC, VM, γ = 0.6
PC, VM, γ = 0.0
VC, PM, γ = 0.0
PC, PM, γ = 0.0
VC, VM, γ = 0.0

AggroPirateWarrior
CubeWarlock

zontal axis represents the winning rate. The colors of
the graph are the same as in Figure 6.
This result shows that using the ﬁlter improved
the winning rate when using CubeWarlock to a maximum of 78.5% and MidrangeJadeShaman to a maximum of 65.5%. This was because CubeWarlock andMidrangeJadeShaman tended to have more action options than AggroPirateWarrior, and the search performance was improved by ﬁltering out inconsistentchoices. On the other hand, it was possible to search
sufﬁciently without using a ﬁlter when using AggroPirateWarrior, which did not have many choices,
so the change in the winning rate was small.

5.4

Winning rate

Figure 6: Match results against Vanilla RHEA.

maximum of 97.5%. This was because the selection
based on the UCB during genetic manipulation could
generate many highly rated individuals with a promising set of behaviors. As a result, the proposed method
can search for promising series of action in the next
generation.
5.3.2 Impact of genetic operators’ rate andﬁlters on performance
We also conducted experiments to measure changes
in the performance by varying the ratio of mutations
and crossovers and by using a ﬁlter. We used an agent
that applied the proposed crossover (PC) and mutation (PM) to genetic operators based on the experimental results presented in Section 5.3.1. Here, theratio of random selection ( γ ) was set to 0.0. The results are presented in Figure 7.
MidrangeJadeShaman
AggroPirateWarrior
CubeWarlock

25:75, without filter
75:25, without filter
50:50, with filter
25:75, with filter

75:25, with filter
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

Winning rate

Figure 7: Winning rates against agents with PC, PM, γ =0.0.

In this ﬁgure, the vertical axis presents the list ofagents with different genetic manipulation rates andthe presence or absence of ﬁltering, whereas the hori-

To demonstrate the performance of our method, we
performed matches between an agent based on the
proposed method and agents that achieved remarkable results in past Hearthstone AI Competitions. Figure 8 shows the winning rate of our agent against
those agents. In this experiment, only decks called
MidrangeJadeShaman and AggroPirateWarrior wereused. Some other decks have been implemented, butthey were not used because of a lack of cards. Here,as the difference in performance is expected to increase depending on the state evaluation method, weused the state evaluation function implemented in AlvaroAgent for game state evaluation.
Vanilla MCTS

Opponents

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

Performance Comparison with
Conventional Methods

AlvaroAgent
Dynamic
Lookahead
TycheAgentMidrangeJadeShaman
MCGS
AggroPirateWarrior
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

Winning rate

Figure 8: Winning rates of the proposed method against existing agents.

In Figure 8, the vertical axis presents the list of
the opponents, while the horizontal axis represents
the winning rate of the proposed method. This ﬁgure
demonstrates that the proposed method is as strongas or stronger than almost all other agents, regardless of which deck is used. In particular, the proposed method outperforms AlvaroAgent, which has
the same state evaluation function, by an average of
53%, suggesting that the proposed method is equallyor even better than AlvaroAgent at searching for actions. On the other hand, when using AggroPirateWarrior, the win rate was 40% against MCGS. This

is most likely because MCGS has an ingenious wayof pruning options even when conducting playouts,
which was more powerful than the state evaluation
function for the relatively simple deck of AggroPirateWarrior, which was able to correctly evaluate thestate of the game.

6 CONCLUSIONS AND FUTURE
WORKIn this paper, we proposed a method for decisionmaking for actions in Hearthstone based on the
RHEA. To apply the RHEA to Hearthstone, we improved the original algorithm by introducing techniques of genetic manipulation, utilizing past search
information, and ﬁltering action options.
We implemented agents based on the proposed
method and the original RHEA to evaluate the effectiveness of the proposed method. The results
showed that the winning rate for each improvement
was higher than that without the improvement. Furthermore, our agent played against the top-performing
agents in past Hearthstone AI Competitions and outperformed most of them.
In future work, we would like to investigate theperformance improvement by parameter tuning because the proposed method has various hyperparameters. We are also interested in improving search efﬁciency. Speciﬁcally, we shall attempt to take over better individuals found during the previous search steps
instead of generating the initial group only at random.

REFERENCES
Blizzard Entertainment (n.d.). Hearthstone ofﬁcial website. Retrieved November 24, 2022, from https://playhearthstone.com.
Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M.,
Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez,D., Samothrakis, S., and Colton, S. (2012). A surveyof monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games,
4(1):1–43.
Bursztein, E. (2016). I am a legend: Hacking hearthstone using statistical learning methods. In 2016 IEEE
conference on computational intelligence and games(CIG), pages 1–8. IEEE.
Choe, J. S. B. and Kim, J.-K. (2019). Enhancing montecarlo tree search for playing hearthstone. In 2019
IEEE Conference on Games (CoG), pages 1–7. IEEE.
Dockhorn, A., Frick, M., Akkaya, Ü., and Kruse, R.
(2018). Predicting opponent moves for improving
hearthstone ai. In International Conference on Infor-

mation Processing and Management of Uncertainty inKnowledge-Based Systems, pages 621–632. Springer.
Dockhorn, A., Hurtado-Grueso, J., Jeurissen, D., Xu, L.,
and Perez-Liebana, D. (2021). Portfolio search andoptimization for general strategy game-playing. In
2021 IEEE Congress on Evolutionary Computation(CEC), pages 2085–2092. IEEE.
Dockhorn, A. and Mostaghim, S. (2019).
Introducing the hearthstone-ai competition. arXiv preprint
arXiv:1906.04238.
Gaina, R. D., Lucas, S. M., and Perez-Liebana, D. (2017).
Rolling horizon evolution enhancements in generalvideo game playing. In 2017 IEEE Conference on
Computational Intelligence and Games (CIG), pages
88–95. IEEE.
Hearthstone Top Decks (n.d.). Retrieved November 24,
2022, from https://www.hearthstonetopdecks.
com/.
Justesen, N., Mahlmann, T., and Togelius, J. (2016). Online
evolution for multi-action adversarial games. In European Conference on the Applications of Evolutionary
Computation, pages 590–603. Springer.
Kocsis, L. and Szepesvári, C. (2006). Bandit based montecarlo planning. In European conference on machinelearning, pages 282–293. Springer.
Perez, D., Samothrakis, S., Lucas, S., and Rohlfshagen, P.
(2013). Rolling horizon evolution versus tree search
for navigation in single-player real-time games. In
Proceedings of the 15th annual conference on Genetic
and evolutionary computation, pages 351–358.
Perez Liebana, D., Dieskau, J., Hunermund, M.,
Mostaghim, S., and Lucas, S. (2015). Open loop
search for general video game playing. In Proceedings of the 2015 Annual Conference on Genetic andEvolutionary Computation, pages 337–344.
Świechowski, M., Tajmajer, T., and Janusz, A. (2018). Improving hearthstone ai by combining mcts and supervised learning algorithms. In 2018 IEEE Conference on Computational Intelligence and Games(CIG), pages 1–8. IEEE.
Wang, D. and Moh, T.-S. (2019). Hearthstone ai: Oops towell played. In Proceedings of the 2019 ACM Southeast Conference, pages 149–154.
Zhang, S. and Buro, M. (2017). Improving hearthstone ai
by learning high-level rollout policies and bucketing
chance node events. In 2017 IEEE Conference on
Computational Intelligence and Games (CIG), pages
309–316. IEEE.