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

181–190 of 194 posts

Re: Magic: The Gathering is Turing Complete

#181

Post by UncleMeat »

manifestsilence wrote: post #177
UncleMeat wrote: post #110

Earlier quoted context omitted.

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.

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

Re: Magic: The Gathering is Turing Complete

#182

Post by afiori »

moate wrote: post #149
afiori wrote: post #145

Earlier quoted context omitted.

on this note there was a nice paper [0] proposing a game entirely focused on hidden information (Hanabi) as a benchmark for automated decisions. [0] https://arxiv.org/abs/1902.00506

There's hidden information, but also finite known quantities. The AI knows what tiles exist, have been played and haven't. Unless you're allowing the AI to know the contents of the deck it's opposing in magic, you're probably making those decision trees impossibly complex. "Is countering this lightning bolt optimal or not" has a lot more meaning when you know what else is in the deck with the lightning bolt.

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.

Re: Magic: The Gathering is Turing Complete

#183

Post by UncleMeat »

logfromblammo wrote: post #120

So add a new rule: Choice-lock. If any player is unable to make a choice for some finite countable number of consecutive turns, they lose. This could have also prevented combining infinite turn combos with the ante-related cards to produce "I have created a game state where I can take ownership all the cards in your deck, and then win," which was fun to do in the original M:tG PC game, even though running through the…

This almost certainly doesn't prevent turing completeness.

You'd just need to add additional construction that every N turns gives each player a choice but where that choice does not affect the behavior of the machine.

Re: Magic: The Gathering is Turing Complete

#184

Post by calf »

hinkley wrote: post #154
calf wrote: post #151

Earlier quoted context omitted.

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…

My understanding is that the undecidability of the halting problem is equivalent to the undecidability of the decision version of compression (does a given string have a Kolmogorov representation, or not). They're saying the same thing and mathematically equivalent to Godel's incompleteness as well.

The difference is that with data compression, you don't get random-looking inputs and would explain why text, voice, image domains are amenable to compression algorithms. In contrast, the state space of programs is exponential in the budget N and looks very random. The exponential explosion makes the analysis very inefficient relative to hardware ability. And then the random-looking state sequences are especially not very compressible. These characteristics are harder to leverage.

The pigeonhole principle works for lossless compression but I don't see the analog to Halt or Rice's theorem, etc.

Re: Magic: The Gathering is Turing Complete

#185

Post by djakjxnanjak »

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.

You might like the RASP: https://en.m.wikipedia.org/wiki/Random-access_stored-program...

Re: Magic: The Gathering is Turing Complete

#186

Post by improv32 »

hinkley wrote: post #154
calf wrote: post #151

Earlier quoted context omitted.

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…

If we knew Magic was limited to N states, then we can conclude that a program running on the Magic Turing machine will never halt if it has not halted after BB(N) steps.

Re: Magic: The Gathering is Turing Complete

#187

Post by simonh »

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

OK that's fair enough, but it's not saying anything about what optimal strategies might actually be, just examining their potential complexity in an extreme edge case scenario.

Re: Magic: The Gathering is Turing Complete

#188

Post by devit »

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.

Not really, it's possible that there is always a strategy that can be proven to be better than entering the computation (because it wins the game deterministically, for instance).

Re: Magic: The Gathering is Turing Complete

#189

Post by vanderZwan »

meruru wrote: post #153
vanderZwan wrote: post #48

Earlier quoted context omitted.

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?

Just use the following rules:

- turns go clockwise

- play one card per turn

- if someone breaks a rule, they take back their card and draw one extra

- first to shed all their cards, followed by saying "Mao!" wins

- saying "Mao" any other times means drawing three cards (so if someone broke a rule playing their last card and had to take back their card, they end up drawing three cards

- Similar to the previous rule: not saying "Mao" upon successfully playing the last card also means drawing three cards. And it is breaking the rules, so the player has to take back the card and draw a card.

- asking any question means drawing a card (be brutal: "WHAT?!" counts as a question)

- one player starts with making up two extra rules

- the winner of a round makes up a new rule, the old rules stay

... then grab a bunch of friends, say "you'll figure it out", come up with two rules of your own and start playing. You'll likely win the round (because they will all ask questions in confusion), and be allowed to add another rule.

Restart after a couple of rounds. Troll until they threaten to quit (at which point you explain the rules) or until they actually figure it out. Watch their expressions go from frustration to gleefully anticipation, and go look for a fresh victim together.

Re: Magic: The Gathering is Turing Complete

#190

Post by moate »

afiori wrote: post #182
moate wrote: post #149

Earlier quoted context omitted.

There's hidden information, but also finite known quantities. The AI knows what tiles exist, have been played and haven't. Unless you're allowing the AI to know the contents of the deck it's opposing in magic, you're probably making those decision trees impossibly complex. "Is countering this lightning bolt optimal or not" has a lot more meaning when you know what else is in the deck with the lightning bolt.

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 does that mean? Most decks are designed for a full tournament grind based on an expected range of decks to play against.

I guess you'd have to have the AI compete in a full tournament, but then the skill level of the individual players becomes a variable. IDK, it just seems like a really big hill to climb.

Post reply on HN