Hello, I am very interest in using gentic programming for AI, specifically in an RTS I''m making. One idea that I''m having a hard time figuring out is how to make it so that the computer genertaed code actually does stuff. Lets say that the program or script the GA needs to create only has functions in it, which don''t have any variables passed to them. This is easy, just change the order of the functions... maybe swap one or two, insert one here or there, get rid of one... I encounter problems when the functions accept arguments. How can I be sure that the values passed to it are valid? will it not take a long time before the GA randomly produces runable code? I''m thinking that maybe the solution is to never have any arguments or only constants or something.... Basically, how can we program the GA so that the code it creates actually runs? how about getting that code to do what we want it to do?! Thanx a lot! Tazzel3d ~ Dwiel

The best way to think of this is as a strong typed language, and consider how LISP functions. You have to divide your primitives into two classes: functions and terminals. In the simplest scenario, all functions accept parameters of and return the same basic type which is the same as all of the terminals.

Think about a basic equation, say x * y + z. The functions are the operators and the terminals are the variables. All operators accept two variables and return one variable all of which are floating point numbers, for example. Using the LISP parse tree structure, you could construct this function as follows:

      +     |  |    *   z   |  |     x    y  

Also, most GP implementations have a portion in which the constructed program is evaluated to verify that it is valid. Invalid ones are discarded. This is not too difficult to do if you enforce strong typing rules.

I hope this makes sense. I'm sure you'll get other suggestions as well as there are a number of very talented people that read this board.

-Kirk




<

[edited by - KirkD on February 5, 2003 9:18:14 AM]

Now that I''m understanding how this all works, I''m tring to figure out how to have the programms generated so that algorithms are actually created instead of modified. What if lets say a Genetic program has found a relatively good solution to the problem, but there exists a much better solution which is much different than the current algo. The chances that this new very different algorithm is created randomly based on the old one is very low. Is it not? How do the programms generating the genetic programms get around this or do they not?

Thanx for the help!

Tazzel3d ~ Dwiel

you start off with an initial population of from 10 to several 1000 individuals. Then it''s all a matter of tweaking and technique to converge upon a solution whilst retaining genetic diversity.





ai-junkie.com

Remember also that from you population of 10 to 1000, you''re choosing members of the population for breeding (crossover) and/or mutation. This process of modification provides your search and optimization.

You may start with 10 organisms that do a terrible job of what you''re trying to accomplish, but your banking on the assumption that through random modifications (crossover and mutation) you''ll eventually hit upon one or more that do a better than terrible job. Most likely, due to the randomness of it all, their performances will be for different reasons. At some stage their pieces may be combined to produce a much better than terrible job, etc. etc.

Also, fup mentioned "retaining genetic diversity" and this is very important. It is all too easy to apply too much selection pressure and end up with a population of poor performers that all look alike. Keep that in mind from the start and you''ll be much better off.

-Kirk

I don''t think there is any one right answer to your question. Here are some things you could try though:

Simplicity. The less your GA''s have to discover, the sooner you''ll get results. Try to strucutre your scripting language so that its really hard to make mistakes that can cause catastrophic failure. Anything that can be ''assumed'' should be. ie) in tic-tac-toe, there are only 9 squares. Never let a GA''s code try to output square be less than 0, or greater than 8. That saves your GA''s from ''learning'' that there are only 9 squares.

You could ''kick-start'' your GA population as well. Write your own solution(s) to the problem in your scripting language. It doesn''t have to be perfect. Use this as the starting code for your GA''s. This way, they have something to work from. To make it easier for the GA processes to modify your code add a lot of ''NULL'' insrtructions. A null instruction is one that doesn''t do anything.

ie:

null
null
a = a
null
null
+
null
1
null
null
null
*
null
null
2
null
null
end
null
null
null


In this way, you can get modifications that: a) do nothing, b) modify something, and c) replace something, all without any ''special'' code on your part. Luck of the draw.

Your question about ''new'' solutions -vs- already discovered ones:

There are different ways to approach this. One way to is too keep multiple ''gene pools''. Instead of just having 1 large population, split it in to 2 or more populations. Every so often, take the top performers from each population and mix them with the others. This way, your program will always be exploring a few different solutions. You can have the fitness / crossover / mutation rules different in each gene pool.

Something else you might want to try is regression. You can have your fitness rules change over time based on statistics you glean from the populations growth.

ie: say the population stops ''discovering'' things and it''s score stabelizes for 200 generations. Stop keeping the best algorithm, instead only keep the best ''offspring'' of the best algorithm. Do this for n generations. Each time the score stabelizes within the n generations of regression, increase the mutation rate again. The score for the population will actually get lower, but the hope is that they will have unlearned whatever it was that got them stuck.

These are just some ideas. Nothing written in stone. Fup''s website has all kinds of good info on GA''s.

I''d love to hear more about your progress . Please post some status reports.

Cheers,
Will

Thanx for the ideas. What I''m doing right now I think will help a lot. Here''s my concept plan:

