In the world of card games, the popularity of Magic: The Gathering soars. This trading card game has gathered 35 Million players spread across 70 countries. Aside from its popularity, the game also is very unpredictable. With the many possibilities, you won’t be able to predict who the winner will be. Alex Churchill, together with his team, investigates the complexity of the game.
His team has measured the computational complexity of the game for the first time by encoding it in a way that can be played by a computer or Turing machine. “This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,” they say.
First, some background. An important task in computer science is to determine whether a problem can be solved in principle. For example, deciding whether two numbers are relatively prime (in other words , whether their largest common divisor is greater than 1) is a task that can be done in a finite number of well-defined steps and so is computable.
In an ordinary game of chess, deciding whether white has a winning strategy is also computable. The process involves testing every possible sequence of moves to see whether white can force a win.
But while both these problems are computable, the resources required to solve them are vastly different.
This is where the notion of computational complexity comes in. This is a ranking based on the resources required to solve the problems.
Interestingly, the game may be more complex than you would expect it to be, as the scientists found it to be non-computable. It really is, in some way, “Magic”al.
(Image Credit: Nathan Rupert )