Magic: The Gathering is Turing Complete | Hacker News Reader

Magic: The Gathering is Turing Complete

arxiv.org

192 pointslelf192 comments

I guess this is newsworthy because a paper was put on arXiv, but the result has been known for a while. See e.g. this submission a year ago: https://news.ycombinator.com/item?id=15712377

I'll just make my submission here then as I don't want to clutter the front page [1]. The submission includes a list of a lot of things that are accidentally turing complete including Magic The Gathering.

[1] http://beza1e1.tuxen.de/articles/accidentally_turing_complet...

I've always objected to the CSS example. It's demonstrating that CSS can do basic arithmetic. When you combine basic arithmetic and an infinite loop, you can make a "Turing machine" with limited memory. But CSS is not providing that loop. CSS is not Turing complete.

It's like pulling the state table out of a Turing machine and showing it off all by itself. It doesn't take much to extend it into a full Turing machine, but it's also not doing much at all by itself. A Turing machine is simple, and half a Turing machine is really simple. It's missing the point of "accidental Turing completeness" if it can't iterate to an actual result.

Off the cuff conjecture, but wouldn't any number of render methods allow for an infinite loop? Animation methods come to mind first.

In CSS itself, I don't know of a way to feed one result back into an earlier one and thus create a loop. If you're talking about JavaScript, it is and was intended to be Turing complete.

Edit: Just saw the HTML/CSS3 example on the page. Mind blown.

I have a more up-to-date list at https://www.gwern.net/Turing-complete

I've heard you can perform arbitrarily difficult calculations just by getting gwern interested enough to write an article.

Why do you consider it surprising that Peano Arithmetic is Turing complete?

Because they're supposed to just be the integers. If it is obvious to you that 'the integers' means undecidability/Turing-completeness, and that integers without multiplication (Presburger) does not, then all I can say is that your mathematical logic intuition is vastly superior to mine and everyone before Turing/Godel.

This version is better because all the moves are forced. The previous version only worked if all players cooperate by taking optional actions.

No it hasnt. This is a new result that requires no choices by either player. It is in the paper.

Where is the actual paper? I just see the overview in the bibliography.

There's a download link to the right of the abstract. Here's the PDF, in case it's not showing up on mobile, or whatever: https://arxiv.org/pdf/1904.09828.pdf

I'll see your Magic and raise you Nomic: https://en.m.wikipedia.org/wiki/Nomic

Some friends and I tried playing Nomic using GitHub and CI. We played three games before getting bored and moving on:

* https://www.jefftk.com/p/nomic-report-iii-conclusion

* https://www.jefftk.com/p/nomic-game-2-another-conclusion

* https://www.jefftk.com/p/nomic-game-3

I have never played Nomic, but I can say from experience that Mao is a very fun way to practice game design skills and troll new players at the same time

https://en.wikipedia.org/wiki/Mao_(card_game)

Mao is a ridiculously fun game. I can't think of another that is as critically reliant on both playing the mechanics and your opponents.

This sounds really cool, but where am I going to find someone who already knows it to play my first game?

Just use the following rules:

- turns go clockwise

- play one card per turn

- if someone breaks a rule, they take back their card and draw one extra

- first to shed all their cards, followed by saying "Mao!" wins

- saying "Mao" any other times means drawing three cards (so if someone broke a rule playing their last card and had to take back their card, they end up drawing three cards

- Similar to the previous rule: not saying "Mao" upon successfully playing the last card also means drawing three cards. And it is breaking the rules, so the player has to take back the card and draw a card.

- asking any question means drawing a card (be brutal: "WHAT?!" counts as a question)

- one player starts with making up two extra rules

- the winner of a round makes up a new rule, the old rules stay

... then grab a bunch of friends, say "you'll figure it out", come up with two rules of your own and start playing. You'll likely win the round (because they will all ask questions in confusion), and be allowed to add another rule.

Restart after a couple of rounds. Troll until they threaten to quit (at which point you explain the rules) or until they actually figure it out. Watch their expressions go from frustration to gleefully anticipation, and go look for a fresh victim together.

I've never heard of Nomic before but now I really want to get a group of nerds together and attempt to play it.

Please count me in ;-)

Can't think of anyone in my direct environment crazy enough to try this.

I had a group of friends who played it in the 1980s.

It was a long-lived informal group of game-players that started in the 1970s, and has continued (with almost-total replacement of the membership over time) until roughly the present day. We played very different games at different times--pencil-and-paper roleplaying games; Risk and Diplomacy; Civilization; Cosmic Encounter; Illuminati; MMORPGS; Nomic; custom versions of several of the above using modified rules and our own maps and other materials.

Nomic worked quite well for one of the iterations of the group. It was very entertaining--though exhausting to play--and it was educational about the legislative process.

I think the most significant thing I learned about legislation is that, regardless of what it is theoretically supposed to accomplish, what it actually does accomplish is to reward legislators who are skillful at gaming the legislative process.

I learned other things, too:

- Given an incentive, people can be incredibly flexible and creative in trying to outmaneuver one another in dealmaking.

- Very often, the most capacious bladder wins.

- If you succeed in making rules about what is allowed, you must expect that others will make rules redefining the terms used in those rules.

- Any self-serving proposal can be made to sound like it's for the common good with the right combination of incentives, creativity, and charisma.

