In the previous post, we saw that for an AI program the major difficulties in Magic can be broken down into two areas, generating legal moves, and scoring the game state. The score might be simplified for now as life points plus mana or something, but the major difficulty remains of generating legal moves.
Ever turn, there's the chance of a player playing any one of hundreds of cards that are legal to play at that point.
To do a good job of looking ahead, we need to prune down the number of possible moves as much as possible.
The beginning of the game has a maximum of possibilities and a minimum of information.
AI programs for games such as chess deal with this problem in the same way as human players. They make several moves out of a "book" of already worked out opening moves.
Personally, I doubt the relevance of this strategy to Magic. If the AI "knew" that a deck was designed for a particular playing style, such as aggressive, control, or combo, there might be some standard opening plays. But at least in the initial stages, the decks constructed by the deckbuilding algorithm are not going to fall into clear categories.
Tuesday, August 24, 2010
Friday, August 20, 2010
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.
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.
Tuesday, August 17, 2010
MtG AI: Deck Construction
Magic is played with decks of cards, 60 or more, chosen from a pool of legal cards.
Walk Before We Run - ignore sideboard issues
WBWR - make the pool of legal cards small to test the code, add to the pool later.
I'd attack this problem with something like a genetic algorithm. A GA has a simple algorithm:
Create a population, give each member a score.
For as long as you want:
Choose high scoring members, modify them, score the new version, and add them to the population.
Take out members of the population based on some criteria (such as a low score).
Several modifications are usually allowed. Mutation changes a population member slightly. Crossover mixes two members of the population.
Lets make Magic decks our population members. Each member is just a list of card numbers, drawn from the list of legal numbers. Mutation might mean switching a number for another legal number. Crossover might mean choosing a number, N, between 1 and 60, and taking the first N cards from one member, and rest up to 60 from a second member. There are more sophisticated versions of these genetic operators that can be invented, as well.
Since we are constantly testing new decks that are similar to our high scoring members, and throwing away poor decks, the overall population is expected to gradually improve its score. If the poopulation is small, we can also expect it to converge on a single solution, a "killer deck" that is better than all the other decks tested. (Is this a killer deck in real life? No way. It is just good in the metagame that our population represents.) There are also ways to encourage the evolution of 'species' - several different decks that remain in the population for long periods.
Of course, the above description is hiding a big issue behind a "Separation of Concerns" wall. How do we score decks? Well, the best thing to do would be to have a huge round robin tournament, and the score for each deck would be its wins minus its losses. Now you can see why I thought "Self Play" was an important heuristic!
Until you get your game play AI running, you can substitute other scoring methods. Invent some way of assigning points to a deck. If a deck with a creature that requires some color, doesn't contain land of that color, then give that deck a penalty. If the same keyword appears on more cards (so the deck has a 'theme') give the deck a bonus. This kind of quick and dirty scoring is also useful in the beginning of a run of deck development. If our first set of decks is generated by just throwing 60 random numbers together, over and over, those decks are going to be really bad. It might save time to not even bother playing these decks until they reach some basic level of sanity.
I wouldn't overdo the scoring heuristics, though. One of the best things about a GA is that it can find a solution to a problem that a human would never think of. Using a lot of heuristics to score decks, instead of letting them compete head to head, is forcing the algorithm to follow your way of thinking.
So that is my approach in nutshell. Self play involving a variable population which improves over time.
Walk Before We Run - ignore sideboard issues
WBWR - make the pool of legal cards small to test the code, add to the pool later.
I'd attack this problem with something like a genetic algorithm. A GA has a simple algorithm:
Create a population, give each member a score.
For as long as you want:
Choose high scoring members, modify them, score the new version, and add them to the population.
Take out members of the population based on some criteria (such as a low score).
Several modifications are usually allowed. Mutation changes a population member slightly. Crossover mixes two members of the population.
Lets make Magic decks our population members. Each member is just a list of card numbers, drawn from the list of legal numbers. Mutation might mean switching a number for another legal number. Crossover might mean choosing a number, N, between 1 and 60, and taking the first N cards from one member, and rest up to 60 from a second member. There are more sophisticated versions of these genetic operators that can be invented, as well.
Since we are constantly testing new decks that are similar to our high scoring members, and throwing away poor decks, the overall population is expected to gradually improve its score. If the poopulation is small, we can also expect it to converge on a single solution, a "killer deck" that is better than all the other decks tested. (Is this a killer deck in real life? No way. It is just good in the metagame that our population represents.) There are also ways to encourage the evolution of 'species' - several different decks that remain in the population for long periods.
Of course, the above description is hiding a big issue behind a "Separation of Concerns" wall. How do we score decks? Well, the best thing to do would be to have a huge round robin tournament, and the score for each deck would be its wins minus its losses. Now you can see why I thought "Self Play" was an important heuristic!
Until you get your game play AI running, you can substitute other scoring methods. Invent some way of assigning points to a deck. If a deck with a creature that requires some color, doesn't contain land of that color, then give that deck a penalty. If the same keyword appears on more cards (so the deck has a 'theme') give the deck a bonus. This kind of quick and dirty scoring is also useful in the beginning of a run of deck development. If our first set of decks is generated by just throwing 60 random numbers together, over and over, those decks are going to be really bad. It might save time to not even bother playing these decks until they reach some basic level of sanity.
I wouldn't overdo the scoring heuristics, though. One of the best things about a GA is that it can find a solution to a problem that a human would never think of. Using a lot of heuristics to score decks, instead of letting them compete head to head, is forcing the algorithm to follow your way of thinking.
So that is my approach in nutshell. Self play involving a variable population which improves over time.
MtG AI: First thoughts
Yes, the complexity of Magic is overwhelming! Where do we start?
Let's start by laying down some well tried heuristics (rules of thumb) for the development process.
Walk Before You Run - this means we might have to try to solve a simpler version of the problem first, learn some lessons, and then attack the bigger problem we really want to solve. Sure we want to play any kind of Magic game out there, but starting off by staring at 10,000+ card descriptions just leads to drooling. Think about ways to cut the problem down to size. Work with only the cards of a recent core set, for example, instead of every card ever made. How about limiting the number of colors? Eliminate enchantments or some other aspect of the game, until later. Even programming some BabyMagic game is going to be a challenge, so start easy. You won't get discouraged (so fast).
Separation of Concerns - this means not trying to solve everything at once in one ball of wax. Magic naturally falls into separate areas, such as deck construction and play. There are even areas such as the metagame and trading values that I won't try to talk to right now. You can attack deck construction separately from play, even if you want to integrate them eventually.
Self Play - the interface of your system should allow the system to play against a copy of itself, not just a human being. The computer can play thousands of games while you sleep, improving it's algorithms, databases, etc. Self play assumes that your AI is written so that learning/improvement can be scored independently of a human. A genetic algorithm is an example of that.
I'm sure we can come up with other high level heuristics like these, but for now this will do nicely.
Let's start by laying down some well tried heuristics (rules of thumb) for the development process.
Walk Before You Run - this means we might have to try to solve a simpler version of the problem first, learn some lessons, and then attack the bigger problem we really want to solve. Sure we want to play any kind of Magic game out there, but starting off by staring at 10,000+ card descriptions just leads to drooling. Think about ways to cut the problem down to size. Work with only the cards of a recent core set, for example, instead of every card ever made. How about limiting the number of colors? Eliminate enchantments or some other aspect of the game, until later. Even programming some BabyMagic game is going to be a challenge, so start easy. You won't get discouraged (so fast).
Separation of Concerns - this means not trying to solve everything at once in one ball of wax. Magic naturally falls into separate areas, such as deck construction and play. There are even areas such as the metagame and trading values that I won't try to talk to right now. You can attack deck construction separately from play, even if you want to integrate them eventually.
Self Play - the interface of your system should allow the system to play against a copy of itself, not just a human being. The computer can play thousands of games while you sleep, improving it's algorithms, databases, etc. Self play assumes that your AI is written so that learning/improvement can be scored independently of a human. A genetic algorithm is an example of that.
I'm sure we can come up with other high level heuristics like these, but for now this will do nicely.
Magic the Gathering, why no AI?
On my mind recently, the lack of good AI for MtG.
Why is this so? It seems that everyone is put off by the bewildering complexities of game mechanics that change the rules as each card is played.
I agree that Magic is more complicated than the sorts of boardgames that are the traditional targets of AI, such as chess. But if you can write game AI for an RTS (Real Time Strategy) game, you should be able to write an AI to play Magic. Given that position, I'd like to write a few posts here on what I think would work for Magic, if you were to go about building an AI for it.
Why is this so? It seems that everyone is put off by the bewildering complexities of game mechanics that change the rules as each card is played.
I agree that Magic is more complicated than the sorts of boardgames that are the traditional targets of AI, such as chess. But if you can write game AI for an RTS (Real Time Strategy) game, you should be able to write an AI to play Magic. Given that position, I'd like to write a few posts here on what I think would work for Magic, if you were to go about building an AI for it.
Subscribe to:
Posts (Atom)
