Artificial Intelligence (AI) is an infinitely, complicated subject. Much like the hole that Alice in Wonderland fell down, “How deep do you want to go?” AI requires a specific area in which to function. Relating to videogames, an AI that simulates driving a car is different that an AI that plays tennis. In order to program a decent AI you have to understand the problem (trying to drive a car or play tennis) and be able to program that logic into the computer.There are many problems when trying to adapt AI routines to MTG Forge. One, MTG Forge’s architecture does not support different AI algorithms. I can’t simply apply min-max and get a better/different AI. (The initial problem I had when trying to apply min-max and other “look ahead” algorithms is that I had an impossible task for copying all of the game data. In theory copying everything is simple, but in practice it is very hard.)
Min-max is an algorithm for two player games that allows the computer to maximize his turn while minimizing his opponent’s. Min-max should be able to answer questions like, “Which creatures should the computer attack with?” but programming it can be very complicated.
Two, even if MTG Forge’s architecture supported different pluggable AI’s they would probably be very complicated. Obviously there could be some “helper” functions so that the new AI wouldn’t have to write everything from scratch. Maybe trying to develop an AI interface for just combat would be a good first step. Creature combat is simple enough to understand and yet complicated enough to be tough. Just answering the question, “When should the computer race?” is hard. (Racing is when you attack each other back and forth.)
I love the idea of AI even though I only know a tiny bit about it. I do know about genetic algorithms and a few other AI algorithms like random hill climbing. I’ve tried to apply min-max to combat, but it is pretty complicated. I like the idea of giving the computer simple plans like “Destroy that big creature” or “Attack and then bounce my creature.” I think even these simple plans would give the AI more depth and personality.
p.s.
As a side note, not all videogames have sophisticated AI routines. Mario’s enemies tend to be basically brain-dead.
I wonder - would stochastic reasoning work? I.e., in cases when the turn, combat etc. are very complicated, simply play, say, 10,000 turns randomly from the same initial state, and check which action tends to lead to the best results.
ReplyDeleteThat works fine for a game where the options are finite, like say chess. But for something like Magic, where the AI wouldn't (well, shouldn't... the computer COULD cheat and iterate through the cards in the human's hand and library...) have a clue what cards the human can/will be playing. It takes long enough for it to determine attackers as it is... sometimes it sits for 20 - 30 seconds as soon as the computer's turn starts. Imagine trying to iterate through the millions of combinations of the 500 card vocabulary of MTG Forge....
ReplyDeleteIn other news, the computer went to the trouble of pumping up a Ghost Warden, (auto gen deck g/w with Timberwatch Elves, and I was playing green elf-pump, so it was a huge beater...) and then proceeded to tap it to pump an attacker... made no sense.
ReplyDeleteHmm.. what would it be like, if your AI would known better deck that it play with (aggressive, speller, card discarder...)
ReplyDeleteEg. When you play first time with deck that you don't know, you can't be as good as when you play with it second time... and then third time ... But when you would know your deck type, you could play better. So every deck would "know" what type it is. With this in mind AI could find key cards for other deck type. So there would be different strategy for different opponents type. Eg. If AI would play against black deck, it would play first key cards which would be more useful against black opponent (creatures that has protection from black, Black ward, COP:Black, Cleanse, Karma...) if opponents deck would be green, then strategy would change.. and from all cards in hand you would first play those with protection from green...
Main point: your AI should somehow define (or gues) opponent deck type, and then first play cards with greater impact on that deck type. How could that be done?
1. Define some deck type - more is better (maybe even subtypes)
types:
green,
black,
white,
blue,
red,
subtypes:
RED-a lot of spells,
RED-a lot of big creatures,
RED-a lot of small creatures,
BLUE-creatures
BLUE-a lot of spells
BLACK-land destroyer
BLACK-regenerate
......and so on.
2.You should than "train" your AI against those decks. So you would choose some decks that would fit into one type (let's say RED-a lot of spells) You would than tell the AI that those decks are RED-a lot of spells. And AI would then iterate some (100) games against those deck types. Cards that would do best against those decks would be marked as key cards against "RED-alot of spells" type opponent. AI should done this with as much decks as possible, for as many types.
How would AI knows whitch card is good against one type of deck?
AI could simple look for cards that were used in a game when AI won. You can also put a priority on them.
Eg. If one card was in every game when AI won, than that card could be very important for this kind of opponent deck type. And so on for other cards.
The problem that AI would have to solve is Which deck type opponent has.
How could that be done... hmmm
I don't know. You should find that out.
But if AI would guesed correctly it would firstly use key cards for this opponent with the highest priority that AI could afford (mana).
I don't know if this solution is good enough, but maybe its worth trying.
Nastyboy
IF you are interested in a working MTG application with Minimax AI, visit http://webpages.charter.net/leowong/
ReplyDelete