Two computer scientists ran the popular card game through a series of tests using a Turing machine and concluded that “Magic: The Gathering is the most computationally complex real-world game known.”
Three researchers put the game through its paces: Stella Biderman at the Georgia Institute of Technology, Austin Herrick at the University of Pennsylvania, and Alex Churchill who is board game designer based in the UK. They translated the powers and properties of each card into a set of encodable steps, then played out games in a Turing machine.
Slight sidestep so the rest of this makes a bit more sense…
The same sort of computation can be used to determine the winner of a game of chess – but it’s simpler due to the limited board size, the number of pieces, and other factors. Judging MtG required some heavier lifting with the fact that is has thousands of cards that could potentially make a 60 card deck.
In the end, the researchers determined that trying to determine if one player has a winning strategy in MtG is like dealing with the halting problem that Turing ran into.
This is the problem of deciding whether a computer program with a specific input will finish running or continue forever. In 1936, Alan Turing proved that no algorithm can determine the answer. In other words, the problem is non-computable.
So Churchill and co’s key result is that determining the outcome of a game of Magic is non-computable. “This is the first result showing that there exists a real-world game for which determining the winning strategy is non-computable,” they say.