Usage
  • 667 views
  • 1112 downloads

Improving Collectible Card Game AI with Heuristic Search and Machine Learning Techniques

  • Author / Creator
    Zhang, Shuyi
  • 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.

  • Subjects / Keywords
  • Graduation date
    Fall 2017
  • Type of Item
    Thesis
  • Degree
    Master of Science
  • DOI
    https://doi.org/10.7939/R34X54W6H
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
    English
  • Institution
    University of Alberta
  • Degree level
    Master's
  • Department
  • Supervisor / co-supervisor and their department(s)
  • Examining committee members and their departments
    • Buro, Michael (Computing Science)
    • Dick, Scott (Electrical & Computer Engineering)
    • Mueller, Martin (Computing Science)