vix.ing · top · new · best · stats · spec

Magic: The Gathering is Turing Complete

Determining the outcome of a Magic: The Gathering game with forced moves is undecidable.

2019/03/24 by Alex Churchill, Stella Biderman, Churchill, Alex +3 · 34 voices · 5 citations
#cs.AI #cs.CC #cs.LO

paper · pdf · doi:10.48550/arxiv.1904.09828

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, solving a problem that has been open for a decade. 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.

Summary

The paper demonstrates that a universal Turing machine can be embedded into a two-player game of Magic: The Gathering using tournament-legal decks. This proves that determining the winner of a game where all remaining moves are forced is non-computable, answering an open problem in algorithmic game theory.

machine-generated · gemma4:31b

In simple words

Imagine a card game where you can use special cards to make other cards do exactly what a computer does. The writers found a way to set up the game so that one person wins only if a certain computer program finishes its work. Because some computer programs never finish, it is impossible to know for sure who will win just by looking at the game board.

machine-generated · gemma4:31b

Outline

machine-generated · gemma4:31b

Argument

  1. A universal Turing machine (UTM) can be simulated using Magic: The Gathering cards.
    The authors provide a detailed construction using creature tokens for the tape, modified Rotlung Reanimators for logic, and specific spells to force movement and reading.
  2. The game's outcome (Alice winning) can be tied directly to whether the simulated UTM halts.
    The construction uses Coalition Victory as a win condition that is only met if the halt symbol is read, triggering the creation of a blue creature.
  3. Determining if a Turing machine halts is undecidable (the Halting Problem).
    Citation of standard computational theory.
  4. Therefore, determining the outcome of a Magic: The Gathering game is undecidable.
    Logical deduction from the embedding of the UTM and the tie to the Halting Problem.

machine-generated · gemma4:31b

Assumptions

machine-generated · gemma4:31b

Claims

machine-generated · gemma4:31b

Proof sketch

  1. The authors embed a universal Turing machine (UTM) into a game of Magic: The Gathering.
  2. They use creature tokens with specific power/toughness to represent the tape and creature types to represent symbols.
  3. Modified 'Rotlung Reanimator' cards act as the controller, triggering based on which token dies to write new symbols and move the head.
  4. The game is configured so that all moves are forced, making the outcome dependent solely on the the UTM's halting behavior.
  5. Since determining if a UTM halts is undecidable (the Halting Problem), determining the winner of this Magic game is also undecidable.

machine-generated · gemma4:31b

Open questions

machine-generated · gemma4:31b

Cited by

Discussions

Related