Artificial Life Forms Evolve Basic Memory, Strategy

Calopteryx notes a New Scientist piece on how digital organisms in a computer world called Avida replicate, mutate, and have evolved a rudimentary form of memory. Another example of evolution in a simulation lab is provided by reader Csiko: "An evolutionary algorithm was used to derive a control strategy for simulated robot soccer players. The results are interesting — after a few hundred generations, the robots learn to defend, pass, and score — amazing considering that there was no trainer in the system; the self-organizing differentiated behavior of the players emerged solely out of the evolutionary process."

Comments

World Cup 2014

[2phar]

Wow look at that teamwork.. maybe those guys could represent England?

Re:World Cup 2014

[captain_dope_pants]

No, they appear to have some skill and cohesion as a team - ther no place for that in the England side :)

Re:World Cup 2014

[Sulphur]

Can they snatch defeat from the jaws of Victory?

Not really amazing...

[blahplusplus]

"amazing considering that there was no trainer in the system;"

Not really, it's merely selecting patterns it is not aware of if it's patterns are "successful" or not. If you run a pattern generator long enough you can get all possible patterns within a finite possibility space.

Re:Not really amazing...

[Trepidity]

You do have to be a bit careful, though--- sometimes there is a hidden trainer in the system. In evolutionary algorithms, there are often a lot of parameters and data structures to tweak at the beginning, e.g., what kinds of crossover and mutation operators do you have, and what's your bit-string encoding? There are a whole lot of ways to slip in human domain knowledge of which things are important into the up-front engineering.

Re:Not really amazing...

[Anonymous Coward]

Saying there wasn't a trainer in the system is a bit of a misunderstanding really.

Evolutionary algorithms always makes use of a fitness function to define which generations are to survive and evolve and which are to die off, this is the case in the presented setup as well. Without knowing the project i'd guess they let the "teams" play against each other and let the winners survive.

If there wasn't a fitness function it wouldn't really be an evolutionary algorithm, evolution sorta implies "survival of the fittest" and all that you know :) The interesting part is observing the emergent behavior, in other words what we were not expecting to get out of the system. When the system doesn't have any knowledge of what a "defender" is, or what "passing the ball" means, it's interesting to see these well-known patterns evolve even when they are not specified, this is what matters to the AI researcher.

Other implementations of evolutionary algorithms may be fun (http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/) but are not showing emergent behavior because you are asking for a specific output through the fitness algorithm. That is the main difference.

Re:Not really amazing...

[OeLeWaPpErKe]

The fun thing is that these robots truly have a one-track mind. They do not learn -at all- within one generation, even if they have a brain that is relatively similar to ours. The brain is configured -entirely- at "birth" by the natural selection algorithm.

And yet they display a few remarkably human traits, that seem to -but don't- indicate learning. Memory. Strategy. Having a strategy responding to the "enemy". Yet by most standards -they don't think during the game. This makes one wonder ... is the fact that humans have memory, adapt "somewhat", devise strategy really an indication of the level of thought we think humans have ?

Makes one wonder just how one-track the human mind is. Everyone likes to always accuse everyone else of "not seeing the truth" about very nontrivial problems. Are people really "seeing the truth" or just repeating what they were programmed ?

History of science definitely seems to agree with the "programmed" argument. Other histories ... even more. We are mindless automatons, we just like to think we aren't.

Re:Not really amazing...

[hvm2hvm]

Depends on what level of perspective you want to look at. If you look at simple tasks and abilities, yes, a human will learn and think (some more than others) over the course of his life. It is evident if you take for example twins that grow in different environments, they get to have different abilities and understanding of the world.

OTOH if you widen your view and look at how humans interact between each other (i.e. society), how they think (technology, culture), and other things like that they don't really learn anything during their life. That's where evolution kicks in, people born in different generations have different ways of interacting and thinking. Some are behind their times while others are ahead which I see as a normal mutation, if you will, that can be a succesful one or a failing one. But even revolutionary people become conservatives after a certain age. That's why people die, that's how society evolves.

Yes, it's not all black and white like I made it sound, some things in the first category are inate and some in the secondary can still be modified by experience but I think my point was properly made.

Re:Not really amazing...

[ultranova]

If you run a pattern generator long enough you can get all possible patterns within a finite possibility space.

While true, this is also completely meaningless. For even trivial pattern spaces of, say, 512 bits, "long enough" would be far longer than the current age of the Universe.

