You've probably read a lot about the successes of artificial intelligence, or AI in short, in Starcraft, which was pretty impressive, but there's one game where AI algorithms obviously need some additional schooling - Magic: The Gathering.
A recent research paper called "Magic: The Gathering is Turing Complete" has looked into the algorithmic structure of Wizards of the Coast's game, and found it to be "the most computationally complex real-world game known in literature".
In their quest to see just how complex Magic: The Gathering is, board game designer Alex Churchill, Georgia Institute of Technology researcher Stella Biderman and University of Pennsylvania's senior analyst Austin Herrick found it to be occasionally impossible for AI to handle.
Just to give you a reference point, calculating potential chess moves is a common analytical task that gets progressively more difficult the further into the game you go, hitting billions sooner than you'd think.
Nevertheless, brute forcing each of these possible options is possible and is done at pretty much every chess tournament you see, thanks to some AI assistance.
Magic: The Gathering, however, is a whole another pair of boots and the possible outcomes can hit such numbers that trying to calculate each one is not only impractical, it's often impossible.
The paper reads, "In addition to showing that optimal strategic play in Magic is non-computable, it also shows that merely evaluating the deterministic consequences of past moves in Magic is non-computable. The full complexity of optimal strategic play remains an open question, as do many other computational aspects of Magic."
Churchill mentioned that while this has little implication for the actual playing of Magic: The Gathering, potential AI designers will benefit from it greatly.
Wizards of the Coast
"Probably anyone who was going to write an AI for Magic would not have made the AI choose its next move by trying to exhaustively compute all possible consequences of the current board state - that'd be crazy. 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)", he told Kotaku.