2

For this question we stablish games as officially recognized board or card games.

Several sources stablish that game as the most complicated one, although it does so by mentioning that a computer was unable to determine optimal play, although it does not explicitly mention that it was compared to all other games.

Some sources are the following:

It's Science: 'Magic: The Gathering' Is The World's Most Complicated Game

"Magic: The Gathering” is officially the world’s most complex game

No doubt it's a hard game to play, but I'm skeptical about the claim as I don't think it can make much difference to, for example, any other card game that is big enough (I'm no expert in "Magic: The Gathering.") I doubt they have checked every possible game in order to determine that it's the hardest one.

From the paper:

This construction establishes that "Magic: The Gathering" is the most computationally complex real-world game known in the literature.

Is the claim that it is the most complicated game in the world true?

12
  • 6
    All three articles reference "Magic: The Gathering is Turing Complete" by Churchill, Biderman, and Herrick (link is to a preprint; I don't know if it's been published).
    – benrg
    Aug 26, 2021 at 20:01
  • 2
    Can you provide some of the claims for why it is the most complicated game? Would be nice to see what they are talking about without having to read a couple of websites and an academic paper.
    – Joe W
    Aug 26, 2021 at 20:21
  • 4
    The titles of those linked articles are misleading. Neither story suggests that MtG is "the most complex" game. They say that researchers have claimed that outcomes of the game cannot be determined with a brute-force algorithm. Maybe then the question should be, are there other games that can't be solved with a brute-force algorithm. But unless it's commonly believed that MtG is the only such game, that question won't be appropriate for this site.
    – Juhasz
    Aug 26, 2021 at 20:44
  • 1
    @Juhasz agree with your sentiment. The articles say it's the most complex real world game, but the paper that it's based on just says that it's Turing Complete. Admittedly Turing Complete means that it's as complex as it can be, as solving it involves solving the unsolvable Halting Problem. This is probably better for BoardGames.SE.
    – DenisS
    Aug 26, 2021 at 20:51
  • 4
    I feel I should mention Nomic, which is also a game (albeit a free one, not one published by a company) whose main gameplay consists of changing the rules of the game itself, which means that AI cannot play the game at all and also that it's more complex than any other game simply because the players can choose to make it so.
    – Erik
    Aug 27, 2021 at 6:37

3 Answers 3

15

Magic: the Gathering is computationally complex, not "complicated"

At least it's not "complicated" in a way that's been quantified by these sources. They appear to be confusing the meaning based on a sloppy understanding of a scientific paper.

"Computational Complexity" is a mathematical concept, and the paper referenced in these articles finds that M:tG is "Turing Complete," which is again a mathematical term with a precise definition. Put very briefly, the rules of Magic can be used to simulate any computer program, given enough time.

This is a clever result, but it doesn't say much about whether the game is "complicated" according the everyday understanding of the word. For example, a different paper from 2007 found a similar trick with the game Minesweeper. Most people would agree that Minesweeper is less "complicated" than Magic, but according to these papers the two are equally "computationally complex".

It's difficult to prove a negative, there does not appear to be a serious or authoritative attempt to classify games by "complicatedness." In any case, the claims in the question do not reference one. Instead they confuse the meaning of a mathematical term used in an academic paper.

6
  • From the paper: "Consequently, we have shown that identifying the outcome of a game of Magic in which all moves are forced for the rest of the game is undecidable." - that's saying more about its complexity than just that it's Turing Complete. You appear to have cherry-picked one particular point they made about its complexity and run with that.
    – Rob Watts
    Aug 26, 2021 at 21:16
  • 4
    @RobWatts That isn't saying more than that it's Turing complete. The undecidability follows from Turing completeness. The Turing completeness is the main result of the paper/preprint, and as far as I can tell they claim nothing stronger than that.
    – benrg
    Aug 26, 2021 at 21:57
  • 5
    The 2007 paper found that for minesweeper played on an infinitely-sized grid. Which is definitely not "real world", so the claim that Magic is "the most computationally complex real-world game" is not really in contradiction. Aug 26, 2021 at 23:40
  • @Fizz just because it's the only one found so far (and even that's debatable depending on your definition of "game") doesn't make it the only Turing-complete game Aug 27, 2021 at 4:32
  • 4
    I'm with Rob Watts -- the key finding is "that optimal play in real-world Magic is at least as hard as the Halting Problem" not the fact that Magic is Turing complete (which is interesting and part of how they proved their result). The rules of Magic could be Turing complete in the sense that it is possible to implement a Turing Machine using them w/o optimal gameplay mapping onto the halting problem (or at least that optimal game play maps onto the halting problem needs to be proven, rather than just taken as a given from the fact that the rules are turing complete)
    – Dave
    Aug 27, 2021 at 14:20