- No matter how bitterly someone opposes your proposal, you can still get their support if you can find the right payoff and add it to your proposal.

- There is no way to limit what other legislators can do to a proposal through amendments (we tried all sorts of things, and they all ultimately failed).

I also learned that real-world legislators have to have incredible endurance. A hotly-contested game of Nomic can drag on for hours and leave all the participants completely exhausted. Real legislation must be much more grueling. The stakes are higher, the costs and rewards are more significant, and the game never ends.

That is the perfect drinking game!

erm "Though similar to role-playing fantasy games such as Dungeons and Dragons"

No MTG is not at all similar to role playing games.

The whole sentence makes even less sense:

"Though similar to role-playing fantasy games such as Dungeons and Dragons, it has significantly more cards and more complex rules than other card games."

As if similarity to D&D said anything at all about number of cards relative to other card games.

D&D has infinite cards.

It is similar in lore/setting.

That was an accurate statement in, say, 1994 but boy did it diverge. Though now they've published a D&D book based on an MTG specific setting so I suppose they could converge again.

It should also be mentioned that Magic effectively "ate up" D&D, when Wizards Of The Coast (owners of MTG) bought TSR (owners of D&D).

Not sure that's true MTG is not based on any of the DnD settings nor does it have Character Races and Classes.

Yep. In fact, the opposite is now true. Some of DnD is now (in part) based on MTG, including an MTG setting, MTG Character Races, and such.

http://dnd.wizards.com/products/tabletop-games/rpg-products/...

You have creature type (a list of tags basically). A Human Soldier or a Goblin Wizard is common in MTG.

You Have a thief in Catan

if my nerd history is correct - MTG almost killed dungeons and dragons in the 90's!

Did it? I sort of thought the 90's death of D&D was more of the hangover of the 'devil worshipping' accusations of the 80's finally hitting.

That and D&D being associated with all things nerd, which was very out of vogue through the 90's.

It definitely took a lot of attention at my local game shop away from traditional table top role playing.

cough 4th Edition cough but Pathfinder took over

Some thoughts about AI: After Chess, Go and StarCraft 1, Magic is definitely an interesting game for AI to tackle next.

While there are certain play patterns, the space of potential actions is extremely large and there is a great number of synergistic interactions between cards that needs to be taken into account.

From an AI perspective Magic is also very hard because it is:

  * Non-deterministic
  * Partially observable
  * Antagonistic

"While there are certain play patterns, the space of potential actions is extremely large and there is a great number of synergistic interactions between cards that needs to be taken into account."

Yes, that's certainly the promise of MTG - and is the reason why I was drawn to it originally and continue to be, at least passively, interested in it.

The idea is that there are so many different cards and so many potential interactions that every deck could be fantastically unique and every game could produce very unique outcomes.

I have found, in 25 years of playing MTG that this is not the case. The reality is that in every release, or set of "legal" cards, there are a few overwhelmingly advantageous cards and card combinations that must either be adhered to or prepared against. Further, "classes" of decks (counter decks, control decks, blast decks, etc.) need to be fairly simple and anti-fragile to work effectively given the random draw, etc.

My opinion, circa 1998 or 1999, was that to really open up the playing space, WOTC needed to produce sets of very complex cards that had abilities and interactions that in themselves were as complicated as the game was. Cards whose abilities and interactions we would still be discovering years later. Perhaps even random attributes/abilities For obvious reasons this is not the direction they went and would be a big hurdle for new players.

And so every set has, effectively, its own channel+fireball and we all play that or prepare for it and for all the turing-completeness, there's not that many surprises at the game store on Friday night ...

Well put! MTG is notorious in the huge gap between the potential complexity and the actual complexity of most games. I've found that deck design is a far more interesting problem than the in-game play strategy, and unfortunately most really interesting decks end up far too fragile or slow to compete with the optimal strategies.

Someone really ought to design a format that bans all the straightforward but powerful cards, forcing a bit more creativity into the mix, but I fear the banned list would be prohibitively long and surprisingly difficult to come up with after the first round of obvious bans. There's always some new infinite combo that's a little too easy to pull off once the super fast quick wins are out of the way.

Edit: there's always that person (I've occasionally been him) who doesn't play to win and just tries to mess with the game's limits as much as possible. I knew someone with a "Jester Deck" that played cards that so mangled the rules that no one could even figure out how to finish the game any more. That was pretty interesting.

I wonder if the problem of "playing the game" optimally is mostly the same as the problem of "choosing the best deck."

It is definitely a factor, but there is no auto-win for any deck. It definitely matters which cards you play and which ones your opponent plays, because just like rock-paper-scissors some cards are good at eliminating specific other cards. But unlike RPS you cannot always enforce a favorable interaction between specific cards. Your opponent can maneuver around whatever you are playing.

Should we rule out the possibility that there are decks which are unbeatable when played well/"correctly"?

I think the probability is very small indeed. I've never met (or even heard about) a deck that you can't destroy with a matching counter. That's why the metagame is so important for higher level magic play.

Yes. Best case is that there are decks that are unbeatable when played correctly against other decks (even if that deck is played correctly). I can think of a few match ups that are likely "auto-lose" based on deck construction.

