(Here’s one of the more technical papers I got. Very, very interesting analysis of Magic AI. Of course, the people out there who actually do Magic AI have a better idea how true these things are, but I think there a bunch of good observations. -Kevin)
Recently, deterministic computer systems have been shown to be highly effective in the solution of various games of strategy previously thought exclusive to the provenance of human thought. Chess, and other chess-like games, are a primary example of this. The ability of computer systems to play strategy games such as chess has presently surpassed all human players. Indeed, for some simpler games, such as checkers, computer programs have successfully “solved” the game – creating an algorithm that, along with a corresponding database of predetermined calculations, can provably determine the best move in any position in a relatively short amount of time. On the other hand, many other strategy games have not been successfully played by computers. This lack of success can be attributed to a variety of vicissitudes, depending on the characteristics of the game being attempted.
Chess is a particularly auspicious candidate for computerized solutions, being that it is: (1) open in the information domain, that is, all aspects of the game state are known to all players at all times; (2) highly tactical, that is, many if not most variations involve lines of play in which each player is forced to play from among a very small number of good-looking moves, and where all other moves can be clearly shown to lose, which decreases the branch factor of the game tree; (3) simple to define, that is, each piece moves according to basic geometric factors and legal moves tend to remain legal over long periods of time; (4) drawish, that is, games tend to produce draws and wins always involve capitalizing on the opponent’s errors. These factors combined make chess a good candidate for computer play.
Magic the Gathering, on the other hand, is, for many reasons, poorly suited to be played by an artificial intelligence. These include the facts that it is: (1) closed in the information domain, that is, portions of the game state, such as the content of the players’ hands, is known by only one player, and, additionally, the order of cards within the players’ decks, which, overall, represents most of the information content of the game state, is hidden from both players. This will present problems to any computer trying to play a good game of Magic, although it can be mitigated somewhat by considering the fact that the impact of the information of card order within the deck on the outcome of the game is much lower than that of the information that is available to the players. Additionally, Magic the Gathering is: (2) highly strategic, that is, players are seldom forced to do anything, and there are many points of time within each “turn” where players may act or react (but usually choose not to), further increasing the time complexity of the game tree; (3) difficult to define, that is, as there are thousands of Magic cards in print, many of which have eccentric and difficult to implement rules that alter or create new aspects to the game state, it is difficult to represent and effectively analyze the game state; (4) random in outcome, that is, games tend to be won or lost often based upon random chance, and in many cases strategy is less important than drawing the correct card.
Many of the ways in which Magic is difficult to implement on a computer can be resolved, if only partially, through an aggressive use of Bayesian analysis. In particular, Bayesian analysis allows the program to make decisions based only on a partial knowledge of the game state, and to update its decision algorithms depending on new information that becomes available. However, since the expected behavior of the Magic the Gathering, when considered as a system, is highly dependent on the behavior of the opponent, it is difficult to use Bayesian analysis to determine the correct play in a given situation.
A computer should be able to manage Magic data from multiple perspectives. In general, we can consider the effects of a play as an Aggro, Combo, or Control action. Also, we can attempt to quantify the loss/benefits of an action in terms of variables such as (1) life lost/gained, (2) damage dealt, (3) field advantage, (4) card advantage, (5) mana acceleration, (6) information gained/lost. An example of a card which would give card advantage is Divination, which draws two cards at the cost of one. An example of a card which causes information loss is Time Spiral, since it causes cards from the hand/graveyard to be shuffled back into the library.
When designing a deck, it is important to keep a balance between many different factors. For example, in decks which include mana acceleration, it is critical to have exactly the right number and kinds of cards which provide mana acceleration. Even in decks which do not focus on card advantage, it is often beneficial to include it. For example, I included two Sign in Blood cards in my class tournament deck, in order to provide card advantage at critical times. I also included two Gravediggers, which are also intended to provide card advantage. In general, I found the addition of the additional element of card advantage to be invaluable in defeating certain kinds of Aggro decks within the environment, specifically those which would go full Aggro for the first few turns of the game and then run out of cards to play. Against these sorts of decks, I can trade my creatures one for one (or in many cases one for two) and, by gaining card advantage from such cards, still have one or two extra cards later on to play when my opponent has run out of cards. Similarly, any computer program that attempts to play magic must be aware of elements such as card advantage, field advantage, and mana acceleration, which, although possibly orthogonal to their main strategy, will provide the additional push needed to dominate a similarly situated opponent.
One major barrier to the performance of the Magic the Gathering engine is the lack of professional Magic games recorded in a computer-readable format. In comparison, chess has hundreds of years of history over which the rules of the game have remained basically the same, and millions of recorded games played throughout that history. The nature of chess also lends itself to being recorded and analyzed by computer programs. On the other hand, Magic the Gathering has rules that change every few months, and its games have no real ability to be recorded, partially due to the limited information available to players.
Several elements of strategy which I found useful during the tournament could, under the right conditions, be adapted to play using a computer algorithm. I found that it was generally best to get out a creature on turn one, and to use the most powerful creature available when one does so. So, for example, I started off many games with my tournament deck by playing a Swamp and then casting a Vampire Lacerator, which is a 2/2 with a negative ability of life loss for its controller. If I am going second, this is especially useful because it discourages attacks from 1/1 creatures my opponent may have played on his or her first turn. If I am going first, then I can usually attack on turn 2 for 2 damage, and then play an appropriate 2-drop creature, such as a Rathi Trapper 1/2 or a Putrid Leech 2/2, both of which can block enemy one-drop attackers. A computer would also need to know when to trade its creatures for its opponent’s creatures; for example, if I played a Vampire Lacerator on turn 1, and my opponent played a Goblin Guide 2/2 and swung with it, I would probably block and trade my Lacerator for his Goblin; on the other hand, if instead I was playing green and had out a Llanowar Elves 1/1, and my opponent played a Raging Goblin 1/1 Haste and swung, I would probably not block and the computer ought not to block either. On the other hand, there may be special conditions during which these actions would not be correct. For example, if I controlled a Lacerator and my opponent swung with a Goblin Guide, and I noticed that I have a Child of Night and two Feast of Bloods in my hand, then I might not block in order that I can play my Child of Night on turn two, and then control two vampires in order to satisfy the cast condition for Feast of Blood. So this situation is really more complicated than simple rules can determine. This is why Magic is such a complicated game and is hard for computers to play well.