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

51–60 of 194 posts

Re: Magic: The Gathering is Turing Complete

#51

Post by shapiro92 »

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…

but those interactions are actually not as large as a real time game such as Dota or even Go. Your deck has an X amount of cards and the synergies can be easily calculated from a machine. The real problem would be, is it smart enough to beat an unknown opponent deck?

Re: Magic: The Gathering is Turing Complete

#52

Post by dagw »

shapiro92 wrote: post #51
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…

but those interactions are actually not as large as a real time game such as Dota or even Go. Your deck has an X amount of cards and the synergies can be easily calculated from a machine. The real problem would be, is it smart enough to beat an unknown opponent deck?

and the synergies can be easily calculated from a machine

This article is all about how those synergies are Turing complete and thus cannot be easily calculated since doing so reduces down to solving the halting problem.

edit: that being said I suspect that writing an AI that plays "well enough" to beat human players, as opposed to optimally, is quite doable.

Re: Magic: The Gathering is Turing Complete

#53

Post by mrob »

yorwba wrote: post #22

I guess this is newsworthy because a paper was put on arXiv, but the result has been known for a while. See e.g. this submission a year ago: https://news.ycombinator.com/item?id=15712377

This version is better because all the moves are forced. The previous version only worked if all players cooperate by taking optional actions.

Re: Magic: The Gathering is Turing Complete

#54

Post by Al-Khwarizmi »

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.

Maybe the UI isn't great in an absolute sense (that situation would be really tedious to play), but I don't see how it could be made substantially better. It wouldn't be better if that situation arose in a physical Magic game either... the problem there is the game state, not the UI.

Re: Magic: The Gathering is Turing Complete

#55

Post by rishav_sharan »

lmm wrote: post #26
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's not so strange: the game is Turing complete, so the winner can be undecidable because who wins is the…

Can you ELI5 how a game can be Turing complete? I have only heard that in relation to programming languages.

Re: Magic: The Gathering is Turing Complete

#56

Post by badpun »

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…

You can easily gain infinite amount of mana, life, creatures.

Re: Magic: The Gathering is Turing Complete

#57

Post by Benjamin_Dobell »

Al-Khwarizmi wrote: post #54
Benjamin_Dobell wrote: post #42

Earlier quoted context omitted.

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.

Maybe the UI isn't great in an absolute sense (that situation would be really tedious to play), but I don't see how it could be made substantially better. It wouldn't be better if that situation arose in a physical Magic game either... the problem there is the game state, not the UI.

My point was that for people that have never seen MtG Arena before, it's non-obvious that there's more going on off-screen. A more intuitive UI would make that situation more explicit and not require explanation.

As you've rightly pointed out, a better UI isn't going to solve the UX issue of ridiculous game state; but it could better depict the state itself.

Re: Magic: The Gathering is Turing Complete

#59

Post by rcxdude »

bow_ wrote: post #37
Khoth wrote: post #30

Earlier quoted context omitted.

Actions in Magic: the Gathering let you create "tokens" which are like cards but aren't limited in number. Although you can only have a finite number in any given game, there's no upper bound on how many you can have.

There is indeed no limitation on the number of tokens in a game. There are many combo wins that involve having (technically) infinite tokens, dealing infinite damage, gaining infinite life, taking infinite turns. You get the idea. I said technically because in practice, setting this to a very large number is enough for the win. Dealing 1e6 damage is, although possible, already way overkill in most cases when your opp…

Though you do need to pick a number. The paper itself describes a game state which devolves into the 'the player who picks a larger number wins', and even gaining a large but finite amount of life can be dangerous if you don't go large enough (I have heard of a specific example of someone gaining arbitrary life, picking a google, and then losing by have their life reduced to zero through a series of losses of half their life).

Re: Magic: The Gathering is Turing Complete

#60

Post by bigcostooge2 »

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…

This is strictly incorrect. 60 is the minimum deck size. There is no maximum.

You may have up to 4 copies of a non-basic land per deck. There are then limitations on how many of particular cards can be played at once. In general, the battlefield has no max size.

But as others have mentioned, there are mechanics to take creatures from the graveyard and generate infinite mana.

Post reply on HN