Live data from Hacker News

Magic: The Gathering is Turing Complete

arxiv.org

111–120 of 194 posts

Re: Magic: The Gathering is Turing Complete

#111

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

Re: Magic: The Gathering is Turing Complete

#112
post #98
post #3

erm "Though similar to role-playing fantasy games such as Dungeons and Dragons" No MTG is not at all similar to role playing games.

if my nerd history is correct - MTG almost killed dungeons and dragons in the 90's!

cough 4th Edition cough but Pathfinder took over

Re: Magic: The Gathering is Turing Complete

#113
post #78

Earlier quoted context omitted.

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

You have creature type (a list of tags basically). A Human Soldier or a Goblin Wizard is common in MTG.

You Have a thief in Catan

Re: Magic: The Gathering is Turing Complete

#114
post #67

Earlier quoted context omitted.

As many as you can shuffle unassisted is the upper limit.

Does this mean that players with larger hands are allowed more cards? Or is it an idealized "you can shuffle"?

In practice there is no strategic benefit of having more cards. There is one bad deck that uses more than 250 (to win with Battle of Wits). It arguably breaks the rule already.

Re: Magic: The Gathering is Turing Complete

#115

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

Re: Magic: The Gathering is Turing Complete

#116
post #4

Somehow I highly doubt Magic is the most complex played game in the world. For instance there are many different card games, what's to say Magic is more complex than them?

Did you actually read the paper? There's a mathematical definition of complexity that is used, and on that metric it is shown to be far harder than any other previously analyzed game.

Re: Magic: The Gathering is Turing Complete

#117
post #97

Earlier quoted context omitted.

I wonder if the problem of "playing the game" optimally is mostly the same as the problem of "choosing the best deck."

It is definitely a factor, but there is no auto-win for any deck. It definitely matters which cards you play and which ones your opponent plays, because just like rock-paper-scissors some cards are good at eliminating specific other cards. But unlike RPS you cannot always enforce a favorable interaction between specific cards. Your opponent can maneuver around whatever you are playing.

Should we rule out the possibility that there are decks which are unbeatable when played well/"correctly"?

Re: Magic: The Gathering is Turing Complete

#118
post #40

Earlier quoted context omitted.

I've never heard of Nomic before but now I really want to get a group of nerds together and attempt to play it.

Please count me in ;-) Can't think of anyone in my direct environment crazy enough to try this.

I had a group of friends who played it in the 1980s.

It was a long-lived informal group of game-players that started in the 1970s, and has continued (with almost-total replacement of the membership over time) until roughly the present day. We played very different games at different times--pencil-and-paper roleplaying games; Risk and Diplomacy; Civilization; Cosmic Encounter; Illuminati; MMORPGS; Nomic; custom versions of several of the above using modified rules and our own maps and other materials.

Nomic worked quite well for one of the iterations of the group. It was very entertaining--though exhausting to play--and it was educational about the legislative process.

I think the most significant thing I learned about legislation is that, regardless of what it is theoretically supposed to accomplish, what it actually does accomplish is to reward legislators who are skillful at gaming the legislative process.

I learned other things, too:

- Given an incentive, people can be incredibly flexible and creative in trying to outmaneuver one another in dealmaking.

- Very often, the most capacious bladder wins.

- If you succeed in making rules about what is allowed, you must expect that others will make rules redefining the terms used in those rules.

- Any self-serving proposal can be made to sound like it's for the common good with the right combination of incentives, creativity, and charisma.

- No matter how bitterly someone opposes your proposal, you can still get their support if you can find the right payoff and add it to your proposal.

- There is no way to limit what other legislators can do to a proposal through amendments (we tried all sorts of things, and they all ultimately failed).

I also learned that real-world legislators have to have incredible endurance. A hotly-contested game of Nomic can drag on for hours and leave all the participants completely exhausted. Real legislation must be much more grueling. The stakes are higher, the costs and rewards are more significant, and the game never ends.

Re: Magic: The Gathering is Turing Complete

#119
post #8

Does it actually make sense to say that something that is non-computable is most complex? That seems like a contradiction.

Lots of things are more complicated than a computer can handle. There's an entire hierarchy of non-computable problems by complexity (actually several).

Re: Magic: The Gathering is Turing Complete

#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 combo to actually take all of the cards was a bit tedious.

Post reply on HN