Reducing the complexity of decision-making process in the Hearthstone simulator

Performance of a Hearthstone simulator based on MCTS can be significantly improved by applying graph theory. Creating a directed graph from gameplay actions and using it as a logical basis for the decision-making process enforces “correct” card play order. It also allows the AI to focus on tasks for choosing the most appropriate action or target.

In my previous article I have introduced a new simulator for Hearthstone called HearthMatic. The simulator is based on Monte Carlo Tree Search (MCTS) algorithm combined with heuristics represented as a set of gameplay rules for each card and deck.

The basic MCTS process for a card game is shown in Figure 1. This is a simplified game state where the player has 2 mana crystals, The Coin, Frostbolt and Mana Wyrm in hand with hero power already played. The AI should decide what the best move to play next is.

 

ReducingComplexity-1.png

Figure 1: The basic MCTS process for Hearthstone

 

Already in this simplified situation with only three possible gameplay actions we can see the complexity of the task the AI needs to solve. The root MCTS node has three candidates (and children after Expansion phase).  Finding the “obvious” best move by executing MCTS this way would require time for the algorithm which in the case of our online simulator is not available.

We can overcome this problem by constructing a directed graph with gameplay actions as vertices and play order as directed edges shown in Figure 2.

 

ReducingComplexity-2.png

Figure 2: Directed graph of gameplay actions

 

Now, when building an MCTS tree, only the source vertices from the graph are selected as candidate nodes in MCTS. In the case of complex game states, the next candidate is found by topological sort of the graph with ignoring cycle creating edges.

Implementing the graph creation prior the best move search, the MCTS tree is significantly reduced as shown in Figure 3.

ReducingComplexity-3.png

Figure 3: MCTS tree after leaving only source vertices as candidates

 

Let’s now examine a more complex game state with Acolyte of Pain on table (ready to attack), Fireblast not played and the same three cards in hand. The MCTS tree prior to extracting candidates by the graph algorithm would look as in Figure 4 (not all candidate nodes are shown to maintain the visibility).

ReducingComplexity-4.png

Figure 4: Example of a more complex game state

 

In this example, there are some unrelated gameplay actions. The graph of the gameplay is shown in Figure 5. It is assumed that Fireblast could target the friendly minion in order to draw a card.

 

ReducingComplexity-5.png

Figure 5: Directed graph with unrelated gameplay actions

 

In this graph we see two connected components in the graph. Now we only take outgoing (source) vertices as candidates for the MCTS tree, shown in Figure 6. In the case of complex graphs, each component needs to be topologically sorted in order to find next candidate(s) for the MCTS.

 

ReducingComplexity-6.png

Figure 6: MCTS tree after reduction by graph algorithm

 

This algorithm has been implemented and tested in HearthMatic. It has improved the decision-making process of the basic MCTS search for all deck archetypes especially for Combo decks.

Reihax.

HearthMatic: The missing tool for Hearthstone

In this post, we present an automated solution for developing Hearthstone strategies, planning gameplay turn-by-turn, building a “perfect” deck and checking its performance by running hundreds of simulations against other players’ decks or trending decks.

 

“Deceptively Simple. Insanely Fun.”

Yeah, we all know Hearthstone. It is insanely fun, but is it really that simple?

Is it really enough to create an account, buy (or not buy) some cards, and just start playing and being a good player? No, it’s not!

We all know that in order to even be an average player you need to plan your gameplay ahead.

How do you do that at the moment? Probably in your head. You know the cards, you know the relations between them, you know the current meta, and then what? You create some kind of plan in your head and build a deck.

Ok, how do you build a deck? By knowing all available cards and their synergies, or just going to a website and trying to use some ideas from other players’ decks.

When you’ve finally finished building your deck, what do you do next? You play several games and see that it was not everything you initially planned. Then you go back and forth, mostly recalling all the information from your head and trying to modify your “perfect” deck. After hours (or days) of checking the performance of your “revolutionary deck”, you just decide to go with another class and start all over again.

 

Here we present another way: using HearthMatic!

