ERA

Download the full-sized PDF of Improving Collectible Card Game AI with Heuristic Search and Machine Learning TechniquesDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R34X54W6H

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

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

Descriptions

Other title
Subject/Keyword
Computing Science
Heuristic Search
Machine Learning
Artificial Intelligence
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Zhang, Shuyi
Supervisor and department
Buro, Michael (Computing Science)
Examining committee member and department
Buro, Michael (Computing Science)
Dick, Scott (Electrical & Computer Engineering)
Mueller, Martin (Computing Science)
Department
Department of Computing Science
Specialization

Date accepted
2017-09-12T15:10:52Z
Graduation date
2017-11:Fall 2017
Degree
Master of Science
Degree level
Master's
Abstract
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.
Language
English
DOI
doi:10.7939/R34X54W6H
Rights
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. 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.
Citation for previous publication
S. Zhang and M. Buro, “Improving Hearthstone AI by learning high-level rollout policies and bucketing chance node events,” in IEEE Conference on Computational Intelligence in Games (CIG 2017).

File Details

Date Uploaded
Date Modified
2017-09-12T21:10:53.838+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 14298232
Last modified: 2017:11:08 16:54:58-07:00
Filename: Zhang_Shuyi_201709_MSc.pdf
Original checksum: b1ad508bbdedc5539edf00ef89471983
Well formed: true
Valid: true
Page count: 53
Activity of users you follow
User Activity Date