Most of the games AI has surpassed humans at have several things in common, and one of the biggest is they don't contain a great deal of hidden information. Chess is all in the open, with very set defined options. There are a ton of different game states, but none of them involve "what if my opponent suddenly drew the one card that I cannot in any way do anything about to prevent ruination".

TL;dr- robots will never defeat the "heart of the cards" unless you stack the game in their favor.

on this note there was a nice paper [0] proposing a game entirely focused on hidden information (Hanabi) as a benchmark for automated decisions.

[0] https://arxiv.org/abs/1902.00506

There's hidden information, but also finite known quantities. The AI knows what tiles exist, have been played and haven't.

Unless you're allowing the AI to know the contents of the deck it's opposing in magic, you're probably making those decision trees impossibly complex. "Is countering this lightning bolt optimal or not" has a lot more meaning when you know what else is in the deck with the lightning bolt.

That is an interesting point, it is actually a strategy in the game to speculate on the opponent deck composition so it would make sense not to trivialize it here.

Of course, but how do you "fairly" account for that? You could teach the computer what the "meta" looks like, but players never reveal full deck contents to each other in tournament play.

Also, how does the AI select its deck? Does the player know going in what deck it will be playing? Part of the problem here is that you can build a weird, off meta deck for either the AI or player that can win a single game but what does that mean? Most decks are designed for a full tournament grind based on an expected range of decks to play against.

I guess you'd have to have the AI compete in a full tournament, but then the skill level of the individual players becomes a variable. IDK, it just seems like a really big hill to climb.

In theory if you had an unlimited amount of time and compute resources couldn't you just construct all possible decks and play them against each other, perhaps with some mix of naive and pre-trained strategies?

Yes. Got any extra "unlimited amount of time and computer resources" lying around?

I mean when we get to that level, couldn't we just use our unlimited time and resources to just create a model of the entire universe and just observe all the people playing the game and at all skill levels as well?

Imbalanced decks usually have their key pieces banned by WotC. As a result, in a sense, the game adapts to the players.

Depends on what you expect the AI to do. If you allow it access to a DB of decklists to compare opponent cards/choices against, it gets "easier" but still complex. There's so many branching option trees though.

Could be interesting to see what happened, I just don't think you'd be able to build an "unbeatable" machine that didn't also cheat the RNG elements of the game/have the full decklist of its opponent.

but those interactions are actually not as large as a real time game such as Dota or even Go. Your deck has an X amount of cards and the synergies can be easily calculated from a machine. The real problem would be, is it smart enough to beat an unknown opponent deck?

As a Magic player (since 1996) and Go player (since 2004) and also deep learning scientist, the main issue with Magic is modeling the game. The interactions and exceptions are really numerous, I expect Magic Arena and Magic Online are a mess of spaghetti code.

For go modeling basically you have in input an image of the go board, and for DOTA an image of your screen and the action you have are "limited" and do not change wildly depending of the state of your screen (except if you're dead on Dota).

For Magic, you can't just use deep reinforcement learning with an image input, you need to somehow track the state of your deck, cards, instant effects, what your opponent did ...

Arena at least has the advantage of not including all-cards-ever, only going a few sets back relative to release. That strips out some of the worst of them.

I suggest you look at projects like Shandalar 2012 and such - the original game is from the Banding era, but the 'AI' isn't too bad.

and the synergies can be easily calculated from a machine

This article is all about how those synergies are Turing complete and thus cannot be easily calculated since doing so reduces down to solving the halting problem.

edit: that being said I suspect that writing an AI that plays "well enough" to beat human players, as opposed to optimally, is quite doable.

One step before that is Hanabi: https://arxiv.org/abs/1902.00506

Does it actually make sense to say that something that is non-computable is most complex?

That seems like a contradiction.

I think you are misunderstanding the article. The point is that when the game is considered as a computation, the problem of figuring out who is going to win is not computable. Like every discussion of the halting problem, this is about whether or not a program exists that can calculate how some other specific program will behave.

I understood that, but question whether it's meaningful to say that is therefore more complex. Complexity theory just doesn't apply? (Or does it?)

Well, it's at least as complex as a Turing machine. That's a statement of complexity.

Maybe you are asking whether it is possible for the winning strategy of a very simple deterministic game to be non-computable. In other words, maybe there's a possible way of defining computability which is orthogonal to complexity. The CS definitions of both terms are closely connected to Turing machines, though. Can you imagine a simple deterministic game that couldn't be "solved" by an algorithm?

The set of all problems that can be solved by a Turing machine if there's an answer (possibly hanging if there's no answer) sits at the top of the complexity hierarchy (it's equivalent to the recursively enumerable languages)

The usual complexity classes of decision problems, such as P and NP, are subsets of what a Turing machine can solve, and so are weaker complexity classes.

Lots of things are more complicated than a computer can handle. There's an entire hierarchy of non-computable problems by complexity (actually several).

A collection of things that are Turing-complete by accident https://news.ycombinator.com/item?id=16383072

DeepMind engineers are probably getting triggered by this headline :)

They'll have to finish solving Hanabi first: https://twitter.com/deepmindai/status/1092471486936436736

The actual article (as opposed to this summary) states that it's the most computationally complex game, which is quite a different claim.

While this paper shows that a player can create a game state where deciding the game result is Turing-complete, it does not show that doing so is an optimal strategy under any circumstance (in particular, the setup requires a starting situation where the player can just win the game instead of performing the setup).