Re:Not really amazing...

[mdda]

Not really. While the literature makes a lot of fine distinctions between the various cross-over methods/rates etc., in reality it's pretty academic.

Getting the genetic process going on a population is a really small amount of code, and there's a huge payoff to seeing it work for yourself (rather than using someone else's Black Box code).

The real key is that 'mashing' two individuals together to create a 'child' (evolution) is a whole lot better than creating a child as a random variation of one of those individuals (hill climbing), which is in turn a whole lot better than simply creating new individuals at random (monkeys at keyboards).

But you don't have to trust me. You should be able to code something up in an hour or two to see the effects. Don't worry about the details. This stuff really works.

Re:Not really amazing...

[bussdriver]

The problem space is so vast when you get into the necessary details humans take for granted:
Its so vast that it makes secure passwords look simplistic - this is far beyond brute forcing AES encryption. Even a simplified problem space is usually quite large in terms of possible combinations the only advantage AI work has is that there are no singular solutions but a large fuzzy set of solutions that are reasonably acceptable.

Say a monkey typed 99% of Shakespeare but it was wrong only for 1% of it: next attempt being random, the monkey would likely have 0% Shakespeare! There would be no convergence towards the answer. Even bruteforcing encryption rules out past attempts to avoid repeating itself but a random search does not. Furthermore, say the problem space is random - so then a 99% Shakespeare is light years away from the 100% Shakespeare, then no matter what the process for convergence (ie evolution) it is not going to converge which effectively puts you into the same situation as a random search.

The monkey typing thing is a silly way to state the obvious and sound good while doing so. "Its POSSIBLE but impractically time consuming" doesn't sound as good. These AI problems are nothing like monkey's typing - they learn and progress towards competency which is totally different! Again, they do this quite quickly since anything near the monkey approach wouldn't get there in our lifetimes (winning the lotto is more likely.)

