{"id":123,"date":"2009-12-13T19:47:13","date_gmt":"2009-12-14T03:47:13","guid":{"rendered":"http:\/\/magic.kevinleung.com\/?p=123"},"modified":"2009-12-13T19:47:13","modified_gmt":"2009-12-14T03:47:13","slug":"on-the-application-of-bayesian-analysis-to-magic-by-chris-d","status":"publish","type":"post","link":"http:\/\/magic.kevinleung.com\/?p=123","title":{"rendered":"On the Application of Bayesian Analysis to Magic by Chris D"},"content":{"rendered":"

(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)<\/em><\/p>\n

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.\u00a0 Chess, and other chess-like games, are a primary example of this.\u00a0 The ability of computer systems to play strategy games such as chess has presently surpassed all human players.\u00a0 Indeed, for some simpler games, such as checkers, computer programs have successfully \u201csolved\u201d the game \u2013 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.\u00a0 On the other hand, many other strategy games have not been successfully played by computers.\u00a0 This lack of success can be attributed to a variety of vicissitudes, depending on the characteristics of the game being attempted.<\/p>\n

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\u2019s errors.\u00a0 These factors combined make chess a good candidate for computer play.<\/p>\n

Magic the Gathering, on the other hand, is, for many reasons, poorly suited to be played by an artificial intelligence.\u00a0 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\u2019 hands, is known by only one player, and, additionally, the order of cards within the players\u2019 decks, which, overall, represents most of the information content of the game state, is hidden from both players.\u00a0 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.\u00a0 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 \u201cturn\u201d 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.<\/p>\n

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.\u00a0 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.\u00a0 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.<\/p>\n

A computer should be able to manage Magic data from multiple perspectives.\u00a0 In general, we can consider the effects of a play as an Aggro, Combo, or Control action.\u00a0 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.\u00a0 An example of a card which would give card advantage is Divination, which draws two cards at the cost of one.\u00a0 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.<\/p>\n

When designing a deck, it is important to keep a balance between many different factors.\u00a0 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.\u00a0 Even in decks which do not focus on card advantage, it is often beneficial to include it.\u00a0 For example, I included two Sign in Blood cards in my class tournament deck, in order to provide card advantage at critical times.\u00a0 I also included two Gravediggers, which are also intended to provide card advantage.\u00a0 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.\u00a0 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.\u00a0 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.<\/p>\n

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.\u00a0 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.\u00a0 The nature of chess also lends itself to being recorded and analyzed by computer programs.\u00a0 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.<\/p>\n

Several elements of strategy which I found useful during the tournament could, under the right conditions, be adapted to play using a computer algorithm.\u00a0 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.\u00a0 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.\u00a0 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.\u00a0 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.\u00a0 A computer would also need to know when to trade its creatures for its opponent\u2019s 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.\u00a0 On the other hand, there may be special conditions during which these actions would not be correct.\u00a0 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.\u00a0 So this situation is really more complicated than simple rules can determine.\u00a0 This is why Magic is such a complicated game and is hard for computers to play well.<\/p>\n","protected":false},"excerpt":{"rendered":"

(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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[6,15],"tags":[],"_links":{"self":[{"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=\/wp\/v2\/posts\/123"}],"collection":[{"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=123"}],"version-history":[{"count":1,"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=\/wp\/v2\/posts\/123\/revisions"}],"predecessor-version":[{"id":124,"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=\/wp\/v2\/posts\/123\/revisions\/124"}],"wp:attachment":[{"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=123"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/magic.kevinleung.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}