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

131–140 of 194 posts

Re: Magic: The Gathering is Turing Complete

#131

Post by stellaathena »

gpderetta wrote: post #79
mywittyname wrote: post #69

Earlier quoted context omitted.

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

Unless you really really want a Battle of Wits deck (which is maybe tier 7) there is really no advantage and quite a bit of a disadvantage to running more than the minimum allowed number of cards.

For those who don't play Magic, this is on a scale where tier 1 decks are top decks, tier 2 decks are reasonable, tier 3 decks have serious weaknesses but are playable.

Re: Magic: The Gathering is Turing Complete

#132

Post by mankyd »

vectorEQ wrote: post #122
mankyd wrote: post #115

Earlier quoted context omitted.

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

saying anything your computer can do in such a sentence is misleading. computers are far far away from turing machines these days. they can do much more. for example, good luck making a socket connection on Magic the gathering. even if you can compute everything you need with it, you will never succeed to connect...

That's a statement about the practical engineering involved, yes. However, saying a computer is "Turing complete" is not misleading. It is purely a statement of its mathematical properties.

If sockets were given absurd timeouts and/or you could run MtG at much higher speeds, (and it was given a medium through which it could communicate), it would have no problem making a socket connection. It is only the practicality of the matter that becomes a barrier.

Re: Magic: The Gathering is Turing Complete

#133

Post by lawn »

stellaathena wrote: post #116
lawn wrote: post #4

Somehow I highly doubt Magic is the most complex played game in the world. For instance there are many different card games, what's to say Magic is more complex than them?

Did you actually read the paper? There's a mathematical definition of complexity that is used, and on that metric it is shown to be far harder than any other previously analyzed game.

Yes. The paper is good, the title of the submission was not.

Of course by now the title and even the submission link has completely changed (it was linked to an article before).

Re: Magic: The Gathering is Turing Complete

#134

Post by jackfrodo »

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)

Mao is a ridiculously fun game. I can't think of another that is as critically reliant on both playing the mechanics and your opponents.

Re: Magic: The Gathering is Turing Complete

#135

Post by penteract »

sonofgod wrote: post #102
wareotie wrote: post #72

Earlier quoted context omitted.

And at least there is a card that can be insert an unlimited amount of times and it is not a land. So technically, the combinations are infinite.

Presumably there is an optimal Island / Persistant Petitioners only deck ratio against a dumb opponent who does nothing but draw a card a turn and play a land. I wonder if it's irrational?

Since you want to draw both lands and petitioners, there's an advantage to having a smaller deck, so this probably wouldn't be the case.

Re: Magic: The Gathering is Turing Complete

#136

Post by HelloNurse »

hjk05 wrote: post #33
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 doesn’t have finite number of pieces, or finite number of actions each turn though. Naturally people have implemented Turing machines in mtg. www.toothycat.net/~hologram/Turing Also, the endgame criteria of mgt can be changed, but that said there is only a finite number of simple possible endgames in a sense.

It depends. I'm pretty sure it is possible to layer an unlimited number of contrasting win/lose conditions; distinguishing essentially different "endgames" seems slippery.

Re: Magic: The Gathering is Turing Complete

#137

Post by justinmchase »

UncleMeat wrote: post #107
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

No it hasnt. This is a new result that requires no choices by either player. It is in the paper.

Where is the actual paper? I just see the overview in the bibliography.

Re: Magic: The Gathering is Turing Complete

#139

Post by hu3 »

justinmchase wrote: post #138
hu3 wrote: post #5

Direct link to the study "Magic: The Gathering is Turing Complete": https://arxiv.org/pdf/1904.09828.pdf

Thank you sir, I am not smart enough to find the direct link from the overview page linked apparently.

You're welcome.

When I posted this, the thread linked to a sensationalist article. The link was later edited along with the title.

Re: Magic: The Gathering is Turing Complete

#140

Post by Zanni »

justinmchase wrote: post #137
UncleMeat wrote: post #107

Earlier quoted context omitted.

No it hasnt. This is a new result that requires no choices by either player. It is in the paper.

Where is the actual paper? I just see the overview in the bibliography.

There's a download link to the right of the abstract. Here's the PDF, in case it's not showing up on mobile, or whatever: https://arxiv.org/pdf/1904.09828.pdf
Post reply on HN