10.03.2019 - Round 1 results of our "A Love Letter For FreeBASIC" game dev competition have been published. Please be sure to check the results thread: http://games.freebasic.net/forum/index.php?topic=629.0. Don't forget that the competition is continuing with a round 2, lasting till 29th of April, 300 USD first prize. Stay tuned!

Author Topic: Evolutionary AI  (Read 4012 times)

notthecheatr

  • Global Moderator
  • Forum Sage
  • *****
  • Posts: 351
  • Who's the guy from 21 Jump Street?
    • AOL Instant Messenger - notthecheatr
    • Yahoo Instant Messenger - TheMysteriousStrangerFromMars
    • View Profile
    • notthecheatr Home
    • Email
Evolutionary AI
« on: August 31, 2009, 02:16:24 PM »
I remember reading about evolutionary AI ages ago but I don't know where and I haven't seen a whole lot about it.  I'm kind of interested in it and want to experiment with it.  My ultimate goal here is not a game, but merely a simulation.

The idea is to create free agents inside an environment, then have them respond and react to the environment based on electronic "DNA" which is modified over time so the agents can "evolve" to become more intelligent and work better over time.  This is applied in the game NERO (though I don't know how), and I've seen it discussed occasionally on AI websites.

My idea is to create a basic free agent object with electronic DNA which can be extended to whatever you need it for.  I want to eventually create a simulation with "dumb" predator objects and evolving prey objects which learn to become better at evading the predators.  Perhaps at some point the predators would also be evolvable so the system could produce feedback and constantly be evolving.  Anyways, that's the idea.

Does anyone have any ideas, resources, websites, code, anything relevant?
The funniest thing happened yesterday.

Brick Break

  • Forum Sage
  • *****
  • Posts: 405
    • View Profile
Re: Evolutionary AI
« Reply #1 on: August 31, 2009, 03:02:03 PM »
Evolutionary AI- now there's an idea. I see a lot of talk about stuff like this on forum.thegamecreatos.com. A good example of this is cleverbot.com. It records the messages responded to certain messages and says those responses when the original message is asked. For example:
Bot: What color is the sky?
Me: Blue.
Me: What color is the sky?
Bot: Blue.

Also, somebody at TGC made a game in which the enemy physically evolves, or something like that. It seems kind of stupid, but I guess it's the same basic idea. More on that here.


Now that you bring up the idea, I think I'm going to have to experiment with that myself. :) Would it be OK if I made something relevant to this in DarkBASIC and posted it here? It's still BASIC, and it doesn't need to compile because I'll provide binaries. You might be able to adapt the source to FB though.

Mitchell

  • Forum Howler
  • ****
  • Posts: 197
  • Rockin Geek
    • View Profile
    • Email
Re: Evolutionary AI
« Reply #2 on: August 31, 2009, 03:10:25 PM »
Cool. What type of evolutionary AI are you going to try?

Pity. I had a cool link to a simple Java one with little creatures in it. Google may pull up some real interesting stuff though.

ETA: Here it is: http://www.probability.ca/jeff/java/evolution.html
« Last Edit: August 31, 2009, 03:18:34 PM by Mitchell »
Never underestimate the destructive powers of somebody doing something new without having any clue of how to do it. :P

notthecheatr

  • Global Moderator
  • Forum Sage
  • *****
  • Posts: 351
  • Who's the guy from 21 Jump Street?
    • AOL Instant Messenger - notthecheatr
    • Yahoo Instant Messenger - TheMysteriousStrangerFromMars
    • View Profile
    • notthecheatr Home
    • Email
Re: Evolutionary AI
« Reply #3 on: September 01, 2009, 10:56:31 AM »
Now that you bring up the idea, I think I'm going to have to experiment with that myself. :) Would it be OK if I made something relevant to this in DarkBASIC and posted it here? It's still BASIC, and it doesn't need to compile because I'll provide binaries. You might be able to adapt the source to FB though.
Neat stuff and I'd be very interested to see what you come up with.  Source and binaries both would be very interesting.


Cool. What type of evolutionary AI are you going to try?
I'm not sure.  Like I said, I'd kind of like to try a simulation of a predator/prey system, but I'm not really sure where to start.  Any resources, tutorials, papers, etc. you happen to know of would be cool.

ETA: Here it is: http://www.probability.ca/jeff/java/evolution.html
Pretty cool, albeit simple.  Kind of hard to take your eyes off once you start, you want to keep watching and see what happens next 8) Maybe I'll try implementing something similar in FreeBasic.
The funniest thing happened yesterday.

Mitchell

  • Forum Howler
  • ****
  • Posts: 197
  • Rockin Geek
    • View Profile
    • Email
Re: Evolutionary AI
« Reply #4 on: September 01, 2009, 05:04:04 PM »
I did some research on Genetic Algorithms and a little bit of Genetic Programming for my high school senior project using none other than Freebasic. There's quite a bit of material on it, if you know where to look (ahem, the all knowing Google).

I'd advise starting out with a simple Genetic algorithms, because they're straight forward, more likely to work, and it seems (to me at least) the majority of research is in this branch. And don't worry about the terminology too much; it's more about getting the sucker to work, and there is much overlap between meanings of these words. There's some other neat tutorial java applets on the subject.