So it seems perfectly possible (and in fact highly likely) that this result does not hold if players play optimally, especially if deck selection is included in the strategy.

In game playing theory, an optimal strategy is a function that takes any state and tells you the proper next move. It does not matter how you got there

For MTG strategy to be computable you must be able to compute whether entering this computation is a good choice, which requires solving the halting problem.

Not really, it's possible that there is always a strategy that can be proven to be better than entering the computation (because it wins the game deterministically, for instance).

This does mean that MTG is not algorithmically solvable, which is very interesting. However, in most cases I think it is heuristically trivial to determine the best move.

Sure, but that isn't what theory people care about. Most real world SAT instances are tractable. But SAT is still NP-Complete.

True. There's sort of a divide in this thread over two questions that are interesting in completely different ways. One is how deep a game MTG is in practice, and the other is whether it is an algorithmically solvable game (no). My take-away, other than it being really cool that it's Turing-Complete, is that any bot will need to accept that not all infinities it could get stuck in are even detectable and resort to heuristics at a certain point.

The paper hasn't got anything to do with optimal game strategies, it's just showing what it is possible to achieve computationally within the rules of the game. If you're looking for advice on how to pay to win, this paper really isn't for you.

This is not correct: the paper does have to do with optimal strategies. They even say as much in the abstract.

>In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem, solving a problem that has been open for a decade

This is an important distinction, as I've found that the optimal strategies in Magic are very rarely the most intricate ones or the ones involving recursive constructs. Occasionally a trivial infinite loop becomes part of a top deck, but you definitely aren't going to see someone doing the equivalent of calculating pi to win.

I think the Turing completeness is definitely still part of the appeal of Magic, because the bizarre edge cases and complexity occasionally do creep in to even serious play and add a lot of interest, but the complexity is of the iceberg variety, where most of it rarely makes itself visible most of the time.

OK that's fair enough, but it's not saying anything about what optimal strategies might actually be, just examining their potential complexity in an extreme edge case scenario.

So add a new rule:

Choice-lock. If any player is unable to make a choice for some finite countable number of consecutive turns, they lose.

This could have also prevented combining infinite turn combos with the ante-related cards to produce "I have created a game state where I can take ownership all the cards in your deck, and then win," which was fun to do in the original M:tG PC game, even though running through the combo to actually take all of the cards was a bit tedious.

This almost certainly doesn't prevent turing completeness.

You'd just need to add additional construction that every N turns gives each player a choice but where that choice does not affect the behavior of the machine.

Now, if only we had algorithm to decide whether for provided game table state, the chain of triggers ever stops or continues indefinitely.

It stops at the Nth instruction, where N is determined by some game designer to be long enough to create interesting combos, but not so long that one player can force the other to be their CPU indefinitely.

This seems like a bizarre rule to add. Why is this result even a bad thing for Magic?

It makes it more difficult to create challenging-but-still-fair bots in computerized versions of the game.

Challenging but fair bots are by definition not supposed to treat the game as totally algorithmically solvable. They can work fine on heuristics rather than algorithms, the same way that players do. There are moments when a player needs to think through all the possibilities available in the game state, and other moments when they just use a rule of thumb, like, "use this card to destroy the greatest threat currently out because time is not currently on my side to wait for what they might play next".

But that's already how bots are made. You don't need to add rules to the game before you can constrict the thinking time of entertainment AI

Oh good. This will be handy if I ever need to compute FFT's using only Magic cards.

I don't understand why researchers are so interested in 'Turing completeness'. The concept of a Turing machine which operates on a strip of tape is outdated and no longer intuitive. It would be good if the abstraction of a 'Turing machine' could be refined into something more modern.

To be more specific about what the other responses say:

Being "equivalent to a TM" and being "equivalent to the Python compiler" mean the exact same thing. Pretty much every widely used model of computation is equivalent in computing power to Turing machines. The notable exceptions are all weaker than Turing machines, such as arithmetic circuits.

The importance of Turing Completeness is the capabilities it offers, not the model of the machine that offers them. The machine doesn't matter at all, which is precisely why the "strip of tape" is still used.

You might like the RASP: https://en.m.wikipedia.org/wiki/Random-access_stored-program...

Considering that all of life essentially runs on a strip of tape and machine(s) that can read and write to it, I think it's still pretty relevant.

"By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. "

What is this input? Board size?

If you generalize chess to an N*N board, it becomes PSPACE complete to decide which player has a winning strategy:

https://www.sciencedirect.com/science/article/pii/0022000083...

I think that the number of positions that need to be considered for a brute force exhaustive search are roughly proportional to an exponential function of the number of moves made, so the statement holds true for that.

In reality, the number of possible moves is not constant and depends on the current position.

It is board size for Go, because the starting condition is an empty board. For chess, I would expect the complexity to also be a function of the number of pieces, and possibly the types of pieces.

Usually it would be number of legal moves. Of course this would also change throughout the game as pieces are removed.

The number of legal moves is an intermediate calculation. The input is the initial game state, and the output is usually the number of possible final game states.

Somehow I highly doubt Magic is the most complex played game in the world.

For instance there are many different card games, what's to say Magic is more complex than them?

I actually believe it may be the hardest card game to compute.

Magic has been around since 1993, and releases new cards every year. There are currently > 15,000 unique cards in the game.

