Magic: The Gathering is a popular and notoriously complicated trading card game that pits players against each other, placing them in the role of wizards who do battle with the help of spells, magical artifacts and mythical creatures.
A team of researchers from the U.S. and U.K. has now found that no algorithm can possibly determine a winner, making it potentially the world's most complex game, according to a study published on the preprint website ArXiv.org.
A team led Alex Churchill, an independent researcher from Cambridge, England, measured the complexity of the game by encoding it so it could be played by a computer, MIT Technology Review reported.
"This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature," the authors wrote in the study.
Computational complexity is a ranking determined by the resources required to solve problems. Tasks that can be done in a finite number of well-defined units are deemed computable, even if some are very hard to compute.
For example, determining whether one player can win in a game of chess—which can be done by testing every possible sequence of moves—is a complex affair but is still computable. On the other hand, tasks for which there are no existing algorithms capable of solving them are called non-computable problems.
Because most games have finite limits on their complexity—such as the size of a board—most research into the algorithmic theory of real-world games has focused on generalizations of these games rather than the versions that are played by people, the authors said.
But for the latest study, the team encoded the powers and properties of the cards used in Magic so that a computer could play itself, mimicking the real-world game. The researchers found that trying to determine whether one player was going to win or not was impossible—or, in other words, "non-computable."
"This is the first result showing that there exists a real-world game for which determining the winning strategy is non-computable," the authors said. They say that their results have significant implications for the field of game theory, in which the leading theory assumes that any game must be computable.
"Magic: The Gathering does not fit assumptions commonly made by computer scientists while modeling games," the authors said.
Uncommon Knowledge
Newsweek is committed to challenging conventional wisdom and finding connections in the search for common ground.
Newsweek is committed to challenging conventional wisdom and finding connections in the search for common ground.
About the writer
Aristos is a Newsweek science reporter with the London, U.K., bureau. He reports on science and health topics, including; animal, ... Read more
To read how Newsweek uses AI as a newsroom tool, Click here.
