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

121–130 of 194 posts

Re: Magic: The Gathering is Turing Complete

#121

Post by stellaathena »

simonh wrote: post #73
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…

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

Re: Magic: The Gathering is Turing Complete

#122

Post by vectorEQ »

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

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

Re: Magic: The Gathering is Turing Complete

#123

Post by maxsilver »

C1sc0cat wrote: post #46
gberger wrote: post #7

Earlier quoted context omitted.

It is similar in lore/setting.

Not sure that's true MTG is not based on any of the DnD settings nor does it have Character Races and Classes.

Yep. In fact, the opposite is now true. Some of DnD is now (in part) based on MTG, including an MTG setting, MTG Character Races, and such.

http://dnd.wizards.com/products/tabletop-games/rpg-products/...

Re: Magic: The Gathering is Turing Complete

#124

Post by stellaathena »

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 seems like a bizarre rule to add. Why is this result even a bad thing for Magic?

Re: Magic: The Gathering is Turing Complete

#125

Post by svachalek »

IggleSniggle wrote: post #111
Dylan16807 wrote: post #90

Earlier quoted context omitted.

I've always objected to the CSS example. It's demonstrating that CSS can do basic arithmetic . When you combine basic arithmetic and an infinite loop, you can make a "Turing machine" with limited memory. But CSS is not providing that loop. CSS is not Turing complete. It's like pulling the state table out of a Turing machine and showing it off all by itself. It doesn't take much to extend it into a full Turing machine…

Off the cuff conjecture, but wouldn't any number of render methods allow for an infinite loop? Animation methods come to mind first.

In CSS itself, I don't know of a way to feed one result back into an earlier one and thus create a loop. If you're talking about JavaScript, it is and was intended to be Turing complete.

Edit: Just saw the HTML/CSS3 example on the page. Mind blown.

Re: Magic: The Gathering is Turing Complete

#126

Post by crimsonalucard »

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 express every possible computation in the language, and thus in these cases Turing completeness is not a design smell.

Re: Magic: The Gathering is Turing Complete

#127

Post by magnat »

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…

Now, if only we had algorithm to decide whether for provided game table state, the chain of triggers ever stops or continues indefinitely.

Re: Magic: The Gathering is Turing Complete

#128

Post by logfromblammo »

magnat wrote: post #127
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…

Now, if only we had algorithm to decide whether for provided game table state, the chain of triggers ever stops or continues indefinitely.

It stops at the Nth instruction, where N is determined by some game designer to be long enough to create interesting combos, but not so long that one player can force the other to be their CPU indefinitely.

Re: Magic: The Gathering is Turing Complete

#129

Post by logfromblammo »

stellaathena wrote: post #124
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 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.

Re: Magic: The Gathering is Turing Complete

#130

Post by UncleMeat »

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.

"Complexity" has a very precise meaning. None of these other games have been proven to be Turing Complete.
Post reply on HN