When playing, you don't know what the next card drawn will be. You also don't know what is in your opponents hand.

In poker for example, there is a very small pool of possible top decks and hands.

Search trees in Magic (especially "eternal" formats that allow you to pick cards from any expansion) would be too massive to compute.

These cards are not vanilla either (not just statpools) - they contain over 100 categorical effects and many of them have unique effects.

I'd guess at least 1000 have unique effects and interactions.

Add on to that the fact that magic is both a pro-active and re-active card game. In most card games (aka hearthstone for example) you cast cards on your turn. In Magic you can cast many cards "in response" e.g. counterspells. You can also just play some cards on opponents turn.

Beyond this the game is split into a number of phases and card timing by phase is very important. Sometimes you want to cast on end step vs combat - the same spell does the same thing but might be much lower risk depending on the phase.

Basically their argument is that in all those other games determining the optimal strategy is computable (in the computer science sense) while MTG is the only non-computable real world game they could find. If that is a valid definition of a 'complex' game is left as an exercise to the reader.

Did you actually read the paper? There's a mathematical definition of complexity that is used, and on that metric it is shown to be far harder than any other previously analyzed game.

Yes. The paper is good, the title of the submission was not.

Of course by now the title and even the submission link has completely changed (it was linked to an article before).

Complex in a cs sense.

Chess is fully computable. Magic is not.

Direct link to the study "Magic: The Gathering is Turing Complete":

https://arxiv.org/pdf/1904.09828.pdf

Thanks, from reading the abstract, is sounds as if they have an algorithm for the halting problem.

Thank you sir, I am not smart enough to find the direct link from the overview page linked apparently.

You're welcome.

When I posted this, the thread linked to a sensationalist article. The link was later edited along with the title.

Basic question but what does being Turing complete actually signify? I get the concept but don't know why it matters.

In theory, if you can perform a computation/algorithm on one turing-complete device, you can transform it to run on another. That is to say, anything your desktop computer can do, Magic can do as well (albeit much much _much_ slower).

To be more accurate: anything your desktop computer can compute, Magic can compute (disregarding resource constraints).

Hm so the mechanics within the game provide all the logical basis that a cpu requires?

Setup the correct way, yes.

saying anything your computer can do in such a sentence is misleading. computers are far far away from turing machines these days. they can do much more. for example, good luck making a socket connection on Magic the gathering. even if you can compute everything you need with it, you will never succeed to connect...

That's a statement about the practical engineering involved, yes. However, saying a computer is "Turing complete" is not misleading. It is purely a statement of its mathematical properties.

If sockets were given absurd timeouts and/or you could run MtG at much higher speeds, (and it was given a medium through which it could communicate), it would have no problem making a socket connection. It is only the practicality of the matter that becomes a barrier.

You're missing the point.

Technically it means if you're trying to write an algorithm to play Magic the same algorithm could translated and applied to solving the halting problem (i.e. a reduction of Halt to Magic exists). So your task is that difficult. Thus the theory says it is a logical contradiction for any algorithm to exist that can solve Magic. In practice, this can be different because we are routinely successful in special cases for example we still have anti virus programs in practice, just no one perfect anti virus program can exist for the same reason.

What happens in Magic when you run out of cards? If the tape isn't infinite then there are lots of algorithms that halt.

The halting problem is like the pigeonhole principle. Just because there is no general compression algorithm doesn't mean we don't use compression all day every day. We have solutions for many interesting subsets of the problem domain, and that's good enough.

We can also tell if a program will halt in no more than N clock cycles by providing the analysis with a budget. If the budget is exhausted then the program would keep running for an unknown duration longer than the limit. Possibly 1 cycle. For third party code, you could just refuse to run that code at all. There are some useful programs that would get rejected but there are many useful ones that would not. So implementing an "infinite loop detector" as a "really big loop detector" wouldn't be the dumbest thing to try, anymore than implementing video compression is.

My understanding is that the undecidability of the halting problem is equivalent to the undecidability of the decision version of compression (does a given string have a Kolmogorov representation, or not). They're saying the same thing and mathematically equivalent to Godel's incompleteness as well.

The difference is that with data compression, you don't get random-looking inputs and would explain why text, voice, image domains are amenable to compression algorithms. In contrast, the state space of programs is exponential in the budget N and looks very random. The exponential explosion makes the analysis very inefficient relative to hardware ability. And then the random-looking state sequences are especially not very compressible. These characteristics are harder to leverage.

The pigeonhole principle works for lossless compression but I don't see the analog to Halt or Rice's theorem, etc.

If we knew Magic was limited to N states, then we can conclude that a program running on the Magic Turing machine will never halt if it has not halted after BB(N) steps.

In magic, if you run out of cards, you lose, but there are ways to restore your cards so you never run out, so games can continue theoretically forever.

And even if you don't, it's possible to create infinite resources combining a finite number of cards. Like creating infinite tokens, infinite mana. The paper uses an infinite number of creature tokens to represent an infinite tape.

General and obvious answer: That means something can (theoretically) compute on it’s own, on the highest computing level.

Personal importance: something like mgtg and duplo train tracks, which isn’t intended to build a Turing computer, is used to build one, it’s challenging and a creative outlet of tech knowledge. My favorite example is red stone in Minecraft.

