Monday, November 10, 2008

AI Thoughts – Genetic Algorithms and Neural Networks

AI (artificial intelligence) is a great subject so I thought I would discuss what little I know about it. Let me first tell you a little about my educational background, I have my bachelor’s in Information Science and I didn’t take any AI classes in college. My knowledge about AI comes from miscellaneous web articles and the three random books I have own the subject.

AI encompasses a huge number of topics ranging from getting a computer to drive a car to trying to find fraudulent credit card charges. There are many different types of AI algorithms and techniques. Some techniques require a vast amount of historical data while others do not. Videogame AI usually has to be fast, to simulate the response of a real human. In my opinion most videogames have only a very basic AI. Many videogames like Mario don’t have any AI and it is just the player versus the environment.

People sometimes talk about neural networks or genetic algorithms but they don’t usually work well for videogames. Neural networks usually have many inputs and only one output. They are typically used to output an answer like yes or no. Neural networks are also very complicated to setup and test.

Genetic algorithms find an optimal or near-optimal solution to a problem by generating random actions. Granted the problem could be “how to win a game of Magic” but encoding a game of Magic into a genetic algorithm would be extremely difficult. Usually genetic algorithms are encoded as strings, although this is not a requirement. The strings are split and combined to form new strings. Each string is evaluated until a solution is found.

Join me next time as I continue our journey into AI.

10 comments:

Forge said...

Hm..no comments, maybe I've confused too many people, lol.

bob said...

I have studied AI at Uni (only to undergraduate level) covering both ANN and GA methods.

While an interesting post, I am struggling to see the point exactly.

Just for kicks you may want to consider using a GA to optimise an ANN - very lazy method to get a network (or network topology) that works.

Forge said...

The only point is that AI is hard, thats all.

WilLoW :--) said...

I was talking in one of your previous posts about an AI that would remember which cards "hurt" it. Therefore the AI would "adapt" to your deck.
This is completely adhoc, but I implemented a basic version of this in the current version of my game, and it gives interesting results. Overall it feels like the AI is seeking revenge, mainly targeting the cards that did the most damage during previous games.
There is a multiplier if the cards do damage directly to the AI. so if you have flying creatures but the AI doesn't, you'll make lots of direct damage to the AI with these creatures, therefore these flying creatures will be more and more likely to get hit by a lightning bolt or whatever the AI can play against them :)
I also added some indirect parameters. for example, if an Aura is attached to a card that does lots of damage, the AI tends to think that the Aura might be the cause (and will therefore try to destroy this aura when possible).

There are still lots of flaws in this system (how about enchantments, how about deckmill decks, etc...), but it gives some interesting results. For example, the AI doesn't give a chance to my black vise anymore, and tends to destroy it as soon as it is in play :p

Anonymous said...

I just got to say game AI is not as hard as you make it out to be.

Admittedly, we won’t be seeing a computer matching human intelligence any time soon, but (to take a layman’s approach) just think of all the computer games on the shelves right now, most (if not all) employ some sort of artificial intelligence and the fast majority of these are quite sophisticated.

Now I know I will be flamed and told if I can do it better I should go right ahead and do it. But this is not the point I am trying to make, I am not claiming to be an AI expert, but you clearly are also not one.

Perhaps you should try to do a bit more research. Sometimes these postings remind me of the notorious "Indian" codeproject contributions...

Gando the Wandering Fool said...

twasnt confusing in the least...however since I was visiting my Dad's I didnt check your blog. Nor do I feel that comment on this subject is particularly needful. It seemed more about filling space than communicating something to us about MTG Forge which is what I am watching this blog for.

Now onto mr Anny Mouse..if you HAVE something constructive to say (and I think you do) why hide? Show us who you are? Or whom you'd like to be...that way we know its you and not an imposter. As far as flaming goes, that seems rather counter productive but your comment does beg the question...why not contribute something real?

Forge said...

Willow,

"Therefore the AI would "adapt" to your deck.
This is completely adhoc, but I implemented a basic version of this in the current version of my game, and it gives interesting results."

Very cool, at least it seems like the AI has a game plan. Even simple game planning would boost the computer's IQ.

juzamjedi said...

Hello,

I have never programmed AI myself although have done some simple programming as a hobby. I can definitely see a few ways to improve the AI in MTG Forge:

Blocking
- Computer rarely blocks even when it has extra blockers
- Computer seems to randomly select which blocker to use against an attacker instead of comparing attack / defense

*Potential* stats vs. current stats
- Many creatures can get pumped up, but computer fails to utilize
- Cards in hand (Giant Growth, etc.) that can pump up the critter

Drafting
- I find that the rare lands (Bayou, etc.) are almost never selected by computer. But these lands are wicked awesome especially in this format where you rely on multiple colors of magic.

Also I read your note that computer cannot play some (any?) cards on human turn. This is a major disadvantage to computer and needs to be fixed!

I could maybe see how an ANN could be set up to refine the AI. But honestly there are some simple heuristic changes like these and some others that would really help the AI a lot!

aimyaya said...

I was using GA for TSP during finishing my final test project on 2003. But right now, GA only becoming another hobby to me, because I don't have much time to exploring it anymore.. :(

Randy said...

I'm a teacher and I'm interested in learning about computer science even though that doesn't have to do with anything I teach, but I want that as a complement. Today on my way to my job I found a brochure about computer courses and also said something concerning Generic Viagra