Related:<p><i>Magic: The Gathering is Turing Complete (2019)</i> - <a href="https://news.ycombinator.com/item?id=30502908">https://news.ycombinator.com/item?id=30502908</a> - Feb 2022 (1 comment)<p><i>Magic: The Gathering is Turing Complete</i> - <a href="https://news.ycombinator.com/item?id=19847939">https://news.ycombinator.com/item?id=19847939</a> - May 2019 (192 comments)<p><i>Magic: The Gathering Is Turing Complete</i> - <a href="https://news.ycombinator.com/item?id=19744072">https://news.ycombinator.com/item?id=19744072</a> - April 2019 (1 comment)<p><i>Magic: The Gathering Is Turing Complete (2012)</i> - <a href="https://news.ycombinator.com/item?id=15712377">https://news.ycombinator.com/item?id=15712377</a> - Nov 2017 (115 comments)<p><i>Magic: The Gathering Is Turing Complete (v5)</i> - <a href="https://news.ycombinator.com/item?id=10317224">https://news.ycombinator.com/item?id=10317224</a> - Oct 2015 (31 comments)<p><i>Magic: the Gathering is Turing Complete</i> - <a href="https://news.ycombinator.com/item?id=4511384">https://news.ycombinator.com/item?id=4511384</a> - Sept 2012 (1 comment)<p><i>Magic: the Gathering is Turing Complete</i> - <a href="https://news.ycombinator.com/item?id=4506865">https://news.ycombinator.com/item?id=4506865</a> - Sept 2012 (1 comment)
Here's a demo: <a href="https://www.youtube.com/watch?v=pdmODVYPDLA" rel="nofollow noreferrer">https://www.youtube.com/watch?v=pdmODVYPDLA</a><p>Didn't realize this before watching, but it's interesting that there's an incredibly complicated board state but the game state / actions are deterministic, e.g. the players don't have any choices about what to do once the machine is set up.
I was thinking about how Magic the Gathering has so many infinite combos. In a deck with a wide variety of cards, you're likely to be able to accidentally construct an infinite combo.<p>For those who don't play, the most iconic infinite combo involves two cards, the first says "Whenever you gain life, an opponent loses that much life.", the second card says "Whenever an opponent loses life, you gain that much life."<p>These cards, when combined, do nothing... until you gain a life or an opponent takes damage. Then their effects combined means a chain reaction that repeats until your opponents are dead and you have gained as much life as they had.<p>There's a variety of infinite combos in MTG. Some of them involve a creature that says "Tap to add mana to your mana pool" combined with another card that says "Pay mana to untap a creature", allowing you to tap and untap an infinite number of times.<p>Some infinite combos involve returning a card to your hand, and recasting it which gives you the resources you need to return it to your hand and recast again. Some infinite combos involve looping a card from your discard pile repeatedly.<p>There are no one-card infinite combos (that would likely not make it past the testers), but there are plenty of two-card infinite combos, and an combinatorically increasing number of three and four card infinite combos.<p>I think there is some similarity computationally speaking between turing completeness, and the ability to construct an infinite combo in a game like MTG. An infinite allows you (the player) to continue taking the same action over and over again, accumulating some game resource in the process. This bears resemblance to the infinite tape Turing envisioned, a way to hold data. Player actions are much analogous to the instruction set. Infinites that are optional for the player (not all infinites in MTG are optional once the pieces are on the board) can also stand in for conditional statements - a key requirement of turing completeness.<p>I'd be interested in seeing the bare minimum number of cards required to generate turing completeness. If anybody else knows more about this domain, I would love to hear their opinions.
This paper gets cited in almost every Magic thread, of which there have been 2 recently that may interest this audience:<p><a href="https://news.ycombinator.com/item?id=38525978">https://news.ycombinator.com/item?id=38525978</a> <i>(I hacked Magic the Gathering: Arena for a 100% win rate)</i><p><a href="https://news.ycombinator.com/item?id=38533105">https://news.ycombinator.com/item?id=38533105</a> <i>(Fine-tuning Mistral 7B on Magic the Gathering Draft)</i>
A great read on that topic is Gwern's Surprisingly Turing Complete: <a href="https://gwern.net/turing-complete" rel="nofollow noreferrer">https://gwern.net/turing-complete</a>
<a href="https://www.mtggoldfish.com/deck/3933484#paper" rel="nofollow noreferrer">https://www.mtggoldfish.com/deck/3933484#paper</a><p>This deck has gotten cheaper in the last couple years, looks like it's currently $2400 to build.
> In [4], the author presents a Magic: The Gathering end-
game that embeds a universal Turing machine. However, this
work has a major issue: it’s not quite deterministic. At several
points in the simulation, players have the ability to stop the
computation at any time by opting to decline to use effects that
say “may.” For example, Kazuul Warlord reads “Whenever
Kazuul Warlord or another Ally enters the battlefield under
your control, you may put a +1/ + 1 counter on each Ally
you control.” Declining to use this ability will interfere with
the Turing machine, either causing it to stop or causing it
to perform a different calculation from the one intended.
The construction as given in Churchill [4] works under the
assumption that all players that are given the option to do
something actually do it, but as the author notes it fails without
this assumption. Attempts to correct this issue are discussed
in Churchill et al. [5].
In this work, we solve this problem by reformulating the
construction to exclusively use cards with mandatory effects<p>So they only use cards with mandatory effects/triggers.
Doesn't this mean that this whole work if flawed because it only applies to a subset of MTG cards?
Waiting for someone to port Pokemon to MTG and then run that one exploit that allows you to execute arbitrary code using in-game commands in order to play Pong.
I've wondered can a game similar to MTG be created but cards for real-life, as a means to educate those who gravitate to devour such information and strategy as a force to first spot and raise the alarms loudly enough to counter any tyrannical-authoritarian tactics?<p>Perhaps a hybrid card-board game with a foundation similar to Monopoly?<p>It's something I want to eventually help create, though I'm not in a position to put a proper effort needed to get the base created.<p>There are a few computer games that simulate this evolution though, no? But perhaps without the level of detail such as slippery-slope policies that an opponent [whether directed by a player or machine] may try to pass their parliament, other tactics like playing a card that successfully "manufactures consent" with the population to move various dials/levers ahead to implement turnkey authoritarianism - to then at a certain point in future once enough foundation is laid, the population not paying adequate attention to the empire - entertained excessively, the player-machine can then execute on locking down their society?
MoTG also had the concept of a stack, e.g. if I have two mishra's factory (<a href="https://gatherer.wizards.com/pages/card/details.aspx?name=Mishra%27s%20Factory" rel="nofollow noreferrer">https://gatherer.wizards.com/pages/card/details.aspx?name=Mi...</a>), activate one to make it a 2/2, you decide to lightning bolt it (deals 3 damage), I then tap the other to make to a 3/3, then tap this one to make it a 4/4.<p>And phases and timing: if you don't do anything, and I tap to attack, and THEN you lightning bolt it... then I can no longer tap it to... yeah, you get the idea.<p>Fun times.
Always found it funny how "the stack", which exists in MTG to make it more deterministic and comprehensible, also makes this kind of arbitrary complexity easier to reason about and pull off.<p>Also, how consistent the rules are overall. e.g. the players themselves count as planeswalkers.
so if I kept redrawing neighbors I'd find that one woman, that could engineer my dream child (after we made sweet sweet love)?<p>that is, if another neighbor didn't chose to redraw that exact time when I didn't ...<p>wait. are you saying I need to get rid of that one neighbor? wait.