It means telling whether the game is a draw or a win is undecidable. So magic strategy is not computable.

It should be retitled as 'MTG is the most complex game we've played'. I would counter that other card driven games like Android Netrunner, Terraforming Mars, Lisboa, Hanabi, etc are just as or even more complex.

I have to disagree on that. At least Terraforming Mars and Hanabi have a playtime limited by ever-dwindling resources. I don't know the other games, but I suspect they also have some kind of supply that has a limit in how much it can be used/aquired.

MTG has ways to return to a previously seen play state, technically allowing a game to continue infinitely, depending on your deck, of course.

Loops don't really add complexity. MtG can add now tokens of arbitrary number. So that can add arbitrary complexity.

Terraforming Mars can continue infinitely. The end state requires players to deliberately take the actions to reach it. If no player chooses to end the game, it never will. Players could continue forever to use engines that generate points each round, to unbounded totals.

By game theory they shouldn't; eventually a player will be able to end the game while ahead and should do so; but we're already disregarding the motivation of winning for MTG.

(An expansion introduces a rule that each round automatically advances one of the game-ending parameters, but says you can play either with or without that rule.)

I don't know the others, but I played Terraforming Mars and, compared to MtG, it is a very simple game - even without taking into account the vast difference in number of available cards.

In TM there is almost no re-using of cards. Once a card is played, it either is discarded (red), provides a one-time bonus (green) or provides passive/active effect (blue). Only blue cards could be considered as being re-usable, but even that is only as far as the actual passive/active effect goes (which is separate from the effect it may generate when entering the game). Compare it with MtG, where many cards provide effects which allow discarded cards to be returned to the game (ranging from simple "ressurect creature" effects to such that allow shuffling whole stack of discarded cards back into the deck).

Also there is no stack in TM. And gaming the stack to your advantage is one of the core mechanics of MtG. A card you played may have different effects depending on cards your enemy plays in response, and these may have their effects altered by the cards you play in response, etc.

"Complexity" has a very precise meaning. None of these other games have been proven to be Turing Complete.

I played Netrunner a lot, and it beats MTG in base rules(as i do mean absolute minimum of MTG rules) complexity.

When it comes to cards themselves, and their effect on gameplay, it blows netrunner away.

Just look how effect layers are constructed, or even a simple stack and priority itself, not to mention infinite loops.

I do agree that i had way more fun playing Netrunner, mostly because you cannot be mana screwed/flooded like in mtg - as you can spend action to get resources or cards.

From the paper:

"In this work, we solve this problem by reformulating the construction to exclusively use cards with mandatory effects."

So it's more a of a subset of MTG's rules. Still, there are commercial video games out beyond MTG and they've been out for some time. Why has the game theory field not kept up with them?

> Still, there are commercial video games out beyond MTG and they've been out for some time. Why has the game theory field not kept up with them?

Why assume that it hasn't? The paper cites http://drops.dagstuhl.de/opus/volltexte/2018/8805/pdf/LIPIcs... which claims to "show the undecidability of whether a team has a forced win in a number of well known videogames including: Team Fortress 2, Super Smash Brothers: Brawl, and Mario Kart."

No it isn't: The goal is to use a specific construction with specific cards to build a universal Turing machine.

Unlike previous attempts, which used cards that leave some room for Player agenda, this new version doesn't.

I'd claim strongly, that any game with:

- finite number of pieces (eg. cards)

- finite number of actions each round

- clear endgame criteria

is computionally solvable. What comes with randomness is stochasticity, but if that made game unsolvable what about poker (solved for limit heads-up) and even scrabble?

Probably it's kind of semantic problem. I'm not complexity nor game theory expert.

Magic The Gathering is different from the games you mentioned in that it is defined by cards that rewrite the rules of the game. There are already at least five known ways to implement Turing machines, for example:

https://www.toothycat.net/~hologram/Turing/

If you then think about the sheer number of existing M:tG cards and the implied number of possible combinations of those cards and changes to the rules (even if "optimized" to combinations that eliminate obviously nonsensical strategies like only having spells that require green mana and no sources of green mana) and the ways those cards can interact, then the computational complexity of the game explodes in ways that no other game can compare to.

And that's not even what these people showed, I think. They showed that beyond this, the complexity is worse than NP-hard.

FWIW that's my old site, showing the 2012 version of the result, which required cooperation between 4 players. The version in the paper on arXiv is the result of my latest research (with Stella and Austin) where we get it down to 2 players and eliminate all choices required by any player.

I am planning to update the toothycat.net site pretty soon with this new result, though.

> I'd claim strongly [...] I'm not complexity nor game theory expert.

Why are you making “strong” claims in a field you admittedly are not an expert in? This is not how polite nor useful conversations happen.

MTG doesn’t have finite number of pieces, or finite number of actions each turn though.

Naturally people have implemented Turing machines in mtg. www.toothycat.net/~hologram/Turing

Also, the endgame criteria of mgt can be changed, but that said there is only a finite number of simple possible endgames in a sense.

It depends. I'm pretty sure it is possible to layer an unlimited number of contrasting win/lose conditions; distinguishing essentially different "endgames" seems slippery.

Actions in Magic: the Gathering let you create "tokens" which are like cards but aren't limited in number. Although you can only have a finite number in any given game, there's no upper bound on how many you can have.

