Hacker News new | past | comments | ask | show | jobs | submit login
Magic: The Gathering Is Turing Complete (v5) (toothycat.net)
120 points by icelancer on Oct 2, 2015 | hide | past | favorite | 31 comments



I'm not a Magic player personally, but I learnt about it through the project I did on this game. Learnt how complex it is and really good for doing different analysis. We created a Deck Builder Toolkit, which should help inexperienced players to build their card deck in order to improve card synergies and overall success ratio. Fortunately my team mate was experienced player while we were building this. If anyone interested, you can check project info here: https://www.dropbox.com/s/hojm1rfqgkz5dn4/Poster.pdf?dl=0 And Git repo here: https://github.com/dzeno/deck-builder-toolkit


The procedure mentions that you need 43 Rotlung Reanimators. A magic deck can only have at most 4 copies of the same card. :-) How are the copies created? Shouldn't be too hard to create infinite copies of a card, but I didn't see this mentioned anywhere.


On the "Cards" page, http://www.toothycat.net/~hologram/Turing/Cards.html:

> The first sixteen Reanimators were cast in the normal fashion, four by each of the players, and donated by a Bazaar Trader. The other twenty are Clones and Vesuvan Shapeshifters copying a Rotlung Reanimator. The phasing enchantments can include Teferi's Curse, Cloak of Invisibility, and Copy Enchantment, cast by any player and donated by a Bazaar Trader. These creatures and Auras must not be tokens, because tokens disappear when phased out.


So to be Turing complete you have to play with 4 players?


The machine as demonstrated on that page requires 4 players. There are probably ways to do it with fewer, but you might have to accept situations where two abilities trigger and the players need to choose an order to put them on the stack (though it makes no difference either way).


There are cards that allow for copying creatures, so that can be worked around.

A more glaring error is the usage of Time and Tide together with comes-into-play effects. At least earlier, comes into play effects did was NOT triggered by phasing.

I stopped playing a few years ago, so they might have changed that rule though.


Nice catch. They don't trigger according to the latest rules:

702.25d The phasing event doesn’t actually cause a permanent to change zones or control, even though it’s treated as though it’s not on the battlefield and not under its controller’s control while it’s phased out. Zone-change triggers don’t trigger when a permanent phases in or out. Counters remain on a permanent while it’s phased out. Effects that check a phased-in permanent’s history won’t treat the phasing event as having caused the permanent to leave or enter the battlefield or its controller’s control.

I don't think this is a problem because they don't use phasing to trigger comes-into-play effects, but only to change the color rules. This is clever because you can keep both parts of the machine, head and color, from interfering with each other.


This isn't an error. The machine doesn't use phasing to trigger enter-the-battlefield triggers, merely to switch between the two states (sets of Rotlung Reanimators watching for the current token dying).


Maybe this is limited and you happened to draft 43 Reanimators


ah, I was wondering where I had misplaced my rotlung cube


Its funny how the rules were at most 4 copies, yet I had a red/white deck that had different versions of essentially the same spell (1 red + n colorless damage to target player or creature), and used it frequently against people who didn't understand how to properly defend against it. Had something like 12 cards in that deck that just did that.


Fun fact. The deck size isn't limited by the rules in tournaments as long as you don't delay the game by shuffling/handling it. A deck with around a thousand cards would be quite a nightmare to deck-check by a judge, and still be fairly quick to shuffle.


Well. You can have as many cards as you like, but still just 4 copies of any card, apart from basic lands. So there's very little benefit to having 200 cards in your deck.



And anything involving Shadowborn Apostle:

444 Shadowborn Apostle

1 Reaper from the Abyss

1 Sire of Insanity

2 Griselbrand

4 Cavern of Souls

214 Swamp

There are probably better lists but I like the simplicity of this one and the 666-card deck.

Source: http://www.channelfireball.com/articles/frank-analysis-is-pl...


Is this from Unhinged?


Unsure if you are serious, but no, it's from an actual core set. Some battle of wits players did "okay" in a couple of tournaments too.


There was a modern legal deck which used this card and birthing pod (now banned) and actually won a decent number of mtgo events: http://archive.wizards.com/Magic/magazine/Article.aspx?x=mtg...


> but still just 4 copies of any card

If you are playing Limited (i.e. Draft or Sealed decks) then you can have as many copies as you have in your card pool.

Although you may have some trouble finding 200 cards to use in a Limited event :)


Sometimes it's nice to spare yourself getting milled. :)


Originally, the 4 copy maximum didn't exist. However, there were two early decks that broke the game:

  20x Black Lotus 
  20x Channel 
  20x Fireball 
Gatherer links: http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver... http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver... http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...

As long as you get 2x Lotus, 1x other two in your opening 7 cards, first turn kill. Play two lotus, sacrifice one for green, one for red. Play channel with green. Give up 19 life. Do 22 damage with Fireball.

Black Lotus is worth five figures these days, so building that deck would be very expensive. Replacing them with Mountains and Forests gives you a deck for less than ten dollars that can routinely kill on the fourthish turn every time, though.

The second one is even sillier: (see edits and citations below, I slightly mis-remembered this one, but the concept is the same)

  60x Shahrazad
http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...

This was Richard Garfield's favorite card. But due to the way the rules work, a subgame within a subgame within a subgame within.... means that you win, due to the way that rounding works.


Even better is:

  31 Ancestral Recall
  25 Black Lotus
  3 Timetwister
  1 Braingeyser
You don't need 2x of any one thing to get started, you only need 1 Lotus and 1 Timetwister or Ancestral Recall.

If anything gets countered, you are very, very likely to be able to keep going and win the same turn.

Timetwister lets you recycle, so you can generate infinite mana.

Braingeyser kills the opponent, and doubles as card draw itself, in the unlikely event that you stall out.

You also don't lose to a turn 1 Lightning Bolt, like you do with Channel.

A mulligan to two still has a fairly high likelihood of winning on the first turn.


Ah nice!


Shahrazad, aka MTG virtualization. Too bad there aren't other ways to encode bits. Also, if you lose half your life and you're at 1, what happens?


  > Too bad there aren't other ways to encode bits.
Well, I mean, if you look at the article, it encodes a turing machine, so... oh man what about playing Shahrazad inside of the turing game...

  > Also, if you lose half your life and you're at 1, what happens?
So there's an entire section of the rules that had to be added, just for Shahrazad. http://media.wizards.com/images/magic/tcg/resources/rules/Ma... is the link, Section 715, subgames. Now that I'm re-reading, I _think_ that you actually win by decking, not by life: you just play with a larger than usual deck, and

  715.3. Because each player draws seven cards when a game begins,
  any player with fewer than seven cards in his or her deck will
  lose the subgame when state-based actions are checked during the 
  upkeep step of the first turn, regardless of any mulligans that 
  player takes. (See rule 704, “State-Based Actions.”)
Here's the citation for it being Richard's favorite card, and a commentor leaves an explanation: https://www.reddit.com/r/IAmA/comments/20f1dn/we_are_richard...

Mox Pearl is simpler and faster than Plains!


The Shahrazad deck also presumably needs either Plains or Black Lotus.


Ahh yes, good call. I will leave my post the way it is to leave your reply coherent, my mental model was "Only Shahrazad", which is true, but you still need to pay for it...

EDIT: Looks like Mox Pearl is the right way to go.


make sure they don't find out about Kor Firewalker or Leyline of Sanctity


I'm generally all for esoteric programming stuff, but trying to understand this really hurt my head.

Kudos to these guys to figuring this out.


Yes. AlexTFish (HN name) / Hologram (elsewhere) is brilliant.


Time for somebody to play Magic inside Magic!




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: