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

161–170 of 194 posts

Re: Magic: The Gathering is Turing Complete

#161

Post by justinmchase »

Benjamin_Dobell wrote: post #42
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.

Combat resolution/targeting can get a wee bit out of hand: https://i.redd.it/wyn3d22evs011.jpg This is not the worst I've seen, simply what I was able to turn-up on short notice. EDIT: To clarify (the UI isn't great), what you see above is a selection of the "cards" (creatures/tokens) in play, more are off screen.

Do you know if there is a video showing a full turing complete game? I can't quite visualize what is going on.

Re: Magic: The Gathering is Turing Complete

#162

Post by hannasanarion »

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…

In magic, if you run out of cards, you lose, but there are ways to restore your cards so you never run out, so games can continue theoretically forever.

Re: Magic: The Gathering is Turing Complete

#163

Post by hannasanarion »

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.

But that's already how bots are made. You don't need to add rules to the game before you can constrict the thinking time of entertainment AI

Re: Magic: The Gathering is Turing Complete

#164

Post by hannasanarion »

crimsonalucard wrote: post #126

Turing completeness in something designed to be domain specific is a sign of bloat and is a sort of smell. It's a sign of a design taken so far that it now has the capability to compute anything when in all intents and purposes it's design is domain specific. One other example of this is css. Did you know css is Turing complete? Note that most programming languages are Turing complete because that is the domain: To e…

CSS is not turing complete. CSS can do arithmetic, but it has no way to designate routines or repeat its own behavior.

Re: Magic: The Gathering is Turing Complete

#165

Post by hannasanarion »

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 player's move, the decision they have to make is obvious, so the players don't have to collaborate in order to produce the scenario, it will arise naturally out of the state of the game with two rational players trying to win.

Re: Magic: The Gathering is Turing Complete

#166

Post by thiagoharry »

hannasanarion wrote: post #162
hinkley wrote: post #154

Earlier quoted context omitted.

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 magic, if you run out of cards, you lose, but there are ways to restore your cards so you never run out, so games can continue theoretically forever.

And even if you don't, it's possible to create infinite resources combining a finite number of cards. Like creating infinite tokens, infinite mana. The paper uses an infinite number of creature tokens to represent an infinite tape.

Re: Magic: The Gathering is Turing Complete

#167

Post by eindiran »

gwern wrote: post #92
mettamage wrote: post #38

Earlier quoted context omitted.

I'll just make my submission here then as I don't want to clutter the front page [1]. The submission includes a list of a lot of things that are accidentally turing complete including Magic The Gathering. [1] http://beza1e1.tuxen.de/articles/accidentally_turing_complet...

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?

Re: Magic: The Gathering is Turing Complete

#168

Post by stellaathena »

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.

To be more specific about what the other responses say:

Being "equivalent to a TM" and being "equivalent to the Python compiler" mean the exact same thing. Pretty much every widely used model of computation is equivalent in computing power to Turing machines. The notable exceptions are all weaker than Turing machines, such as arithmetic circuits.

Re: Magic: The Gathering is Turing Complete

#169

Post by crimsonalucard »

hannasanarion wrote: post #164
crimsonalucard wrote: post #126

Turing completeness in something designed to be domain specific is a sign of bloat and is a sort of smell. It's a sign of a design taken so far that it now has the capability to compute anything when in all intents and purposes it's design is domain specific. One other example of this is css. Did you know css is Turing complete? Note that most programming languages are Turing complete because that is the domain: To e…

CSS is not turing complete. CSS can do arithmetic, but it has no way to designate routines or repeat its own behavior.

You are not categorically wrong because I missed some semantics in my statements. However the essence of what your saying is incorrect.

Let me rephrase more specifically: CSS3 + HTML5 is turing complete. Since CSS is always used in the context of HTML I left that out, but rigor is important!

source: https://stackoverflow.com/questions/2497146/is-css-turing-co...

Note that this happened with the later versions of CSS indicating that the specification became turing complete after years and years of tacking on features. This is the pattern of bloat accumulating over time.

Re: Magic: The Gathering is Turing Complete

#170

Post by thatoneuser »

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

Hm so the mechanics within the game provide all the logical basis that a cpu requires?
Post reply on HN