[HN Gopher] Magic: The Gathering Is Turing Complete (2019)
___________________________________________________________________
 
Magic: The Gathering Is Turing Complete (2019)
 
Author : ekiauhce
Score  : 51 points
Date   : 2023-12-14 20:35 UTC (2 hours ago)
 
web link (arxiv.org)
w3m dump (arxiv.org)
 
| turtleyacht wrote:
| (2019)
 
| bentona wrote:
| Here's a demo: https://www.youtube.com/watch?v=pdmODVYPDLA
| 
| 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.
 
  | trescenzi wrote:
  | One my decks is actually built around getting the game into
  | infinite combos which cannot end but that also don't kill
  | anyone so the game ends in a tie. Same sort of thing. Always
  | fun to pull off.
 
    | dwd wrote:
    | Blue control deck?
    | 
    | Frustrating to play against if the loop is working, but often
    | weak on killing power if it takes a lot of sacrificing to pay
    | the upkeep.
    | 
    | I remember one game decades ago where I was slowly ground
    | down by the tapping of a solitary Tim.
 
      | brightball wrote:
      | I honestly thought calling Prodigal Sorcerers "Tim" was
      | just a thing from a guy at my local comic store growing up.
      | 
      | Thanks for that memory.
 
        | dwd wrote:
        | Tim: There!
        | 
        | King Arthur: What, behind the rabbit?
        | 
        | Tim: It is the rabbit!
        | 
        | King Arthur: You silly sod!
 
      | trescenzi wrote:
      | No it's a group hug Commander/EDH deck. We all win
      | together!
      | 
      | But yes it does kinda frustrate people. That's the downside
      | of liking Magic because of it being fun to break as a
      | system and not because you want to smash giant monsters
      | into each other.
 
    | Fezzik wrote:
    | Most IRL play groups I've played with would count that as a
    | loss for you (or, most likely, just not invite you back). And
    | in competitive/regulated play you would timeout and lose. Not
    | sure who these weirdos are that are stipulating to a draw
    | against a deck that is unable to win.
    | 
    | Edit: I was wrong! I've only been playing competitively on
    | Arena for years now. Per Rule 725.4 infinite loops are draws.
 
      | badRNG wrote:
      | Seems somewhat analogous to draw by repetition in Chess
 