Here's the one site that I could say helped me the most in learning it: http://www.obitko.com/tutorials/genetic-algorithms/index.php . It's a lot of material, but just take it page by page and it should make sense.
Never underestimate the destructive powers of somebody doing something new without having any clue of how to do it. :P

notthecheatr

  • Global Moderator
  • Forum Sage
  • *****
  • Posts: 351
  • Who's the guy from 21 Jump Street?
    • AOL Instant Messenger - notthecheatr
    • Yahoo Instant Messenger - TheMysteriousStrangerFromMars
    • View Profile
    • notthecheatr Home
    • Email
Re: Evolutionary AI
« Reply #5 on: September 03, 2009, 12:04:31 PM »
Nice link, I'll have to mess around with that one a bit.

Google turns up some things, mostly a lot of higher level books for graduate courses and whatnot.  There are a few things that can be understood by normal hobbyists like myself though, so I have an interest 8)
The funniest thing happened yesterday.

rdc

  • Novice
  • ***
  • Posts: 61
  • If (Rnd * 100) = 1 Then Print "You're in trouble!"
    • View Profile
    • Clark Productions
    • Email
Re: Evolutionary AI
« Reply #6 on: September 03, 2009, 07:20:24 PM »
What you are looking for here is a classifier system (CS) which is a combination of a genetic algorithm (GA) and selection method. A GA is a search algorithm, a way to select a set of genes through a fitness function. The CS reads the data from the environment, adjusts the GA parameters so that the selection process generates genes that matches the current environmental conditions. It may sound a bit complicated, but it is actually quite straight-forward. The difficulty is in the creation of the DNA code and assigning a fitness function.

GAs are quite easy to code (I have done a few over the years).

First you need to define the gene code. For example, suppose that you are creating an agent that can eat, move and reproduce. These are the actions that the CS would control within the environment based on the current environmental conditions. However, they don't define the genetic makeup of the agent, so you have define the basic genes that generate the behaviors. Some possible genes could be energy level generated from eating, reproduction level based on energy level and age, age of the agent in generations, and movement speed that would also be based on energy level or some other factor.

You could also approach the problem based on characteristics. For example, you could define a mouth that allows the agent to eat a certain amount, the number of legs that would determine the speed of the agent, the sex of the agent so that it could only mate with certain other agents, and so on. The gene structure depends on how you want to express the behaviors of the agent.

Once you define the gene code, you need to define a fitness function for the agent. What is the criteria for successful agents? For biological systems, success means reproduction, so the fitness function for something like an simulated agent would simply be surviving until it can reproduce. If you introduce a crowding factor into the simulation, that is more agents mean less food so the system is self limiting, you don't really need to define an external fitness function, since the crowding factor will act as a fitness function eliminating under-performing agents.

For the first generation, you simply generate x number of agents using randomly selected values for the genes. After that, you can use existing agents to generate new agents through reproduction, and occasionally introduce a random factor into the mix through mutation or spontaneous (random) generation.

The next thing to look at is the reproduction method. If reproduction is asexual, then you swap genes within the agent with a chance of mutation. In order for this to work, all of the gene criteria need to have the same meaning. For example, suppose you have a gene code of: energy | max age | speed. The values of each range from 1 to 100. These would represent percentages rather than actual numbers so that you are working with genes that relate to each other in a meaningful way. The actual numbers of the gene values could be anything, and different from one another, but making them percentage amounts within the gene definition enables you to manipulate the genes without worrying about range issues you might have with actual values.

So, to generate a new agent, you cut the gene randomly at a boundary.  Say you randomly select the energy-max age boundary. This leaves you with energy and max age | speed. You then swap the genes, resulting in max age | speed | energy. These are then mapped into the new agent gene code so that energy < max age, max age < speed, speed < energy. This is why the gene code needs to be consistent since you are mapping the values of the old gene to the new gene.

Once the gene is mapped, you can see if a mutation occurs, a very small chance, and then adjust a characteristic by a small amount. This helps keep the gene pool from stagnating.

For sexual reproduction, you randomly swap genes from two agents to produce the new agent. In this case, the gene values do not have to be consistent, since you are working from two different genes and the transfer is from one characteristic to another characteristic, without crossing over. You could introduce crossover is you want, but again, the genes need to be consistent.

The CS would then take all the agents and perform the different defined behaviors for a cycle based on the gene values. These could be different for each agent or the same for all agents. They could be another set of genes in addition to the characteristics. The behaviors might be: die due to old age or starvation, eat, look for food, move to food, avoid predator and reproduce. The cycle would then repeat.

Mitchell

  • Forum Howler
  • ****
  • Posts: 197
  • Rockin Geek
    • View Profile
    • Email
Re: Evolutionary AI
« Reply #7 on: September 03, 2009, 08:06:04 PM »
Ha. Found my old jump drive. Here's a little .doc file that has a loop of what may you expect if you had, say 2 competing members in a evolutionary program: http://freefile.kristopherw.us/uploads/mitchell/mutation_cycle.doc. The task is the evaluation function, to be more accurate. And this is for two players: just a simplification. Red and blue are representations of competing members, and what they represent is what you want to emphasize.
Never underestimate the destructive powers of somebody doing something new without having any clue of how to do it. :P