Inspiration for this tool came from “Magic: The Gathering” and the way how professional Magic players plan and develop their strategies, build and test their decks before attending a tournament. (For really enthusiastic players we recommend a great book by Patrick Chapin “Next Level Deck Building”.)

 

So, let’s start.

When starting with strategy planning and deck building, The Magic players are at an advantage of having real paper cards in their hands. They are able to put them on a table, reorder them as they like and think about solving a puzzle of building their next “killer” deck.

In HearthMatic we start the same way, but instead of building a deck from a pageable list of cards we give our users the possibility to freely add and position cards on the screen just like ordinary paper cards on a table.

If we decide to build our deck using the Top-Down approach, we can start with some card that will be the backbone of our strategy and go on adding more cards that support our initial idea. HearthMatic supports this approach by having the possibility to add cards by relation (Figure 1). We select a card that we want to support, and a list of cards in relation with the selected card appears in the left portion of the screen.

AddByRelations1.jpg

Figure 1: Quickly find related cards and inspect relations in deck

 

After this step, we can use the Bottom-Up approach and analyze what is NOT present in our deck by inspecting its deck coverage (Figure 2, Figure 3).

AddByDeckCoverage1.jpg

Figure 2: Add cards by deck coverage

 

AddByCoverageTag2.pngFigure 3: Find gaps and plan turn-by-turn gameplay

 

If we are confident enough in our deck we can run quick simulations against another player’s deck on the HearthMatic website. HearthMatic simulator is based on the MCTS (Monte Carlo Tree Search) algorithm with the possibility for advanced players to include their knowledge about the game in the decision-making process of the simulator. This knowledge is recorded as a set of rules for each card that serve as suggestions to the simulator, but are not mandatory. The rules are already predefined (Figure 4) but the users are allowed to change them as they like. This way, the simulator is spared from calculating “stupid” moves and figuring out that they were stupid, so instead of that the simulator has more time to spend on trying out the “good” moves to deliver better results. Best results are obtained when running 20 or more simulations for one deck.

StartSimulation1.jpg

Figure 4: Set custom rules for simulation (not mandatory)

 

When starting a simulation, users are allowed to choose random or specific community or private decks as opponent decks (Figure 5).

StartSimulation2.jpg

Figure 5: Choose opponent deck(s) for simulation

 

Once the simulations are done we can further analyze our deck’s performance by inspecting Bottom-Up diagrams (Figure 6) and also Gameplay Actions by Card diagrams (Figure 7).

BottomUp.jpg

Figure 6: Bottom-Up diagrams give insights about deck/card performance

 

ActionsByCard.jpg

Figure 7: Gameplay actions by card

 

Next, we can perform Backwards analysis and check step by step from the end of the game what went well and what went badly. For this analysis HearthMatic lets you go through Gameplay turn-by-turn (Figure 8).

Gameplay.jpg

Figure 8: Analyze simulation results turn-by-turn

 

The important thing is that HearthMatic allows you to perform systematic analysis, helps you with data from a database instead of having to keep it all in your head (think of completely new players) and saves you time by simulating dozens of matches in a matter of minutes, that you would normally spend playing real games in order to tune your deck.

A forward approach of deck building is supported in HearthMatic by giving the possibility to create synergy snippets from cards. This way, we define a group of cards that we want to play early or later in the game (Figure 9). Then, instead of starting a deck with a single card, we can start with a synergy snippet and then add cards by relation.

Snippets.png

Figure 9: Define your strategy snippets

 

Other options for adding cards are:

  • by frequency: sorted list of most frequently used cards for a defined class and archetype
  • by simulation results: sorted list of cards that performed well in simulations
  • by filters like card mechanic, card type, race, rarity etc.

AddCards.jpg

Figure 10: Add cards options

 

That is it for now.

HearthMatic at its current stage is a work in progress and we plan to improve some features (like Gameplay Viewer) as well as add new features (like custom cards support) and we would be grateful if you could send us your suggestions and critiques by using the annoying Feedback button on the bottom of the page.

 

Thank you for taking the time to read this post,

Reihax.

 

TL;DR Website made for Hearthstone players that lets you interactively build decks and even simulate matches with your own decks in order to make deck building, strategy planning and deck tuning way easier.