Improving Collectible Card Game AI with Heuristic Search and Machine Learning Techniques
Shuyi Zhang · ERA: Education and Research Archive (University of Alberta) · 2017
Modern board, card, and video games are challenging domains for AI research due to their complex game mechanics and large state and action spaces. For instance, in Hearthstone — a popular collectible card (CC) (video) game developed by Blizzard Entertainment — two players first construct their own card decks from hundreds different cards and then draw and play cards to cast spells, select weapons, and combat minions and the opponent's hero. Players' turns are often comprised of multiple actions, including drawing new cards, which leads to enormous branching factors that pose a problem for state-of-the-art heuristic search methods. This thesis starts with a brief description of the game of Hearthstone and the modeling and implementation of the Hearthstone simulator that serves as the test environment for our research. Then we present a determinized Monte Carlo Tree Search (MCTS) based approach for this game and two main contributions of this approach. First, we introduce our chance node bucketing method (CNB) for reducing chance event branching factors by bucketing outcomes with similar outcomes and pre-sampling for each bucket. CNB is incorporated to the in-tree phase of the determinized MCTS algorithm and improves the search efficiency. Second, we define and train high-level policy networks that can be used to enhance the quality of MCTS rollouts and play games independently. We apply these ideas to the game of Hearthstone and show significant improvements over a state-of-the-art AI system.