In this paper, the authors explore the complexity of optimal play in the trading card game, Magic: The Gathering. They demonstrate that achieving optimal play in this real-world game is as difficult as solving the Halting Problem, a problem that has remained open for ten years. The authors present a methodology for incorporating an arbitrary Turing machine into a game of Magic, ensuring that the first player will win only if the Turing machine halts. Importantly, this result applies to standard tournament legal decks and does not rely on chance or hidden information. The construction also forces every move made by both players, making it highly unusual. The authors conclude by discussing the implications of their findings for a unified computational theory of games and consider the playability of such a board in a tournament setting.
https://arxiv.org/abs/1904.09828