Fascinating Attempt to Code an AI for Magic: the Gathering

I had looked for such things a few years back and came up empty. I also felt the same way that you do, that the number of heuristics to consider is immense. It may benefit from looking at AI techniques in chess/checkers in which the heuristics provide an evaluation of power based on the current state of the board. You may be able to apply a similar technique to M:TG - not sure.

-Kirk

That would be a good place to start. Find out what the computer AI considers the different pieces in chess to be used for, and then write up a comparison code for your cards in MTG.

Such as one set for resources, one set for defense cards, and a second for offense cards. It also needs to consider the cards in play by the opposing player while making a move too.

I suppose you'd do it something like this:
1) Consider enemy cards]
2) Evaluate available cards based on player movement]
Do we need defense or offense? ]
3) View available cards, calculate possible combinations and repurcussions]
4) Select card types to enact on this choice]

Luck.

Im not too sharp on the AI aspect of the project, but for a long time I played the game, and I can to some degree confirm that blogs stance. Game state is a large factor, so jamming that full of heuristics is a good move, but what is really important is a working knowledge of all the cards, and all the interactions.

The thing is, even if you narrow it down to one set of cards, thats like 150 for a small set, and there are alot of 2, 3 and 4 card combinations, and they all work in fairly unique way.

So although it seems like it might be a good project, i honestly think any sort of compitant AI is out of the question, unless you tune the AI to a specific deck for it to play.

If the AI knowing one deck is good enough, the number of interacting cards is fairly low (as little as 10 different non land cards in multiples of 4), meaning it might only need to know how to use 10 cards, and a few basic combinations.

By what I know of the game, it seems this simple heuristic approach won't work very well. The first thing I would try is Monte Carlo methods, which work reasonably well for a huge variety of games (from poker to go).

I assume by Monte Carlo methods you would use a probabalistic approach, correct? Such as, given the current set of cards on the table and those in my hand, which card has the best probability of winning? Would you have to do an extensive set of game simulations in order to establish the underlying probabilities?

-Kirk

By Monte Carlo methods I mean something like the following.

Off-line preparation:
- Come up with a very fast (and inaccurate) function that given a game situation returns a probability distribution of what a player will do. You can make some sort of parametric model using simple heuristics. Ideally you would tune the parameters by maximizing the likelihood of a database of games.

During the game, each time you need to make a decision:
- Since this is a game of incomplete information, generate a few thousand possible complete configurations of the game (including the exact content of the decks). For each of these configurations, play a first move using an algorithm like Upper-Confidence Bounds. From the resulting position, simulate the rest of the game using the very fast function described above to pick the rest of the moves.
- Accumulate statistics on each possible first move. You should probably weight the results of each simulation by the likelihood of its configuration, using Bayes's formula at each previous action in the game, or something of that sort.
- Pick the move with the best winning ratio.

Merely implementing the game rules and allowing an adequate representation of cards would be a serious challenge; the old computer version from Microprose had only "easy" cards and still seemed by all accounts unable to reason about them.

Any approach, including the mentioned ones of planning, heuristic rules and stochastic simulation, need a correct model of cards and of the game as a foundation; neglect and AI ignorance of available moves and of minor aspects of the game in progress can only lead to several kinds of disaster:

- A hailstorm of bugs (e.g. data corruption when the second attack occurs in a turn, cheaply fixed to become data corruption in case of an "unlikely" third attack).

