Stories
Slash Boxes
Comments

SoylentNews is people

posted by martyb on Thursday May 09 2019, @06:22PM   Printer-friendly
from the Next-target-for-DeepMind? dept.

"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


Original Submission

Related Stories

How Magic the Gathering Began, and Where it Goes Next 35 comments

The game originated in the early 1990s in the mind of Richard Garfield, at the time a graduate student working towards a PhD in combinatorial mathematics at the University of Pennsylvania. A life-long tabletop gamer, he had approached a publisher to pitch an idea for a game about programming robots, only to be told that the company needed something more portable and cheaper to produce.

Magic was Garfield's response, and it involved one major innovation that set it apart from any game previously released.
...
Magic's latest set marks a turning point for the game. Magic Origins focuses on five of the game's most popular recurring characters – a move that provides a jumping-on point for new players intimidated by over two decades' worth of accumulated storylines.

I played D&D, Gamma World, Traveller, and many RPG's avidly into college, but when I first saw Magic and its $20 price for a single card I discovered there were lines I would not cross. As an adult I have a civil engineering friend whom I've watched over the last decade and a half disappear and then emerge, going cold turkey, only to re-submerge for another year. For those who took up Magic, why did you take it up and do you still play?


Original Submission

The Game Mastermind Turns 50 this Year 12 comments

The simple codebreaking game Mastermind turns 50 this year. Vice goes into some background regarding the now classical game and its heyday.

If you only know Mastermind as a well-worn and underplayed fixture of living room closets and nursing home common areas, you may have no idea just how big this thing was in its early years. Invented in 1970, Mastermind would sell 30 million copies before that decade was up, and boast a national championship at the Playboy Club, a fan in Muhammed Ali, official use by the Australian military for training, and 80% ownership amongst the population of Denmark. "I never thought a game would be invented again," marvelled the manager of a Missouri toy store in 1977. "A real classic like Monopoly."

[...] If you don't know Mastermind at all, i.e. you never lived in Denmark, it's played over a board with a codemaker who creates a sequence of four different colored pegs, and a codebreaker who must replicate that exact pattern within a certain number of tries. With each guess, the codemaker can only advise whether the codebreaker has placed a peg in its correct position, or a peg that is in the sequence but incorrectly placed. According to the game's creators, an answer in five tries is "better than average"; two or fewer is pure luck. In 1978, a British teenager, John Searjeant, dominated the Mastermind World Championship by solving a code with just three guesses in 19 seconds. (In second place was Cindy Forth, 18, of Canada; she remembers being awarded a trophy and copies of Mastermind.)

Mordechai Meirowitz, an Israeli telephone technician, developed Mastermind in 1970 from an existing game of apocryphal origin, Bulls and Cows, which used numbers instead of colored pegs. Nobody, by the way, knows where Bulls and Cows came from. Computer scientists who adapted the first known versions in the 1960s variously remembered the game to me as one hundred and one thousand years old. Whatever its age, it's clear nobody ever did as well out of Bulls and Cows as Meirowitz, who retired from game development and lived comfortably off royalties not long after selling the Mastermind prototype to Invicta, a British plastics firm expanding from industrial parts and window shutters into games and toys.

The story relates a couple of tales of intrigue related to the game.

