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

71–80 of 194 posts

Re: Magic: The Gathering is Turing Complete

#71

Post by wool_gather »

tapland wrote: post #67
tacone wrote: post #64

Earlier quoted context omitted.

AFAIK 60 the minimum number of cards you have to put in your deck, but (at the least at the times) there was not a maximum number. 20k is the number of unique cards, but you can put as much as 4 copies of the same card in your deck for the vast majority of cards. You can also put as many "normal" lands as you wish in your deck.

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

Re: Magic: The Gathering is Turing Complete

#72

Post by wareotie »

tacone wrote: post #64
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…

AFAIK 60 the minimum number of cards you have to put in your deck, but (at the least at the times) there was not a maximum number. 20k is the number of unique cards, but you can put as much as 4 copies of the same card in your deck for the vast majority of cards. You can also put as many "normal" lands as you wish in your deck.

And at least there is a card that can be insert an unlimited amount of times and it is not a land. So technically, the combinations are infinite.

Re: Magic: The Gathering is Turing Complete

#73

Post by simonh »

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.

Re: Magic: The Gathering is Turing Complete

#74

Post by lmkg »

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.

The output of a computer program can be unsolveable, even though the source of the program has finite characters. It's the same thing. (Literally: you're building an interpreter out of cards.)

Re: Magic: The Gathering is Turing Complete

#75

Post by Xelbair »

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.

I played Netrunner a lot, and it beats MTG in base rules(as i do mean absolute minimum of MTG rules) complexity.

When it comes to cards themselves, and their effect on gameplay, it blows netrunner away.

Just look how effect layers are constructed, or even a simple stack and priority itself, not to mention infinite loops.

I do agree that i had way more fun playing Netrunner, mostly because you cannot be mana screwed/flooded like in mtg - as you can spend action to get resources or cards.

Re: Magic: The Gathering is Turing Complete

#76

Post by jefftk »

baltimore wrote: post #11

I'll see your Magic and raise you Nomic: https://en.m.wikipedia.org/wiki/Nomic

Some friends and I tried playing Nomic using GitHub and CI. We played three games before getting bored and moving on:

* https://www.jefftk.com/p/nomic-report-iii-conclusion

* https://www.jefftk.com/p/nomic-game-2-another-conclusion

* https://www.jefftk.com/p/nomic-game-3

Re: Magic: The Gathering is Turing Complete

#77

Post by ivl »

mywittyname wrote: post #69
tapland wrote: post #67

Earlier quoted context omitted.

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

This is an interesting rule, as it seems to provide an advantage to players on the basis on hand size.

More cards is not seen as an advantage. There are a couple cases where you may want more cards, but usually up to about 75. It's about drawing the right cards, not just many, and more cards makes your deck less reliable, simply on the likelihood of drawing the card you want.

Re: Magic: The Gathering is Turing Complete

#78

Post by aloisdg »

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.

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

Re: Magic: The Gathering is Turing Complete

#79

Post by gpderetta »

mywittyname wrote: post #69
tapland wrote: post #67

Earlier quoted context omitted.

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

This is an interesting rule, as it seems to provide an advantage to players on the basis on hand size.

Unless you really really want a Battle of Wits deck (which is maybe tier 7) there is really no advantage and quite a bit of a disadvantage to running more than the minimum allowed number of cards.

Re: Magic: The Gathering is Turing Complete

#80

Post by Xelbair »

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…

there are cards that:

restore your library,

grab cards from exile(out of game, literally),

Reverse win conditions,

Prevent losing,

Generate infinite loops - both deterministic and not(with randomness).

Create tokens(sometimes coupled with above) - which provide unlimited resources with a sac outlet.

And those aren't fringe cases - for example in EDH format quite a lot of decks win by creating some kind of infinite loop, or by generating infinite resources(or sky high amount of them)

So i would argue that resources aren't finite.

Post reply on HN