| swagasaurus-rex wrote:
| 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.
| 
| 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."
| 
| 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.
| 
| 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.
| 
| 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.
| 
| 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.
| 
| 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.
| 
| 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.
 
  | Severian wrote:
  | Please correct me if I'm wrong, but I thought an infinite combo
  | that doesn't require user at interaction results in a draw. So
  | your first example would be this, but the tapping one isn't.
  | It's been years since i played however.
 
    | swagasaurus-rex wrote:
    | Infinite combos that require the player to opt into repeating
    | an action will not end in a draw, because the player is
    | expected to decide on the number of times the combo will
    | repeat for.
    | 
    | Infinite combos that not optional but win you the game
    | instantly, like the sanguine bond + exquisite blood combo I
    | mentioned earlier, means you just win.
    | 
    | Infinite combos that are not optional but do not win you the
    | game result in a draw.
 
    | dmorgan81 wrote:
    | It depends. If the game state changes, say like a change in
    | one player's life total, then the loop won't usually end in a
    | draw. In the example above the opponent will eventually die.
    | 
    | In paper once a player has demonstrated a loop they must
    | choose a number of times to repeat the loop and then the game
    | is fast forwarded to the chosen end state. For example, a
    | player might execute a loop that could gain them infinite
    | life, but really they must choose a point to stop. Usually
    | that player will choose 1,000,000,000,000 or another
    | "essentially infinite" value and the game moves on.
    | 
    | There are infinite loops that can draw the game, but in a
    | tournament game if one player can take an action that would
    | end the loop, say by destroying one of the loop pieces, that
    | player must take that action. Only if no player can end the
    | loop does the game end in draw.
 
      | thom wrote:
      | Is that true? If your opponent creates a loop but you have
      | a spell that can end it, I don't believe you're compelled
      | to cast it if you decide the draw is more favourable.
      | Definitely don't like that rule if it exists.
 
        | dmorgan81 wrote:
        | The Magic tournament rules cover this:
        | 
        | "Some loops are sustained by choices rather than actions.
        | In these cases, the rules above may be applied, with the
        | player making a different choice rather than ceasing to
        | take an action. The game moves to the point where the
        | player makes that choice. If the choice involves hidden
        | information, a judge may be needed to determine whether
        | any choice is available that will not continue the loop."
        | 
        | Basically if a player has open information, like an
        | activated ability, that could end the loop that player is
        | not allowed to not use it to keep the loop going
        | indefinitely. If that player instead has hidden
        | information, i.e. a card in hand, that could end the loop
        | any player can call a judge to confirm that and force the
        | player to end the loop.
        | 
        | Note this doesn't extend past cards in hand, though. If a
        | player has some way to search their deck for a card that
        | could end the loop, they are not forced to search and
        | then play that card. At that level it moves from a player
        | intentionally delaying the game with the resources at
        | hand or in play to a judge dictating a player's actions.
 
        | thom wrote:
        | Don't like that at all! I suppose some chess tournaments
        | have "no draws before move X" but it's a feeble rule that
        | players easily overcome with repetitions etc. Forcing
        | someone to take an action that they might deem worse for
        | their chances seems wrong.
 
        | dmorgan81 wrote:
        | It's mostly for time purposes. Nobody wants to wait
        | another hour for the round to end because someone is
        | trying to draw their game, which means those players
        | potentially have to play yet another game. In reality it
        | doesn't happen that often.
        | 
        | In your games with your friends feel free to ignore this
        | rule. If you made a deck that managed to pull it off I
        | would think it was cool.
 
    | thom wrote:
    | There's never a time where players can't interact - just
    | passing priority or putting triggered abilities on the stack
    | are actions. And each time this could happen the game checks
    | state based actions to see if someone has won. That said, if
    | both players have no options or just pass (which is more
    | pronounced online) then you can end up in inescapable loops
    | that cause draws. A classic example is this Luis Scott-Vargas
    | game:
    | 
    | https://youtu.be/AGXG5rNe_tI?feature=shared
 
  | thom wrote:
  | For what it's worth, it's currently vintage cube season on
  | Magic Online and you can draft a deck with multiple infinite
  | combos without much effort. Sadly you have to do all the
  | clicking so you might run out of time. Paper magic is much
  | kinder because once you've demonstrated a loop you can
  | basically assign infinite damage, gain infinite life, create
  | infinite creatures etc without having to play it out.
 
    | jacksontheel wrote:
    | What's funny is that after demonstrating the loop you still
    | have to give a concrete number of times that you repeat it.
    | You can't deal infinite damage, but you sure can do a
    | googolplex damage.
 
  | wwilim wrote:
  | My favourite combo ever was infinite 5/5 dinosaurs
 
| lvncelot wrote:
| A great read on that topic is Gwern's Surprisingly Turing
| Complete: https://gwern.net/turing-complete
 
| iamevn wrote:
| https://www.mtggoldfish.com/deck/3933484#paper
| 
| This deck has gotten cheaper in the last couple years, looks like
| it's currently $2400 to build.
 
  | bordercases wrote:
  | Is it competitive?
 
    | iamevn wrote:
    | The odds of getting the combo off are extremely low so
    | probably not.
 
    | mattnewton wrote:
    | Definitely not. I don't think you could actually pull this
    | off against another pile of cards trying to play
    | traditionally unless your opponents are in on the joke.
 
| mdaniel wrote:
| This paper gets cited in almost every Magic thread, of which
| there have been 2 recently that may interest this audience:
| 
| https://news.ycombinator.com/item?id=38525978 _(I hacked Magic
| the Gathering: Arena for a 100% win rate)_
| 
| https://news.ycombinator.com/item?id=38533105 _(Fine-tuning
| Mistral 7B on Magic the Gathering Draft)_
 
| xarope wrote:
| MoTG also had the concept of a stack, e.g. if I have two mishra's
| factory (https://gatherer.wizards.com/pages/card/details.aspx?nam
| e=Mi...), 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.
| 
| 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.
| 
| Fun times.
 
___________________________________________________________________
(page generated 2023-12-14 23:00 UTC)