Monte Carlo Tree Search experiments in Hearthstone

Published on IEEE CIG 2017

I successfully finished my master thesis under the supervision of Pedro Santos & Francisco Melo about developing an AI system for the card game Hearthstone: Heroes of Warcraft: the most popular online CCG game, with 50 million players as of April 2016.

In this work, I propose the use of Monte Carlo Tree Search (MCTS), as it is becoming a de facto standard in game AI and is particularly suited to address the chance elements in Hearthstone. In particular, I propose a modified version of MCTS which integrates expert knowledge in the algorithm’s search process.

Such integration is done, on one hand, through a database of decks that the algorithm uses to cope with the imperfect information; and, on the other hand, through the inclusion of a heuristic that guides the MCTS rollout phase and which effectively circumvents the large search space of the game.

The heuristic represents a particular game strategy, and aims at supporting the selection and simulation process.

Summarizing, the contributions are as follows:

• The first contribution consists in using a deck database to address the problem of hidden information in the game;
• The second and main contribution is the integration of a heuristic to handle the large search space of the game.