Magic: The Gathering is Turing Complete • Hacker News Board

Re: Magic: The Gathering is Turing Complete

#171

Post by babyloneleven » Tue, May 07, 2019, 7:54 PM UTC

Sahhaese wrote: post #44

theoh wrote: post #21

Earlier 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?)

The set of all problems that can be solved by a Turing machine if there's an answer (possibly hanging if there's no answer) sits at the top of the complexity hierarchy (it's equivalent to the recursively enumerable languages)

The usual complexity classes of decision problems, such as P and NP, are subsets of what a Turing machine can solve, and so are weaker complexity classes.

Re: Magic: The Gathering is Turing Complete

#172

Post by T-hawk » Tue, May 07, 2019, 8:01 PM UTC

mattashii wrote: post #24

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 have to disagree on that. At least Terraforming Mars and Hanabi have a playtime limited by ever-dwindling resources. I don't know the other games, but I suspect they also have some kind of supply that has a limit in how much it can be used/aquired. MTG has ways to return to a previously seen play state, technically allowing a game to continue infinitely, depending on your deck, of course.

Terraforming Mars can continue infinitely. The end state requires players to deliberately take the actions to reach it. If no player chooses to end the game, it never will. Players could continue forever to use engines that generate points each round, to unbounded totals.

By game theory they shouldn't; eventually a player will be able to end the game while ahead and should do so; but we're already disregarding the motivation of winning for MTG.

(An expansion introduces a rule that each round automatically advances one of the game-ending parameters, but says you can play either with or without that rule.)

Re: Magic: The Gathering is Turing Complete

#173

Post by Qwertystop » Tue, May 07, 2019, 8:11 PM UTC

mratsim wrote: post #68

shapiro92 wrote: post #51

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

Arena at least has the advantage of not including all-cards-ever, only going a few sets back relative to release. That strips out some of the worst of them.

Re: Magic: The Gathering is Turing Complete

#174

Post by gwern » Tue, May 07, 2019, 8:14 PM UTC

eindiran wrote: post #167

gwern wrote: post #92

Earlier quoted context omitted.

I have a more up-to-date list at https://www.gwern.net/Turing-complete

Why do you consider it surprising that Peano Arithmetic is Turing complete?

Because they're supposed to just be the integers. If it is obvious to you that 'the integers' means undecidability/Turing-completeness, and that integers without multiplication (Presburger) does not, then all I can say is that your mathematical logic intuition is vastly superior to mine and everyone before Turing/Godel.

Re: Magic: The Gathering is Turing Complete

#175

Post by manifestsilence » Tue, May 07, 2019, 8:48 PM UTC

rsync wrote: post #150

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…

"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." Yes, that's certainly the promise of MTG - and is the reason why I was drawn to it originally and continue to be, at least passively, interested in it. The idea is that there are so many different cards and so many potenti…

Well put! MTG is notorious in the huge gap between the potential complexity and the actual complexity of most games. I've found that deck design is a far more interesting problem than the in-game play strategy, and unfortunately most really interesting decks end up far too fragile or slow to compete with the optimal strategies.

Someone really ought to design a format that bans all the straightforward but powerful cards, forcing a bit more creativity into the mix, but I fear the banned list would be prohibitively long and surprisingly difficult to come up with after the first round of obvious bans. There's always some new infinite combo that's a little too easy to pull off once the super fast quick wins are out of the way.

Edit: there's always that person (I've occasionally been him) who doesn't play to win and just tries to mess with the game's limits as much as possible. I knew someone with a "Jester Deck" that played cards that so mangled the rules that no one could even figure out how to finish the game any more. That was pretty interesting.

Re: Magic: The Gathering is Turing Complete

#176

Post by manifestsilence » Tue, May 07, 2019, 8:57 PM UTC

stellaathena wrote: post #121

simonh wrote: post #73

Earlier quoted context omitted.

The paper hasn't got anything to do with optimal game strategies, it's just showing what it is possible to achieve computationally within the rules of the game. If you're looking for advice on how to pay to win, this paper really isn't for you.

This is not correct: the paper does have to do with optimal strategies. They even say as much in the abstract. >In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem, solving a problem that has been open for a decade

This is an important distinction, as I've found that the optimal strategies in Magic are very rarely the most intricate ones or the ones involving recursive constructs. Occasionally a trivial infinite loop becomes part of a top deck, but you definitely aren't going to see someone doing the equivalent of calculating pi to win.

I think the Turing completeness is definitely still part of the appeal of Magic, because the bizarre edge cases and complexity occasionally do creep in to even serious play and add a lot of interest, but the complexity is of the iceberg variety, where most of it rarely makes itself visible most of the time.

Re: Magic: The Gathering is Turing Complete

#177

Post by manifestsilence » Tue, May 07, 2019, 9:00 PM UTC

UncleMeat wrote: post #110

devit wrote: post #50

While this paper shows that a player can create a game state where deciding the game result is Turing-complete, it does not show that doing so is an optimal strategy under any circumstance (in particular, the setup requires a starting situation where the player can just win the game instead of performing the setup). So it seems perfectly possible (and in fact highly likely) that this result does not hold if players p…

In game playing theory, an optimal strategy is a function that takes any state and tells you the proper next move. It does not matter how you got there For MTG strategy to be computable you must be able to compute whether entering this computation is a good choice, which requires solving the halting problem.

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.

Re: Magic: The Gathering is Turing Complete

#178

Post by manifestsilence » Tue, May 07, 2019, 9:19 PM UTC

hannasanarion wrote: post #165

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…

>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 that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable." It is very straightforward. They are saying that, in the turing machine scenario they've set up, for each pl…

I think they actually engineered it to not just involve obvious or optimal choices by each player, but to give them literally no other choice but to watch the machine do its calculation (or concede the game). They do this by causing all cards other than those needed for the machine to be removed from the game.

Re: Magic: The Gathering is Turing Complete

#179

Post by manifestsilence » Tue, May 07, 2019, 9:32 PM UTC

logfromblammo wrote: post #129

stellaathena wrote: post #124

Earlier quoted context omitted.

This seems like a bizarre rule to add. Why is this result even a bad thing for Magic?

It makes it more difficult to create challenging-but-still-fair bots in computerized versions of the game.

Challenging but fair bots are by definition not supposed to treat the game as totally algorithmically solvable. They can work fine on heuristics rather than algorithms, the same way that players do. There are moments when a player needs to think through all the possibilities available in the game state, and other moments when they just use a rule of thumb, like, "use this card to destroy the greatest threat currently out because time is not currently on my side to wait for what they might play next".

Re: Magic: The Gathering is Turing Complete

#180

Post by mankyd » Tue, May 07, 2019, 10:06 PM UTC

thatoneuser wrote: post #170

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

Hm so the mechanics within the game provide all the logical basis that a cpu requires?

Setup the correct way, yes.