31–40 of 194 posts
erm "Though similar to role-playing fantasy games such as Dungeons and Dragons" No MTG is not at all similar to role playing games.
It is similar in lore/setting.
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.
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.
Naturally people have implemented Turing machines in mtg. www.toothycat.net/~hologram/Turing
Also, the endgame criteria of mgt can be changed, but that said there is only a finite number of simple possible endgames in a sense.
From the paper: "In this work, we solve this problem by reformulating the construction to exclusively use cards with mandatory effects." So it's more a of a subset of MTG's rules. Still, there are commercial video games out beyond MTG and they've been out for some time. Why has the game theory field not kept up with them?
Unlike previous attempts, which used cards that leave some room for Player agenda, this new version doesn't.
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 have to disagree on that. At least Terraforming Mars and Hanabi have a playtime limited by ever-dwindling resources. I don't know the other games, but I suspect they also have some kind of supply that has a limit in how much it can be used/aquired. MTG has ways to return to a previously seen play state, technically allowing a game to continue infinitely, depending on your deck, of course.
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.
Some game have more states than there are atoms in the universe. They are solvable in theory but we will need a bigger universe to put this theory in practice...
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.
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 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 opponent starts with 20 life.
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
[1] http://beza1e1.tuxen.de/articles/accidentally_turing_complet...
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.
https://www.toothycat.net/~hologram/Turing/
If you then think about the sheer number of existing M:tG cards and the implied number of possible combinations of those cards and changes to the rules (even if "optimized" to combinations that eliminate obviously nonsensical strategies like only having spells that require green mana and no sources of green mana) and the ways those cards can interact, then the computational complexity of the game explodes in ways that no other game can compare to.
And that's not even what these people showed, I think. They showed that beyond this, the complexity is worse than NP-hard.
I'll see your Magic and raise you Nomic: https://en.m.wikipedia.org/wiki/Nomic