There is indeed no limitation on the number of tokens in a game.

There are many combo wins that involve having (technically) infinite tokens, dealing infinite damage, gaining infinite life, taking infinite turns. You get the idea.

I said technically because in practice, setting this to a very large number is enough for the win. Dealing 1e6 damage is, although possible, already way overkill in most cases when your opponent starts with 20 life.

Though you do need to pick a number. The paper itself describes a game state which devolves into the 'the player who picks a larger number wins', and even gaining a large but finite amount of life can be dangerous if you don't go large enough (I have heard of a specific example of someone gaining arbitrary life, picking a google, and then losing by have their life reduced to zero through a series of losses of half their life).

Combat resolution/targeting can get a wee bit out of hand:

https://i.redd.it/wyn3d22evs011.jpg

This is not the worst I've seen, simply what I was able to turn-up on short notice.

EDIT: To clarify (the UI isn't great), what you see above is a selection of the "cards" (creatures/tokens) in play, more are off screen.

Maybe the UI isn't great in an absolute sense (that situation would be really tedious to play), but I don't see how it could be made substantially better. It wouldn't be better if that situation arose in a physical Magic game either... the problem there is the game state, not the UI.

My point was that for people that have never seen MtG Arena before, it's non-obvious that there's more going on off-screen. A more intuitive UI would make that situation more explicit and not require explanation.

As you've rightly pointed out, a better UI isn't going to solve the UX issue of ridiculous game state; but it could better depict the state itself.

Do you know if there is a video showing a full turing complete game? I can't quite visualize what is going on.

Well some cards can create additional (potentially infinite) game pieces or resources with which to preform more actions per round.

The output of a computer program can be unsolveable, even though the source of the program has finite characters. It's the same thing. (Literally: you're building an interpreter out of cards.)

MTG can have:

an infinite amount of pieces(there are cards that restore your library, generate infinite amount of mana/tokens)

infinite amount of actions each round, by each player too!

Endgame criteria which can be changed by cards themselves.

Some game have more states than there are atoms in the universe. They are solvable in theory but we will need a bigger universe to put this theory in practice...

Actually they are not even solvable in theory even with a bigger universe of insanely powerful computer. Which is what it means to say that mtg is Turing complete.

Add at least one more:

- doesn't let you repeat actions, or patterns of actions (move back and forth in a stalemate like pattern).

Detecting non-trivial stalemates is hard, though.

Here's a game. It has just one card, it says: "repeat this card's action". Is it solvable?

Turing completeness in something designed to be domain specific is a sign of bloat and is a sort of smell. It's a sign of a design taken so far that it now has the capability to compute anything when in all intents and purposes it's design is domain specific.

One other example of this is css. Did you know css is Turing complete?

Note that most programming languages are Turing complete because that is the domain: To express every possible computation in the language, and thus in these cases Turing completeness is not a design smell.

CSS is not turing complete. CSS can do arithmetic, but it has no way to designate routines or repeat its own behavior.

You are not categorically wrong because I missed some semantics in my statements. However the essence of what your saying is incorrect.

Let me rephrase more specifically: CSS3 + HTML5 is turing complete. Since CSS is always used in the context of HTML I left that out, but rigor is important!

source: https://stackoverflow.com/questions/2497146/is-css-turing-co...

Note that this happened with the later versions of CSS indicating that the specification became turing complete after years and years of tacking on features. This is the pattern of bloat accumulating over time.

MtG is played by choosing 60 cards from 20k. Everything is finite. There must be some generalization in order to make it noncomputable.

There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large.

EDIT: This from the real abstract sounds very strange:

"Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable."

As the other repliers have explained, MtG provides various ways to circumvent that. Thus we found ways to encode millions of pieces of state in tokens, and we ensured that the game loops round computing the Turing machine execution one step at a time.

Your sentence "There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large" is actually key. You're completely right - there are many. What's unusual about our result here is that we found a way to embed a fully functional Turing machine inside not an arbitrary extension of a board game, but inside a board game exactly the way it's normally played.

> EDIT: This from the real abstract sounds very strange:

> "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable."

It's not so strange: the game is Turing complete, so the winner can be undecidable because who wins is the result of some arbitrarily complex computation.

Imagine we play a "game" where I win if there's a nontrivial zero of the Riemann zeta function with real part not equal to one half, otherwise you win. Neither of us has any decisions to make in this game. It's still very difficult to determine who's going to win.

Can you ELI5 how a game can be Turing complete? I have only heard that in relation to programming languages.

A Turing machine has a simple loop of reading the current tape cell, and depending on the current value, writing a new value, changing state and moving the read head on the tape. The paper shows that there are cards in MTG which can be used to implement that kind of loop.

The tape is represented by tokens whose strength increases with their distance from the read head, such that the current cell is the weakest one. On every loop iteration, it gets killed (read) and triggers different effects depending on its type, such as getting replaced (writing a new value), changing the effects that will be active on the next iteration (changing state) and dealing damage to one side of the tape but not the other (moving the read head).

Magic is played by taking a card from the top of your pile and following the instructions on it, then your opponent does the same. In normal games the decks are shuffled, but for this to work you have to be able to program the order of the cards in both decks. In this paper they program the game by constructing the decks using a subset of cards that all have mandatory effects.

