Genetic programming applied to games

Cedric · 2002-07-26T09:53:09

Hey! For a while, I've been thinking about applying genetic programming to game AI. I didn't know it was called genetic programming, but now that I do, I took a look around AI-Depot and didn't see much about Genetic Programming. Why isn't it used? I think the fitness function is quite easy to find in most games. Wouldn't it be an efficient way to generate AI? I'm working on a library that could allow such genetic programs to be created relatively easily. However, I'm still unsure about the interface, so if you could take a look at the following code: typedef int DNABASE; class Hunter:public AnimalWrapper<DNABASE, Hunter>{ public: FLOAT posx, posy; void Move(float dx, float dy); bool LookForEnnemy(float dx, float dy); }; void PlayHunter(){ AnimalFactory<DNABASE, Hunter> HunterFactory; AnimalManager<DNABASE, Hunter> HunterManager(HunterFactory, 0.30f); HunterFactory.RegisterBasicFunctions(); //IF-ELSE, AND, OR, ... HunterFactory.RegisterObservation<bool, float, float, &Hunter::LookForEnnemy, DNANOCONV<DNABASE, float>, DNANOCONV<DNABASE, float> >(); HunterFactory.RegisterAction<float, float, &Hunter::Move, DNANOCONV<DNABASE, float>, DNANOCONV<DNABASE, float> >(); //Game Loop while(true){ Hunter *h = HunterManager.GetNextAnimal(); h->CallIntelligence(); h->CallBestAction(); h->SetFoodLevel(FitnessFunction()); ... } } I know the templated functions is not an ideal interface, and I'm working on that, but AFAIK, it's the fastest way I can make it. Each 'instruction' in my virtual program involves one virtual call. Adding another level of indirection would be slower. The design is centered around an AnimalFactory, that can interpret DNA to create an animal, and an optional AnimalManager, that takes care of all the mutations, reproduction and everything. Users query for the next candidate with the function GetNextAnimal(), and they assign it a score with the function 'SetFoodLevel()'. If my design is flawed, or this concept will never work, I'd rather have some comments now. Currently, my program does create random AI, but I have to work on the genetic operators if I hope to get something significant at the end. Cédric [edited by - cedricl on July 23, 2002 11:58:20 AM]

Artificial Intelligence Programming

Started by Cedric July 23, 2002 10:46 AM

15 comments, last by Cedric 21 years, 9 months ago

Kylotan

10,510

July 24, 2002 04:38 PM

quote:Original post by cedricl
I think the velocity of Pac-Man shouldn''t be taken into account, because he can change it at every game cycle (I didn''t play PM much; he can turn around, can he?)

Surely one of the benefits of approaches like genetic algorithms (and neural nets) is that you give the algorithm as much information as it needs, and let it make the decision on what needs to be taken into account and what does not? You may find it makes a useful correlation that you missed.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

Dreddnafious Maelstrom

586

July 24, 2002 06:22 PM

a couple of things.

1) feel free to "pre-develop" your GA during testing to have a "out of the box" AI that doesn''t slowly spin in circles waiting to get smoked. (save your dna sequence and begin with a competent agent)

2) feel free to combine your state machine, along with heavy use of flags or switches to be sure that your agent will have "context" for any situation it will be required to address.

3) feel free to "flag" recent mutations to attempt to isolate perfomance affecting enhancements.

4) don''t be afraid to "cheat" when it comes to evolution.

5) Store your best mutations in a "mother-brain". you''ll often find that what you feel are successful mutations are "stamped out" by your imperfect logic set.

6) Experiment with a "quid pro quo", map the players keys and isolate it as a set of actions. Generate a score based on the agents response, with the most successful responses garnishing the highest scores. Take into account ALL pertinent info, including environment(range, weapons, current health, whatever) and the generation of the agent.

Yeah, i know, a bit philosophical and not a line of code, i''ve implemented several of these into an ANT colony, it''s not perfect but is coming along nicely, i use GA and NN(mostly GA)

I should probably include this into my signature but my favorite quote is "If I saw farther, it was because I stood on the shoulders of giants" by Sir Isaac Newton. Basically saying that without those that came before, he would have never accomplished the things he did. GA uses this very process to develop intelligent agents, but don''t be afraid to send your agents to college before turning them out into whatever harsh environment you will use them in.

"Let Us Now Try Liberty"-- Frederick Bastiat

Cedric

158

Author

July 24, 2002 11:02 PM

quote:Original post by Kylotan
Surely one of the benefits of approaches like genetic algorithms (and neural nets) is that you give the algorithm as much information as it needs, and let it make the decision on what needs to be taken into account and what does not? You may find it makes a useful correlation that you missed.

Good point. My idea was to remove as much ''unnecessary functions'' as possible, but these may actually help the ghosts.

quote:1) feel free to "pre-develop" your GA during testing to have a "out of the box" AI that doesn''t slowly spin in circles waiting to get smoked. (save your dna sequence and begin with a competent agent)

