[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)
(HTM) web link (arxiv.org)
(TXT) 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)