I am making an RTS game. The AI is a vey important part and I therefor would like it to be very intelligent. I am splitting the AI into modules similar to the way most organizations/governments are split up. I will have a ruler which makes all of the basic decisions which are then passed down to people(AI scripts) that can make more informed descisions and worry them selfs with information that should not be bothering the ruler. One such AI script will be a bugeter. the bugeter will be given the current and long term importance of certains things that the ruler palns on doing. Some examples are defensive current. This will hold a relative value to how much defensive tactics should be invested in now. a corrisponding defensive longterm value will also exist which will be based on what the ruler PLANS on doing in the future. Because the RTS is mostly based on war/battles, that will be a major part. My plan is to have the ruler give a command such as attack enemy #n''s base now. That will go to a commander. The commander will make descisions about what needs to happen for the base attack to work. Such a descision might include an attack on a large out-post. this command goes to a lower commander. This commander then notices that there is a large tank guarding the out-post which must be taken care of before the out-post can be taken. He gives this command to another officer. that officer then goes ahead and attacks the tank... all of the other palans the preced.

each officer or government role will be played by a different GP. Does this sound like a feasable/good idea?

What are your thoughts?

Tazzel3d ~ Dwiel

Modularization is probably a very good idea, but it will increase the complexity of the system and make it harder to find solutions. Consider your ruler-commander relationship. Each agent will need to evolve independent of the other, so in this case you have two GP processes going on simultaneously. The hope is that you have a cooperative evolution such that the two solutions, while independent, work very well together.

I would say that such a system would be very impressive and quite powerful. It might even be an interesting study for emergent behaviors. It will be complex, but certainly interesting.

I also think it sounds like you''ve given this some thought and aren''t jumping into GP blind. That in itself is a huge step in the right direction.

I would strongly recommend checking out AI-Depot, AI Junkie, and GameAI. There are lots of knowledgable people in the forums that are always willing to help. Also, check out Mat Buckland''s book AI Techniques for Game Programming - he''s the brains behind AI Junkie. There is a wealth of information there realted to Evolutionary Computation which you might be able to apply to your system.

-Kirk

Why do you say that making the AI modular would make everything more complex? It seems to me like it would make it more laid out and easy to understand. It also seems that this way, I can give certain AI moduals only the variables and functions that they will possibly need to complete the task. THis should speed up the procces. If it was all one big module, it would have to guess at what variables are needed when. There would be a lot of uselessness going around. I think that this way, I might be able to rate each module on how well it''s doing so that if say one AI programm looses horribly, but lost not because the AI for the military stradegy was bad, but because the budgeter didn''t give them any money. I''m not exactly sure how I could rate them, but it seems like it would be very helpfull and would produce very good results. I''m not sure how feasible that is, and it will probobly be implemented once everything else works, but I''m still giving it some thought.

Also, just out of curiosity, how much time would you expect a complex algorithm such as the one that will hopefully be created take to be created? This time is excluding the programming time of the actual HUMAN programmer

Thanx for the sites, though I''m still having quite a bit of trouble finding good sources which explain genetic programming not genetic algorithms with more than a basic example. Found a few at those sites though thanx!

I also found a book that I might try to get at the library. It''s called "Genetic Programming III: Darwinian Invention and Problem Solving". Looks REALLY cool. Anybody read it before?

Thanx!

Tazzel3d ~ Dwiel

The complexity arises from the pairwise operations of each agent with each other agent(s). Think of it this way: Suppose we have a ruler, a commander, and a budgeter, and suppose you''ve coded a GP app such that you only need 10 organisms per GP. Since you have 3 agents, you need 3 GPs, but now we have to ask the question of how to pair these guys up. The combinatorics say that there are 1000 different combinations - 3 groups, 10 in each group, 10^3.

The ultimate goal is for the various agents to interact with each other such that the outcome of the community is better than that of a different community. I suppose what I''m trying to say is that the problem space gets really big, really fast, and you need a lot of searching to accomodate it, which means lots of processor cycles.

You''re absolutely right in that the complexity of each individual system is less than if we had one big system. But, the complexity of interactions (or possible interactions) increases when you divide them into modules. In the scenario above, you also have to consider that you''re optimizing 3 independent controllers. A single GP is very processor consuming, 3 will cause your electric bill to increase by orders of magnitude. 8^)

As for the GP book, it is volume 3 of Koza''s books. John Koza popularized genetic programming (as well as inventing scratch off lottery tickets), and is considered the father of GP. In actuality, the Fogel boys have been doing GP and various other evolutionary methods for a long, long time and have some great papers. I''ve read the first book, and it was very good. The introductory material would be very valuable for you. I''m not certain of volume III.

Head over to http://citeseer.nj.nec.com/cs and do some searches. You can get some great papers in PDF of PS format. Also check out www.genetic-programming.com and www.natural-selection.com - some good demos and papers are there.

I''ll look around and see if I find more on GP specifically. I agree, the world is abound with GAs and GPs are hard to isolate.

-Kirk