I don''t think GAs and GPs should be limited to online learning. In fact, I feel on-line learning may do very stupid things, because it''s so easy to ''break'' the logic structure of a GP. Much moreso than a regular GA.

quote:3) feel free to "flag" recent mutations to attempt to isolate perfomance affecting enhancements.

4) don''t be afraid to "cheat" when it comes to evolution.

I feel rather bad about cheating. It''s a lot of work with the genetic operators, and it assumes that I know better than random decision-making. Kind of like "If I had built the human body from the ground-up, it would be a lot better."

Thanks for your suggestions.

Until now, I''ve been mostly concerned with the user interface and the core of the "AnimalFactory". Different games have very different needs. For example, in a Tic-Tac-Toe game, you are only allowed to do one move and even if the AI spent a minute thinking about it, it''s no big deal, but in a racing game, you can break/turn right at the same time, and the speed of the AI is rather important.

I think the interface could quite easily provide support for ANNs too, which is another interesting avenue.

My biggest preoccupation right now is definitely evolving those GPs. I really like the idea that I can read any random sequence of bits and make a program out of it, but it prevents me from evolving it as a structured program, rather than as a sequence of bits...

And then, there is the problem of building test cases. Creating a Pac-Man clone doesn''t take months, but it''s still not something I''ll do in an hour. And I''d have to create plenty of games like that to really determine how my library should be designed.

Cédric

Dobbs

164

July 25, 2002 05:15 PM

quote:Original post by kirkd
There''s another article in which someone used GP for spacecraft control.

Is this it? It''s a paper by a guy at Lockheed about using GP to develop spacecraft control systems.

kirkd

505

July 25, 2002 05:23 PM

First off, I'll agree with Kylotan that the velocity of the Pac-Man may not seem to add to the system inuitively, but you might be surprised what the evolved logic comes up with.

As for the idea of cheating, I think the idea that Kylotan was suggesting is to start with a ghost (to continue with the Pac-Man example) that does something logical - perhaps a direct chase - and evolve from there as opposed to starting with a totally random ghost. While the totally random start will likely evolve to something useful, it may take a while.

Another point to make is related to your statement:

quote:My biggest preoccupation right now is definitely evolving those GPs. I really like the idea that I can read any random sequence of bits and make a program out of it, but it prevents me from evolving it as a structured program, rather than as a sequence of bits

Remember that Genetic Programming is different from Genetic Algorithms. If you can represent your decision structure as a tree (such as a LISP tree), you can very easily enforce viability rules and do all the evolutionary computation you want.

Last of all, here are the references I promised:

How to Grow A Starship Pilot, Stephen D. Wilson, GDMag Premier Issue (!!), page 51.

Using Genetic Algorithms to Evolve Computer Opponents, Dan O'Brien, GDMag Feb/Mar 1996, page 26.

The second of these may be exactly the example you're looking for in your original post. Of course, I'd be a fool if I didn't recommend Koza's first book for this topic.

[edited by - KirkD on July 25, 2002 6:25:05 PM]

[edited by - KirkD on July 25, 2002 6:31:43 PM]

Cedric

158

Author

July 26, 2002 08:56 AM

quote:Original post by kirkd
As for the idea of cheating, I think the idea that Kylotan was suggesting is to start with a ghost (to continue with the Pac-Man example) that does something logical - perhaps a direct chase - and evolve from there as opposed to starting with a totally random ghost. While the totally random start will likely evolve to something useful, it may take a while.

First, that wasn''t Kylotan''s idea, it was Maelstrom''s. Writing DNA manually would be a very daunting task right now, but maybe...

quote:Remember that Genetic Programming is different from Genetic Algorithms. If you can represent your decision structure as a tree (such as a LISP tree), you can very easily enforce viability rules and do all the evolutionary computation you want.

Like I said, I didn''t know about GP until a week ago, and I didn''t know about GAs four months ago either. These are ideas I developped on my own, so there are bounds to be stupid things.

But I''ll see if building (and storing) a tree-like structure is a possible alternative. It would certainly allow me to apply more interesting operators.

quote:How to Grow A Starship Pilot, Stephen D. Wilson, GDMag Premier Issue (!!), page 51.

Using Genetic Algorithms to Evolve Computer Opponents, Dan O''Brien, GDMag Feb/Mar 1996, page 26.

The second of these may be exactly the example you''re looking for in your original post. Of course, I''d be a fool if I didn''t recommend Koza''s first book for this topic.

Thanks! I don''t know where I''ll get those GDMags (without buying the whole compilations), but I''ll look for Koza''s book.

Cédric

kirkd

505

July 26, 2002 09:53 AM

My apologies to both Kylotan and Maelstrom - my mistake.

Don''t worry about mistakes. We all make them sooner or later. 8^)

I''ll be in touch by other means to see if we can get you the GDMag articles.

-Kirk

Genetic programming applied to games

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Genetic programming applied to games

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines