One of the most common questions that I get asked is "Why is the AI so bad?" and I understand where people are coming from. When you play a game of Magic in real life you expect a certain level of sophistication from your opponent. A human opponent will attack and block intelligently and play cards that improve his chance of winning. MTG Forge's AI often doesn't attack or block intelligently and sometimes shoots itself in the foot with cards like Ambition's Cost (3B, Sorcery, You draw three cards and you lose 3 life). The computer has been known to play Ambition's Cost when it only has 2 life, thus losing the game. This situation can be improved by programming the computer NOT to play Ambition's Cost when it has 3 or less life but this doesn't improve the situation very much because currently MTG Forge's AI cannot determine whether the cards in his hand are good or not and thus randomly plays Ambition's Cost like a drunken sailor. (Sing with me, What-would-you-do-with-a-drunken-sailor, What-would-you-do-with-a-drunken-sailor, What-would-you-do-with-a-drunken-sailor, Early-in-the-morning, ha.)
One common AI algorithm that is suitable for two player games likes chess and Magic is min-max, also called minimax or alpha-beta (which is an optimized version of min-max). Min-max is named after the conflicting goals of the two players, you want to maximize your chance of winning and your opponent wants to minimize it. In order to use the min-max algorithm you have to be able to generate possible moves for both players.
OK, take a breath **whoooo**. I know we are just scratching the surface but you've digested some difficult stuff and hopefully you feel smarter without having to listen to boring classical music. (I like classical music, just not the screeching violins. Please leave a comment if you actually do play violin.)
Stay tuned for more info, this is a four (or five) part series and yes I do get more technical.
p.s. This is the first time that a web page has mentioned both drunken sailors and the min-max algorithm, my highschool English teacher would be proud. :--)
Nice and funny article :)
ReplyDeleteI feel your pain. The AI for Wagic wasn't so bad at first, buts as we added cards, it got worse at using most of them...
Right now in Wagic the AI is very good with Aggro decks. It has no chance when playing a control deck though, for the same reasons you mentioned: Wagic's AI has close to no idea of what its cards do, besides a basic concept of "positive effect" and "negative effect"
wololo>
ReplyDeletejust looked today into your ai code. what I liked is that you have DAMAGER ability that AI can calculate efficiency. And I thought you have similar abilities like COUNTERSPELL, PUMP, PREVENT, etc. but... anyway I liked your code though I hoped to find min-max there ;))
btw, am I right saying that your AI can't use spells that are not parsed (AbilityFactory, addAbilities, switch (id), etc.)? only with auto keywords?
nantuko84: You're pretty much right. If it's not a parsed ability, the AI in Wagic will always assume by default that it has a "negative" effect, and will cast it on the opponent (or their creatures) if it has targets, or simply avoid to cast it if it doesn't.
ReplyDeleteThis is why we are trying to have as many cards automatically parsed, and progressively remove "hard coded" cards.
"Right now in Wagic the AI is very good with Aggro decks. It has no chance when playing a control deck though."
ReplyDeleteWell that is how MTG Forge's AI is, the "no AI method" method.
It's probably too late to do this but I would like to see a ratings system for each card where the AI would play the card with the highest rating. Of course in each card there will have to be conditions set in which the rating of the card goes up or down depending on the situation. This way you can make combo decks (have the rating go up or down depending if a certain card is available) and have ratings on cards like Ambition's Cost move up or down depending on life and etc.
ReplyDeleteYeah AI is hard. I'm quite happy with the minimax a/b pruning in mine but it took a LONG time to get it right.
ReplyDeleteWhat's nice about it in the long run is you don't have to (for the most part, I have 1 special case for locations and scoring cells) code specifics for the AI. It figures things out on its own. Every once in a while it surprises me with something I hadn't even thought of. :)
telengard> is it possible to port your ai from dreamblade to mtg? as far as I know, your project isn't open source. anyway at least it will be very interesting to get to know how you build your objective function to value different game positions
ReplyDeletePorting it would be somewhat difficult because it assumes that every change to game state is put through an "undo engine" of sorts.
ReplyDeleteThis is quite a lot of work and just about every piece of code that changes a variable while running would need to go through it. Either that or continuously copying the game state (which I tried and it was sloooooowwww).
This is so it can back out changes.
I do have some code that is specific to phased type games that aren't I go you go alternating which could help.
The actual minimax and pruning code is pretty standard. It's the evaluation function that does all the magic (no pun intended). Mine luckily is pretty straight forward and works very well.
I have the luxury of perfect information so it's a little easier than MtG (ok probably a lot easier hehe).
I will probably be putting my code online at some point in the hopes of getting some help w/ the UI. :)
If mtgrares thinks it could be used with his app I'd be more than happy to help out.