A recent study by AI researchers concludes that Magic: The Gathering is one of the world's most complex games. The work provides new insights into game theory, as well as new considerations regarding Turing machines in the testing of certain game states.
The premise of the game remains largely unchanged from its creation in 1993. Two players or more face off in a duel with a deck of at least 60 cards, and there is no maximum to that number, so long as a player can shuffle their deck in their hands unassisted. These decks can be constructed from a pool of nearly 20,000 cards, and with a deep, sophisticated rule set, there is no surprise to players regarding the complexity in attempting to determine the outcome of any given board state.
The study was comprised of the work by Alex Churchill, a researcher and board game designer in the UK, Austin Herric at the University of Pennsylvania, and Stella Biderman at the Georgia Institute of Technology. The project began with the use of a Turing machine, where the team worked to calculate the computational complexity of the game.
While this type of study is not the first of its kind, u/rentar42 offered an in-depth explanation as to the differences between what has been done before and what this recent work aims to conclude. In essence, the recent study concludes that it is possible to create a scenario within the game whereby there is no way to compute the winning strategy, which places the game into what is termed as "non-computable", meaning that regardless of the power and speed of the computer used, one will never be provided a solution that is guaranteed to be the best sequence of moves.
Other games that fall under the broad characterization as being Trading Card Games (TCGs) or Collectible Card Games (CCGs) are Hearthstone and Eternal, from a digital point of view, or smaller-scale paper formats like Star Wars: The Card Game, or Call of Cthulhu LCG, to name but a few. While they can be considered complex in their rules as well, they do not come close to Magic: The Gathering. One reason for this is simply that the vast difference in the volume of cards that are available, the number of phases that make up a players turn, and the extensive rules built up over 26 years of expansions.
Overall, the final report describing in detail how the study was conducted, as well as its concluding statement, is a fascinating read. It will be interesting to see what researchers Churchill, Biderman, and Herrick plan next, and how they may impact the field of game theory.