Magic: The Gathering is a notoriously complex game, filled with innumerable cards that have unique properties, effects, and strategic uses. As such, it’s become a target for AI and computational research – just as everything from chess to StarCraft II has in the past. Now, researchers have determined that Magic is just too complicated for computers to solve.
A recent research paper “establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature.” The researchers include board game designer Alex Churchill, Georgia Institute of Technology researcher Stella Biderman, and senior analyst of the University of Pennsylvania’s Wharton Budget Model Austin Herrick.
The results conclude that “finding the best move in a game of Magic, in the worst case, cannot be computed,” as Churchill tells Kotaku. “There are certain circumstances, even though they’re very contrived, where it’s proven that no algorithm can find whether there exists a winning move.” Instead, there are certain circumstances in which a computer algorithm would never be able to complete its calculation about which move would be the optimal next play.
Plenty of potential Magic games are fully computable, but there are certain deck combinations (totally tournament-legal ones) which, according to the research, present so many potential outcomes that computers can’t – and could not in the future – ever pick the optimum result.
Churchill says “this has very little implication for playing the game in practice, but it does have takeaways for potential AI designers,” since it means nobody could design a Magic-playing AI that would run through every possible outcome before making a play. “They’d do it using heuristics, rules of thumb that give a best guess about how to play. Our paper just proves that the exhaustive computation approach is definitely not the way to go because it’s actually impossible (in some cases).”
Related: Deal yourself into the best card games on PC
The heuristic approach is basically how the Deepmind AI project approached StarCraft II last year, and it’s possible – even likely – that if it or other games could be put to the same test that this research provided, they might prove even more complex than Magic. For now, we can still call Magic the most complex game in the world – at least in our hearts.