Magic: The Gathering is Turing Complete

Re:Magic: The Gathering is Turing Complete by vanderZwan on Tuesday May 07, 2019 @06:59AM (#19848260)

Magic The Gathering is different from the games you mentioned in that it is defined by cards that rewrite the rules of the game. There are already at least five known ways to implement Turing machines, for example:

https://www.toothycat.net/~hologram/Turing/

If you then think about the sheer number of existing M:tG cards and the implied number of possible combinations of those cards and changes to the rules (even if "optimized" to combinations that eliminate obviously nonsensical strategies like only having spells that require green mana and no sources of green mana) and the ways those cards can interact, then the computational complexity of the game explodes in ways that no other game can compare to.

And that's not even what these people showed, I think. They showed that beyond this, the complexity is worse than NP-hard.

[ Parent | on HN ]

Re:Magic: The Gathering is Turing Complete by AlexTFish on Tuesday May 07, 2019 @09:21AM (#19849061)

FWIW that's my old site, showing the 2012 version of the result, which required cooperation between 4 players. The version in the paper on arXiv is the result of my latest research (with Stella and Austin) where we get it down to 2 players and eliminate all choices required by any player.

I am planning to update the toothycat.net site pretty soon with this new result, though.

[ Parent | on HN ]