--- _id: '478' abstract: - lang: eng text: '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.' alternative_title: - Frontiers in Artificial Intelligence and Applications author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 citation: ama: 'Chatterjee K, Ibsen-Jensen R. The complexity of deciding legality of a single step of magic: The gathering. In: Vol 285. IOS Press; 2016:1432-1439. doi:10.3233/978-1-61499-672-9-1432' apa: 'Chatterjee, K., & Ibsen-Jensen, R. (2016). The complexity of deciding legality of a single step of magic: The gathering (Vol. 285, pp. 1432–1439). Presented at the ECAI: European Conference on Artificial Intelligence, The Hague, Netherlands: IOS Press. https://doi.org/10.3233/978-1-61499-672-9-1432' chicago: 'Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Complexity of Deciding Legality of a Single Step of Magic: The Gathering,” 285:1432–39. IOS Press, 2016. https://doi.org/10.3233/978-1-61499-672-9-1432.' ieee: 'K. Chatterjee and R. Ibsen-Jensen, “The complexity of deciding legality of a single step of magic: The gathering,” presented at the ECAI: European Conference on Artificial Intelligence, The Hague, Netherlands, 2016, vol. 285, pp. 1432–1439.' ista: 'Chatterjee K, Ibsen-Jensen R. 2016. The complexity of deciding legality of a single step of magic: The gathering. ECAI: European Conference on Artificial Intelligence, Frontiers in Artificial Intelligence and Applications, vol. 285, 1432–1439.' mla: 'Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Deciding Legality of a Single Step of Magic: The Gathering. Vol. 285, IOS Press, 2016, pp. 1432–39, doi:10.3233/978-1-61499-672-9-1432.' short: K. Chatterjee, R. Ibsen-Jensen, in:, IOS Press, 2016, pp. 1432–1439. conference: end_date: 2016-09-02 location: The Hague, Netherlands name: 'ECAI: European Conference on Artificial Intelligence' start_date: 2016-08-29 date_created: 2018-12-11T11:46:41Z date_published: 2016-01-01T00:00:00Z date_updated: 2021-01-12T08:00:54Z day: '01' ddc: - '004' department: - _id: KrCh doi: 10.3233/978-1-61499-672-9-1432 file: - access_level: open_access checksum: 848043c812ace05e459579c923f3d3cf content_type: application/pdf creator: system date_created: 2018-12-12T10:07:59Z date_updated: 2020-07-14T12:46:35Z file_id: '4658' file_name: IST-2018-950-v1+1_2016_Chatterjee_The_complexity.pdf file_size: 2116225 relation: main_file file_date_updated: 2020-07-14T12:46:35Z has_accepted_license: '1' intvolume: ' 285' language: - iso: eng license: https://creativecommons.org/licenses/by-nc/4.0/ month: '01' oa: 1 oa_version: Published Version page: 1432 - 1439 publication_status: published publisher: IOS Press publist_id: '7342' pubrep_id: '950' quality_controlled: '1' scopus_import: 1 status: public title: 'The complexity of deciding legality of a single step of magic: The gathering' tmp: image: /images/cc_by_nc.png legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) short: CC BY-NC (4.0) type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 285 year: '2016' ...