#### Archived

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

# Genetic programming applied to games

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

## 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 on other sites

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 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 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 on other sites

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 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 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 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 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

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5

• 13
• 19
• 14
• 9
• 9
• ### Forum Statistics

• Total Topics
632931
• Total Posts
3009292
• ### Who's Online (See full list)

There are no registered users currently online

×