Some card games are known for being rather complex and hard to understand at first, requiring knowledge of many rules and cards before getting really good, with Magic: The Gathering being just one example of this.
The game requires players to assemble decks before battling it out in the fantasy world the game is set in, and as reported by Technology Review, this is "the most computationally complex real-world game known in the literature," at least according to a new paper from Alex Churchill, an independent researcher and board game designer in Cambridge; Stella Biderman at the Georgia Institute of Technology; and Austin Herrick from the University of Pennsylvania.
What does this mean though? Well, it's first about deciding whether problems can be solved, which can be done with finding calculations or working out who will win in chess, for example. The difficulty of this is called 'computational complexity', based on resources required to solve problems. If there are no algorithms to solve the problem, they are simply non-computable.
Churchill and the team started by converting each card's powers and properties into a set of steps that can be encoded, playing out a match that unfolds in a Turing machine (a computing machine using rules to define a result). The result: it's actually non-computable, and is similar to the problem of deciding whether a computer program with a specific input will finish running or just continue on forever, something that was determined to have no algorithm to answer in 1936.
"This is the first result showing that there exists a real-world game for which determining the winning strategy is non-computable," the team says. "Magic: The Gathering does not fit assumptions commonly made by computer scientists while modeling games."
Do you understand the game?