- Consistently exploitable foolishness (e.g. the computer doesn't attack with a forestwalk creature as it should because the only forest the opponent has is a fancy land that has had the forest type temporarily assigned rather than a basic Forest).

- User complaints for departing from complex official rules (e.g. the fine points of assigning and redirecting damage during combat) and from the numerous bizarre, inconvenient or unique card texts and errata (e.g. Sands Of Time); the fine points of "rule lawyering" are a big deal because differences in the behaviour of a single card in a single rare case propagate to whole-game strategy and to deck building.
An unfaithful implementation of the game is unreliable for the player, who needs to relearn his skills and strategies for a complex game that might be good but is not the one that you promised and he is interested in.

I agree with Lorenzo that implementing the rules of the game would be challenging, since a formal description may not exist. Of course that's the first part that should be implemented.

As for the rules of the game, here is the official rulebook. Not sure if it counts as a formal description or not, but it's pretty thorough.

Given that individual cards often change the rules or provide exceptions, I am not sure a formal description can exist that is actually of any use.

Quote:

Original post by Kylotan Given that individual cards often change the rules or provide exceptions, I am not sure a formal description can exist that is actually of any use.

I don't think it's impossible: just very hard. The game Puerto Rico has buildings that provide exceptions to the rules, and yet there are a couple of computer implementations that do the right thing. This is achieved by introducing intermediate stages in the turns where cards can do their jobs. It's true that the number of buildings in Puerto Rico is a lot more manageable than the number of cards in Magic, but I think they are similar in nature.

If you have played M:tG on anything beyond the "friendly" level, you would be able to immediately recognize the true area of control: card advantage.

Every combination since the "power 9" has focused on generating card advantage in one (or more) of the main areas of play (hand, library, graveyard and on the field). If you are serious about building an AI, you could use card advantage as your base heuristic. "Does this play generate card advantage in my desired area of play?".

The problem with M:tG is that there are so many cards. You might have to limit yourself to a specific expansion cycle or ruleset, just to maintain a reasonable level of control over your finished product. Otherwise, you could spend the next 15 years tinkering with appropriate weights to every card.

i don't know if this helps or if its relevant but i was in class(high school) with someone who made chess with ai(dumb though) and another class mate made dominoes with complete ai

Hi all, I'm the author of MTG Forge. It lets you play Magic against the computer using all of the rules. It has 714 cards and also lets you play sealed and draft games. My program can download all of the card pictures, just look in the menu when the program first starts up.

The current AI is very, very basic. (Don't fall out of your seats) Basically the computer randomly chooses a card from his hand and plays it. Technically the computer tries to play the most expensive card he can, and tries to play a creature first, then a spell (a one-shot magical effect). The AI also seems a little smarter than it is because I have worked a lot on the attacking and blocking code.

The AI for each card is hardcoded into the card code. There is a method within each card named "canPlayAI():boolean" and returns true if the computer should play that card, and false if it shouldn't. While very basic, it was good enough.

I am working on version 2 which will have some sort of "look ahead" algorithm, like min-max or alpha-beta. Right now I am trying to finish up the user interface. (I hate writing gui code, it is so messy. I would rather just program cards.)

My blog (http://mtgrares.blogspot.com) chronicles my ventures into AI programming and Magic.

Java source code is included
Windows Installer - http://www.mediafire.com/?5ggxjmwvmio
Java Jar (for all other platforms) - http://www.mediafire.com/?1ttoyo321mb

--Forge

http://en.wikipedia.org/wiki/Card_advantage

Its a short wiki, but research into that concept might prove useful. It breaks down all actions into, well, virtual card advantage. Card advantage is good, and its a scaler value, so making a computer want it should be straight-forward. Tiebreaking between different actions might get tricky, but thats another ballgame altogether

#1 A DSL(domain specific language) for defining card classes + an algorithm for classifying cards. The DSL will have to be built on top of the representation of the cards themselves though.
#2 A few dozen utility ratings based on abstract positions

Considering the vast number of cards and rules, I'd say go with utility by ranking utility based on an artificial personality/playtype and then performing the generated actions which provide the most utility. As a human player, I don't know what all the cards do but I can still play any deck because I know the rules so I can predict cause-and-effect and know how to use the cards in a general sense. Special combos could be hard-coded.

It's really hard to know what an opponent will do far into the future but several thousand possible states could be generated in very little time. Using card classes would make coming up with combos on the fly(during the game) much easier. The game could learn to predict stuff by remembering opponent actions in previous turns and by using Markov models, both with specific cards and by analyzing the class of cards used.

Utility/Abstract areas of interest: number of cards in hand, total creature defense/offense, elimination of things which have damaged me/creatures in the past, mana production, having or eliminating special cards, damage to the opponent, life to self. Aspects of the game which a human player must have an appreciation and awareness of must be encoded to the ai as having utility.

I don't know if it will make a better ai player, but the card classes could also be fuzzy(in the sense of fuzzy logic).

Remember, the AI doesn't just have to play a deck (though that is certainly possible). It should also be able to build decks. Let's consider the archtype decks, and how one might weight the cards in a given situation:

Aggro: Here, the goal is to burn your opponent down before they can establish defense. Card advantage is generated on the playing area, normally by sacrificing advantage in the hand. Strong cards will cost 3 or less mana, with easy color requirements. Prefered creatures will have special abilities, such as first strike, shadow, flying, to make them unblockable. Spells tend to focus on removal of threats threat removal, rather than general advantage.

Control: The infamous "no" decks. These decks establish card advantage by simply denying advantage to the opponent. "Counterspell", "Wrath of God" and "Null Rod" are all good examples of control cards. Strong cards will cover a broad range of mana costs, covering the beginning, middle and end game. Prefered reatures and spells are weighted less for what they can do, and more what they can prevent the opponent from doing.

Combo: These decks are designed around the interaction of 2 or 3 specific cards. Card advantage is developed through a single, overwhelming move in an 'all or nothing' kind of play. Often the combo deck can be completely stopped with a well-timed counterspell. Obviously, combo cards ("stroke of genious", "oath of druids", "squee, goblin nabob") are highly valued. Also highly valued are search cards, and cards which will buy the player time.

Each card could be given a weighting based on these 3 archtypes, which would also be valuable in determining play choice.

You can now begin to build personality. Obviously, a control player will assign values very differently than an aggro or combo player, and vice-versa. Here's an example:

Let's say our AI likes to play aggro decks, and prefers black as a primary color, and prefers card advantage on the field. From these choices, the AI can look at the card color, it's weighting as an aggro card, then include or exclude it in her main deck based on whatever other criteria you might assign. Using this model, the AI will naturally be drawn to cards like "Black Knight", "Phyrexian Negator" and whatever else is hot in "black weenie" style decks.

Playstyle will evolve organically from the AI's personality. The higher score the card holds for the given playstyle, the more likely it will be the AI will try to play it under normal circumstances. Continuing with the "black weenie" example above, the AI can evaluate it's cards by which will give it the largest advantage in it's preferred area of control.

For example, "Black Knight" verses "Diabolic Edict": Both have the same mana cost, but one is a permanent, while the other is an instant. Which to play? If there are no creatures on the field, the choice is obvious.

But what if the opponent has 1 creature? In this instance, it is almost always better to play the creature first. First of all, there's summoning sickness. Aggro decks work on building early tempo, and delaying the creature's appearance delays tempo. Second, the instant can be played on either turn. It can be used defensively to remove your opponent's attack on his turn, or it can be used offensively by removing a blocker on your next turn. Third, a creature generates card advantage over time. The longer it is in play, the greater the advantage until tempo is lost. However, the instant generates no card advantage. It generates card parity - one of mine for one of his. And that parity is lost as soon as the opponent plays another creature.

And if the opponent has more than 1 creature? In this instance, We have to determine whether the card parity of casting an instant will outweigh the long-term advantage of playing a creature. Are one or more of my opponent's creatures "special purpose"? Are they costing me tempo? Am I about to die?

Given this analysis, your cards should at least include the following (hidden) values:

AggroWeight
ControlWeight
ComboWeight
AreaOfPrimaryControl (hand,library,field,graveyard)
PrimaryValue
AreaOfSecondaryControl (hand,library,field,graveyard)
SecondaryValue

Of course, this is only a starting point. There are obviously many considerations to make, even in a simple creature rush. (Is my opponent running with mass removal? Are there special conditions in play, like a "Platinum Angel"? Is this creature meant for something other than combat? Have I lost tempo? etc.)

Someone should link the original blogger to this thread.

What about the area of abstract modeling? Would it be possible to develop an AI that could model the game itself based on a large sample of games, without being given specific rules for each card. That is, could an AI be made that would be fed the game state at each point in the game and from that could figure out that 'card 424' is "Destroy target creature" since each time it is played, the person that played the card performs 'choose card' and always selects a creature in the 'in play' area, and then that card is normally[1] moved to the graveyard.

[1] Barring anti-destruction effects (regeneration, indestructable, etc) and destruction-modification effects (destroyed creatures are removed from game / put back in hand / suspended / etc), which it should also be able to learn.