The complexity of deciding legality of a single step of magic: The gathering Conference Paper

Author(s): Chatterjee, Krishnendu; Ibsen-Jensen, Rasmus
Title: The complexity of deciding legality of a single step of magic: The gathering
Title Series: Frontiers in Artificial Intelligence and Applications
Affiliation IST Austria
Abstract: Magic: the Gathering is a game about magical combat for any number of players. Formally it is a zero-sum, imperfect information stochastic game that consists of a potentially unbounded number of steps. We consider the problem of deciding if a move is legal in a given single step of Magic. We show that the problem is (a) coNP-complete in general; and (b) in P if either of two small sets of cards are not used. Our lower bound holds even for single-player Magic games. The significant aspects of our results are as follows: First, in most real-life game problems, the task of deciding whether a given move is legal in a single step is trivial, and the computationally hard task is to find the best sequence of legal moves in the presence of multiple players. In contrast, quite uniquely our hardness result holds for single step and with only one-player. Second, we establish efficient algorithms for important special cases of Magic.
Conference Title: ECAI: European Conference on Artificial Intelligence
Volume: 285
Conference Dates: August 29 - September 2, 2016
Conference Location: The Hague, Netherlands
ISBN: 09226389
Publisher: IOS Press  
Date Published: 2016-01-01
Start Page: 1432
End Page: 1439
Copyright Statement: CC BY
DOI: 10.3233/978-1-61499-672-9-1432
Open access: yes (OA journal)
IST Austria Authors
Related IST Austria Work