Alex Churchill, Stella Biderman, Austin Herrick
2019 · arXiv
$\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.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
19 selected excerpts · 19 total mentions
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: https://arxiv.org/abs/1904.09828 IOW, it's as complicated as possible.
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 some kind of read/write memory plus branching or conditional recursion you're usually there. As an example, Magic The Gathering (the card game) is Turing-complete: https://arxiv.org/abs/1904.09828 . You can use creature tokens as memory and various game mechanics to do flow control. Was this intentional by the designers? Most likely not...
> 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 gathering[1]. > There's plenty of junior programmers… And there are plenty of junior programmers who think containers = virtualisation :) 1. https://arxiv.org/abs/1904.09828
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 interactions is vast, and people delight in discovering clever combinations. Sometimes those combinations can even break the game (like, winning before your opponent even begins). They're so powerful that they're made illegal. A key element of the game is that you will draw your cards in random order, so even if you have a super-powered combination, you need to draw it before your opponent draws their…
own. This particular combination of moves requires a lot of very specific cards. Even if you put all of then in your deck, it will take you a very long time to get them out. Meantime, your opponent is likely to kill you in a more conventional way. This isn't realistic. It's more akin to a chess problem, a thought exercise in what you could do. Similarly, you can arrange your deck to form a Turing-complete computer: https://arxiv.org/abs/1904.09828
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
> 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", https://arstechnica.com/science/2019/06/its-possible-to-buil... for an Ars Technica article, and https://hn.algolia.com/?q=magic+turing for the many HN submissions on that result.
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
2ⁿ > n ∀n ∈ ℕ (n>1), therefore while the test is trivial to define for any finite system with more than one bit, 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 a plank time. For a purely theoretical system (which includes the abstracted rather than physically implemented rules of MtG as used by Churchill, Biderman, & Herrick in their paper), n is effectively ℵ₀. https://arxiv.org/abs/1904.09828
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 as an other example. https://www.ioccc.org/2020/carlini/index.html The paper showed that Transformer with positional encodings and rational activation functions is Turing complete. Rational activation functions with arbitrary precision make sure that you are in the smaller countable infinities, where floats run into that cardinality of the continuum problem. While all nets that use attention are…
feed forward and thus effectively DAGs, they add in positional encodings to move it from well-founded to well ordered. While those constraints allow the authors to make their claims in this paper, they also have serious implications for real world use as rational activation functions are not arbitrarily precise in physically realizable machines in finite time and you will need to find a well-ordering of your data or find a way to force one one it which is not a trivial task. So while interesting, just as it was interesting when someone demonstrated sendmail configurations were Turing complete, it probably isn't as practical as you seem to think of it. As attention is really runtime re-weighting and as feed forward networks are similar to DAGs it is not surprising to me that someone found a way to prove this, but just as I am not going to use the C preprocessor as a universal computation tool as it is also TC, I wouldn't hold your breath waiting for attention to be a universal computation tool either.
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 project started by Churchill [4] and continued by Churchill et al. [5] of embedding a universal Turing machine in Magic: The Gathering such that determining the outcome of the game is equivalent to determining the halting of the Turing machine. This is the first result showing that there exists a real-world game for which determining the winning strategy is non-computable, answering an open question…
of Demaine and Hearn [10] and Auger and Teytaud [1] in the positive. This result, combined with Rice’s Theorem [13], also answers an open problem from Esche [11] in the negative by showing that the equivalence of two strategies for playing Magic is undecidable. > This result raises important foundational questions about the nature of a game itself. As we have already discussed, the leading formal theory of games holds that this construction is unreasonable, if not impossible, and so a reconsideration of those assumptions is called for. In section V-A we discuss additional foundational assumptions of Constraint Logic that Magic: The Gathering violates, and present our interpretation of the implications for a unified theory of games. cf. https://drops.dagstuhl.de/opus/volltexte/2020/12770/
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 complexity of the game for the first time by encoding it in a way that can be played by a computer or Turing machine. “This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,” they say. Anyway, I'm certainly glad that Technology Review has stumbled upon this groundbreaking achievement that we've known since 2019: https://arxiv.org/abs/1904.09828 and reported here repeatedly: https://hn.algolia.com/?q=gathering+turing
>> 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] https://arxiv.org/abs/1904.09828
> I think the game design really lends itself to being enjoyed by programmers Interestingly, Magic is turing complete. https://arxiv.org/abs/1904.09828
> 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 see what happens! I'm not surprised it ends up with some sort of clash; given that it's Turing complete, the game engine obviously can't detect whether a current state will end up halting or not... > And here's the paper on the latest turing machine construction in mtg: https://arxiv.org/abs/1904.09828 Awesome, thanks! I'll definitely check that out
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 an arbitrary setup (and in practice you could set it up such that it halts iff some unknown conjecture is true). 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 And here's the paper on the latest turing machine construction in mtg: https://arxiv.org/abs/1904.09828
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 work, because the game rules are complex enough to simulate a Turing machine, and as a result some board states are undecidable! https://arxiv.org/abs/1904.09828
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
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
> 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
More from the same topics.
Anders Sandberg, Eric Drexler, Toby Ord
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe.
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Scott Aaronson
In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will.
Art Hobson
Quantum foundations are still unsettled, with mixed effects on science and society.