This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
(1)
  • (Score: 3, Insightful) by JoeMerchant on Thursday May 09 2019, @07:02PM (4 children)

    by JoeMerchant (3937) on Thursday May 09 2019, @07:02PM (#841480)

    How much would one have to spend to play Magic the Gathering at those levels of complexity?

    Comparatively, is Hearthstone growing in complexity faster? With Blizzard driving it, I can see Wild mode Hearthstone eclipsing most card games in complexity just due to the sheer manpower driving it.

    Also: is massive complexity really a good thing? I heartily agree with the Hearthstone philosophy of Standard mode where you are limited to "just" the classic plus last two years of cards.

    --
    🌻🌻 [google.com]
    • (Score: 2) by takyon on Thursday May 09 2019, @08:53PM

      by takyon (881) <reversethis-{gro ... s} {ta} {noykat}> on Thursday May 09 2019, @08:53PM (#841541) Journal

      It should be possible to play a digital version of the game, or even with counterfeit cards. I know there is a digital version of MTG, but I don't know if they have filled it with microtransactions or grind. But fundamentally, all the rules and card info are known and can be replicated. And they had to do that to compute the game for this research.

      I suspect it's cheaper than ever to play the game as a cheapskate, since you can just play online multiplayer MTG, but it sounds like bzipitidoo knows more than I do (see below).

      --
      [SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
    • (Score: 2) by tangomargarine on Friday May 10 2019, @04:28PM (1 child)

      by tangomargarine (667) on Friday May 10 2019, @04:28PM (#841902)

      Comparatively, is Hearthstone growing in complexity faster?

      Specifically concerning the Turing-complete aspect, I hear that Hearthstone and Yu-Gi-Oh have a limit on how much board state you can accumulate in one game (max of X minions in play per player). Magic has no such restrictions, and there are decks that can generate arbitrary numbers of tokens in play.

      Would have to look up how many new sets HS releases per year...MtG keeps it up at a pretty good clip. 4 Standard sets a year, and 2-4 others depending on how you count.

      With Blizzard driving it, I can see Wild mode Hearthstone eclipsing most card games in complexity just due to the sheer manpower driving it.

      MtG has an equivalent format called Vintage, where nearly all cards from the game's history are legal to play.

      I heartily agree with the Hearthstone philosophy of Standard mode

      Like above, MtG had Standard long before HS ever existed. And yes, Standard is the big cash cow for WOTC, as that's basically the only way they make money: players opening packs of the last couple sets. It's the easiest format to get into, but after awhile you realize that rotation making your deck illegal every year makes Modern (most sets back to 2003) more affordable long-term, since it doesn't rotate.

      Deck prices of course climb as you go into older formats, but realistically nobody really plays Legacy or Vintage in paper, just online.

      Standard - $60-$600
      Modern - $100-$1,700
      Legacy - $1,100-$6,000
      Vintage - $6,000-$30,000

      source [mtggoldfish.com]

      --
      "Is that really true?" "I just spent the last hour telling you to think for yourself! Didn't you hear anything I said?"
      • (Score: 2) by JoeMerchant on Sunday May 12 2019, @03:09AM

        by JoeMerchant (3937) on Sunday May 12 2019, @03:09AM (#842569)

        Funny, I never paid a cent for Hearthstone (Blizzard has gotten enough of my money other ways - I took it as a philosophical point to play without pay), but... the grind effort required as the decks rotated out eventually helped convince me to quit.

        --
        🌻🌻 [google.com]
    • (Score: 2) by driverless on Sunday May 12 2019, @01:28AM

      by driverless (4770) on Sunday May 12 2019, @01:28AM (#842556)

      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?

      Somewhere below Dragon Poker, I'd guess.

  • (Score: 5, Interesting) by bzipitidoo on Thursday May 09 2019, @07:05PM (13 children)

    by bzipitidoo (4388) on Thursday May 09 2019, @07:05PM (#841482) Journal

    MtG is just crazy expensive. Expect to pay well over $1000 to amass a reasonably competitive collection of cards. And then, expect to pay hundreds more every few months as the game makers churn the collection, removing older cards from play and adding new ones. They certainly were pioneers of "pay to win" gaming, long before online computer games appeared in that space. MtG does have its fun aspects and I played it for quite a few years before I got tired of the crap.

    One of the weirdest parts is the relationship of players to piracy. I regularly used proxy cards, as they were called. Fire up the scanner and the ink jet printer, make a few copies of rare and powerful cards to tuck into the protective plastic sleeves, with a cheap common card to provide the back, and have fun. Or just write the text of the rare card on a slip of paper. But serious MtG players totally freak out over that. Tense up like you're trying to commit a heinous crime, even if it's just a casual game. I never tried using proxies at any official tournament, but I can imagine that definitely being against the rules. They seem to feel that allowing proxies devalues their collection. I suppose it does. What they don't seem to care about is that such techniques would also work for them, let them use rare and valuable cards without paying exorbitant prices. It's like they're rich, and want the "pay to win" aspect.

    In any case, whenever seriously large amounts of money are dragged in to any game, it can warp it out of all recognition. The game becomes very secondary to money.

    • (Score: 4, Informative) by Taibhsear on Thursday May 09 2019, @07:38PM

      by Taibhsear (1464) on Thursday May 09 2019, @07:38PM (#841500)

      To be fair, no one is forcing you to play tournaments for money. Most casual groups don't care about proxies unless it's your entire deck or something you'd literally never have as a new player (Black Lotus, etc.) Plus you never play with the really expensive cards, even in sleeves. You stick those bad boys in a hard case, stick em on a shelf, and print proxies of them to play with. If you want to play on the cheap with real cards look into Pauper format. There's tons of super powerful cards that are common ($0.10-0.50 each).

    • (Score: 2) by nobu_the_bard on Thursday May 09 2019, @08:54PM (5 children)

      by nobu_the_bard (6373) on Thursday May 09 2019, @08:54PM (#841542)

      The reactions to proxies are partly because each player that is serious about the game considers his cards to be an investment. I've known players that offloaded their vintage deck (the most expensive format to play competitively) to help make a down payment on a house. Every "serious" player that invests a lot of time and money into the game wants to believe someday he could walk away if so inclined by just selling his cards to recoup some of those costs.

      I own no high valued old cards for partly this reason. The Chinese fakes have gotten very, very good. I expect someday it won't be possible to distinguish them at all.

      • (Score: 0) by Anonymous Coward on Thursday May 09 2019, @09:16PM (1 child)

        by Anonymous Coward on Thursday May 09 2019, @09:16PM (#841552)
      • (Score: 2) by mth on Thursday May 09 2019, @10:25PM

        by mth (2848) on Thursday May 09 2019, @10:25PM (#841574) Homepage

        Card value depends on how popular a game is. MtG has remained popular for many years, but that's not a guarantee for all games. The people who said they were investing in cards in Valve's Artefact have lost money on those.

      • (Score: 2, Interesting) by Anonymous Coward on Thursday May 09 2019, @10:52PM

        by Anonymous Coward on Thursday May 09 2019, @10:52PM (#841583)

        I was at a friends house for a party. The complete and utter effing wanker uni buddy of my mate saw that there were magic the gathering cards in a cupboard. I didn't know how to play. So, this effing wanker, the kind of person who spends their uni years drinking and crippling other people's chances at finishing uni, pulls a box out of the cupboard and opens it on the floor.

        The owner of the cards walked in as the effing wanker was shuffling the cards. He was upset. He explained that if we wanted to play he had a couple of boxes of common cards. That the box Mr wanker had opened was a brand new still in original packaging box set he was keeping.

        I knew at the time this was a fluckup. The guy did not hold this against me. So far as I know.

        Now I wonder how much that pristine box of magic cards is worth.

      • (Score: 1, Troll) by realDonaldTrump on Friday May 10 2019, @12:49AM

        by realDonaldTrump (6614) on Friday May 10 2019, @12:49AM (#841628) Homepage Journal

        Complicated, and time consuming way of letting folks know, you are rich. Or, at one time used to be rich -- before you bought the very special Magic Cards.

        It's not for me. Not for me because, I have an app and it's so much better. The Fine Art App called, I Am Rich. Very special, very expensive app, crafted in Germany. And I bought it in the early days of iPhone. Something that only 7 other people were allowed to buy. Because Apple saw that one would be a total Game changer and they took it off the market. Turning it into even more of a collector's item -- a limited edition. Only 8 copies were made. And 2 of those, the buyers returned. Something that, I'm sure, they're feeling very foolish about now. Because it's like they were in one of the most exclusive "clubs" in the history of the World. And canceled their membership.

        I Am Rich is very easy to use. I touch the little square on my Home Screen. And out comes the beautiful jewel. The Red Ruby that looks so magnificent on my iPhone XS. I show that one off, very proudly, when I want someone to know that I'm rich. And right away, they know. They know and I can do that without a card table. Without a deck of cards. Without explaining a bunch of rules. It gets the message across so quickly and we can get back to what we were meeting about. Whether it's a nice dinner (KFC), a "friendly" game of Golf, a date with one of the World's top Supermodels, or a strong & smart Nuclear Deal. Terrific!!!

    • (Score: 2) by JoeMerchant on Thursday May 09 2019, @09:13PM (2 children)

      by JoeMerchant (3937) on Thursday May 09 2019, @09:13PM (#841551)

      I know there are too many dimensions to make a simple "card value" - but... that would be my approach to how to play a "fair" card game: both players get to have up to X points worth of cards in their deck.

      Having to buy random packs until you get lucky is just as crappy as baseball cards ever were, moreso: no gum.

      --
      🌻🌻 [google.com]
      • (Score: 2) by vux984 on Thursday May 09 2019, @10:33PM

        by vux984 (5045) on Thursday May 09 2019, @10:33PM (#841576)

        Most people go to the MtG 2ndary markets and buy what they want. In most cases that'll be cheaper.
        You might as well make your points "dollars". And then both players get to spend X dollars :)

        Although lots of people looking for more fair fights do sealed deck / draft. And in non-tournament environments there's a zillion ways to rebalance..

      • (Score: 2) by tangomargarine on Friday May 10 2019, @04:14PM

        by tangomargarine (667) on Friday May 10 2019, @04:14PM (#841898)

        There is a format that does exactly that - Canadian Highlander. [gamepedia.com] But it's not very popular (overshadowed by Commander)...I think I've run into one guy in person who actually had a deck put together for it.

        You may be able to scare up some people online if you wanted to play a game. But you'd probably have to use one of the third-party clients like XMage because I doubt MTGO has built-in support for the point system.

        --
        "Is that really true?" "I just spent the last hour telling you to think for yourself! Didn't you hear anything I said?"
    • (Score: 1, Insightful) by Anonymous Coward on Friday May 10 2019, @02:25AM

      by Anonymous Coward on Friday May 10 2019, @02:25AM (#841668)

      People can't resist artificial scarcity. This is basically Beanie Babies for nerds, and it is built on the same economic house of (literal) cards. Pick the right time to jump off and sell, and you'll do just fine, but just don't be the person that ends up holding the bag.

    • (Score: 2) by tangomargarine on Friday May 10 2019, @04:10PM

      by tangomargarine (667) on Friday May 10 2019, @04:10PM (#841897)

      One of the weirdest parts is the relationship of players to piracy. I regularly used proxy cards, as they were called. Fire up the scanner and the ink jet printer, make a few copies of rare and powerful cards to tuck into the protective plastic sleeves, with a cheap common card to provide the back, and have fun. Or just write the text of the rare card on a slip of paper. But serious MtG players totally freak out over that. Tense up like you're trying to commit a heinous crime, even if it's just a casual game. I never tried using proxies at any official tournament, but I can imagine that definitely being against the rules. They seem to feel that allowing proxies devalues their collection. I suppose it does. What they don't seem to care about is that such techniques would also work for them, let them use rare and valuable cards without paying exorbitant prices. It's like they're rich, and want the "pay to win" aspect.

      With the way WOTC manages things, they tend to reprint $40+ cards that are in high demand very sparingly, so the price never comes down much (or if it does, it's only slightly, for at most a year). Combined with Chinese fakes steadily getting better, I would half like to see us reach the point where the counterfeits can pass as real just to drive the ridiculous price points down.

      --
      "Is that really true?" "I just spent the last hour telling you to think for yourself! Didn't you hear anything I said?"
    • (Score: 2) by driverless on Sunday May 12 2019, @01:37AM

      by driverless (4770) on Sunday May 12 2019, @01:37AM (#842557)

      Thus it's alternative name, "Magic: The Fleecing".

  • (Score: 0) by Anonymous Coward on Thursday May 09 2019, @07:44PM (3 children)

    by Anonymous Coward on Thursday May 09 2019, @07:44PM (#841501)

    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

      by Anonymous Coward on Thursday May 09 2019, @10:54PM (#841586)

      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)

      by Anonymous Coward on Friday May 10 2019, @12:31AM (#841622)

      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

        by vux984 (5045) on Friday May 10 2019, @03:15AM (#841689)

        "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.

  • (Score: 2, Disagree) by darkfeline on Friday May 10 2019, @12:05AM (3 children)

    by darkfeline (1030) on Friday May 10 2019, @12:05AM (#841616) Homepage

    Make a game with the most rules (each card brings with it a "routine" or logic, and there's even extra rules to govern interactions between some cards), of course it's the most complex game.

    It's a pointless title, like the person who weights the most also being the person with the most matter in their body.

    It'd be more interesting to determine the most complex game that can be described/implemented in 1MB for example. Something like N-dimensional Go or Shogi would probably be the winner, although you'd probably want to throw AI at it to optimize the exact rules to use to maximize complexity.

    --
    Join the SDF Public Access UNIX System today!
    • (Score: 3, Insightful) by JoeMerchant on Friday May 10 2019, @01:21AM

      by JoeMerchant (3937) on Friday May 10 2019, @01:21AM (#841637)

      Yes, and no - of course anyone can make up a more complex game, but will anyone play it?

      ~20 years ago, if you put up an e-mail server, you could collect 100+ people to play almost any crappy PBeM (play by email) game, as long as it was free. However, if you cranked up the rules too far, so complicated that people felt like they couldn't compete, the user count would drop off.

      I don't know what their threshold of "popular" was for the study, but I'd set it as something that has endured for 10+ years and has 1000+ identifiable active players, at a minimum.

      I wonder how the game of Go fared in their analysis? Simple rules, astronomical potential outcomes. I bet if you sponsored a pro-league of Go 31x31, you'd not only get the sponsored pro players, but also quite a few enthusiasts who would actively play the even more complex game.

      --
      🌻🌻 [google.com]
    • (Score: 1) by The Vocal Minority on Friday May 10 2019, @05:14AM

      by The Vocal Minority (2765) on Friday May 10 2019, @05:14AM (#841723) Journal

      I had a quick scan through the original paper and I don't think it makes any claim about MtG being the most complex game - only that it is more complex than the halting problem.

      I mean what about ASL, that's supposed to be a pretty complex game?

    • (Score: 0) by Anonymous Coward on Friday May 10 2019, @05:23AM

      by Anonymous Coward on Friday May 10 2019, @05:23AM (#841727)

      here's a turing complete set of rules, and the only limit is the "size of the board":
      https://www.turingtumble.com/ [turingtumble.com]

  • (Score: 0) by Anonymous Coward on Friday May 10 2019, @01:22PM (1 child)

    by Anonymous Coward on Friday May 10 2019, @01:22PM (#841807)

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

    wat

    • (Score: 2) by tangomargarine on Friday May 10 2019, @04:05PM

      by tangomargarine (667) on Friday May 10 2019, @04:05PM (#841893)

      It's high fantasy, with elves and dwarves and magic. Hell, the set that came out a couple weeks ago has the climactic battle happening between two dragons.

      So yeah.

      --
      "Is that really true?" "I just spent the last hour telling you to think for yourself! Didn't you hear anything I said?"
  • (Score: 1) by StarryEyed on Friday May 10 2019, @01:50PM

    by StarryEyed (2888) on Friday May 10 2019, @01:50PM (#841819)
    Clearly they have never played Advanced Squad Leader [pinimg.com]...or Champions [youtube.com].
  • (Score: 1, Interesting) by Anonymous Coward on Friday May 10 2019, @01:52PM (1 child)

    by Anonymous Coward on Friday May 10 2019, @01:52PM (#841820)

    The complexity arise from the low probability of getting a good card in a sea of cheap low tier cards. Feel sorry for the ones hooked into this complex scam.

    • (Score: 3, Informative) by tangomargarine on Friday May 10 2019, @04:03PM

      by tangomargarine (667) on Friday May 10 2019, @04:03PM (#841889)

      Smart people don't buy packs unless they're drafting. You just buy singles online.

      I still don't really understand why draft is such a big format, when you pay $12 to make a deck out of worse cards, and the deck itself is even smaller so more high-variance besides what you actually manage to pick.

      But people opening packs fuels the singles market, so hey. The chumps are necessary.

      --
      "Is that really true?" "I just spent the last hour telling you to think for yourself! Didn't you hear anything I said?"
(1)