By the same authors

From the same journal

From the same journal

Ensemble Determinization in Monte Carlo Tree Search for the Imperfect Information Card Game Magic: The Gathering

Research output: Contribution to journalArticle

Author(s)

Department/unit(s)

Publication details

JournalComputational Intelligence and AI in Games, IEEE Transactions on
DatePublished - 2012
Issue number99
VolumePP
Number of pages1
Original languageEnglish

Abstract

In this paper, we examine the use of Monte Carlo
Tree Search (MCTS) for a variant of one of the most popular and
profitable games in the world: the card game Magic: The Gathering
(M:TG). The game tree for M:TG has a range of distinctive
features, which we discuss here, and has incomplete information
through the opponent’s hidden cards, and randomness through
card drawing from a shuffled deck. We investigate a wide range
of approaches that use determinization, where all hidden and
random information is assumed known to all players, alongside
Monte Carlo Tree Search. We consider a number of variations
to the rollout strategy using a range of levels of sophistication
and expert knowledge, and decaying reward to encourage play
urgency. We examine the effect of utilising various pruning
strategies in order to increase the information gained from each
determinization, alongside methods that increase the relevance of
random choices. Additionally we deconstruct the move generation
procedure into a binary yes/no decision tree and apply MCTS to
this finer grained decision process. We compare our modifications
to a basic MCTS approach for Magic: The Gathering using fixed
decks, and show that significant improvements in playing strength
can be obtained.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations