MtG AI: Playing the Game

My take on MtG deck construction was pretty straightforward from an AI perspective, even though it was very different from the way a human player thinks about the process. But now that we have a deck, how do we play it with an AI?

While the complexities of 11,000+ cards and changing rules might lead to some initial frustration, let's review what is in our favor in trying to build an AI for the game.

Magic is a two person game. The players take turns making plays. If one player wins, the other loses. The game always has a specific state. All of those things are also true of chess, checkers, go, and many other well studied games. So we really do have a lot going for us in terms of theory and ideas.

Two person games of this type are playable by an algorithm called minmax, or alpha-beta pruning. The basic idea is to start from specific game position. Assuming this position is not itself a win for one player, the opposing player has to move. First make a list of all of the players legal moves. Now change the game state (as if they had taken that move) and re-evaluate the state. Is it a win for either player? If not, score the position in terms of relative advantage for one player or the other. Repeat the process, this time scoring eac of the replies of the player to each of the possible moves. And on. And on.

This process builds a tree of game states, as many moves into the future as you have time to evaluate, each one of which has a score. The AI will choose the play at the first level which leads to the best score for it, as far into the future as it can see, assuming that on the player's turn, the player is doing the same thing.

This is a very well understood algorithm in computer science. It depends on two things - being able to generate a list of legal moves for each player, and a way to score game states. It is in these two areas that the complexity of Magic rears its head.

Legal moves

For all the complexity of the Magic turn structure, it really is a game where players strictly take turns moving. You can see this is true because any time Alice takes an action, Bob her opponent can play an 'instant'. So each players legal move list is changing as the game runs through its different phases and turns, but it always includes "play instant from hand". The trouble is that 'instant' is not just one thing, but a whole class of things that or might not be in the hand. But hey, we're already in a lot better position than assuming that at any point in the game a player can play any one of 11,000+ cards!

This is a great reason to start with a very restricted set of cards to play with. For example, the recent computer game "Duels of the Planeswalkers" for Xbox 360 and PC has a game playing AI. This AI doesn't have to deal with 11,000 cards, only the ones allowed in the specific decks of the game itself.

The number of choices for legal move is called "fan out". Both Go and Magic have a big fan out, and that makes it difficult for a computer program to look very far into the future. In comparison, in a game such as checkers the program can analyze the tree many layers forward (actually, in the case of checkers, all the way to the end). The depth of this lookahead is what makes a game AI smart (or dumb).

A way to look deeper is to not look at all the choices at each level. The program can sort the list so that it is looking at the likeliest moves first, and also "prune away" whole sections of the tree that lead to bad results. In AI programming, these are standard ways to speed up and look farther ahead.

Game state evaluation

Each position needs to be scored in order to use our algorithm. Again, this might sound very complicated for Magic, since the "game state" includes the visible cards, the probabilities of the cards not seen, and even the rules themselves (which can change as different cards are played). However, we can start with some very basic scoring based simply on life points, perhaps with some modifiers for mana pool, tapped/untapped cards, etc. All of these are known to both players at all times.

Most of the time, we want our evaluator to be fast rather than accurate. For one thing, it is hard to be accurate. For another, this algorithmic approach relies on evaluating many, many positions to choose the best play.

Summary

Even though Magic is not a game of "perfect information" (unlike chess, where both players have all the information and the same information) we can still analyse it using a standard game algorithm of minmax, looking at legal moves and scoring them. This is all a program has to do to play the game.