Enhancing monte carlo tree search for playing hearthstone

Hearthstone is a popular online collectible card game (CCG). Hearthstone imposes interesting challenges in developing a search algorithm for the game AI. As a CCG, it has a considerable amount of hidden information from each player's private hand and deck. Moreover, the action space is full of stochastic actions compared to other similar games. That is, instead of a single move, each player is allowed to build a move sequence via various combinations of atomic actions. Therefore, when applying any heuristic search algorithm, the branching factor of the search space is extremely large. In this paper, we explore the use of Monte Carlo Tree Search (MCTS) with approaches to reduce the complexity of the search space and decide on the best strategy. First, we utilise state abstraction to present the search space as a Directed Acyclic Graph (DAG) and introduce a variant of Upper Confidence Bound for Trees (UCT) algorithm for the DAG. Next, we apply the sparse sampling algorithm to handle imperfect information and randomness and reduce the stochastic branching factor. This paper presents empirical evaluations of the proposed framework for Hearthstone and the experimental results suggest that our approach is well suited for developing a better AI agent.