Oh good. This will be handy if I ever need to compute FFT's using only Magic cards.
Magic: The Gathering is Turing Complete
91–100 of 194 posts
Re: Magic: The Gathering is Turing Complete
#92I guess this is newsworthy because a paper was put on arXiv, but the result has been known for a while. See e.g. this submission a year ago: https://news.ycombinator.com/item?id=15712377
I'll just make my submission here then as I don't want to clutter the front page [1]. The submission includes a list of a lot of things that are accidentally turing complete including Magic The Gathering. [1] http://beza1e1.tuxen.de/articles/accidentally_turing_complet...
I have a more up-to-date list at https://www.gwern.net/Turing-complete
Re: Magic: The Gathering is Turing Complete
#93I'll see your Magic and raise you Nomic: https://en.m.wikipedia.org/wiki/Nomic
I've never heard of Nomic before but now I really want to get a group of nerds together and attempt to play it.
Please count me in ;-)
Can't think of anyone in my direct environment crazy enough to try this.
Re: Magic: The Gathering is Turing Complete
#94Earlier quoted context omitted.
It is similar in lore/setting.
That was an accurate statement in, say, 1994 but boy did it diverge. Though now they've published a D&D book based on an MTG specific setting so I suppose they could converge again.
It should also be mentioned that Magic effectively "ate up" D&D, when Wizards Of The Coast (owners of MTG) bought TSR (owners of D&D).
Re: Magic: The Gathering is Turing Complete
#95Earlier quoted context omitted.
I think you are misunderstanding the article. The point is that when the game is considered as a computation, the problem of figuring out who is going to win is not computable. Like every discussion of the halting problem, this is about whether or not a program exists that can calculate how some other specific program will behave.
I understood that, but question whether it's meaningful to say that is therefore more complex. Complexity theory just doesn't apply? (Or does it?)
Well, it's at least as complex as a Turing machine. That's a statement of complexity.
Maybe you are asking whether it is possible for the winning strategy of a very simple deterministic game to be non-computable. In other words, maybe there's a possible way of defining computability which is orthogonal to complexity. The CS definitions of both terms are closely connected to Turing machines, though. Can you imagine a simple deterministic game that couldn't be "solved" by an algorithm?
Re: Magic: The Gathering is Turing Complete
#96Earlier quoted context omitted.
Also, most of the cards are probably some basic lands and simple creatures without any skills.
I would be surprised if this is the case. Of those 20k unique cards, exactly 5 are basic lands (6 if you count Wastes). I also have a feeling that vanilla creatures are less common than non-vanilla creatures (and creatures are a just a subset of all card types).
They meant most of the 60 chosen are lands.
Re: Magic: The Gathering is Turing Complete
#97Some thoughts about AI: After Chess, Go and StarCraft 1, Magic is definitely an interesting game for AI to tackle next. While there are certain play patterns, the space of potential actions is extremely large and there is a great number of synergistic interactions between cards that needs to be taken into account. From an AI perspective Magic is also very hard because it is: * Non-deterministic * Partially observable…
I wonder if the problem of "playing the game" optimally is mostly the same as the problem of "choosing the best deck."
It is definitely a factor, but there is no auto-win for any deck. It definitely matters which cards you play and which ones your opponent plays, because just like rock-paper-scissors some cards are good at eliminating specific other cards. But unlike RPS you cannot always enforce a favorable interaction between specific cards. Your opponent can maneuver around whatever you are playing.
Re: Magic: The Gathering is Turing Complete
#98erm "Though similar to role-playing fantasy games such as Dungeons and Dragons" No MTG is not at all similar to role playing games.
if my nerd history is correct - MTG almost killed dungeons and dragons in the 90's!
Re: Magic: The Gathering is Turing Complete
#99Earlier quoted context omitted.
but those interactions are actually not as large as a real time game such as Dota or even Go. Your deck has an X amount of cards and the synergies can be easily calculated from a machine. The real problem would be, is it smart enough to beat an unknown opponent deck?
As a Magic player (since 1996) and Go player (since 2004) and also deep learning scientist, the main issue with Magic is modeling the game. The interactions and exceptions are really numerous, I expect Magic Arena and Magic Online are a mess of spaghetti code. For go modeling basically you have in input an image of the go board, and for DOTA an image of your screen and the action you have are "limited" and do not cha…
I suggest you look at projects like Shandalar 2012 and such - the original game is from the Banding era, but the 'AI' isn't too bad.
Re: Magic: The Gathering is Turing Complete
#100MtG is played by choosing 60 cards from 20k. Everything is finite. There must be some generalization in order to make it noncomputable. There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large. EDIT: This from the real abstract sounds very strange: "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows…
AFAIK 60 the minimum number of cards you have to put in your deck, but (at the least at the times) there was not a maximum number. 20k is the number of unique cards, but you can put as much as 4 copies of the same card in your deck for the vast majority of cards. You can also put as many "normal" lands as you wish in your deck.
For constructed formats the minimum is 60. For limited formats the minimum is 40. For EDH/Commander it is 100 (including the commander card).
Every card that either has the subtype "basic" or that has a card text that explicitly states so (for example: Relentless Rats), can be included in any number of copies. All other cards can be included at most 4 times or at most 1 time if it is a EDH/Commander deck.
There are 11 cards with subtype basic: https://scryfall.com/search?q=t%3Abasic&unique=cards&as=grid...
And 4 non-basic cards that can be included in any number: https://scryfall.com/search?q=o%3A%22A+deck+can+have+any+num...