News for hackers. Stuff that matters.
Re:Magic: The Gathering Is Turing Complete (2019) by swagasaurus-rex on Thursday December 14, 2023 @04:20PM (#38647393)
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.

Re:Magic: The Gathering Is Turing Complete (2019) by thom on Thursday December 14, 2023 @04:43PM (#38647697)
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.
Re:Magic: The Gathering Is Turing Complete (2019) by jacksontheel on Thursday December 14, 2023 @05:50PM (#38648486)
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.
Re:Magic: The Gathering Is Turing Complete (2019) by A_D_E_P_T on Friday December 15, 2023 @07:32AM (#38653501)
Why go for such a small number? Raise Graham's Number to the power of itself -- at the very least.

https://research.phys.cmu.edu/biophysics/2021/01/09/nobody-c...

I'm sure it can be entertaining to try and deal the largest possible finite amount of damage, which requires finding uncommonly large numbers.

Re:Magic: The Gathering Is Turing Complete (2019) by tromp on Friday December 15, 2023 @08:02AM (#38653721)
Raising Google's Number to itself doesn't make it appreciably bigger. Instead you can pick TREE(3), or SCG(13), or Loader's Number which is about the largest famous one we know how to compute.

Beyond that there's the likes of Busy Beaver numbers and beyond that is Rayo's number.

Btw, Graham's Number is less than BB(49 bits) [1].

[1] https://codegolf.stackexchange.com/questions/6430/shortest-t...

Re:Magic: The Gathering Is Turing Complete (2019) by Severian on Thursday December 14, 2023 @04:29PM (#38647511)
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.
Re:Magic: The Gathering Is Turing Complete (2019) by swagasaurus-rex on Thursday December 14, 2023 @04:39PM (#38647640)
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.

Re:Magic: The Gathering Is Turing Complete (2019) by pierat on Thursday December 14, 2023 @06:57PM (#38649219)
> Infinite combos that are not optional but do not win you the game result in a draw.

There's the 'donate an unsacrificable islandhome creature to an opponent who has no islands'.

Infinite amount of state based checks happen that are unavoidable, and cause the game to draw.

Re:Magic: The Gathering Is Turing Complete (2019) by dmorgan81 on Thursday December 14, 2023 @04:46PM (#38647738)
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.

Re:Magic: The Gathering Is Turing Complete (2019) by thom on Thursday December 14, 2023 @04:51PM (#38647798)
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.
Re:Magic: The Gathering Is Turing Complete (2019) by dmorgan81 on Thursday December 14, 2023 @05:05PM (#38647975)
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.

Re:Magic: The Gathering Is Turing Complete (2019) by greiskul on Thursday December 14, 2023 @06:27PM (#38648888)
One nitpick, even if you have have an action that stops the loop, you are not necessarily required to take it, and can choose the draw instead.

719.5. No player can be forced to perform an action that would end a loop other than actions called for by objects involved in the loop.

The rule about choices in mandatory action comes into play for cases like an Oblivion Ring loop. If there is another valid target for the oblivion ring, you must choose it instead of forcing a draw. You can't say that you always choose the opponents Oblivion ring.

Re:Magic: The Gathering Is Turing Complete (2019) by thom on Thursday December 14, 2023 @05:27PM (#38648225)
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.
Re:Magic: The Gathering Is Turing Complete (2019) by greiskul on Thursday December 14, 2023 @06:30PM (#38648915)
The rule is not precisely that, it is only if the mandatory actions of the loop offer you the choice, that you must eventually choose one that stops the loop. Classic infinite loop example is 3 oblivion rings exiling each other. If there is another valid target, you must choose it.
Re:Magic: The Gathering Is Turing Complete (2019) by dmorgan81 on Thursday December 14, 2023 @05:45PM (#38648434)
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.

Re:Magic: The Gathering Is Turing Complete (2019) by caf on Thursday December 14, 2023 @11:56PM (#38651138)
There was recently a ruling/clarification on exactly this kind of loop that has become relevant in competitive Pioneer format: https://mtgrocks.com/mtg-ruling-may-cause-problematic-turn-t...
Re:Magic: The Gathering Is Turing Complete (2019) by thom on Friday December 15, 2023 @03:45AM (#38652277)
Yeah, I’ve come round to this because the base case is a zero mana activated ability that you never stop activating. That ought to give you a loss on time the moment your opponent calls a judge and you refuse to stop. More complex loops where you nevertheless choose to continue and can’t make a convincing case you’re progressing should be the same. The recent ruling just short circuits that discussion for one specific combo so I suppose I’m fine. For online play we have clocks and they should fix MTGO’s stack depth.

I’m still not convinced uncontrollable loops should be forcibly avoided. That seems unnatural and I’m not really against draws per se. I guess I’d just feel very angry in chess if I were forced to play a worse move and lose when a repetition leading to a draw was available.

Re:Magic: The Gathering Is Turing Complete (2019) by caf on Sunday December 17, 2023 @08:45AM (#38672793)
In the recent ruling case (Amalia/Wildgrowth Walker), neither decision (mill cards or leave the same card on top of the deck) ends the loop, though. The loop will still continue with an empty library. The idea is that making the mill choice might eventually tempt the opponent to end the loop, if they have the ability - so that does seem a lot different to the "you must choose to stop looping if you can" case.
Re:Magic: The Gathering Is Turing Complete (2019) by thom on Thursday December 14, 2023 @04:49PM (#38647771)
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

Re:Magic: The Gathering Is Turing Complete (2019) by wwilim on Thursday December 14, 2023 @05:45PM (#38648440)
My favourite combo ever was infinite 5/5 dinosaurs
Re:Magic: The Gathering Is Turing Complete (2019) by throwaway743 on Thursday December 14, 2023 @06:00PM (#38648595)
You just described my Vampire deck, using Vito and Exquisite Blood.

Personal favorite is Squirrel's Nest + Earthcraft. Coat of Arms is optional fun lol

Re:Magic: The Gathering Is Turing Complete (2019) by cbsmith on Friday December 15, 2023 @01:19AM (#38651536)
Re:Magic: The Gathering Is Turing Complete (2019) by vikingerik on Friday December 15, 2023 @06:15AM (#38653014)
> There are no one-card infinite combos

There are. Basalt Monolith has "tap: add 3 mana" and "3 mana: untap". It doesn't actually have any net effect without some other card triggering on that or modifying it somehow, but it actually can do an infinite number of actions by itself as one card.

Re:Magic: The Gathering Is Turing Complete (2019) by swagasaurus-rex on Friday December 15, 2023 @02:06PM (#38657432)
Obligatory "we finally broke basalt monolith"

This card is a staple for so many infinite combos because, just like you're saying, it adds mana (the biggest restriction to pulling off broken effects), and it can be an engine for any number of complimentary effects that trigger off tapping or untapping or reducing costs or copying triggers.