I think what they do is set up a sequence of cards that 'initialises' the game state with various creatures and resources. These together with the game rules form the Turing machine. Then they have a sequence of cards that correspond to the 'paper tape' of symbols a Turing machine operates on.

there are cards that:

restore your library,

grab cards from exile(out of game, literally),

Reverse win conditions,

Prevent losing,

Generate infinite loops - both deterministic and not(with randomness).

Create tokens(sometimes coupled with above) - which provide unlimited resources with a sac outlet.

And those aren't fringe cases - for example in EDH format quite a lot of decks win by creating some kind of infinite loop, or by generating infinite resources(or sky high amount of them)

So i would argue that resources aren't finite.

AFAIK 60 the minimum number of cards you have to put in your deck, but (at the least at the times) there was not a maximum number.

20k is the number of unique cards, but you can put as much as 4 copies of the same card in your deck for the vast majority of cards. You can also put as many "normal" lands as you wish in your deck.

For constructed formats the minimum is 60. For limited formats the minimum is 40. For EDH/Commander it is 100 (including the commander card).

Every card that either has the subtype "basic" or that has a card text that explicitly states so (for example: Relentless Rats), can be included in any number of copies. All other cards can be included at most 4 times or at most 1 time if it is a EDH/Commander deck.

There are 11 cards with subtype basic: https://scryfall.com/search?q=t%3Abasic&unique=cards&as=grid...

And 4 non-basic cards that can be included in any number: https://scryfall.com/search?q=o%3A%22A+deck+can+have+any+num...

As many as you can shuffle unassisted is the upper limit.

Does this mean that players with larger hands are allowed more cards? Or is it an idealized "you can shuffle"?

In practice there is no strategic benefit of having more cards. There is one bad deck that uses more than 250 (to win with Battle of Wits). It arguably breaks the rule already.

This is an interesting rule, as it seems to provide an advantage to players on the basis on hand size.

It's not, pretty much all decks stick to the minimum required number because the more cards in your deck the less likely you are to see any particular card you want or need. To that end where they're available in the format many decks will run 'fetch lands' which search the deck for a particular type of land in order to thin out the remaining deck.

More cards is not seen as an advantage. There are a couple cases where you may want more cards, but usually up to about 75. It's about drawing the right cards, not just many, and more cards makes your deck less reliable, simply on the likelihood of drawing the card you want.

Unless you really really want a Battle of Wits deck (which is maybe tier 7) there is really no advantage and quite a bit of a disadvantage to running more than the minimum allowed number of cards.

For those who don't play Magic, this is on a scale where tier 1 decks are top decks, tier 2 decks are reasonable, tier 3 decks have serious weaknesses but are playable.

And at least there is a card that can be insert an unlimited amount of times and it is not a land. So technically, the combinations are infinite.

Presumably there is an optimal Island / Persistant Petitioners only deck ratio against a dumb opponent who does nothing but draw a card a turn and play a land.

I wonder if it's irrational?

Since you want to draw both lands and petitioners, there's an advantage to having a smaller deck, so this probably wouldn't be the case.

Aha, thanks! Then my comment does not apply!

> Everything is finite.

No, you can recycle resources and there are cards that remove termination conditions of the game. For example Platinum Angel or Lich's Mastery.

Do keep in mind that 60 cards is just one Magic format, one of the most popular official formats is Commander which is 100 card singleton.

Beyond that, those are not cards in the sense of poker cards with stats and an effect. Many of these have unique effects specific to that card.

There are also 100+ categorical effects. Creature types, color types.

Plus Magic is played on both players turns unlike other card games. Divide both turns into phases with pros and cons of casting.

It's more complex than it sounds when you just call it a "card game" - it is much more deep than most any other card game and does not truly feel like a card game except the fact that you play with cards.

The game has infinite loops, race conditions, etc which come in many unpredictable shapes.

>EDIT: This from the real abstract sounds very strange:

>"Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable."

It is very straightforward. They are saying that, in the turing machine scenario they've set up, for each player's move, the decision they have to make is obvious, so the players don't have to collaborate in order to produce the scenario, it will arise naturally out of the state of the game with two rational players trying to win.

I think they actually engineered it to not just involve obvious or optimal choices by each player, but to give them literally no other choice but to watch the machine do its calculation (or concede the game). They do this by causing all cards other than those needed for the machine to be removed from the game.

In a non-cynical way: are you aware the PDF can be viewed on the right?

You can easily gain infinite amount of mana, life, creatures.

Eh, just because you have a big 20000 choose 60 initial set doesn't make it "most complex".

That's not their argument either. The gist of their argument is that you can combine those cards and the legal moves they allow to encode a Turing machine and thus determining the winner is equivalent to solving the halting problem.

Deck building is not the entirety of the decision involved in playing magic. One of the points in the paper is that the number of decisions in the game is potentially infinite and that the consequences of those decisions can at lease in principle be rendered incomputable.

And the paper proves that this is true even if all the moves in the game are forced by cards that give you no choices to make as players.

Also, most of the cards are probably some basic lands and simple creatures without any skills.

I would be surprised if this is the case. Of those 20k unique cards, exactly 5 are basic lands (6 if you count Wastes). I also have a feeling that vanilla creatures are less common than non-vanilla creatures (and creatures are a just a subset of all card types).

They meant most of the 60 chosen are lands.

Reply on news.ycombinator.com