Live data from Hacker News

Magic: The Gathering is Turing Complete

arxiv.org

191–194 of 194 posts

Re: Magic: The Gathering is Turing Complete

#191
post #190
post #182

Earlier quoted context omitted.

That is an interesting point, it is actually a strategy in the game to speculate on the opponent deck composition so it would make sense not to trivialize it here.

Of course, but how do you "fairly" account for that? You could teach the computer what the "meta" looks like, but players never reveal full deck contents to each other in tournament play. Also, how does the AI select its deck? Does the player know going in what deck it will be playing? Part of the problem here is that you can build a weird, off meta deck for either the AI or player that can win a single game but what…

In theory if you had an unlimited amount of time and compute resources couldn't you just construct all possible decks and play them against each other, perhaps with some mix of naive and pre-trained strategies?

Re: Magic: The Gathering is Turing Complete

#192
post #190

Earlier quoted context omitted.

Of course, but how do you "fairly" account for that? You could teach the computer what the "meta" looks like, but players never reveal full deck contents to each other in tournament play. Also, how does the AI select its deck? Does the player know going in what deck it will be playing? Part of the problem here is that you can build a weird, off meta deck for either the AI or player that can win a single game but what…

In theory if you had an unlimited amount of time and compute resources couldn't you just construct all possible decks and play them against each other, perhaps with some mix of naive and pre-trained strategies?

Yes. Got any extra "unlimited amount of time and computer resources" lying around?

I mean when we get to that level, couldn't we just use our unlimited time and resources to just create a model of the entire universe and just observe all the people playing the game and at all skill levels as well?

Re: Magic: The Gathering is Turing Complete

#194

Earlier quoted context omitted.

This does mean that MTG is not algorithmically solvable, which is very interesting. However, in most cases I think it is heuristically trivial to determine the best move.

Sure, but that isn't what theory people care about. Most real world SAT instances are tractable. But SAT is still NP-Complete.

True. There's sort of a divide in this thread over two questions that are interesting in completely different ways. One is how deep a game MTG is in practice, and the other is whether it is an algorithmically solvable game (no). My take-away, other than it being really cool that it's Turing-Complete, is that any bot will need to accept that not all infinities it could get stuck in are even detectable and resort to heuristics at a certain point.
Post reply on HN