5 ms·

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

42 points by dtx1 4y ago

oneoff786 4y ago
Hmm under this method wouldn’t this apply to any game that allows cycles of moves that go nowhere?
- iamevn 4y ago
  I think what's really interesting about this formulation is that after one player sets it up, every step of the resolution of the rules for the simulated Turing Machine is forced for both players.
  - oneoff786 4y ago
    Ehhh only if going deep into Turing machine states is actually advantageous. I’m guessing it’s not. I don’t play however.
    - UncleMeat 4y ago
      No. Once the board state is set up it is not possible for either player to make a decision that diverges from the TM simulation. It has nothing about advantageousness or strategy.
      - oneoff786 4y ago
        I said “deep”. The whole “technically this is part of a Turing machine” argument does not mean you need to think about such things at all. Leveraging the potential of a Turing machine is not going to help you win. 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.
        UncleMeat 4y ago
        Obviously the setup is not practical in a real game. The point is a theoretical demonstration that the rules of MTG can be used to compute arbitrary functions, demonstrating that there can be no general computable strategy for all game states. This is similar to lots of CS results, where we might demonstrate that some problem is NP-Complete or undecidable or whatever even though in practice there are efficient algorithms that work for most instances of these problems.
        oneoff786 4y ago
        Sure, but my point is that the computability of something is a poor measure of its complexity as a game of the non computable aspects are game theoretically always a dumb idea. 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.
hitpointdrew 4y ago
Thats an adorable little “proof”, you got there. But, Magic is not even remotely “the most complex game”. Whoever has said this has never even attempted to play a game like “The Campaign for North Africa.” Reading the rules and setting the game up alone can hardly been done in a single day.
- mdaniel 4y ago
  I think they're referring to it being Turing complete, which is unlikely for Campaign for North Africa (although this is the first I've heard of that game, so), and they actually do qualify their assertion with "computationally complex": > 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 https://arxiv.org/abs/1904.09828 and reported here repeatedly: https://hn.algolia.com/?q=gathering+turing https://hn.algolia.com/?q=gathering+turing
  - forgotpwd16 4y ago
    >I'm certainly glad that Technology Review has stumbled upon this groundbreaking achievement that we've known since 2019 The article was published in 2019, about a month since the arXiv paper was published.
trynewideas 4y ago
Computationally complex; "Churchill and co’s key result is that determining the outcome of a game of Magic is non-computable," making the claim that Magic is the first "undecidable real game" to exist. From the study: https://arxiv.org/abs/1904.09828 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. cf. https://drops.dagstuhl.de/opus/volltexte/2020/12770/ https://drops.dagstuhl.de/opus/volltexte/2020/12770/
- synu 4y ago
  Is the outcome of a game of Diplomacy computable?
iamevn 4y ago
Quoting my own previous comment on the paper, > 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 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.
- mdaniel 4y ago
  > 4 Grim Monolith $1,110.00 > 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"?
  - actually_a_dog 4y ago
    That depends. What would be the purpose of doing so? 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.
  - raffraffraff 4y ago
    Can someone explain how this is any better than pay-to-ein games?
    - stnikolauswagne 4y ago
      My argument would be that it caps out at a certain point where more money stopes equalling higher win%, I have played a lot of high level magic tournaments and budget was never really something that impacted the meta game at the higher levels. 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.
jdmoreira 4y ago
In case I can convince someone here we go… There are two wonderful nostalgia mtg formats that I play often, very much enjoy and recommend. 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!
sprkwd 4y ago
* laughs in Twilight Imperium *
sieabahlpark 4y ago
[dead]

42 points by dtx1 4y ago

oneoff786 4y ago

Hmm under this method wouldn’t this apply to any game that allows cycles of moves that go nowhere?

iamevn 4y ago
I think what's really interesting about this formulation is that after one player sets it up, every step of the resolution of the rules for the simulated Turing Machine is forced for both players.
- oneoff786 4y ago
  Ehhh only if going deep into Turing machine states is actually advantageous. I’m guessing it’s not. I don’t play however.
  - UncleMeat 4y ago
    No. Once the board state is set up it is not possible for either player to make a decision that diverges from the TM simulation. It has nothing about advantageousness or strategy.
    - oneoff786 4y ago
      I said “deep”. The whole “technically this is part of a Turing machine” argument does not mean you need to think about such things at all. Leveraging the potential of a Turing machine is not going to help you win. 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.
      - UncleMeat 4y ago
        Obviously the setup is not practical in a real game. The point is a theoretical demonstration that the rules of MTG can be used to compute arbitrary functions, demonstrating that there can be no general computable strategy for all game states. This is similar to lots of CS results, where we might demonstrate that some problem is NP-Complete or undecidable or whatever even though in practice there are efficient algorithms that work for most instances of these problems.
        oneoff786 4y ago
        Sure, but my point is that the computability of something is a poor measure of its complexity as a game of the non computable aspects are game theoretically always a dumb idea. 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.

hitpointdrew 4y ago

Thats an adorable little “proof”, you got there. But, Magic is not even remotely “the most complex game”. Whoever has said this has never even attempted to play a game like “The Campaign for North Africa.” Reading the rules and setting the game up alone can hardly been done in a single day.

mdaniel 4y ago
I think they're referring to it being Turing complete, which is unlikely for Campaign for North Africa (although this is the first I've heard of that game, so), and they actually do qualify their assertion with "computationally complex": > 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 https://arxiv.org/abs/1904.09828 and reported here repeatedly: https://hn.algolia.com/?q=gathering+turing https://hn.algolia.com/?q=gathering+turing
- forgotpwd16 4y ago
  >I'm certainly glad that Technology Review has stumbled upon this groundbreaking achievement that we've known since 2019 The article was published in 2019, about a month since the arXiv paper was published.

trynewideas 4y ago

Computationally complex; "Churchill and co’s key result is that determining the outcome of a game of Magic is non-computable," making the claim that Magic is the first "undecidable real game" to exist. From the study: https://arxiv.org/abs/1904.09828 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. cf. https://drops.dagstuhl.de/opus/volltexte/2020/12770/ https://drops.dagstuhl.de/opus/volltexte/2020/12770/

synu 4y ago
Is the outcome of a game of Diplomacy computable?

iamevn 4y ago

Quoting my own previous comment on the paper, > 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 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.

mdaniel 4y ago
> 4 Grim Monolith $1,110.00 > 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"?
- actually_a_dog 4y ago
  That depends. What would be the purpose of doing so? 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.
- raffraffraff 4y ago
  Can someone explain how this is any better than pay-to-ein games?
  - stnikolauswagne 4y ago
    My argument would be that it caps out at a certain point where more money stopes equalling higher win%, I have played a lot of high level magic tournaments and budget was never really something that impacted the meta game at the higher levels. 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.

jdmoreira 4y ago

In case I can convince someone here we go… There are two wonderful nostalgia mtg formats that I play often, very much enjoy and recommend. 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!

sprkwd 4y ago

* laughs in Twilight Imperium *

sieabahlpark 4y ago

[dead]