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

141–150 of 194 posts

Re: Magic: The Gathering is Turing Complete

#141

Post by moate »

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…

Depends on what you expect the AI to do. If you allow it access to a DB of decklists to compare opponent cards/choices against, it gets "easier" but still complex. There's so many branching option trees though.

Could be interesting to see what happened, I just don't think you'd be able to build an "unbeatable" machine that didn't also cheat the RNG elements of the game/have the full decklist of its opponent.

Re: Magic: The Gathering is Turing Complete

#142

Post by arbitrage »

vectorEQ wrote: post #122
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).

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

You're missing the point.

Re: Magic: The Gathering is Turing Complete

#143

Post by moate »

staticautomatic wrote: post #117
vaylian wrote: post #97

Earlier quoted context omitted.

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"?

Yes. Best case is that there are decks that are unbeatable when played correctly against other decks (even if that deck is played correctly). I can think of a few match ups that are likely "auto-lose" based on deck construction.

Most of the games AI has surpassed humans at have several things in common, and one of the biggest is they don't contain a great deal of hidden information. Chess is all in the open, with very set defined options. There are a ton of different game states, but none of them involve "what if my opponent suddenly drew the one card that I cannot in any way do anything about to prevent ruination".

TL;dr- robots will never defeat the "heart of the cards" unless you stack the game in their favor.

Re: Magic: The Gathering is Turing Complete

#144

Post by Y_Y »

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

I've heard you can perform arbitrarily difficult calculations just by getting gwern interested enough to write an article.

Re: Magic: The Gathering is Turing Complete

#145

Post by afiori »

moate wrote: post #143
staticautomatic wrote: post #117

Earlier quoted context omitted.

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

Yes. Best case is that there are decks that are unbeatable when played correctly against other decks (even if that deck is played correctly). I can think of a few match ups that are likely "auto-lose" based on deck construction. Most of the games AI has surpassed humans at have several things in common, and one of the biggest is they don't contain a great deal of hidden information. Chess is all in the open, with ver…

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

Re: Magic: The Gathering is Turing Complete

#146

Post by CryoLogic »

lawn wrote: 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?

I actually believe it may be the hardest card game to compute.

Magic has been around since 1993, and releases new cards every year. There are currently > 15,000 unique cards in the game.

When playing, you don't know what the next card drawn will be. You also don't know what is in your opponents hand.

In poker for example, there is a very small pool of possible top decks and hands.

Search trees in Magic (especially "eternal" formats that allow you to pick cards from any expansion) would be too massive to compute.

These cards are not vanilla either (not just statpools) - they contain over 100 categorical effects and many of them have unique effects.

I'd guess at least 1000 have unique effects and interactions.

Add on to that the fact that magic is both a pro-active and re-active card game. In most card games (aka hearthstone for example) you cast cards on your turn. In Magic you can cast many cards "in response" e.g. counterspells. You can also just play some cards on opponents turn.

Beyond this the game is split into a number of phases and card timing by phase is very important. Sometimes you want to cast on end step vs combat - the same spell does the same thing but might be much lower risk depending on the phase.

Re: Magic: The Gathering is Turing Complete

#147

Post by CryoLogic »

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…

Do keep in mind that 60 cards is just one Magic format, one of the most popular official formats is Commander which is 100 card singleton.

Beyond that, those are not cards in the sense of poker cards with stats and an effect. Many of these have unique effects specific to that card.

There are also 100+ categorical effects. Creature types, color types.

Plus Magic is played on both players turns unlike other card games. Divide both turns into phases with pros and cons of casting.

It's more complex than it sounds when you just call it a "card game" - it is much more deep than most any other card game and does not truly feel like a card game except the fact that you play with cards.

The game has infinite loops, race conditions, etc which come in many unpredictable shapes.

Re: Magic: The Gathering is Turing Complete

#148

Post by ReidZB »

staticautomatic wrote: post #117
vaylian wrote: post #97

Earlier quoted context omitted.

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"?

Imbalanced decks usually have their key pieces banned by WotC. As a result, in a sense, the game adapts to the players.

Re: Magic: The Gathering is Turing Complete

#149

Post by moate »

afiori wrote: post #145
moate wrote: post #143

Earlier quoted context omitted.

Yes. Best case is that there are decks that are unbeatable when played correctly against other decks (even if that deck is played correctly). I can think of a few match ups that are likely "auto-lose" based on deck construction. Most of the games AI has surpassed humans at have several things in common, and one of the biggest is they don't contain a great deal of hidden information. Chess is all in the open, with ver…

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.

Re: Magic: The Gathering is Turing Complete

#150

Post by rsync »

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 potential interactions that every deck could be fantastically unique and every game could produce very unique outcomes.

I have found, in 25 years of playing MTG that this is not the case. The reality is that in every release, or set of "legal" cards, there are a few overwhelmingly advantageous cards and card combinations that must either be adhered to or prepared against. Further, "classes" of decks (counter decks, control decks, blast decks, etc.) need to be fairly simple and anti-fragile to work effectively given the random draw, etc.

My opinion, circa 1998 or 1999, was that to really open up the playing space, WOTC needed to produce sets of very complex cards that had abilities and interactions that in themselves were as complicated as the game was. Cards whose abilities and interactions we would still be discovering years later. Perhaps even random attributes/abilities For obvious reasons this is not the direction they went and would be a big hurdle for new players.

And so every set has, effectively, its own channel+fireball and we all play that or prepare for it and for all the turing-completeness, there's not that many surprises at the game store on Friday night ...

Post reply on HN