Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Magic: The Gathering is Turing Complete

arxiv.org

Post reply on HN
Print view View original

81–90 of 194 posts

Re: Magic: The Gathering is Turing Complete

#81

Post by Xelbair »

r34 wrote: post #27

I'd claim strongly, that any game with: - finite number of pieces (eg. cards) - finite number of actions each round - clear endgame criteria is computionally solvable. What comes with randomness is stochasticity, but if that made game unsolvable what about poker (solved for limit heads-up) and even scrabble? Probably it's kind of semantic problem. I'm not complexity nor game theory expert.

MTG can have:

an infinite amount of pieces(there are cards that restore your library, generate infinite amount of mana/tokens)

infinite amount of actions each round, by each player too!

Endgame criteria which can be changed by cards themselves.

Re: Magic: The Gathering is Turing Complete

#82

Post by petters »

tacone wrote: post #64
petters wrote: post #16

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

Aha, thanks! Then my comment does not apply!

Re: Magic: The Gathering is Turing Complete

#83

Post by gpderetta »

k__ wrote: post #28
emilfihlman wrote: post #6

Eh, just because you have a big 20000 choose 60 initial set doesn't make it "most complex".

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

Re: Magic: The Gathering is Turing Complete

#84

Post by 0xfeba »

r34 wrote: post #27

I'd claim strongly, that any game with: - finite number of pieces (eg. cards) - finite number of actions each round - clear endgame criteria is computionally solvable. What comes with randomness is stochasticity, but if that made game unsolvable what about poker (solved for limit heads-up) and even scrabble? Probably it's kind of semantic problem. I'm not complexity nor game theory expert.

Add at least one more:

- doesn't let you repeat actions, or patterns of actions (move back and forth in a stalemate like pattern).

Detecting non-trivial stalemates is hard, though.

Re: Magic: The Gathering is Turing Complete

#85

Post by AlexTFish »

petters wrote: post #16

MtG 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…

As the other repliers have explained, MtG provides various ways to circumvent that. Thus we found ways to encode millions of pieces of state in tokens, and we ensured that the game loops round computing the Turing machine execution one step at a time.

Your sentence "There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large" is actually key. You're completely right - there are many. What's unusual about our result here is that we found a way to embed a fully functional Turing machine inside not an arbitrary extension of a board game, but inside a board game exactly the way it's normally played.

Re: Magic: The Gathering is Turing Complete

#86

Post by AlexTFish »

vanderZwan wrote: post #39
r34 wrote: post #27

I'd claim strongly, that any game with: - finite number of pieces (eg. cards) - finite number of actions each round - clear endgame criteria is computionally solvable. What comes with randomness is stochasticity, but if that made game unsolvable what about poker (solved for limit heads-up) and even scrabble? Probably it's kind of semantic problem. I'm not complexity nor game theory expert.

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…

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.

Re: Magic: The Gathering is Turing Complete

#87

Post by rtkwe »

mywittyname wrote: post #69
tapland wrote: post #67

Earlier quoted context omitted.

As many as you can shuffle unassisted is the upper limit.

This is an interesting rule, as it seems to provide an advantage to players on the basis on hand size.

It's not, pretty much all decks stick to the minimum required number because the more cards in your deck the less likely you are to see any particular card you want or need. To that end where they're available in the format many decks will run 'fetch lands' which search the deck for a particular type of land in order to thin out the remaining deck.

Re: Magic: The Gathering is Turing Complete

#88

Post by kruczek »

arey_abhishek wrote: post #10

It should be retitled as 'MTG is the most complex game we've played'. I would counter that other card driven games like Android Netrunner, Terraforming Mars, Lisboa, Hanabi, etc are just as or even more complex.

I don't know the others, but I played Terraforming Mars and, compared to MtG, it is a very simple game - even without taking into account the vast difference in number of available cards.

In TM there is almost no re-using of cards. Once a card is played, it either is discarded (red), provides a one-time bonus (green) or provides passive/active effect (blue). Only blue cards could be considered as being re-usable, but even that is only as far as the actual passive/active effect goes (which is separate from the effect it may generate when entering the game). Compare it with MtG, where many cards provide effects which allow discarded cards to be returned to the game (ranging from simple "ressurect creature" effects to such that allow shuffling whole stack of discarded cards back into the deck).

Also there is no stack in TM. And gaming the stack to your advantage is one of the core mechanics of MtG. A card you played may have different effects depending on cards your enemy plays in response, and these may have their effects altered by the cards you play in response, etc.

Re: Magic: The Gathering is Turing Complete

#89

Post by staticautomatic »

vaylian wrote: post #49

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

Re: Magic: The Gathering is Turing Complete

#90

Post by Dylan16807 »

mettamage wrote: post #38
yorwba wrote: post #22

I 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've always objected to the CSS example. It's demonstrating that CSS can do basic arithmetic. When you combine basic arithmetic and an infinite loop, you can make a "Turing machine" with limited memory. But CSS is not providing that loop. CSS is not Turing complete.

It's like pulling the state table out of a Turing machine and showing it off all by itself. It doesn't take much to extend it into a full Turing machine, but it's also not doing much at all by itself. A Turing machine is simple, and half a Turing machine is really simple. It's missing the point of "accidental Turing completeness" if it can't iterate to an actual result.

Post reply on HN