13 ms·
Magic: The Gathering Is Turing Complete (2012)
- cantrip 9y agoPrevious discussion: https://news.ycombinator.com/from?site=toothycat.net https://news.ycombinator.com/from?site=toothycat.net
- AgentEpsilon 9y agoNo it isn't. I can forgive the extremely contrived decks, but using a card to completely change the behavior of the majority of your cards doesn't mean the game itself is Turing complete. If anything, this is just showing how you can utilize Magic game mechanics to create a Turing Machine.
- rhaps0dy 9y ago>the game itself is Turing complete [...] you can utilize Magic game mechanics to create a Turing Machine Aren't those two statements equivalent?
- deleted 9y ago[deleted]
- cgmg 9y ago> this is just showing how you can utilize Magic game mechanics to create a Turing Machine I believe that is the point.
- _Codemonkeyism 9y agoNo it isn't. With some contrieved meaning of the cards, which has nothing to do with the "meaning of the card" in Magic the game, like "State B, Colour 16: Stay in state B, colour this space 18, move one step right." it recreates a complicated and arcane turing machine.
- gipp 9y agoThat's like saying a file on your computer is just a "contrived meaning" of the way magnetic domains are arranged on some glass platters in your hard drive.
- _Codemonkeyism 9y agoIt's like saying parking cars are turing complete, if a blue car means X and a red car means Y etc. 'Reanimator 17B actually says "Whenever a Rat (R0) dies, make a Sliver (S1M).' The linked page is not using the rules of Magic the gathering or the texts on the cards, but uses it's own rules what cards mean. The game rules of magic the gathering are not turing complete, because the linked post is not talking about Magic the Gathering game.
- gipp 9y agoThose aren't new rules for the cards that they're just contriving out of thin air. When it says that's what it "actually says", it means that's what the net effect of the card's actual text is in the environment that's been set up. It's just a rhetorical shortcut to help explain how the system works. All the cards are using the correct text as normal.
- dsp1234 9y agoThis is like saying, "Draw go" isn't talking about MTG. It's shorthand for all of the steps that you'd need to complete. Just like someone playing an Eggs deck is going to say "Casting KCI + IW, draw 2, float 2" or "Here is the main loop. I'm going to do that until I hit banefire, then hit you for infinite damage." What's interesting is actual MTG gameplay uses a HUGE amount of shortcuts on every play, because saying every single thing you and the opponent have to do during each step and phase would be incredibly time consuming.
- crankylinuxuser 9y agoWell, that gets weird. It can have shortcuts and also won't have shortcuts. If you play Commander or multiplayer, then its usually a heck of a lot less formal. Ive also played some local tournament games where the players were good-natured and we all just had fun. Then I've played some tournaments locally and at Gencon that were methodical and clockwork style "Please indicate what you did, step by ste-COUNTER". Or you get the priority police up and running, where you have to explicitly pass priority. I hate those games with a passion - it just drains the fun out via rules-lawyering. I've not played in a few years, primarily because the game was feeling much more like 'loot crates' that I've railed against prior. And with $3.50/pack, I didn't feel like I was getting enjoyment. You either buy buy buy, or get left in the dust and destroyed in games because you didnt buy buy buy.
- mabbo 9y agoThere lots of maybe-valid criticisms about this setup- oh, you have to use so many game mechanics to make this work; you need to have 4 players all working together to do it and get just the right conditions; this can never happen in real play. You miss this point. Once, as an undergrad, I had just learned about the O(n) selection algorithm (you can get the kth largest element in an unsorted list in linear time for any value of k, which is awesome)[0], and mentioned it to a grad student friend, but said "It's O(n), but the constant in the front is enormous, so it's usually totally impractical". The reply has stuck with me ever since: "I doesn't matter if this particular algorithm has a big constant. What matters is that this algorithm proves it is even possible to accomplish this task in linear time. It might not have been." Similarly, this Magic: The Gathering Turing Complete proof is contrived, silly, impractical, and you are welcome to scoff at it all you want. The point wasn't to make something practical, it was to prove it can be done. Now all that's left is finding a practical way to do it too. [0]https://en.wikipedia.org/wiki/Median_of_medians https://en.wikipedia.org/wiki/Median_of_medians
- nlperguiy 9y agoBut the constant is not large. O(n) quickselect is extremely fast algorithm.
- mabbo 9y agoOh, you should have seen my implementation then.
- chowells 9y agoQuickselect has an O(n^2) worst case, unless you use a variant like Tarjan's median-of-medians algorithm for selecting the pivot. And that does have awful constant factors.
- mabbo 9y agoYeah, this was the specific algorithm I meant. O(n) time, but in my undergrad implementation, it wasn't useful with less than billions of items, vs just sorting and selecting with highly optimized sorts.
- sethev 9y agoSo mtgox could have been implemented in Magic: The Gathering.
- paulmd 9y agoSurely it would have been implemented in Magic: The Gathering Online? ;) (MTGox was a trading site for virtual trading cards, not real ones. It was "MTG Online: Exchange", not "MTG: Online Exchange"...)
- schoen 9y agoI never knew that and never knew where the colon went! Thanks for pointing this out.
- ggggtez 9y agoIncorrect. MTGO is not a true turing machine because it doesn't have infinite tape. >The model of the tape is as follows. A series of Zombie tokens controlled by Alex represent the tape to the right of the current head However, it seems that there is a limit to the number of creature tokens in MTGO which does not exist in the paper game.
- Smaug123 9y agoFor that matter, a physical digital computer has a bounded number of states it can be in, so it can't be Turing complete at all, if you're going to be really pedantic. You're only allowed to say MTGO is not Turing complete if you also agree that Java is not Turing complete (because the 32-bit JVM has bounded memory it can access).
- sincerely 9y agoMTGO has a limit of 200 tokens. That's not a whole lot.
- ubernostrum 9y agoThere's also the infamous video of (well-known professional player) Luis Scott-Vargas "breaking" MTGO by causing the game to wind up in a non-terminating loop of mandatory actions: https://www.youtube.com/watch?v=AGXG5rNe_tI https://www.youtube.com/watch?v=AGXG5rNe_tI For those who are confused, the card involved there is Oblivion Ring: http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=397760 http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver... Its effect is that, when it comes into play, you choose a non-land card in play that gets exiled (removed from play) for as long as Oblivion Ring stays in play, then gets returned once Oblivion Ring leaves play. This game devolves into a situation where there are three Oblivion Rings and no other non-land cards, so: Ring 1 exiles Ring 2, which returns Ring 3, which exiles Ring 1, which returns Ring 2, which exiles Ring 3, which returns Ring 1, which exiles Ring 2, and so on to infinity. The rules state that when a loop like this occurs (which is not often in real play), the game is an automatic draw.
- Rickasaurus 9y agoThis idea inspired the 2011 ICFP programming contest, lambda the gathering: http://icfpc2011.blogspot.jp/2011/06/task-description-contest-starts-now.html http://icfpc2011.blogspot.jp/2011/06/task-description-contes...
- jeremy7600 9y agoShouldn't this be (2012)?
- sctb 9y agoSince we're not reading it in Japanese, yes. Thanks!
- pimmen 9y agoAbsolutely awesome. I could probably talk for hours with this guy!
- rulusidaze 9y agoA pencil and paper is Turing Complete. A bunch of rocks in a grid is Turing Complete.[1] Sorry to be an ass but I can't even guess how many "X is Turing Complete" things I've seen over the years. Turing's point wasn't to define what can be a computer, it was to define the limits of computation itself. Which is a far more interesting topic, hence my irritation with this post. [1]https://xkcd.com/505/ https://xkcd.com/505/
- valbaca 9y agoTrue, but this is a game with no intention of being Turing complete. Yet there is a set of cards and mechanics within an "innocuous" game that resulted in a Turing Machine.
- rulusidaze 9y ago>there is a set [...with] mechanics Welcome to the definition of a Turing Complete system. Also the game in question is not "innocuous." The author admits to creating an artificial scenario under which a Turing Machine is possible.
- Yen 9y agoI believe GP's point is that Magic: The Gathering was not intended to be a turing-complete set of rules and cards. I.e., the game design was _intended_ to be entirely decidable. Indeed, certain game rules discuss what happens when events trigger each other in a loop - and if the loop is non-halting, the game ends in a draw. This rule is only meaningful if the halting problem for M:tG is decidable! However, in creating enough "relatively simple" cards, most of which are of the form "when one thing happens, another thing then happens", the designers of M:tG have managed to _accidentally_ create a non-decidable system. Sure, this particular example is contrived, but it has the implications that a non-contrived game state could find itself in an undecidable state! It is theoretically possible that a natural, tournament-level game could reach a state where it can't be decided if one player or the other wins, or if it's a draw. (Or, at minimum, deciding the outcome of the game might require sufficiently convincing a tournament official of your mathematical proof that the game in fact will halt , within some known finite time).
- _Codemonkeyism 9y agoOT: I have a MTG deck from somewhere between Arabian Nights and before Legends. From those here that still play MTG, are cards still anything worth? [Edit] Thanks a lot to everyone who answered!
- rsync 9y agoYes - old, rare cards (especially powerful ones that are now considered "broken") have only risen in value. They're also quite provocative. Once every few years I'll break out my very, very old "power nine" deck and play with it at the local game store. All games stop. Everyone comes to look. People take pictures.
- lolive 9y agoYep! Even basic lands are worth 100$! https://www.m.ebay.fr/itm/Mountain-Magic-Arabian-Nights-original-Scan-15L133-/361451813040?nav=SEARCH https://www.m.ebay.fr/itm/Mountain-Magic-Arabian-Nights-orig...
- mswiss 9y agoholy crap I didn't realize these were worth that much, I have boxes of these in my closet right now with cards from Unlimited/Legacy to Tempest(maybe some newer but i forget what the releases were called). Where's a good place to sell these? Ebay?
- maxiepoo 9y agoAs someone that does not understand the rules of Magic, how do they get around the fact that a Turing machine requires infinite memory? Presumably a particular game of Magic has a finite set of cards and probably states too?
- deepnotderp 9y agoTokens or an infinite blink (exiled and returns) mechanism I think. I haven't seen the thing in a while :)
- staticautomatic 9y agoYou can also go infinite with time warp and a means of fetching it from your graveyard.
- valbaca 9y agoMany Magic cards can create "tokens" which don't count as cards, but can operate in the same way as cards in many ways. You can have as many tokens as you can create. The MTM (Magic Turing Machine) seems to rely on this. It's actually within the rules to "go infinite" with tokens. For example, you have a Foo which taps (is spent) to create a Bar token. The Bar token can untap (reset) Foo. Since you can do this as much as possible, within the rules you effectively just simulate that you can repeat the combo, pick a number (100, 1 million or 1 Googolplex), and you have that many. The proof is much more complex than that, using various creature types (zombie, rats, etc.) and other game states, but that is how the infinite memory problem can be overcome. It's also worth noting that the infinite memory requirements is often ignored when showing Turing Completeness. (I play a lot of Magic and just took a glance at the page)
- dragontamer 9y agoThe tape is actually very simple. +1/+1 counters on Zombies represent the tape to the right. +1/+1 counters on Yetis represent the tape to the left. Whenever you reach the "end of Tape" (ie: All your Zombies are now Yetis), there's a trigger that creates a new Zombie token. Effectively creating "infinite tape". I didn't read to see how it worked on the "Yeti side", but I presume its the same concept. Moving the tape back and forth is about putting -1/-1 counters on Yetis and +1/+1 counters on Zombies, or vice versa. Death triggers convert Yetis into Zombies and vice versa. There are 18-states representing the "tape head" (which I presume to be the current creature with zero counters on it). I haven't really looked into how it works, but "Halt" state is pretty amusing actually. The "Halt" state kills all players, which "Halts" the program.
- gt_ 9y agoI quit playing Magic in 1999 when my 4 friends and I found out we were playing by the wrong rules. We went into town, to a tournament at a comic shop, and saw the games taking 20 minutes. Ours took 1-2 days. We tried what was, to us, the “new rules” and we were disappointed, gave up. It was a big blow. Suddenly the cards were less enchanted, the decks were less sacred. Maybe if I had understood the Turing completeness of Magic, I would have had it in me to start a tournament under our rules. Well, I still could if I had written them down. I’m pretty sure they were the best rules.
- mirceal 9y agoclassic "i'm not quite sure and at this point i'm too afraid to ask" to be fair to wotc, learning and playing the game nowadays is pretty straightforward.
- PhasmaFelis 9y ago> Ours took 1-2 days. ...What were you doing?
- gt_ 9y agoI don't remember the exact difference but it was only a small change from the normal rules that had an exponential impact.
- harpiaharpyja 9y agoThat's really curious, too bad you forgot.
- gt_ 9y agoIf I were to re-learn the rules, I could probably point it out. The best I recall is we were skipping a small step in the turn cycle.
- PascLeRasc 9y ago
- deleted 9y ago[deleted]