Archived

This topic is now archived and is closed to further replies.

Genetic programming applied to games

This topic is 5624 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
I must admit not understanding what your program snippet there does.

Personally I haven''t found much use in genetic algorithms in actual gameplay. A couple of potential uses that seem like they''d work but which I haven''t tested myself include optimising the search heuristic for A* across a given map, quickly (this would be done before the game starts), and picking the weapon/angle/velocity for a Worms-style game (because exhaustively searching every weapon, every angle and every velocity would take forever.)

The problem I come across generally is that unless the problem domain is many-dimensional or continuous, you can just do a brute-force search with greater accuracy, a negligible performance penalty, and reduced development time. I''d love to see some more ideas on practical applications in the gaming world where these issues aren''t true.

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

Share this post


Link to post
Share on other sites
In theory, if you can break down an AI into a variety of distinct steps - but are unsure as to what order they should go in, you can run many itterations beginning with a random order of those steps. The ones that come out on top, you keep and reshuffle with a GA. After a while, you will have kept ones that have a prefered order to those steps. You would then use those orders for your steps to actually create the AI.

Also, in theory, this could be used as in the box AI... but there are so many rounds that would need to be run that the AI would look/feel really stupid until you manage to cull out the crap. In many cases, it is just as easy to create the scripts with human observation and decisions rather than letting things sort themselves out through GAs.

Of course, a big deciding factor would be how complex the situation is. GAs may, by not really searching down a pre-conceived notion, come up with something new and different that a human AI scripter may miss.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"
RIPPL Sports - NFL Statistical Analysis and Prediction System

Share this post


Link to post
Share on other sites
I''ve been reading An Introduction to Genetic Algorithms by Melanie Mitchell (heartily recommended to any and all interested parties) and the general consensus (here as well) seems to be that GAs are best suited to extremely large search spaces where exhaustive methods would take too long so a few (pseudo) random elements are selected and tested for fitness and those above a certain cutoff are "crossed". In considering AI for games, GAs seem a pretty bad choice for the action/reflex variety, though plausible for highly mathematical/logical/strategic games like chess or a turn-based RTS.

For games with soft real-time constraints, however, other methods would appear better choices. There was a recent thread (started by Magmai Kai Holmlor, IIRC) about creating an "AITL" - an Artificial Intelligence Template Library containing generic routines for performing and aggregating those tasks most routinely performed in AI, specifically game AI. There was some interest expressed, but it appears that the field is still too non-concrete for proper, widely applicable abstraction to occur.

Share this post


Link to post
Share on other sites
Ok, I''ll clarify a few things. First of all, I''m not sure everybody knows what I''m talking about. I''m talking about this:

http://www.genetic-programming.com/gpanimatedtutorial.html

Essentially, GP creates random programs (instead of using random values and trying to find the best combinations as in traditional GAs).

I haven''t really read about it except for the link above, but I have given it a lot of thought. Instead of having numerical inputs and outputs like in an ANN, I would like to ''feed'' functions to the Genetical Programming algorithm. Some functions are ''observing'' the environment (input), while some others are ''actions'' (output). Plus, there are plenty of basic functions (if-else, or, and, addition, multiplication, etc.).

All these functions are part of a function pool, and they are numbered. The GP algorithm creates a random program out of them, by interpreting the given DNA. The DNA is then evolved using classical GA algorithms.

Cédric

Share this post


Link to post
Share on other sites
I think that is rather what I was talking about. The sequences are really functions that can be ordered in a variety of ways. So really, you are just deciding the best way to order your actions (program). In a way, it''s just an automated way of writing the "best" AI script.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"
RIPPL Sports - NFL Statistical Analysis and Prediction System

Share this post


Link to post
Share on other sites
The problem you're running into here is the distinction between Genetic Programming and Genetic Algorithms. Essentially, GAs reduce a problem to a string (typically a bit string, but not necessarily) which can be recombined and mutated to still produce a logical interpretation. GP on the other hand is all about building logical procedures. The best example of this is to consider a tree structure for mathematical equations or decision structures.

What you suggest sounds like a good idea, and actually GDMag has an article from way back in which someone developed an RPG AI using this type of approach. I think his approach was based on a RISK-type game in which the actions were built up from an Assembly Language type set. He used GP to construct the AIs actions and ran various members of the population against each other for selection, etc. There's another article in which someone used GP for spacecraft control. I'll look them up and give you the references. I've also see GP used for the snake game on cell phones. The biggest hurdle that you'll face is making certain that whatever rule system you evolve must make sense. This is more than trivial, but not outside the realm of possible.

