Fascinating Attempt to Code an AI for Magic: the Gathering
Author
I just randomly came across this guy's blog, which chronicals several years of effort in the construction of an AI to play Magic: the Gathering.
His AI seems to lack a proper planner, so it considers only the instantaneous state of the game using a huge number of heuristics. I'm not even sure how one would write a M:TG description language so that you could write an AI capable of reasoning about different M:TG plays.
I used to play M:TG all the time as a kid. I'm tempted to try writing my own AI as a fun project. The number of considerations boggle the mind, though. If anyone has heard of similar projects, I'd love to hear about them.
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
-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.
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.
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
-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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
