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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s