I personally am hoping to start working on a Pac-Man clone in which the movements of the ghosts are evolved over time. I'd like to also co-evolve a Pac-Man at the same time and see what types of behaviors emerge. There are a number of good inputs to consider here - are the ghosts aware of each other? Do they have a knowledge of PacMan's velocity as well as position, etc. Fun stuff!!

-Kirk

[edited by - KirkD on July 23, 2002 3:54:40 PM]

Share this post


Link to post
Share on other sites
[Edit: In response to InnocuousFox]
Yes, but then I have a few comments/questions:
quote:
Original post by InnocuousFox
In theory, if you can break down an AI into a variety of distinct steps - but are unsure as to what order they should go in, you can run many itterations beginning with a random order of those steps. The ones that come out on top, you keep and reshuffle with a GA. After a while, you will have kept ones that have a prefered order to those steps. You would then use those orders for your steps to actually create the AI.

Can we say that any program is just a collection of ordered statements? According to the link I provided (and what I would like to do), there is more structure than there is in a simple script.
quote:
Also, in theory, this could be used as in the box AI... but there are so many rounds that would need to be run that the AI would look/feel really stupid until you manage to cull out the crap. In many cases, it is just as easy to create the scripts with human observation and decisions rather than letting things sort themselves out through GAs.

I don't understand this comment (not a native english speaker). So many rounds?

One idea that I have is to take the time it takes to run the AI into account in the fitness function. If the GP is too slow, kill it and let the more efficient GPs survive. Hence, it could be used in action/oriented games.

In fact, the way I see it, my GPs would perform very poorly in complex games like chess, but it could be good in situations where the input is limited, and easily represented.

Cédric

[continued]
quote:
Original post by Kirkd
I personally am hoping to start working on a Pac-Man clone in which the movements of the ghosts are evolved over time. I'd like to also co-evolve a Pac-Man at the same time and see what types of behaviors emerge. There are a number of good inputs to consider here - are the ghosts aware of each other? Do they have a knowledge of PacMan's velocity as well as position, etc. Fun stuff!!


Man, I had the exact same idea! And each ghost's DNA could be evolved independently, so that they acquire slightly different strategies when they realize they can't compete with the best ghost!

Oh, the fun!

[edited by - cedricl on July 23, 2002 4:08:14 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by cedricl
Man, I had the exact same idea! And each ghost''s DNA could be evolved independently, so that they acquire slightly different strategies when they realize they can''t compete with the best ghost!

Oh, the fun!




Ah, yes, fun indeed. My thoughts on the Pac-Man ghosts was not so much the best possible ghost but the possible emergence of teamwork between the ghosts. Presumably, the best ghost will take the shortest route to the Pac-Man in a dynamic manner, changing its tragectory according to how the Pac-Man is moving. But, with knowledge of the other ghosts, I wonder if there would be modifications such that the Pac-Man could be trapped by two or more ghosts. Interesting theory, but everything works in theory.

As for the GDMag articles, I didn''t have a chance to look them up last night. I''ll try again tonight. In the mean time, here''s a link to the Snake Game application I mentioned before. And, no surprise, it''s right here on GameDev. Nice work guys!!

http://www.gamedev.net/reference/programming/features/gpsnake/

quote:
Original post by kirkd
Ah, yes, fun indeed. My thoughts on the Pac-Man ghosts was not so much the best possible ghost but the possible emergence of teamwork between the ghosts. Presumably, the best ghost will take the shortest route to the Pac-Man in a dynamic manner, changing its tragectory according to how the Pac-Man is moving. But, with knowledge of the other ghosts, I wonder if there would be modifications such that the Pac-Man could be trapped by two or more ghosts. Interesting theory, but everything works in theory.

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?)
quote:
As for the GDMag articles, I didn''t have a chance to look them up last night. I''ll try again tonight. In the mean time, here''s a link to the Snake Game application I mentioned before. And, no surprise, it''s right here on GameDev. Nice work guys!!


Nice! Very interesting, especially how they chose their functions. I was disappointed that they didn''t really speak about their genetic operators, though. That''s my biggest concern right now. Until now, I only used mutations as if the DNA was a string of int, whereas the link I gave above suggested evolving the GP by taking its structure into account.

Cédric

Share this post


Link to post
Share on other sites
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 ]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites