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

151–160 of 194 posts

Re: Magic: The Gathering is Turing Complete

#151

Post by calf »

thatoneuser wrote: post #103

Basic question but what does being Turing complete actually signify? I get the concept but don't know why it matters.

Technically it means if you're trying to write an algorithm to play Magic the same algorithm could translated and applied to solving the halting problem (i.e. a reduction of Halt to Magic exists). So your task is that difficult. Thus the theory says it is a logical contradiction for any algorithm to exist that can solve Magic. In practice, this can be different because we are routinely successful in special cases for example we still have anti virus programs in practice, just no one perfect anti virus program can exist for the same reason.

Re: Magic: The Gathering is Turing Complete

#152

Post by _0ffh »

staticautomatic wrote: post #117
vaylian wrote: post #97

Earlier quoted context omitted.

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.

Should we rule out the possibility that there are decks which are unbeatable when played well/"correctly"?

I think the probability is very small indeed. I've never met (or even heard about) a deck that you can't destroy with a matching counter. That's why the metagame is so important for higher level magic play.

Re: Magic: The Gathering is Turing Complete

#153

Post by meruru »

vanderZwan wrote: post #48
baltimore wrote: post #11

I'll see your Magic and raise you Nomic: https://en.m.wikipedia.org/wiki/Nomic

I have never played Nomic, but I can say from experience that Mao is a very fun way to practice game design skills and troll new players at the same time https://en.wikipedia.org/wiki/Mao_(card_game)

This sounds really cool, but where am I going to find someone who already knows it to play my first game?

Re: Magic: The Gathering is Turing Complete

#154

Post by hinkley »

calf wrote: post #151
thatoneuser wrote: post #103

Basic question but what does being Turing complete actually signify? I get the concept but don't know why it matters.

Technically it means if you're trying to write an algorithm to play Magic the same algorithm could translated and applied to solving the halting problem (i.e. a reduction of Halt to Magic exists). So your task is that difficult. Thus the theory says it is a logical contradiction for any algorithm to exist that can solve Magic. In practice, this can be different because we are routinely successful in special cases for…

What happens in Magic when you run out of cards? If the tape isn't infinite then there are lots of algorithms that halt.

The halting problem is like the pigeonhole principle. Just because there is no general compression algorithm doesn't mean we don't use compression all day every day. We have solutions for many interesting subsets of the problem domain, and that's good enough.

We can also tell if a program will halt in no more than N clock cycles by providing the analysis with a budget. If the budget is exhausted then the program would keep running for an unknown duration longer than the limit. Possibly 1 cycle. For third party code, you could just refuse to run that code at all. There are some useful programs that would get rejected but there are many useful ones that would not. So implementing an "infinite loop detector" as a "really big loop detector" wouldn't be the dumbest thing to try, anymore than implementing video compression is.

Re: Magic: The Gathering is Turing Complete

#155

Post by cryptica »

I don't understand why researchers are so interested in 'Turing completeness'. The concept of a Turing machine which operates on a strip of tape is outdated and no longer intuitive. It would be good if the abstraction of a 'Turing machine' could be refined into something more modern.

Re: Magic: The Gathering is Turing Complete

#156

Post by Retra »

cryptica wrote: post #155

I don't understand why researchers are so interested in 'Turing completeness'. The concept of a Turing machine which operates on a strip of tape is outdated and no longer intuitive. It would be good if the abstraction of a 'Turing machine' could be refined into something more modern.

The importance of Turing Completeness is the capabilities it offers, not the model of the machine that offers them. The machine doesn't matter at all, which is precisely why the "strip of tape" is still used.

Re: Magic: The Gathering is Turing Complete

#157

Post by pazimzadeh »

cryptica wrote: post #155

I don't understand why researchers are so interested in 'Turing completeness'. The concept of a Turing machine which operates on a strip of tape is outdated and no longer intuitive. It would be good if the abstraction of a 'Turing machine' could be refined into something more modern.

Considering that all of life essentially runs on a strip of tape and machine(s) that can read and write to it, I think it's still pretty relevant.

Re: Magic: The Gathering is Turing Complete

#158

Post by feenix566 »

eequah9L wrote: post #18
C1sc0cat wrote: post #3

erm "Though similar to role-playing fantasy games such as Dungeons and Dragons" No MTG is not at all similar to role playing games.

The whole sentence makes even less sense: "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." As if similarity to D&D said anything at all about number of cards relative to other card games.

D&D has infinite cards.

Re: Magic: The Gathering is Turing Complete

#159

Post by magicalhippo »

mankyd wrote: post #115
thatoneuser wrote: post #103

Basic question but what does being Turing complete actually signify? I get the concept but don't know why it matters.

In theory, if you can perform a computation/algorithm on one turing-complete device, you can transform it to run on another. That is to say, anything your desktop computer can do, Magic can do as well (albeit much much _much_ slower).

To be more accurate: anything your desktop computer can compute, Magic can compute (disregarding resource constraints).

Re: Magic: The Gathering is Turing Complete

#160

Post by forgot-my-pw »

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…

One step before that is Hanabi: https://arxiv.org/abs/1902.00506
Post reply on HN