I would have thought that a game as complex as MTG would require a lot of overhead in terms of creating an AI opponent. But nope! You can actually check out all of the logic for Sparky, including a few places in the debug UI where WOTC developers reached a corner case that they felt was not worth implementing. I don't blame them - MTG is a beast of a game to try to have full coverage for!
This is a huge understatement, since the game is nearly (no infinite loops) Turing complete, and people have a lot of fun with that. I assume there's a lot of work already done on AI strategy for it though.
The post title should probably have a "Show HN:" on it too, since you're posting it yourself.
The game is constantly changing because new sets are rotating through, but I believe it is possible to create infinite loops with certain dynamics, or at least it has been possible at various points. ie. something like creating/killing token characters with "on entry"/"on exit"/"untap" mechanics, etc. Not all of them result in either player taking damage.
The rules explicitly address infinite loops and forbid players from forever taking actions that create one. If one would occur anyways, the game ends in a draw.
https://mtg.fandom.com/wiki/Loop
Ok, so instead of being turing complete it requires solving the halting problem to properly referee it?
No - because the referee doesn't have to devise a program to do it. They can decide whatever they want. Also the statement of the halting problem isn't about it being impossible to tell whether a program will terminate, it's about it being impossible to devise a program that can tell whether any other program running on a turing machine (which actual physical computers are not, since they have finite state) will terminate.
For any program running on actual physical computer hardware it is obviously possible to tell whether it will terminate. For an actual game of magic, which has considerably less possible state, it's likely even trivial 99.9% of the time. The remaining 0.01% are up to the judge. In the case of MTGA on a computer, there are hard-coded limits on many things (but a lack of enforcement of the first part of the loop rule. Nexus of Fate wasn't a good time.).
It is absolutely not true that for any problem on a real computer it's possible to tell if it terminates, other than fairly trivial observations such as noting that if it runs longer than 2^(size of memory) steps it must be looping.
If you could, then I'd start using your "real computer" halt checker to instantly mine bitcoin or break all cryptography, so let me know when you figure out out.
Hmmm. Reading on...
So you are saying "You can't do it, even though it's trivially obvious that you can."
Or maybe "If we ignore that it is possible, it is not possible."
What am I supposed to do with your comment?
They're referring to the halting problem. If you believe you can solve it, you will win money[0].
[0] https://www.claymath.org/millennium/p-vs-np
Proving that you can programatically determine whether a program halts when you limit the turing machine to finite memory is trivial - which the conversation you interjected was about.
They weren't saying the problem was trivial. They were saying that if you massively reduce the problem to its most trivial form, then its trivial form is doable.
Neither was I? The proof is trivial - actually doing it is very much not.
How would you prove it in the non-trivial case?
What? Are you trolling?
I've no idea what you're talking about. If you ask a non-content free question I can help.
2ⁿ > n ∀n ∈ ℕ (n>1), therefore while the test is trivial to define for any finite system, in practice you can't do that many steps even for very small n — n=256 states is 2^256 tests is just shy of 2e26 years if each test takes one Planck time.
For a purely theoretical system (which includes the abstracted rather than physically implemented rules of MtG as used by Churchill, Biderman, & Herrick in their paper), n is effectively ℵ₀.
https://arxiv.org/abs/1904.09828
We don't actually need to know whether something will result in a loop ahead of time, so there's another approach which is much more doable in the context of MTG: Most digital CCG engines already record every past state through a history of actions (some even have full match replays). Together with engine-limits on recursively triggered actions, it really isn't that much data. You can check for repeated state here.
The most naive implementation would replay the entire previous match every time a new action happens. A better implementation realizes that you don't need to - because once you have one repeat, everything after should be a repeat as well, so you really can just keep running and merely check for repeats at strategic points (such as between turns or on any human input). Store the serialized state at those points in some appropriate Set implementation to make checking easy and fast. Increase the spacing between those checkpoints, deleting old ones, if space becomes an issue - though if you get to this point, the game has run for so long that the humans playing it probably need medical attention.
If you want to get even fancier, store serialized state rarely and just store hashes of state at checkpoints, replay from a serialized state using recorded inputs once you detect a collision.
All of this is possible because of the human element: Human just aren't physically capable of producing enough input to make a computer sweat about recording it.
One downside of this approach is that it requires some programmatic refeering in case of "numbers go up" scenarios if you don't want to wait for some player's health pool or token pile to run into the engine limit and keep the game to a length a human can enjoy (do you cap these for comparison? compare with low precision? only allow a decrease?). There's some other scenarios that will not repeat exact state until a human died of old age too. However in real life magic "Loop" is not such a narrow term - just one number being slightly different will not save you from having to explain yourself to the judge.
It'll stop this guy in any case: https://www.reddit.com/r/MagicArena/comments/amxhnk/is_there...
Since what they did was reportable behavior, I suppose technically human referees would eventually take care of it anyways.
Any test of this type only works if there is a repeat, which you can only know about if you have a finite machine, and even with finite steps it takes 2^n steps[0] to be sure you've hit an infinite loop. Even in a computer, even with a fairly small deck to build the state, you'll time out on things like the stars going out before you can rule out any loop.
And there isn't necessarily any repeat at all in the unbounded case. The state is recorded by 18 types of card, where "moving" left or right along the tape modifies the number of hitpoints on each card. At that point, I think you can still kinda decide if it halts or is infinite with the Busy Beaver number, except only "kinda" because now you run into the problem that the Busy Beaver number itself isn't generally computable because of the halting problem.
Also the lower bound S-number for a mere 2-state 6-symbol machine, let alone the 2-state 18-symbol one in the paper, is already 10⇈10⇈(10^(10^115)), which is so much larger than the Poincaré recurrence time of the universe (even when measured in Planck times) as to make those periods themselves to be infinitesimal rounding errors.
In practice, it's the opposite problem: for both humans and computers, even if you already know what it's going to compute and it's only doing something simple, it takes ages to get through enough states to say either way. It's a very slow Turing machine.
[0] well actually[1] it's something more like min(2^n, BB(2, 18)), but BB numbers grow so much faster that in practice they only matter for infinite tapes
[1] I've probably got this wrong, like getting the m and n switched around because the terminology doesn't seem to be entirely consistent, hence me starting that footnote with the traditional catchphrase for someone about to say something stupid :P
MTG doesn't require solving the halting problem because, if neither player nor the referee can come up with a way to halt a loop, then the match ends (long ago, when I played, it ended in a draw; other comments in this thread suggest that a player intentionally doing this may incur a loss now).
You probably meant 99.99%, or 0.1%.
There are multiple unresolvable game states (panglacial wurm...) but there are catch all rules which allows judges to say 'you're not trying to win, so your blocking line results in a game loss'. They have banned cards before (painter's servant) which resulted in competitive non-deterministic winning sequences that forced hundreds of game actions to resolve.
Is that how it goes now? It used to be infinite loops (e.g. playing a Faceless Butcher when the only creature in play is a Faceless Butcher that exiled another Faceless Butchers) resulted in a draw, not a loss.
Forced infinite loops are still a draw, but setting up a complex-enough board state where the infinite-ness or forced-ness of a particular loop is hard for the judge to decide on will just result in a game loss.
Put another way: you can try to set up a game state in a competitive match where the judge has to solve the Collatz conjecture, but because that would take way too long and clearly be contrary to good sportsmanship, you'd never reach that point.
Probably not, the infinite loop rules are specifically about rules where a player cannot make a choice in the process.
It's possible that there's a way to do something turing-challenging or busy-beavery in such a situation, but it's usually pretty difficult to make complex unbendable loops, they're usually very direct cases where taking an action more or less forces you to immediately take the same action again, so the loop has...two steps. Anything much bigger or more complex and you're basically assured to have player choice.
There's probably room to do something where a player is clearly losing unless they do something which might continue a situation that is undecidable.
If you have two choices for spend/untap, I think it would be fairly trivial to create Turing complete logic that also presents discretion and requires involvement from the player. However, it sounds like such an arrangement can still considered a draw in “competitive play”. There are many formats to Magic, though. If any other Turing machine had an outside observer ready to pull the plug after an arbitrary amount of time, does it make it less of a Turing machine?
Semantically, yes. Turing machines (actual ideal ones that only exist in maths papers) always compute forever. They are also instantaneous and have infinite resources.
The argument is that MtG is Turing complete except for that part, because it cannot compute forever, even in an ideal scenario where time and space are infinitely available, because the rules explicitly forbid it.
An ideal Turing machine with someone to pull the plug is not a Turing machine. Also: just because humans can recognize some infinite loops doesn't mean we can recognize all infinite loops, so the person pulling the plug may be misinterpreting and pulling the plug on a machine that would otherwise eventually halt.
The halting problem does not forbid us from discerning if SOME programs will ever halt. It says that there are definitely programs for which we cannot know.
I suspect most of the MTG infinite loops are something like "A triggers B, B triggers C, and C triggers A". Asserting that the loop will never resolve is not a violation of the halting problem.
Absolutely, but assuming that magic the gathering without the rule about loops is turing complete, then it's possible to set up all programs in magic the gathering, not just nice ones. In particular there exists a program where it is impossible to tell whether it is in an infinite loop or not without solving the halting problem.
The rule cited is worded to only apply to loops that go on indefinitely (machines that don't halt), so the referee can't even know whether or not they're allowed to apply the rule against a without knowing if it halts. On the particular machine mentioned above that would require solving the halting problem.
And yes, I'm sure the people saying "they'd just kick you out if you tried this in a tournament" are right. That's really not the point. The point is the cited rule doesn't really make things better with respect to turing completeness. If magic the gathering without the cited rule is turing complete, then with it it's both just-shy-of-turing-complete* (you'd be able to run any program that does halt) and uncomputable.
* Depending on the precise definition of "turing complete" it might in fact be turing complete. You can evaluate any program. Either it does halt and you can report the output, or it doesn't halt and you can report that you're in an infinite loop because the referee-oracle said so. That's probably enough to satisfy most definitions - even if it's a strange way to implement it.
Is there any practical strategy that approaches this complexity at all? I have never played. But I assume this claim is just that you can technically create some stateful stuff if you’re explicitly not trying to win
Turing machines? Not really. Infinite loops[0]? All the time. The designers generally try to avoid those being legal in "Standard" unless it's extremely unlikely to happen (only the most recent few years of cards are legal in tournament play. In casual play anything can be legal if your group is okay with it).
A common trope is to have a card that allows you to create mana, and then a way to infinitely bring that card back from the discard pile, allowing for infinite mana. Then you play a card that says something like "spend X mana to deal X damage" and you deal a trillion damage.
[0] the above commenter is correct that a true infinite loop is not allowed. But you're allowed to create a scenario where an infinite loop happens according to a repeating choice you can make (essentially a while loop) and repeat as much as you want within the match timer while still allowing time for your damage card. The general etiquette is just to say "I can do this a billion times and so I deal a billion damage".
I've actually been at a local (mostly informal) tournament where someone with an Elf deck managed to pump their life into the thousands (you start with 20 or 40 depending on the ruleset), and his opponent with a Goblin deck got an infinite combo for infinite damage. But the Elf player refused to accept "I can do this infinity times" and made him actually try to perform his card combo over a thousand times before the round timer ran out. Goblin deck did not win.
I'm not terribly familiar with tournament rules, but AFAIK in paper games you can always shortcut truly infinite actions by picking a number and the opponent has to accept it, it is not just etiquette.
This is only true if the series of actions you take in the combo are fully deterministic. If the combo includes non-deterministic steps (usually anything related to deck shuffling) you can't use shortcuts and have to actually perform the steps.
Even if the deck shuffling is deterministically irrelevant?
The deck shuffling is relevant due to other factors. There is a card in the combo deck that reshuffles the discard pile into the deck when it's put to discard, and the deck revolves around (as a shortcutted, freely undertaken combo) dealing one damage every time a certain creature goes to the discard pile. As you re-shuffle every time the 'engine' piece is hit, you can't predict how many times you need to activate the discard combo, so it cannot be shortcutted. Shortcutting in magic requires stating exactly as many iterations as will occur and the clear end state.
Slow play is the phrase explaining why indeterminate combos don't get shortcutted. "An indeterminate-loop combo may take anywhere from fifteen minutes to fifteen hundred years to actually succeed, and we really do not need to be waiting around to see which it's going to be."
Well yes, don't bring four horsemen or Gitrog dredge to a tournament. But the majority of combos are not like that.
So the Goblin-deck owner allowed the Elf-deck owner to do a "I give myself 1000 life" with a combo but the Elf-deck owner wouldn't let the Goblin-deck owner do the same with damage? That's kind of a jerk move if so.
If the Elf can give themselves infinite life in response to the infinite damage, then they have essentially won, because however much damage the Goblin would deal, they can just go "OK, but before that damage applies I give myself enough life to survive". The Goblin deck can never reach a game state where they win.
If the combos are sequential and the Elf has to commit to a certain number of life before the Goblin commits to a certain number of damage, then the Goblin would win.
There are some other possible intricacies (can they give themselves 1 life infinite times? or infinite life once?) From the mechanics of how the game usually goes, I would assume the first case applies here.
The way match/tournament rules work, when you have an infinite loop you can pick any number of iterations, but it has to be a number, not "infinity". Which means that the interaction of two infinite combos comes down to which one occurs with priority over which other.
If the elf deck can gain "infinite life" at instant speed, then they'd win over a goblin deck that can deal infinite damage at sorcery speed, because whatever number the goblin player picks, the elf deck can pick that number squared, for instance.
If both players can combo at instant speed then it's an impasse and they have to jockey for who can put their opponent in a position where they're tapped out, etc.
I agree that in formal tournaments this would happen, but the comment I was responding to was about a "casual tournament." I was assuming the 1000 life was with a sorcery (e.g. infinite mana combo + stream of life). In casual play, shortcuts are only when both sides agree, so it would be a jerk move to not agree to one that benefits your opponent after your opponent has agreed to one that benefited you.
The elf player cheated, your opponent can't stop you from shortcutting a valid loop.
An interesting result of how MtG handles infinite loops plus how it handles priority is that in a scenario where two players attempt to go infinite whoever gets to name their number last wins. And that most infinite loops are non-reloadable, in that when you stop repeating them, you can't restart them for free. I have seen a game that was lost because one player had an infinite life combo, named "a hundred trillion" and wrote their life total down on a piece of paper, and later in the game an opponent who had apparently mis-heard "a hundred billion" and didn't think to check only elected to repeat their infinite combo a trillion times.
So the moral of this story is, uh, always name Graham's number. Or don't because I'm not sure what a Judge is to do if two people name numbers so large that the Judge can't work out which one is bigger on a pocket calculator.
(I think that in a Comp REL game, in your scenario, the Goblin player should have won unless the combo was non-deterministic.)
It's not that easy. There are strategies but they depend on the game format (standard, legacy, modern, etc) and on a deep understanding of the game meta. You cannot devise a strategy that works under any conditions. Lookup the rules + understand that new abilities and cards are introduced all the time.
Let us listen to the sweet stories of Sherazad...
https://gatherer.wizards.com/pages/card/Discussion.aspx?mult...
Here's a paper on creating a Turing machine in Magic:
https://arxiv.org/abs/1904.09828
I'm not sure what level of complexity you're looking for, but there are some pretty complex combos that have been viable over the years, even in formats that don't use some of the older "broken" cards. One popular strategy for a while in the "Modern" format, which doesn't allow cards for the first 10 years or so of the game, used a mechanic called "Storm" where a spell would be copied for every spell you previously cast in the same turn. A card called Grapeshot had this ability and did 1 damage, so the deck played creatures that made your spells cost less mana and spells that gave you extra mana or draw cards, and the goal was to cast 19 spells and then grapeshot your opponent for their entire starting life total of 20, often as early as on their fourth turn. It was consistent enough that it was a staple in the format for at least a few years (although I haven't kept up with the meta as much for a few years now). Another higher variance but potentially even faster combo used a creature called Griselbrand, which let you pay 7 life to draw 7 cards, a bunch of mana "rituals" like storm, and used a card called Nourishing Shoal to let you exile certain cards from your hand to gain life. The win condition was typically to draw at least 7 lands and cast a creature that let you discard a land to do 3 damage, and it could potentially do this on the very first turn, although eventually one of the cards that was necessary for it to function got banned in modern, although by then Griselbrand decks weren't really ever played due to there being far more consistent options with better ability to deal with an opponent trying to thwart their game plan. If you include Legacy (which allows cards from any point in the history of the game but still with a custom ban list) or Vintage (where all cards are allowed but some are "restricted" to only one copy instead of the typical 4 per deck), there are even more powerful combos you can take advantage of.
Combo decks have always and likely will always be a part of the meta for most formats, although to varying degrees depending on how many cards the format has available and how effective it happens to be in the current meta. It's considered one of the three main deck archetypes along with "control" decks that attempt to shut down what the opponent is trying to do and slowly build an advantage over time and "aggro" which use a more straightforward approach of just attacking the opponent with creatures or spells (or both). Not everything cleanly fits into one of those strategies of course, and even a deck that has a win condition that fits into one archetype might dip into the other as a backup plan (e.g. a combo deck with control elements that help it buy time if it can't get off the combo as quickly as it would prefer, or a control deck with some efficient creatures that it can use for a surprise attack if the circumstance makes sense), but even in a setting like playing a few games at a card shop on a Friday night, seeing a combo deck with the level of complexity described above isn't really uncommon at all.
That said, I've read that a lot of the hardest cards to program tend to be the ones that subvert the basic expectations of the game. One infamous example that comes to mind is a creature that after being cast added an extra turn after yours where you controlled your opponent, after which they took their regular turn and the turn order resumed its previous alternation. Programming that would require adding in the ability to show one player's hidden game state to the other, let them make any sort of decisions using their cards that the player would normally do (short of literally conceding the game) and inserting an extra turn in the order with that weird control mechanism...all just for one card out of tens of thousands! Obviously most cards are not that complex, and Arena specifically doesn't attempt to support literally every card in existence and instead supports cards going back to its initial stable release along with explicitly chosen cards added to special Arena-only sets in order to introduce them, but when its an explicit rule that the text on the card overrides the normal rules of the game when they disagree, it very quickly gets to the point where you need to consider that there will likely be an edge cast for almost any possible state transition.
Arena's rule engine and AI is based on Duels of the Planeswalkers, so they had several years to develop the AI player.
The AI player just casts the first card it has the mana to cast, regardless of if any normal player would do it. As an example Sparky will gladly cast a kill spell on their own creature if the opponent has none, or cast protection spells on the opponents creatures if it has no creatures itself. This is far different than duels of the planewalkers.
Arena's rule engine was explicitly not based on Duels; this was a big selling point when it first launched to replace Duels, and they've gone into some detail since then describing how it works. See https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-n... for instance.
14-15 years ...
"The game can be used to encode a Turing machine" is not at all the same as "it is difficult to write a program that can play a legal action in every situation". It's the latter that seems to be difficult for the bot authors.
This is trivial (just forfeit).
The hard part is figuring out the best possible action to select from. MTG is particularly hard at this because: * Some actions are only allowed in certain conditions (e.g. in response to, in a specific phase, etc) * Actions vary significantly not only in their effects but also in their inputs (some require targeting a creature, a player, an opponent, a card in hand, a card in exile, a name of a card that could exist). Some have a varying list of inputs (target many creatures). This variance makes it hard to encode the action space. * The state space is huge. It is not only determined by the cards in play, but is also affected by the meta-game (to play optimally players have to play in a specific way to avoid getting countered by a card that could be in play by the opponent, because that card is legal to play and is commonly used by decks that look like what the opponent is playing). * Technically the state space is also infinite because you can create infinite loops that keep creating more and more triggers/creatures/etc.
Oh I completely agree, I'm just shitting on the idea that this has anything to do with the game being "Turing-complete".
Show HN is for projects people can play with, not blog posts. https://news.ycombinator.com/showhn.html
The sample code plus walkthrough sounds like "things people can run on their computers". :)
Don't make me regret removing the sentence that explicitly pointed out that the sample code in an appendix is not the point of the linked page.
It is actually Turing Complete: https://arxiv.org/abs/1904.09828