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 ]

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.

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

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.

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]

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

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