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.
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.
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.
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).
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.
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.
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.