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

Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus (2016) The complexity of deciding legality of a single step of magic: The gathering. In: ECAI: European Conference on Artificial Intelligence, August 29 - September 2, 2016, The Hague, Netherlands.

[img] Text
2016_Chatterjee_The_complexity.pdf - Published Version
Available under License Creative Commons Attribution.
[IST-2018-950-v1+1]
Download (2066Kb)
Official URL: http://dx.doi.org/10.3233/978-1-61499-672-9-1432

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.

Item Type: Conference or Workshop Item (Paper)
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
Research Group: Chatterjee Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 29 Jan 2018 09:04
Last Modified: 29 Jan 2018 09:04
URI: https://repository.ist.ac.at/id/eprint/950

Actions (login required)

View Item View Item