HackerPapers

arXiv:1904.09828cs.AI

Magic: The Gathering is Turing Complete

Alex Churchill, Stella Biderman, Austin Herrick

Abstract

$\textit{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 $\textit{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 $\textit{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 $\textit{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.

arXiv comments
Journal reference
DOI
Subjects
cs.AIArtificial Intelligence cs.CCComputational Complexity cs.LOLogic in Computer Science

On Hacker News

Linked by 25 identifiable commenters in 26 comments across 20 threads, from May 2019 to Jun 2026. Found in 12 HN submissions from Apr 2019 to Apr 2026. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments20 threads

  1. MTG Bench: Testing how well LLMs can play Magic 1 comment

    • I was wondering how complicated it could really be, and it turns out that some people showed in 2019 that it's Turing-complete -- meaning that any conceivable computation can be simulated by a MTG game, indeed a game in which every move by every player is forced…

      akoboldfryingView on HNParent context

  2. Show HN: X86CSS – An x86 CPU emulator written in CSS 1 comment

    • I don't know much about CSS, but Turing completeness is notorious for showing up in systems unintentionally. It doesn't take much to be Turing-complete - if a system provides unbounded read/write memory plus branching or conditional recursion you're usually there. As an example…

      FartyMcFarterView on HNParent context

  3. We Need to Talk About Docker Hub 1 comment

    • > There's several use cases to virtualization Containers are not virtualisation. > So whatever you do with docker can also be done with type 1, 2 virtualization This statement is redundant. Whatever you do with docker can also be done with a Turing machine built using magic the…

      orfView on HNParent context

  4. Deal infinite damage for 4GRU, as long as the twin primes conjecture is true 1 comment

    • It's not advantageous. It's merely amusing. MtG is a deck-building game, rather than a board game. They keep issuing new kinds of cards, with new capabilities. You can make your deck out of any cards you like (depending on who is running the game). The number of possible…

      jfengelView on HNParent context

  5. How to sort your library in exactly 51,271 steps 1 comment

    • I love the whimsy of this. I'm not familiar with Magic, but now I wonder - is Magic Turing complete? And of course the answer appears to be yes! [0] [0] https://arxiv.org/abs/1904.09828

      anitilView on HNParent context

  6. The creator of 'Magic: The Gathering' knows where it all went wrong 1 comment
  7. Apollo 11 vs. USB-C Chargers (2020) 1 comment

    • > is the game? Sure. One of the "Surprisingly Turing-Complete" examples is that "Magic: the Gathering: not just TC, but above arithmetic in the hierarchy ". See https://arxiv.org/abs/1904.09828 for the preprint "Magic: The Gathering is Turing Complete"…

      eesmithView on HNParent context

  8. I hacked Magic the Gathering: Arena for a 100% win rate 4 comments

    • Here's a paper on creating a Turing machine in Magic: https://arxiv.org/abs/1904.09828

      sciolistView on HNParent context

    • It is actually Turing Complete: https://arxiv.org/abs/1904.09828

      fauriaView on HNParent context

    • 2ⁿ > n ∀n ∈ ℕ (n>1), therefore while the test is trivial to define for any finite system, in practice you can't do that many steps even for very small n — n=256 states is 2^256 tests is just shy of 2e26 years if each test takes one Planck time. For a purely theoretical system…

      ben_wView on HNParent context

    • This is buried but fascinating: magic the gathering is turing complete, probably even more complicated than simply uncomputable , and possibly the most complicated major real world game https://arxiv.org/abs/1904.09828

      ljlolelView on HNParent context

  9. Show HN: Marsha – An LLM-Based Programming Language 1 comment

    • So, Magic: the Gathering (being Turing complete[0]) is a programming language? [0]: https://arxiv.org/abs/1904.09828

      jacheeView on HNParent context

  10. Attention is Turing complete (2021) [pdf] 1 comment

    • Note that Magic: The Gathering is Turing Complete https://arxiv.org/abs/1904.09828 Something being Turing Complete just that means in principle it could be used to solve any computation problem. But this may require infinite memory or infinite time. printf() is Turing complete…

      nyrikkiView on HNParent context

  11. “Magic: The Gathering” is officially the world’s most complex game 2 comments

    • I think they're referring to it being Turing complete, which is unlikely for Campaign for North Africa (although this is the first I've heard of that game, so), and they actually do qualify their assertion with "computationally complex": > His team has measured the computational…

      mdanielView on HNParent context

    • Computationally complex; "Churchill and co’s key result is that determining the outcome of a game of Magic is non-computable," making the claim that Magic is the first "undecidable real game" to exist. From the study: https://arxiv.org/abs/1904.09828 > This paper completes the…

      trynewideasView on HNParent context

  12. Surprisingly Turing-Complete (2021) 1 comment
  13. Turing Machines Are Recurrent Neural Networks (1996) 1 comment
  14. AI Is Ushering in a New Scientific Revolution 1 comment

    • >> For one - a neural network is a universal function approximator. And Magic: the Gathering is Turing-Complete [1], but we are not communicating over an implementation of the http protocol in Magic: the Gathering. Because that would be awfully inconvenient. ______________ [1]…

      YeGoblynQueenneView on HNParent context

  15. Trading cards are cool again 1 comment

    • > I think the game design really lends itself to being enjoyed by programmers Interestingly, Magic is turing complete. https://arxiv.org/abs/1904.09828

      monocasaView on HNParent context

  16. How the Magic: The Gathering Color Wheel Explains Humanity 2 comments

    • That rule is exactly where the the construction used becomes interesting: it's built in such a way so that if the turing machine halts, the player who set it up wins the game. If it doesn't, by the rule above, it's a draw. So it's fundamentally impossible to tell the result of…

      rcxdudeView on HNParent context

    • > Regarding the oblivion ring loop, there's an example of it being used on MTGO, which doesn't end well (basically seems to crash the server and/or client): https://www.youtube.com/watch?v=AGXG5rNe_tI Oh wow, I should have realized that somebody would try it out online just to…

      saghmView on HNParent context

  17. Simplifying Board Games 1 comment

    • Most of the complexity is to handle a small number of cards that are essentially never used except to prompt rule puzzles. The rules have to be very complex to accommodate when these complex cards redouble their complexity by interacting with each other. Sadly, this doesn't…

      dodobirdlordView on HNParent context

  18. My Kid Lost a Game of 'Magic' to Its Creator But Scored a Piece of Its Art 1 comment

    • Related to your comment, here's the paper [0] and Because Science recently made a video about how such a game would look like [1]. [0] https://arxiv.org/abs/1904.09828 [1] https://www.youtube.com/watch?v=pdmODVYPDLA

      cyberfartView on HNParent context

  19. Rediscovering rules for ancient board games 1 comment

    • > I don't think there's a single person today that knows all the rules. Knowing the rules won't even save you, the game has undecidable interactions. https://arxiv.org/abs/1904.09828

      dodobirdlordView on HNParent context

  20. Magic: The Gathering is Turing Complete 2 comments

    • Direct link to the study "Magic: The Gathering is Turing Complete": https://arxiv.org/pdf/1904.09828.pdf

      hu3View on HNParent context

    • There's a download link to the right of the abstract. Here's the PDF, in case it's not showing up on mobile, or whatever: https://arxiv.org/pdf/1904.09828.pdf

      ZanniView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.