SoylentNews is people
SoylentNews
"Magic: The Gathering" is officially the world's most complex game
Magic: The Gathering is a card game in which wizards cast spells, summon creatures, and exploit magic objects to defeat their opponents. In the game, two or more players each assemble a deck of 60 cards with varying powers. They choose these decks from a pool of some 20,000 cards created as the game evolved. 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.
And that raises an interesting question: among real-world games (those that people actually play, as opposed to the hypothetical ones game theorists usually consider), where does Magic fall in complexity?
Today we get an answer thanks to the work of Alex Churchill, an independent researcher and board game designer in Cambridge, UK; Stella Biderman at the Georgia Institute of Technology; and Austin Herrick at the University of Pennsylvania.
His team has measured the computational complexity of the game for the first time by encoding it in a way that can be played by a computer or Turing machine. "This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature," they say.
Magic: The Gathering is Turing Complete (arXiv:1904.09828)
Related: How Magic the Gathering Began, and Where it Goes Next
(Score: 0) by Anonymous Coward on Thursday May 09 2019, @07:44PM (3 children)
Admittedly I wouldn't have thought about it this way, so this is still scientifically interesting and useful to know.
However, in retrospect, this is an obvious finding. We have a game system with exponential (or at least high-polynomial) game mechanic interactions; when a new card comes out which says "deal 1 damage to a creature," it nominally can interact with every other creature ever created. Moreover, it is still changing with new content being added.
I can't think of any other games which have both of those attributes, and have more raw content than Magic (it being the first), so, "of course it is the most complicated one."
(Score: 1, Insightful) by Anonymous Coward on Thursday May 09 2019, @10:54PM
There are MUDs out there that have been in operation for 2 to 3 decades
(Score: 0) by Anonymous Coward on Friday May 10 2019, @12:31AM (1 child)
On the other hand, every card which says "deal 1 damage to a creature," is functionally identical, regardless of the picture and the name. The actual complexity of MtG really isn't that insane from some perspectives. It's just that the rules allow a ton of cards that don't exist, so you have this totally arbitrary subset of the rulespace in the cards. In some sense, the game of all possible Magic cards is actually quite a bit simpler to analyze than the game of all extant Magic cards.
Past that, any given game of Magic using only specific cards is not insanely complex, because the existence of thousands of other cards outside of play doesn't actually effect a specific game with specific decks. It's only when you get to trying to analyze how to acquire and build optimal decks out of actual cards that it really turns impossible to explore.
(Score: 3, Informative) by vux984 on Friday May 10 2019, @03:15AM
"On the other hand, every card which says "deal 1 damage to a creature," is functionally identical, regardless of the picture and the name."
More or less yes, the picture never matters, but behavior can diverge on color, cost, name, and even what set they are from:
https://scryfall.com/card/hml/101/apocalypse-chime [scryfall.com]
"Past that, any given game of Magic using only specific cards is not insanely complex, because the existence of thousands of other cards outside of play doesn't actually effect a specific game with specific decks."
Correct. Unless:
https://scryfall.com/card/jud/64/death-wish?utm_source=api [scryfall.com] ...and many more.
MtG likes to mess with you.
there are cards that change the rules; add triggers, change the mechanics, change the victory conditions... or do all at once...
https://scryfall.com/card/dom/98/lichs-mastery [scryfall.com]
And even card's that change the text of other cards...
https://scryfall.com/card/5ed/124/sleight-of-mind [scryfall.com]
Cards that are two cards (split cards) that you can play either split, two faced cards that have either one face or the other active at a time. And then when you start cloning and copying them and moving them between zones with Clone, Phasing, etc yeah.
I've always thought its among the most complex games out there.
And then you can add the parody/party cards from unglued and unstable etc to really mess things up. I wonder if they even looked at that stuff.