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.
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.
| Original language | English |
|---|---|
| Article number | 6218176 |
| Number of pages | 1 |
| Journal | Computational Intelligence and AI in Games, IEEE Transactions on |
| Volume | PP |
| Issue number | 99 |
| DOIs | |
| Publication status | Published - 2012 |