Just because it is mindbogglingly complex does not mean it is intelligent...or that it has something we'd normally think of as a "memory" either. Its possible our brains are just pattern matching machines - and since we can only understand the most simple of such things we'll never figure it out (but could build a brain which could figure it out eventually and perhaps our brains are just an extremely fuzzy non-linear pattern match for #42.)

What's the news?

[synoniem]

When you program some evolutionary theory in your digital world and your digital world is developing some evolutionary lifeform that is news?

Re:What's the news?

[OeLeWaPpErKe]

You don't have to go into philosophy to get these. Theoretical mathematics will help you out here.

Suppose you had a "perfect" learner. One that tries every theoretically possible analytical technique. And then it manages to surprise you : it discovers existing mathematics, and perhaps a bit more, but nothing truly remarkable. That would simply be the result of a mathematical property of the "mathematical space" (the set of all possible mathematical knowledge, of, say all Godel-sentences) : that would simply mean that space is chaotic.

There are already known properties of the total mathematical search space : for one, it's not necessarily consistent (and thus not necessarily correct). It is known to be large: there is more mathematics than there are atoms in the universe (but it remains an open question if the subset of correct mathematical theory is infinite. Theoretically it could even be the empty set - that mathematics is fundamentally flawed).

Too late to call this "evolutionary":

[carlhaagen]

A bit more than 15 years ago I saw a documentary on Discovery Channel featuring identical work being made by a brittish scientist / computer programmer. His software spawned simple "lifeforms" made up by basic 2D and 3D geometrical objects - cubes, cylinders, flat triangles etc., - that were then trying to evolve methods of how to most efficiently move and travel in the simulated environment they were put in - sometimes an airy environment with ground underneath them, and gravity, and sometimes an "ocean" in which the "lifeforms" swam. Minute after minute the "lifeforms" jiggered and bounced around like broken machinery, but slowly developing a method for moving and navigating that was the most efficient for their particular shape. He spawned caterpillar-like animals made up from chains of cubes, that slowly learned how to wriggle and crawl just like catterpillars and snakes do. He spawned randomized "freaks" that learned that sometimes managed to learn how to walk with their disfiguring, and sometimes learning that the only way was to throw some bodypart around to pull themselves forward. He spawned biped animals that slowly learned how to jump to move forward, an triped animals that learned how to skip from one leg to the other, to the third. He spawned lifeforms in a watery environment that learned how to rhythmically oscillate their bodyparts to create propulsion in order to swim forward and turn around. To me, this was just as impressive, if not more, than the featured story. As a curious detail to it all, the programmer developed his software in BlitzBasic, running on a heavily accelerated Amiga 1200.

Re:Too late to call this "evolutionary":

[whatajoke]

Was it Karl Sims? Specifically this work

Addendum to first article is pretty good

[somersault]

In the late 1980s, ecologist Thomas Ray, who is now at the University of Oklahoma in Norman, got wind of Core Wars and saw its potential for studying evolution. He built Tierra, a computerised world populated by self-replicating programs that could make errors as they reproduced.

When the cloned programs filled the memory space available to them, they began overwriting existing copies. Then things changed. The original program was 80 lines long, but after some time Ray saw a 79-line program appear, then a 78-line one. Gradually, to fit more copies in, the programs trimmed their own code, one line at a time. Then one emerged that was 45 lines long. It had eliminated its copy instruction, and replaced it with a shorter piece of code that allowed it to hijack the copying code of a longer program. Digital evolvers had arrived, and a virus was born.

Avida is Tierra's rightful successor. Its environment can be made far more complex, it allows for more flexibility and more analysis, and - crucially - its organisms can't use each other's code. That makes them more life-like than the inhabitants of Tierra.

Actually, organisms using each others code sounds way more like our world than ones that can't leech off each other. They already pointed out viruses, and plenty of species exist today that need other species to continue to survive.. in fact pretty much all animals need to eat other lifeforms because we can't draw energy from the sun directly.

Re:Addendum to first article is pretty good

[Dunbal]

Organisms can perfectly draw energy directly from the sun, and animals and humans still do (such as vitamin D production).

      As a physician I find your statement ludicrous. While there is a photochemical step in the synthesis of vitamin D it's hardly fair calling a double bond being split by a photon as "drawing energy" from the sun. For that matter you could say that the dimerization of thymine in DNA by sunlight (which produces the genetic damage observed when a person is exposed to UV radiation) is another way we "draw energy" from the sun.

      Humans do not produce ATP from sunlight. Period.

      And I would agree with OP - all organisms, including plants, are directly dependent on other organisms. Without nitrogen fixing bacteria to fix nitrogen for the plants, and without decomposing bacteria to release minerals again into the soil, even plants would not exist. While the organisms that are set up to harvest sunlight directly from photosynthesis are the biggest input into the food chain, they can't live without the rest of it, especially the lowly decomposers. We're now all totally dependent on one another.

True fooball (soccer) behaviour

[PolygamousRanchKid]

The robots need to become spoiled, overpaid millionaires, who refuse to train (France). Brag a lot (England) that their opponent is a bunch of "boys" (Germany), who are afraid of them. Then take a 4-1 shellacking from the "boys." And despite being the defending champions, and having a world class league in their country, bow out early. Because all of the players in their first class league are from South America (Italy), and the they have no good domestic players.

Robots with vuvuzelas? No, thanks. My next nightmare.

Intelligent Design tag?

[mangu]

I would tag this as "Intelligent Design".

This is a very simple demonstration that something can evolve from simple beginnings, if the creator was intelligent enough.

A not-so-intelligent designer, OTOH, would probably prefer to create its beings in their final state because it takes more effort to create a system capable of evolution.

Re:Intelligent Design tag?

[mdda]

Actually no. The evolution mechanism is really robust.

Basically, if you have a bunch of random individuals, and the 'evolution' just mashes a bunch of the better ones together, you'll see the increase in fitness occurring. But it's not just a small effect : almost any crazy 'mashing together' method works, and the adaptation will spark off unbelievably quickly.

I know this because I did this for my PhD back in 1995. I had a choice then between going the Neural Net path, and playing around with the Genetic Algorithm/Genetic Programming stuff. Simple experiments proved that making NNs 'do the right thing' was a fairly tricky process of getting things set up right (and your formulae had to be right, etc : a fairly sensitive procedure). But the Genetic stuff was amazingly robust : almost any crazy method of crushing individuals together will produce remarkable innovation and learning (on a population basis).

But don't take my word for it, write a small piece of code yourself. The literature makes it sound like a more exact science that it needs to be. As I said, almost any 'mashup' method will work - the 'evolution thing' will simply find a way to 'protect' the important stuff.

So while this looks like 'old news' in some ways, I'm glad that they've got an eye-opening application : More people should know how much the computer guys can add to the biological evolution debate.

Re:Intelligent Design tag?

[sco08y]

I would tag this as "more proof soccer sucks." Really, soccer aficionados claim they see all these advanced movements, and that someone really does play better.

But, let's face it, they don't. They're just a bunch of people running around randomly, and occasionally someone scores by pure chance. That's why the games are always 0-0.

Seeing good soccer in random movement is part of the faith, much like astrologers see divine constellations in the random pattern of stars in the night.

Re:Intelligent Design tag?

[node 3]

I would tag this as "Intelligent Design".

The whole point is that this wasn't designed. Only the initial conditions were designed, and the designers then let them go on their own without any knowledge or comprehension as to how they would progress. The bullshit that is known as "Intelligent Design" is based on the assumption that the end results are too complex to have arisen on their own. In this case, the ability for the soccer players to know how to pass and such would be seen as "too complex" to have arisen by trial and error from a basic initial condition, but this is exactly what happened.

This was not intelligent design. It is, in fact, the very definition of evolution. It's also worth noting that evolution says absolutely nothing about the initial conditions for life, only how it progressed since it began.

Re:Intelligent Design tag?

[deapbluesea]

Basically, if you have a bunch of random individuals, and the 'evolution' just mashes a bunch of the better ones together, you'll see the increase in fitness occurring.

Funny, I did my Masters degree in 2003 on GAs and the major finding is that, while the system finds novel solutions, it also exploits the weaknesses of the fitness function very easily. In other words, if you wanted to get a particular result, you had to put most of your effort into the fitness function that describes the desired result. This doesn't work without said function, ergo, design is the key, not simply mashing things together. In fact, if you run a GA without a fitness function, you get a random walk, aka monkeys on a typewriter.

It's foolish to conflate computational optimization methods with biological evolution. While the mechanisms are similar, the means by which it occurs is about as closely related as AI is to human thought

Tierra was - and is - really cool.

[Dr. Manhattan]

In the late 1980s, ecologist Thomas Ray, who is now at the University of Oklahoma in Norman, got wind of Core Wars and saw its potential for studying evolution. He built Tierra, a computerised world populated by self-replicating programs that could make errors as they reproduced.

I was so amazed by the results claimed for Tierra that I went and reimplemented it myself. And damned if I didn't get similar results. At the time, it blew me away that such a system could come up with novel solutions I hadn't expected or 'programmed in'. Indeed, a couple times it took me a while to even figure out how the things worked.

Re:Err... what's the news?

[lalena]

I read the article wanting to know how the Avida developed memory. Basically, the programmer included an instruction that said "Do what you did last time" It is not evolution if the programmer hands them the ability. Also, when the goal stays in the same location every time, your robots can develop "memory" through the program itself. Ex: To go 2 up & 3 left -> Forward, Forward, Turn Left, Forward, Forward, Forward. No intelligence in the search pattern. This is simply memorizing the location of the goal. I would not call this memory.

I am very interested in this subject and get excited every time Slashdot posts a new story in this topic, but I never see any real advances vs. what I was doing in school 20 years ago. This doesn't mean advances aren't being made, but I think they are now at the level where they don't make simple easy-read stories. Real robots (not simulated ones) getting form point A to B (not just wanting to go from A to B) over rough terrain without help (mars rovers) is much more complicated and a required advance to put this technology into a real application. MIT, NASA, National Labs always seem to have interesting projects going on.

We celebrate these simple outdated advances in AI when we have hundreds of programs out there now capable of playing World of Warcraft without help simply to collect virtual gold to sell for cash.

Another reason I hate these articles is that they don't include any real specifics. You could learn more reading Wikipeida on GA, GP, ANN... It was a video of a Koza project that got me really interested in this topic. Why don't people include something like this in the article. A couple of years ago, I decided to rewrite one of my old projects so that people could easily run it online - Ant Simulator. Watching the system quickly learn or solve a problem is much more satisfying than reading an article written by someone that doesn't actually understand the field.

Re:God

[V!NCENT]

Evolution isn't some process, it's a phenomenon.

Genes get mixed and mutate and everything turns to chaos.

What survives and duplicates gets to the next level. That which dies cannot duplicate and dies.

How simple do you want it? This is where you stop thinking, God or no god.

Re:Oh...

[Mikkeles]

A pre-publication (not behind a paywall) version of the Avida (PDF) paper is here.
A good guide for those who don't welcome our new artificial, man-made overlords and wish to resist ;^)

Re:God

[V!NCENT]

http://www.washingtonpost.com/wp-dyn/content/article/2010/05/28/AR2010052801856.html