{"id":891,"date":"2020-03-26T10:04:28","date_gmt":"2020-03-26T10:04:28","guid":{"rendered":"https:\/\/www.usmtgproxy.com\/?page_id=891"},"modified":"2020-03-26T10:07:08","modified_gmt":"2020-03-26T10:07:08","slug":"magic-the-gathering-is-so-complex-it-could-stump-a-computer","status":"publish","type":"page","link":"https:\/\/www.usmtgproxy.com\/magic-the-gathering-is-so-complex-it-could-stump-a-computer\/","title":{"rendered":"Magic: The Gathering Is So Complex It Could Stump A Computer"},"content":{"rendered":"

Anyone who\u2019s ever tried to play\u00a0Magic: The Gathering<\/em>\u00a0or listened to a friend explain it to them has had to reckon with the learning curve of all its intricate rules and even more confounding cards. Human players might not be alone in feeling overwhelmed:\u00a0A new research paper<\/a>\u00a0argues that the game is so complex that there are even cases where a computer theoretically wouldn\u2019t be able to figure out how to win.<\/p>\n

A group of researchers argues that\u00a0Magic: The Gathering<\/em>\u00a0is so complex there are cases in which it would be impossible for a computer to figure out a fool-proof way to win. \u201cThis construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,\u201d they write.<\/p>\n

The team, which includes Alex Churchill, a board game designer, Stella Biderman, a researcher at the Georgia Institute of Technology, and Austin Herrick, a senior analyst at the University of Pennsylvania\u2019s Wharton Budget Model initiative, wanted to see just how complex the fantasy card game was from a computational standpoint.\u00a0What they ended up finding<\/a>\u00a0was that\u00a0Magic: The Gathering<\/em>\u00a0isn\u2019t just more complex than most other games, it\u2019s actually noncomputable in some cases. It\u2019s yet unclear just how many of those cases there are, but there are currently conceivable matches where there\u2019s no way an algorithm can figure out the optimal path to victory.<\/p>\n

The research was based on coding two decks of legacy\u00a0Magic: The Gathering<\/em>\u00a0cards, which span the entire history of the game excluding certain banned cards, and creating a mathematical model to interpret the cards within the context of the game\u2019s rules to return future board states based on which cards are played and in which order. As you can see from the following deck list, the cards used are some of the more complex ones from the game\u2019s history.<\/p>\n

\"\"<\/p>\n

Cleansing Beam, for example, deals two damage to its target creature and each other creature that it shares a color with it. Coalition Victory, meanwhile, automatically lets you win the game if you control a land of each basic land type and a creature of each color. Then there\u2019s Illusory Gains, an aura that automatically attaches to each new creature an opponent plays and brings it under your control. These card effects, combined with others, created enough alternative possible courses of action that the research team\u2019s model was unable to return a result.<\/p>\n

In chess it\u2019s extremely resource intensive to compute how one side can win. After the first two moves in chess, there are 400 different possible outcomes.\u00a0After the sixth, there are 121 million<\/a>. It\u2019s still theoretically possible to compute, though. Based on the noncomputable cases these researchers found, that\u2019s not the case in\u00a0Magic: The Gathering<\/em>, despite the fact that it\u2019s a two-player, zero-sum game using premade decks of cards, making it unique among all the other games currently studied in the field.<\/p>\n

\u201cThis is the first result showing that there exists a real-world game for which determining the winning strategy is noncomputable,\u201d the authors write.<\/p>\n

Of course, this doesn\u2019t apply to just any game of\u00a0Magic: The Gathering<\/em>. The researchers explored a very specific set of cards and starting hands based on certain requirements. For example, the decks \u201cexclusively use cards with mandatory effects,\u201d which means they don\u2019t include cards where a player would choose from varied possible outcomes. But all of the cards used are tournament legal within the rules of the legacy format.<\/p>\n

While the study has potential implications for game theory and computer science research, it also lays clear the sheer potential for discovery in\u00a0Magic<\/em>. \u201cThe full complexity of optimal strategic play remains an open question, as do many other computational aspects of\u00a0Magic<\/em>,\u201d they authors write. \u201cFor example, a player appears to have infinitely many moves available to them from some board states of Magic\u2026[which] has the potentially to highly impact the way we understand and model games as a form of computation.\u201d<\/p>\n

Ultimately it seems fitting for a game based in a multiverse whose rules are infinitely malleable.<\/p>\n

[Update – 6:16, 5\/8\/19]:<\/strong>\u00a0Shortly after publication, Alex Churchill, one of the authors of the paper, responded to\u00a0Kotaku<\/em>\u00a0in an email with some further clarifications on the group\u2019s findings.<\/p>\n

\u201cWhat we\u2019ve proven is that the operation of \u201cfinding the best move in a game of Magic,\u201d\u00a0in the worst case, cannot be computed,\u201d he said. \u201cThere are certain circumstances, even though they\u2019re very contrived, where it\u2019s proven that no algorithm can find whether there exists a winning move. In fact, since we eliminate all player choice, we\u2019ve proved something slightly stronger: that it\u2019s impossible in the general case for an algorithm to look at a board state and see whether it\u2019s possible for the game to end at all.\u201d<\/p>\n

He went on:<\/p>\n

\n

\u201cThis is what computer scientists care about when they talk about the complexity of an algorithm. The algorithm might be easy to solve in almost all cases, but we\u2019ve shown that the worst case is as hard as it can be.\u201d<\/p>\n

\u201cThis has very little implication for playing the game in practice, but it does have takeaways for potential AI designers. 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\u2019d be crazy. They\u2019d 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\u2019s actually impossible (in some cases).\u201d<\/p>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"

Anyone who\u2019s ever tried to play\u00a0Magic: The Gathering\u00a0or listened to a friend explain it to them has had to reckon with the learning curve of all its intricate rules and even more confounding cards. Human players might not be alone in feeling overwhelmed:\u00a0A new research paper\u00a0argues that the game is so complex that there are … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/www.usmtgproxy.com\/wp-json\/wp\/v2\/pages\/891"}],"collection":[{"href":"https:\/\/www.usmtgproxy.com\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.usmtgproxy.com\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.usmtgproxy.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.usmtgproxy.com\/wp-json\/wp\/v2\/comments?post=891"}],"version-history":[{"count":0,"href":"https:\/\/www.usmtgproxy.com\/wp-json\/wp\/v2\/pages\/891\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.usmtgproxy.com\/wp-json\/wp\/v2\/media?parent=891"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}