LIPIcs.FUN.2024.31.pdf
- Filesize: 3.86 MB
- 19 pages
Document
A Programming Language Embedded in Magic: The Gathering
Authors
Alex Churchill 
-
Part of:
Volume:
12th International Conference on Fun with Algorithms (FUN 2024)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2024-05-29
File
Document Identifiers
Author Details
Cite As Get BibTex
Howe Choong Yin and Alex Churchill. A Programming Language Embedded in Magic: The Gathering. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
https://doi.org/10.4230/LIPIcs.FUN.2024.31
Abstract
Previous work demonstrated that the trading card game Magic: The Gathering is Turing complete, by embedding a universal Turing machine inside the game. However, this is extremely hard to program, and known programs are extremely inefficient. We demonstrate techniques for disabling Magic cards except when certain conditions are met, and use them to build a microcontroller with a versatile programming language embedded within a Magic game state. We remove all choices made by players, forcing all player moves except when a program instruction asks a player for input. This demonstrates Magic to be at least as complex as any two-player perfect knowledge game, which we demonstrate by supplying sample programs for Nim and the Collatz conjecture embedded in Magic. As with previous work, our result applies to how real Magic is played, and can be achieved using a tournament-legal deck; but the execution is far faster than previous constructions, generally one cycle of game turns per program instruction.
Subject Classification
ACM Subject Classification
- Theory of computation → Representations of games and their complexity
Keywords
- Programming
- computability theory
- Magic: the Gathering
- two-player games
- tabletop games
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Jan Biel. How to run any program in a Magic: The Gathering Turing machine, 2019. URL: https://www.youtube.com/watch?v=YzXoFldEux4.
-
Alex Churchill, Stella Biderman, and Austin Herrick. Magic: The Gathering is Turing complete. In 10th International Conference on Fun with Algorithms (FUN 2020), 2020.
- Alex Churchill and Choong Yin Howe. Magic microcontroller simulator, April 2024. URL: https://www.toothycat.net/~hologram/Magic/MTGProgSimulatorText.html.
- Alex Churchill and Choong Yin Howe. Magic microcontroller website, April 2024. URL: https://www.toothycat.net/~hologram/Magic/.
- Choong Yin Howe and Alex Churchill. Magic microcontroller full version, April 2024. URL: https://www.toothycat.net/~hologram/Magic/Magic_Microcontroller_full.pdf.
- Choong Yin Howe and Alex Churchill. A more easily programmable system constructible in Magic: The Gathering, April 2024. URL: https://cyh31.neocities.org/amepscimtg/explanation.
- William "Huey" Jensen. Retro deck highlight: Huey’s 2002 battle of wits, June 2023. URL: https://strategy.channelfireball.com/home/retro-deck-highlight-hueys-2002-battle-of-wits/.
- Jeffrey C. Lagarias. The 3x+1 problem: An overview. The Ultimate Challenge: The 3x+1 Problem, pages 3-29, 2010. URL: https://doi.org/10.48550/arXiv.2111.02635.
- Z.A. Melzak. An informal arithmetical approach to computability and computation. Canadian Mathematical Bulletin, 4(3):279-293, 1961. URL: https://doi.org/10.4153/CMB-1961-031-9.
- Wizards of the Coast. Magic: The Gathering comprehensive rules, January 2024. URL: https://magic.wizards.com/en/rules.
- Wizards of the Coast. Magic: The Gathering tournament rules, January 2024. URL: https://wpn.wizards.com/en/rules-documents.