8

The authors (Churchill et al) make a rather strong claim:

Prior to this work, no undecidable real games were known to exist.

By "real game" they seem to mean a game played with the rules that are used in real life, rather than modifications of the rules. This may be where reporters got the idea that Magic is "the most complicated game", so it's worth examining.

The rules of most games immediately rule out Turing completeness, as the authors themselves point out:

As most games have finite limits on their complexity (such as the size of a game board) most research in algorithmic game theory of real-world games has primarily looked at generalisations of commonly played games rather than the real-world versions of the games.

(I added the Wikipedia link.)

Turing completeness requires an unbounded number of states and an unbounded number of moves (reference: any computer science text), so the claim that Magic as actually played is Turing complete includes the claim that there is no limit on the duration, move count, or size (number of pieces in play) of a game in the real-life rules. For example, if you are only allowed to use cards and tokens that were manufactured before the game started, then the number of pieces in play is bounded, and the game is (in the authors' words) "trivially decidable" as a result. I don't know whether rules of that sort exist in Magic tournaments, but I would expect that they do, either explicitly or as a consequence of other explicit rules.

In the abstract they also claim

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.

Undecidability requires an infinite set of problem instances, so this claim doesn't apply to initial states (decks), since those are always limited in size and content by the rules. It applies to games which started an unbounded number of moves ago, in which the players have already made an unbounded number of non-trivial decisions, since that's the only way to created an unbounded number of different states. (It also applies only if the rules satisfy the requirements of Turing completeness as mentioned above.)

They also make the following odd claim:

[L]eading formal theory of strategic games claims that the unbounded memory required to simulate a Turing machine entirely in a game would be a violation of the very nature of a game [9].

They return to this later, and seem to believe that they've shown that existing models of games are inadequate to describe Magic, which is definitely wrong. Reference [9] is "Constraint Logic: A Uniform Framework for Modeling Computation as Games" by Demaine and Hearn. Churchill et al may be referring to the section "What is a game?" where Demaine and Hearn say

One key difference [between games and Turing machines] is in the size of the state: Turing machines have infinite tapes, so the state at any time is unbounded, while we always require the state of a game to be defined by a finite board position. We can, of course, bound the size of a Turing-machine tape, or use a circuit model of computation, but such restrictions limit the model of computation from general decidability. By contrast, we show that no such limitations exist for games.

It's unclear to me what Demaine and Hearn are trying to say here. The statement that "the state at any time is unbounded" is false at face value. The state of a Turing machine at any time is finite (i.e., finitely describable) in the same way as the games they model. Since they say "no such limitations exist for games", and later use Conway's Life (which has long been known to be Turing complete) as an example of a game, it seems clear that their framework does support games like unbounded Magic – and even if it doesn't, there is nothing remotely new about the idea of mathematically modeling such games.

Churchill et al in their conclusion even say

it seems likely that a super-Turing model of games would be necessary to explain Magic.

(italics theirs). If this is a claim that Magic might violate the Church-Turing_thesis – and I see no other way to interpret it – then it's absurd, and completely unsupported by the rest of the preprint.

The answer so far is based on the arXiv preprint. This work has also been published as a peer reviewed conference paper, according to Biderman's CV. The full conference proceedings including this paper are available here. The published version seems to be essentially the same, including even the more extreme claims from the preprint, which leads me to question the competence of the reviewers and editors.

6
  • Given that the game itself has some 200-page rulebook and the paper often refers to one or other rule, I'm not too surprised probably no "regular" reviewer at a CS conference could really vouch for the correctness of all the claims... (unless they happed to be a regular player of this game) but the fact that they only gave a passing read to the more clear CS claims is rather disappointing. Aug 27, 2021 at 10:20
  • It seems the gist of the unboundedness comes from some "move" that could actually take an arbitrary number of steps. Right before the conclusion they say "In addition to the Comprehensive Rules [16], play at sanctioned Magic: The Gathering tournaments is also governed by the Tournament Rules [17]. Some of these rules, most notably the ones involving slow play, may affect an individual’s ability to successfully execute the combo due to concerns about the sheer amount of time it would take to manually move the tokens around to simulate a computation on a Turing machine." Aug 27, 2021 at 10:28
  • "This would not be a concern for two agents with sufficiently high computational power, as the Tournament Rules also provide a mechanism called “shortcuts” for players to skip carrying out laborious loops if both players agree on the game state at the beginning and the end of the shortcut." So their claim that this is "real-world" is only about the game ruleset in reality... rather than about the instance they analyze/prove as Turing-complete... I should probably write this as an answer, but I'm not 100% sure I understood what they meant. Aug 27, 2021 at 10:30
  • It's even less clear to me what counts as arbitrary-size tape. It seems you can generate arbitrary numbers using some card combos. (These numbers are part of a "board state" that decides if a move is allowed, or something like that.) At one point they refer to a SE discussion on that matter: cstheory.stackexchange.com/questions/41384/… Aug 27, 2021 at 12:39
  • In regards to the game as played being unbounded, the number of MtG cards in a game is finite and fixed, but various game mechanics use non-card tokens, and the number of tokens in play is potentially unbounded.
    – Mark
    Sep 9, 2021 at 2:12
4

Yes, the claim appears to be true in a certain precise, technical sense based on notions of theoretical computer science. This may or may not correspond to the subjective human experience of a human player comparing how “complicated” they regard it is to play Magic: The Gathering versus some other game.

  1. Credibility of the research.

The claim in the Forbes article is based on an academic paper (“Magic: The Gathering Is Turing Complete”, by Churchill, Biderman and Herrick). So it makes sense to first ask if that research is even correct. The paper was published in the proceedings of the 10th International Conference on Fun with Algorithms (FUN 2021), a computer science conference. So it is peer-reviewed, at least by the standards of a computer science conference. Although it is well-known that math and computer science conferences aren’t quite as strict with their peer review process as academic journals (since they operate on a tight schedule), that lends the research a good level of credibility.

Moreover, the technical claim of the paper is quite plausible. I haven’t read the details, but what it’s doing is fairly similar to standard ideas used in the literature. There are many papers discussing the computational complexity of various games.

Based on those two factors, I would assume that the result of the paper is correct with a pretty high likelihood. Although there is a possibility that the results are incorrect — mistakes do happen occasionally in this kind of theoretical research — the chances of this being the case here seem pretty small.

  1. Technical content of the claim.

The technical claim is that Magic: The Gathering is Turing-complete. That means, loosely speaking, that determining the outcome of a game given its current state, assuming players are playing optimally, is a question to which the answer is potentially not just very hard to find, but unknowable even in principle. So, in some sense that means Magic is not just the most complex game known, but the most complex game that can exist. That is, its complexity may be matched by some other games, but cannot be exceeded.

The way the authors of the paper show this is by showing that to answer the question about the game’s outcome one has to be capable of answering a different question (“does a given Turing machine ever halt?”) for which it is already known that the answer is potentially unknowable (in technical language, the halting problem is undecidable). This type of argument is standard in theoretical computer science, although the specific details of carrying it out vary from case to case.

  1. Summary.

Articles in the media trying to make academic research “accessible” to the public usually don’t do a very good job of conveying precisely what the research claims; often they even deliberately try to sensationalize the results and make them sound as exciting (and, dare I say, click-baity) as possible, which comes necessarily at the cost of a further loss of precision and nuance. The Forbes article cited here is no exception, so some healthy skepticism is certainly warranted. Notably, the original authors of the study did not claim that “Magic is the most complicated game”, but made a precise technical claim.

With that being said, it is not unreasonable to interpret their claim as fundamentally saying that Magic is, in a theoretical sense, as complicated as any game can ever hope to be.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .