License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2021.9
URN: urn:nbn:de:0030-drops-127706
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12770/
Churchill, Alex ;
Biderman, Stella ;
Herrick, Austin
Magic: The Gathering Is Turing Complete
Abstract
Magic: The Gathering is a popular and famously complicated trading card game about magical combat. In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem. This provides a positive answer to the question "is there a real-world game where perfect play is undecidable under the rules in which it is typically played?", a question that has been open for a decade [David Auger and Oliver Teytaud, 2012; Erik D. Demaine and Robert A. Hearn, 2009]. To do this, we present a methodology for embedding an arbitrary Turing machine into a game of Magic such that the first player is guaranteed to win the game if and only if the Turing machine halts. Our result applies to how real Magic is played, can be achieved using standard-size tournament-legal decks, and does not rely on stochasticity or hidden information. Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable. We conclude with a discussion of the implications for a unified computational theory of games and remarks about the playability of such a board in a tournament setting.
BibTeX - Entry
@InProceedings{churchill_et_al:LIPIcs:2020:12770,
author = {Alex Churchill and Stella Biderman and Austin Herrick},
title = {{Magic: The Gathering Is Turing Complete}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {9:1--9:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Martin Farach-Colton and Giuseppe Prencipe and Ryuhei Uehara},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12770},
URN = {urn:nbn:de:0030-drops-127706},
doi = {10.4230/LIPIcs.FUN.2021.9},
annote = {Keywords: Turing machines, computability theory, Magic: the Gathering, two-player games}
}
|
Keywords: |
|
Turing machines, computability theory, Magic: the Gathering, two-player games |
|
Collection: |
|
10th International Conference on Fun with Algorithms (FUN 2021) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
16.09.2020 |
