I'll see your Magic and raise you Nomic: https://en.m.wikipedia.org/wiki/Nomic
Magic: The Gathering is Turing Complete
11–20 of 194 posts
Re: Magic: The Gathering is Turing Complete
#12"By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. "
What is this input? Board size?
Re: Magic: The Gathering is Turing Complete
#13Somehow 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?
Basically their argument is that in all those other games determining the optimal strategy is computable (in the computer science sense) while MTG is the only non-computable real world game they could find. If that is a valid definition of a 'complex' game is left as an exercise to the reader.
Re: Magic: The Gathering is Turing Complete
#14"By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. " What is this input? Board size?
Usually it would be number of legal moves. Of course this would also change throughout the game as pieces are removed.
Re: Magic: The Gathering is Turing Complete
#15"By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. " What is this input? Board size?
It is board size for Go, because the starting condition is an empty board. For chess, I would expect the complexity to also be a function of the number of pieces, and possibly the types of pieces.
Re: Magic: The Gathering is Turing Complete
#16MtG 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 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."
Re: Magic: The Gathering is Turing Complete
#17"By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. " What is this input? Board size?
If you generalize chess to an N*N board, it becomes PSPACE complete to decide which player has a winning strategy:
https://www.sciencedirect.com/science/article/pii/0022000083...
Re: Magic: The Gathering is Turing Complete
#18erm "Though similar to role-playing fantasy games such as Dungeons and Dragons" No MTG is not at all similar to role playing games.
The whole sentence makes even less sense:
"Though similar to role-playing fantasy games such as Dungeons and Dragons, it has significantly more cards and more complex rules than other card games."
As if similarity to D&D said anything at all about number of cards relative to other card games.
Re: Magic: The Gathering is Turing Complete
#19"By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. " What is this input? Board size?
Usually it would be number of legal moves. Of course this would also change throughout the game as pieces are removed.
The number of legal moves is an intermediate calculation. The input is the initial game state, and the output is usually the number of possible final game states.
Re: Magic: The Gathering is Turing Complete
#20Direct link to the study "Magic: The Gathering is Turing Complete": https://arxiv.org/pdf/1904.09828.pdf
Thanks, from reading the abstract, is sounds as if they have an algorithm for the halting problem.