“Magic: The Gathering” is officially the world’s most complex game
technologyreview.com
technologyreview.com
> 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.
Anyway, I'm certainly glad that Technology Review has stumbled upon this groundbreaking achievement that we've known since 2019: https://arxiv.org/abs/1904.09828 and reported here repeatedly: https://hn.algolia.com/?q=gathering+turing
The article was published in 2019, about a month since the arXiv paper was published.
> If I did the math right, the odds of hitting the opening hand you want is 0.00004%. Give or take a mulligan and maybe being able to get the combo off on turn two or three I think that's high enough odds that one could conceivably eventually succeed (assuming they can find opponents for years and years).
Here's the deck list: https://www.mtggoldfish.com/deck/3933484#paper which has actually come down in price a decent amount recently. It's on my list of silly things to buy.
> 4 Power Artifact $996.00
Yeowzers, I wonder if there are replacements for those two cards that would bring the price down into the realm of what I consider "silly things to buy"?
If it's because you want to play the deck and see it work, then just get a sharpie, some paper, 8 generic Magic cards, and some deck sleeves. For those 4 cards, just write "Grim Monolith" or "Power Artifact" plus whatever else you need on there to remind you what they do.
If that's not it, or not at least close to the reason you're asking, then the answer is probably that those 8 cards are critical components of the engine, and you need to have them if you're going to play them in a "serious" setting.
I always compare it to something like golf, my nearest golf club is 1500€/year, the equipment would probably be another 500 or so, does this make golf a play-to-win game or just an expensive hobby?
E: Ironically the thing thats most pay-to-win about magic is the way tournaments used to be ran, being actually competitive at a decent level involves 1-2 trips to different cities on the continent a month, with the occasional trip to a different continent thrown in. In my competitive years I spend like 1k/year on cards, pulled in 2k/year in winnings and spent probably 8k in flights and hotel costs.
There are also some very good and still cheap decks. Price is a function of supply and demand, and some decks can take advantage of high-supply low-demand cards (because they only work in a very particular deck).
Budget probably is a factor for tournament play. Small differences can be big at that level of play, and proxies aren't allowed.
Having a high end mtg deck is like having a membership at a private golf club, it gives you access to other players who also are willing to invest good money into the game and take it seriously. My main modern deck is something like $500 and in theory I could sell it and get some of that back down the road. I couldn't imagine shuffling a deck worth 100k+ though.
Playing Magic in tournaments has largely been P2W for decades. It's a collectable card game, so the cards have varying rarity. The more powerful cards cost more on the secondary market. And Wizards of the Coast (and now Hasbro) keeps releasing new cards, which require more investment.
But if I'm playing with my friends, we can make up whatever rules we want. I can easily source proxy ('fake') cards much more cheaply. Or, what we used to do, you get a land card (which is practically worthless) and write the name of the card you want on it. Then you act as if that land is the card you wrote.
So amongst friends it's not nearly as expensive, because you can play Magic outside of the tournament ruleset. Not so with most P2W video games.
From the study: https://arxiv.org/abs/1904.09828
> This paper completes the project started by Churchill [4] and continued by Churchill et al. [5] of embedding a universal Turing machine in Magic: The Gathering such that determining the outcome of the game is equivalent to determining the halting of the Turing machine. This is the first result showing that there exists a real-world game for which determining the winning strategy is non-computable, answering an open question of Demaine and Hearn [10] and Auger and Teytaud [1] in the positive. This result, combined with Rice’s Theorem [13], also answers an open problem from Esche [11] in the negative by showing that the equivalence of two strategies for playing Magic is undecidable.
> This result raises important foundational questions about the nature of a game itself. As we have already discussed, the leading formal theory of games holds that this construction is unreasonable, if not impossible, and so a reconsideration of those assumptions is called for. In section V-A we discuss additional foundational assumptions of Constraint Logic that Magic: The Gathering violates, and present our interpretation of the implications for a unified theory of games.
One is oldschool aka 93/94 where you guessed it, only legal cards are from ABU and the four horsemen sets.
The other (and much better format) is Premodern. Which goes form 4ed to Scourge with a really good banlist, healthy meta and competitive scene.
Highly recommend these rabbit holes if someone is looking into coming back to the game!
The average number of turns in an online game is less than 7 turns. I would further posit that if you constrained possible actions to decisions that good players are likely to make, the game is no longer Turing complete.
You could make a similar claim about a game where any player can win at any time if they choose, but can alternatively do anything else. It’s not computable, but it is irrelevant to the complexity.
You could probably also argue that a Turing intending player is still computable if playing against someone with a defined strategy. Because they will be halted by the other player winning.