As I work on MTG Forge version 2, I keep thinking about the artificial intelligence (AI). How can I, a guy who isn’t an expert in AI, write and program a better AI? The AI could attack or block better, but how? One of the key phases in Magic is creature combat but making any combat choice is complicated. The cards you see in play only make up a small part of the puzzle. The AI can only see the creatures in play, so it has to make all of its decisions blindfolded. It doesn’t have years of experience or intuition to rely on. (Technically the AI can also see the cards in your hand and deck but trying to use that information is extremely complicated.)
So this leads me to the question, “How good can the AI be if it only considers the board?” The AI could comprehensively consider all the creatures in play and determine how to maximize the situation. Basically the AI would have function that evaluated the board and it would try to maximize it, but would this really help the AI play better?
The next level of AI would consider the board position and the cards in his hand, thus enabling him to effectively use Giant Growth and Terror. This type of AI would be a definite improvement over its primitive ancestor. The AI would seem more “alive” and would occasionally make a surprising play. (One of my goals is to have the AI surprise the player because it makes the game more interesting.)
Obviously there could be another level of AI that also considered the type of deck it was using and the type of deck it was playing against. I’m not sure if I’ll get to this level of sophistication, but I will keep it in mind.
Articles about the AI generate the most comments, so feel free to post your opinion. And if you are an expert in AI or write AI for videogames, please e-mail me.
--Forge (mtgrares yahoo com)
Posts
21 comments:
Essentially what most experienced players do is exactly what you are describing...they imagine what could be in your hand (and they have a good guess because they know your deck...maybe better than you do) and then they weigh the possibilities before making any tactical decisions in combat or on the stack. So the AI's first task is to "KNOW" the decks. "What cards are likely to be drawn?" Ok then now that we have a clue about that then we ask: "What cards are likely to be played?"...and finally "what is the best solution to each play?" it can get tricky with combos but the task with playing against a combo deck is relatively simple...stop the most dynamic part of the combo. So your plan should be to identify the combos and then find their weakness.
(artifacts/enchantments get disenchanted, creatures get bolted, or removed, lands get destroyed, spells get countered, either directly by spell/ability or by removing their target(s).
One example from MTG Forge: me vs the AI: Ive got only a Sakura-Tribe Elder in play, it plays a Flametongue kavu, in response to it playing the kavu I sacrifice the elder...then the kavu comes in play...(It should die to its own ability, it doesnt because Forge is buggy but it should.) But if I play the same move on the AI it doesnt see the ability to sacrifice and so loses its Sakura without trying to stop me.
My point here is you could check for simple tactics when there are targets on the stack...Is this counterable? Should it be countered? what is the cost to the AI to do so?
What are the benefits? etc...if you break down each opportunity into the right questions you will get a much better player as a result.
Gando - what you are talking about is nigh impossible for a game like Magic. It sounds so easy when you describe it, but that's because you can imagine how you think. However, the AI has no idea what the cards are (how would the AI "know" what cards can do? You'd have to give a programmatic meaning to each ability, which is much harder than just implementing the rules for the ability)
Hell, they can't even take that approach with chess, which is a much easier game compared to Magic (no hidden info, each piece has relatively few abilities, etc).
I beg to differ. It might be beyond the capabilities of us hobbiests but I know for a fact it is doable at least on the rudimentary levels. The problem is figuring out how to make the logic conform to the game at hand...One thing is allowing the game to rate each potential move (which is how most chess games operate) and at the sum of the ratings pick the best numerical choice...its not perfect but I dont think anyone expects AI logic to be perfect...just functional.
On an unrelated and entirely different subject...the drafting functionality of MTGForge2 would be greatly enhanced I think at least from the player's perspective, by giving the cards a rarity attribute within the card.txt "database" instead of using differing rarities to create the draft sets...have one file that the player can edit called (for instance) "draftingsets.txt" and all the cards named in it are in the drafting set...their frequency determined by the rarity attribute.
This would save tons of effort and time sorting out "undesirable" cards either to make the drafting easier or harder as the player desires. For instance knowing how the mtgforge ai currently plays I try to leave out the cards that break it (tremor for example), or that give it a hard time (vanilla 1/1s or overcosted underfunctional cards... the less of these in the sets the better the ai plays.).
If I were a weaker player I might want to remove some of the more bomblike cards (meadowboon for example) or cards that tend to give the AI a serious advantage (wrath of god).
It's just a suggestion and I know this topic isnt related but frankly I'm not sure where else to post this.
I know this isn't a very constructive post I just wanted to let you know that there are a lot of us that appreciate the amount of effort and accomplishments you are putting forward with this project. From most of us anonymous users that frequent your board or those that will enjoy the fruits of your labor, I'm saying thank you.
Sorry, I meant my post wasn't productive because it doesn't talk about your topic.
The best Magic AI I've seen so far is Deckbot's alpha-beta pruning system.
An Adhoc AI like the one you're talking about can have a very acceptable level, but at some point it will show its limits. To quote Deckbot's author: "Doing that will limit the engine to the skill of the programmer."
Obviously, one has to add ad-hoc stuff to limit the size of the search tree.
The main problem is that this eats lots of CPU...
Another solution would be an AI that has poor skills, but is easy to program. Therefore lots of people could create new AI players. They probably wouldn't be the best players out there, but this would give best replay value.
I'm thinking of IBM's robocode, for example.
That would be, for example, an AI that attacks whenever it can, or an AI that prefers to block a lot, an AI that will rather try to cast spells rather than creatures, etc... very basic stuff, but with lots of customization
Another idea I had is an AI that learns basic stuff about you and your decks when it plays... For example, the creatures in your deck that dealt the most damage during your last game, or the spells/cards that gave you the most life, stuff like that.
This is still very ad-hoc and there are lots of flaws, but that would make an AI that seems to "remember"
As far as adhoc is concerned, an AI that knows how to play its own deck is a good start, but will probably not be enough as the AI cannot predict what the player will have in his own deck.
The way I see it, an algorithm such as minimax or alpha-beta is the best long term solution. Lots of efforts need to be put into it, but once it's done, it doesn't matter if the rules change or if new cards are added, which is great.
I spoke with one of the guys working on Incantus the other day on IRC. His expectations in terms of AI were far to high, and he tends to forget that we're not looking for perfection, we're looking for fun. That's probably why the guys at incantus decided not to do an AI.
@Willow, I like your idea of an AI which plays cards and then rates their results and uses this info in future games. I don't know how useful it would be in magic given that card play is based heavily on the game's situation, but after enough time I think the computer might learn enough to start surprising us.
Willow,
Deckbot does have the best approach, and seems to use a pretty simple board evaluation function to optimize the minimax traversal.
I think you mistook MageKing's musings on strong AI to be my position on AI for Incantus. The reason I'm not focusing on AI is that first i want to get the core rule engine finished, and then optimize it for minimax. The problem with minimax searching is that building the tree requires simulating the game, which either involves a lot of copying of game state, or an undo facility. Copying in python is really slow, and a friend who is implementing an AI version of Dreamblade (another WotC collectible game, but with miniatures) found a 100-fold speedup in the search when he ported his code from python to C++. I'd rather have a rules correct engine than an AI, since the basic minimax is really simple (the difficulty is optimizing it so you can search a few 100k nodes/sec). Also, unlike chess, the search tree is imbalanced, since it is possible to do many actions on your turn.
Gando - in your second post, the approach you say that chess programs use is the one I'm advocating. The rules engine just presents all possible moves to the AI, and the AI will search each one recursively (plus to optimizations like alpha-beta pruning). The benefit of this is that you don't have to program an AI for each card, which is the approach that MtGForge takes.
My musings on Strong AI were not at all related to the task of actually creating an AI for Incantus. They were just that... musings. I was attempting to point out that any AI we made would be inferior to a human unless it was a Strong AI (and therefore could meet or exceed human performance in all areas), which we won't have for a few decades more at least, by which point making an AI for Incantus will have become largely irrelevant.
As for actual AI coding, doing it card-by-card (the "hardcoded" way) probably produces the best results in the simplest way... the AI will always know what a card is capable of, but adding a new card can take forever, and it doesn't necessarily mean the AI will employ effective strategies.
The learning idea ("this card often allows my opponent to gain large amounts of life, so I should use this counterspell on it") is much better, despite the amount of time it will take for the AI to learn to be effective, because it more closely mirrors how a real player will learn (a real player will be augmented by knowledge given directly, I.E. "This card is rarely effective, so you'll want to save your counterspell for this much more powerful one he has", so the AI will inevitably be slower to pick things up, but if well-coded it could eventually match the performance of "low-level" players). It even allows you to pull tricks that normally only work on humans ("Oh, this card? Why, it hardly ever allows me to get a huge advantage. Look, it's barely having any effect at all. Your spells against it would just be a waste of effort."). On the other hand, you'd also want the AI to be able to be able to perform some kind of pattern-recognition/extrapolation logic, or they'd look at any card with an X cost and be horribly confused/take forever to build up a reliable "database" of knowledge about that card.
Personally, I'm allowed to ramble musings about Strong AI because I know that I won't ever need to do any AI coding. That doesn't mean Incantus won't ever have AI... it just means that if it has it, it won't be added by someone as inexperienced as me. ;)
Lots of good info here. I've implemented an AI for a game similar to MtG (Dreamblade, think MtG on a chess like board with miniatures instead of cards, awesome game!). I think incantus mentioned it above.
Anyway, I use minimax w/ AB pruning similar to Deckbot. I get *very* good performance in C++ (350-400k/nps), horrible performance in python (can eval about 1k/nps). I have some special code to handle the fact that there are a varying number of actions a player can take which makes evaluating the static state of the board "fair". My static evaluation function doesn't do much. I look at 3 things. Current victory points, conquest points (at the end of the turn whoever has more conquest gets a victory, 6 victory to win), and a static score for each spot on the board (relative to the player). This helps at lower depths. That's it. At high depths 15+ it does quite well.
Unlike MtG, Dreamblade is a game of perfect information so I do not have to deal with that. Everything else is pretty much the same. There are core rules and the abilities etc change the rules.
Given the scope of a game like MtG I'm not sure how you could model an AI any other way (except for maybe using minimax along with something like Monte Carlo).
I'd love to be proven wrong though. :)
~telengard
Cool, lots of good points !
And I also understand that the hope for an AI in Incantus is not dead, which makes my day !
Good luck to everyone who's working on an AI !
Im not sure I was 100% clear which irks me. I believe the game needs to have a rules engine that is 100% not based on particular cards. Each and everything a card can do should be a rule in the engine...so taking that into account with AI development for this game I hope the AI can evaluate not the specific cards in any one deck but as you said the capabilities of the deck being played as well as simulating on some level an understanding of how the AI deck should work optimally. (Note that I do not ever expect the computer to be consistantly better than me or even as good as me. That would be great but Im not holding my breath.) I just want to be able to play a game with it (no matter the format) and know there is a strong possibility of losing. (And not because of rules glitches or nasty bugs either.) I realise that for this to happen the game has to be smarter than it is.
I think if the phases are all installed and rules are strictly enforced the game will become that much more challenging.
Also the AI has to be able to play instant speed effects all the time...not just sporadically. It has to be able to respond to something simple happening with the following questions?
Can this event hurt me?
Can I prevent it?
can I sacrifice something to counter the effect? (Sac to Fallen Angel to avoid control magic for example.)
can I cast a spell which nullifies the effect? (Giant growth vs Lightning Bolt on a creature.)
can I counter the spell (if it is a spell) or ability (if it is an ability?
I know these are hard questions to answer and obviously the game isnt going to be always able to answer them correctly. But an attempt to do so is better than no attempt...Shandalar does try to some extent, though it is weak. Very occasionally playing that game I found myself surprised by a move the computer made (not counting the weirdnesses that let it do some very odd things indeed.)
Im confident that mtgrares will eventually figure out the answers to some of these questions as he loves the game and loves programming. I hope we can help him figure out how.
I feel almost positive the Shandalar AI had a "do a completely random move" routine, because that's the only way to explain some of its behavior... such as using Tawnos' Weaponry on one of my creatures for no reason whatsoever (it had literally no effect... neither deck had anything that cared about the power of that creature, it wasn't under threat of lethal damage, it wasn't even in combat).
On the plus side, making an AI using any of the aforementioned techniques would probably create one superior to the Shandalar AI, so we can take heart from that. ;)
Never played Shandalar, but I believe it had a limited set of cards and more than one programmer working on it.
The fact that the set of cards do not evolve allows for the kind of AI you're talking about, but for long term "add as much card as we can" systems such as MTG Forge, this becomes difficult.
For each new card you add, you have to update the AI, not only to take into account the new card, but how the AI should handle the OLD cards now that there is this possibility of this new card being in the game.
The five questions you think the AI should ask itself are, IMO, really difficult to solve, and need lot of extra information from the coder, for a result that will be, at best, acceptable.
I'm not saying this is not a good idea, but I'm pretty sure that you (the player) will find the limits of such an AI after a few games.
Basically, you have to keep in mind that a computer does not think. The best AIs just try all possibilities and choose the best. That's called minimax, and it works.
Willow you havent said anything I disagree with though I might quibble with your syntax :)
My blogs about the AI always gets the most number of comments. Thanks for everyone input. Basically we all know that writing any AI is hard and writing a good AI is extra hard.
Thanks for the general praise also. Magic is fun and MTG Forge is fun.
Hopefully version 2 with have a some version of alpha-beta pruning. The hard part is making actions "undo-able" so that the AI can look ahead and then reset the game state.
good luck, I wanted to add an undo feature to my code, but currently that would take too much time and it wouldn't be that fun... so I gave up and will go with a basic stupid AI for the moment.
Well in order to use a search algorithm for the AI like alpha-beta pruning you have to have an "undo."
what the deck works like is maybe hard... that's 60 cards to "think of" at the same time. I hope that something like "i have 60 life, so test of endurance would be good now." is possible.
test of endurance is an enchantment that only has a triggered ability, so it doesn't really do anything to the board what i think is easily spotted by the AI.
maybe doran is similar. you can say he's a 5/5 or so, but it's not so easy to see for the AI. say you evaluate the board by summing the power of creatures. this makes your results very odd. the right way would be to sum up the "potential combat damage", which may be tricky.
generally, effects that change the rules in an unusual way are tricky to evaluate, because the evaluation function relies on "expert knowledge". and minimax helps only when you either play games to the end (very consumptive) or evaluate the state after a few iterations to see what the best move is.
Post a Comment