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());
...
}
}
Genetic programming applied to games
July 23, 2002 10:46 AM
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:
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]
July 23, 2002 02:03 PM
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 ]
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 ]
July 23, 2002 02:11 PM
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
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
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play
"Reducing the world to mathematical equations!"
2,123
July 23, 2002 02:26 PM
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.
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.
July 23, 2002 02:34 PM
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
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
July 23, 2002 02:44 PM
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
Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
RIPPL Sports - NFL Statistical Analysis and Prediction System
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play
"Reducing the world to mathematical equations!"
505
July 23, 2002 02:53 PM
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]
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]
July 23, 2002 03:01 PM
[Edit: In response to InnocuousFox]
Yes, but then I have a few comments/questions:
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.
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]
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]
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]
505
July 24, 2002 07:14 AM
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/
July 24, 2002 08:08 AM
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
