ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

CAs that exhibit evolution-like behavior

For discussion of other cellular automata.

CAs that exhibit evolution-like behavior

Postby Sphenocorona » July 17th, 2013, 9:56 pm

This topic will be for discussing CAs that exhibit evolution-like behavior, such as EvoLoop. I know there is already alot of info about these sorts of things, but I thought it might be helpful to have a spot for sharing ideas about such things.
Sphenocorona
 
Posts: 470
Joined: April 9th, 2013, 11:03 pm

Re: CAs that exhibit evolution-like behavior

Postby twinb7 » February 20th, 2014, 1:25 pm

Unfortunately I have yet to find or create a CA that fulfills my desire to get this kind of behavior, and just right. Loops are close, but tend not to increase in complexity.
Someday I'll work on a rule with... Some sort of spaceship and genetic code support, and replication requires finding 'food' particles or something.
twinb7
 
Posts: 172
Joined: February 11th, 2014, 8:08 pm
Location: Ames, Iowa

Re: CAs that exhibit evolution-like behavior

Postby dvgrn » February 20th, 2014, 3:19 pm

twinb7 wrote:Unfortunately I have yet to find or create a CA that fulfills my desire to get this kind of behavior, and just right. Loops are close, but tend not to increase in complexity.

Yes, it seems as if there ought to be more "evolution-like" behavior somewhere in CA-space. Quite possibly we're just looking at the wrong scale [link is to an article by Nick Gotts in Andy Adamatzky's book]... Maybe if we could watch rules at billion-tick increments, looking at blocks a million cells on a side, something interesting might eventually crawl out of the soup.

twinb7 wrote:Someday I'll work on a rule with... Some sort of spaceship and genetic code support, and replication requires finding 'food' particles or something.

That seems like a very good list of requirements for designing a rule to try to avoid an eventual plateau in complexity. Seems like the genetic code would have to be on about the same order of complexity as the program language in Core Wars, or Tom Ray's Tierra, which can evolve parasites, symbiosis, and other interesting higher-level behavior.

-- But I'm probably years out of date with my references. I guess Avida is a more recent and ongoing effort along the same lines, but I don't know how much farther up the complexity curve Avida has gotten compared to Tierra.

Anyway, neither of these are CAs, strictly speaking. Seems like if you wanted to start way down at the CA level, you'd have to get through a whole extra set of emergent headaches -- i.e., figuring out how to build structures that can reliably interpret a genetic code, and also handle copying errors and other mutations without the whole system collapsing into chaos. It's very tempting to just try extending one of the Evoloops variants somehow, but as you say that doesn't seem to be quite good enough.

I don't know about the "food particles" idea -- somehow that doesn't seem very CA-like. I immediately imagined a little oscillator along the lines of a chloroplast or a mitochondrion, sitting there generating new food particles, or converting one type of particle to another.
User avatar
dvgrn
Moderator
 
Posts: 4921
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: CAs that exhibit evolution-like behavior

Postby c0b0p0 » March 27th, 2014, 6:44 pm

A hexagonal lattice would probably be easier to implement this kind of CA on -- it has six axes of symmetry, rather than four. Either way, it would be very difficult to implement this behavior, especially mutation. If one sticks to variants of Evoloop, he might want to create a cross between Sexyloop and Goucher Loops, which would probably be explosive.

One of the main disadvantages with using loops is that they turn out to be explosive, so it is difficult to find interesting patterns in these rules. (Are all the proposed "evolving CA" explosive?)

However, without using loops the CA might not be runnable within Golly, as in a hexagonal lattice with symmetry rotate6reflect there are 16777216 rules (of course, most of them are uninteresting), and no one is going to take the time to look at all these rules and see if they are interesting or not. Another approach might be to start with a predefined list of interesting rules and emulate mutations among these rules.

Mutation, of course, is very difficult. The only way I can think of doing it to do it would be to have a gigantic neighborhood (say, 99 cells on a side) and get a cell to mutate iff there were no cells of its type in its neighborhood. Unortunately, Golly could not come close to running that.

Prescinding from whole mutation business, here is a very primitive rule competition example on a square grid.
@RULE CompeteLife2x2


@TABLE

n_states:3
neighborhood:Moore
symmetries:permute

var a={0,1}
var b={a}
var c={a}
var d={a}
var e={a}
var f={0,2}
var g={f}
var h={f}
var i={f}
var j={f}
var k={f}
var l={f}
var m={f}
var n={0,1,2}
var o={n}
var p={n}
var q={n}
var r={n}
var s={n}
var t={n}
var u={a}
var v={a}
var w={a}
0,2,2,2,a,b,c,d,e,2
0,2,2,2,2,2,2,a,b,2
2,a,b,c,d,e,u,v,w,0
2,2,2,2,n,a,b,c,d,0
2,2,2,2,2,2,2,n,o,0
0,1,1,1,f,g,h,i,j,1
1,a,f,g,h,i,j,k,l,0
1,1,1,1,1,n,o,p,q,0
2,1,1,1,p,q,r,s,t,1
1,2,2,2,p,q,r,s,t,2

@COLORS

1    0    0  255
2  255    0    0
3    0  255    0
c0b0p0
 
Posts: 645
Joined: February 26th, 2014, 4:48 pm

Re: CAs that exhibit evolution-like behavior

Postby c0b0p0 » March 31st, 2014, 6:55 pm

c0b0p0 wrote:Mutation, of course, is very difficult. The only way I can think of doing it to do it would be to have a gigantic neighborhood (say, 99 cells on a side) and get a cell to mutate iff there were no cells of its type in its neighborhood. Unfortunately, Golly could not come close to running that.


A better plan which would actually be closer to being runnable within Golly would be to have a cell mutate if it was alive and had the same state for n (perhaps 5-15) consecutive generations, changing a single birth condition or survival condition according to its neighbors. This method would have at most 16777216 * n states. As having the neighborhood with 99 cells on a side would require at least 2^10101 states, this is a substantial improvement.

If one prefers implementing the "interesting rule mutation" concept instead, I can think of three interesting two-state isotropic hexagonal rules (unfortunately, this is very limited): Hex-B2omS2, HexLife, and 22da.

I almost certainly have overlooked certain rules, so if any one comes up with a hexagonal rule that meets the above specifications and is interesting, please post it on this thread.
c0b0p0
 
Posts: 645
Joined: February 26th, 2014, 4:48 pm

Re: CAs that exhibit evolution-like behavior

Postby c0b0p0 » April 6th, 2014, 8:07 pm

twinb7 wrote:Unfortunately I have yet to find or create a CA that fulfills my desire to get this kind of behavior, and just right. Loops are close, but tend not to increase in complexity.
Someday I'll work on a rule with... Some sort of spaceship and genetic code support, and replication requires finding 'food' particles or something.

Competition for space is interesting enough, not to mention competition for food! Here are the rules I am considering for competition.

1. No cell can mutate to an explosive rule. The reason for this is that explosive rules would take over and eliminate all the other rules, unless some constraint was introduced, which would probably be expensiive in terms of required cell states.
2. If a cell must mutate (that is, it has been alive for n generations) but cannot according to (1), then it dies.
3. If a cell is touched by cells using a different rule so that that cell would be born if it had been in state 0, then it just dies.
4. If a dead cell is touched by cells using two different rules B(R1B)/S(R1S) and B(R2B)/S(R2S), such that both would produce a birth in that cell and thus it would need to have two different colors, then it becomes a cell with the rule B(2o OR (R1B XOR R2B))/S(R1S XOR R2S). If that rule is explosive, the cell remains in state 0.
c0b0p0
 
Posts: 645
Joined: February 26th, 2014, 4:48 pm

Re: CAs that exhibit evolution-like behavior

Postby c0b0p0 » May 10th, 2014, 4:45 pm

Eliminating explosive rules doesn't get one far. Here's what I came up with before I couldn't find any further way to eliminate a significant chunk of rules.
Cannot have B1 -> 16777216 rules
Must have B2o -> 8388608 rules
Cannot have B2m/S0 -> 6291456 rules
Cannot have B2m/S1 -> 4718592 rules
Cannot have B2p/S01 -> 4128768 rules
Cannot have S012o -> 3612672 rules
Cannot have B2p/S12o -> 3161088 rules
c0b0p0
 
Posts: 645
Joined: February 26th, 2014, 4:48 pm

Re: CAs that exhibit evolution-like behavior

Postby c0b0p0 » May 13th, 2014, 9:32 pm

Here's the updated list of requirements for nonexplosive rules, going half an order of magnitude further.
Cannot have B1o -> 16777216
Must have B2o -> 8388608
Cannot have B2m/S0o -> 6291456
Cannot have B2m/S1o -> 4718592
Cannot have B2p/S0o1o -> 4128768
Cannot have S1o2o -> 3096576
Cannot have B2p/S1o2o -> 2709504
Cannot have B2m/S2o2m2p -> 2540160
Cannot have B2m3o3m -> 1905120
Cannot have S2o2m3o -> 1428840
c0b0p0
 
Posts: 645
Joined: February 26th, 2014, 4:48 pm

Re: CAs that exhibit evolution-like behavior

Postby wildmyron » May 14th, 2014, 6:22 am

This is an area which I am really interested in too but for the moment I don't have a lot of theory to contribute. My own ideas revolve around combining a diffusion CA with some sort of chemical automata. But for the moment I'll following along with the discussion here.

twinb7 wrote:Unfortunately I have yet to find or create a CA that fulfills my desire to get this kind of behavior, and just right. Loops are close, but tend not to increase in complexity.
Someday I'll work on a rule with... Some sort of spaceship and genetic code support, and replication requires finding 'food' particles or something.

Have you seen Lotus Artificial Life? In particular, http://alife.co.uk/hal/index.html and http://alife.co.uk/crystal2d/index.html . In both cases, set delay to 100 to see a bit of what's going on. I don't really understand what actually is going on in these CA, but I suspect that a large part of the reproduction mechanism is more in the underlying CA rather than the patterns which are evolving.

@c0b0p0 I'm not sure I follow where you're going with the mutation of which rule a cell is using. Do you expect the most interesting non-explosive rule to begin to dominate, or is it meant to be an integral part of how patterns evolve (in the CA sense, not the genetic sense) in the CA universe you're attempting to create? Or is the state of the cell the rule itself, rather than On or Off as determined by the current rule?
wildmyron
 
Posts: 864
Joined: August 9th, 2013, 12:45 am

Re: CAs that exhibit evolution-like behavior

Postby c0b0p0 » May 16th, 2014, 4:30 pm

@wildmyron: The state of the cell in any given gerenation is a combination of the rule that governs its transition to the next generation and the state of its correspnding cell in the background two-state "noise" that follows the rule B2o2m/S1o. The background noise should only be used for mutation.

Here's the updated list of requirements for non-explosive rules.
Cannot have B1o
Must have B2o
Cannot have B2m/S0o
Cannot have B2m/S1o
Cannot have B2p/S0o1o
Cannot have S1o2o
Cannot have B2m/S2o2m2p
Cannot have B2m3o3m
Cannot have S2o2m3o
Cannot have B2p/S0o2o2m
Cannot have B2p/S0o2o2p
c0b0p0
 
Posts: 645
Joined: February 26th, 2014, 4:48 pm

Re: CAs that exhibit evolution-like behavior

Postby Tezcatlipoca » September 9th, 2014, 11:29 pm

Hi guys. I'm new here. I come from the biological sciences and am a programmer, though not the best one. I'm really fascinated in how we can make better Life like simulations of biological evolution and specifically of self replicating macromolecules. It's been far too long since I've had a math class and I haven't been deep into the programming or the programs that surround the community here yet, though I plan to learn more shortly. But for now I'm still really interested and thoughtful in how this can be done conceptually.

I feel like the idea of starting from a point where there is a plan that creates a structure doesn't mimic perfectly life and evolution. At the base of it, back at the fundamental level the structure was the plan. Small molecules that were shaped such that when encountering the separate composing parts of itself by random chance it would configure these into a structure like itself (but not with absolutely perfect fidelity each time). So it seems like life generation because of "proximity to life" could be replaced with "proximity to composing resources" somehow to improve the analogy to biological life.

Say if there were 5 states of each cell, 0 (this is the off state), 1, 2, 3, and 4. They are randomly seeded within a bounding area (but the 0 state should be more common I'm thinking). Each state has a preferred orientation for two other states (e.g. a 1 likes a 2 on it's immediate right) and when it is adjacent to a cell with a preferred orientation but this cell is not in that preferred location, it reconfigures by swapping the cell that is in the preferred position with the out of place cell that it wants there. Once in correct position cells are locked in their state (or are somewhat resistant to be separated or move together):
CODE: SELECT ALL
. . . 1 3 . . . 1-2
. . 2 . . => . . 3 . .
. . . . . . . . . .


Could four states with each state having two relationships with other states be enough to create an "L" shape that could replicate itself? I think an L shape could make an interlocking L shape. Maybe it would need orientation or handedness. I'm unsure. I'm playing with grids a little though trying to see what might happen. Feel free to join me in speculation or to give me some education if you'd like. Thanks!
User avatar
Tezcatlipoca
 
Posts: 81
Joined: September 9th, 2014, 11:40 am

Re: CAs that exhibit evolution-like behavior

Postby Tezcatlipoca » September 10th, 2014, 10:39 pm

Today I "breed" a 34 x 34 cell self replicator with a stable population in a bounded grid. Sadly it's rather stable. There's not a high rate of mutation, though there is some. I am getting a feel for mutation overall in the system though. This is really pretty amazing. I have about 20 or so different lineages with different "evolved" self replicators. Some have a higher rate of mutation than others. Some are rather complicated and even have a two stage life cycle. I wish I could come up with a way to subject them to different selection pressures...
User avatar
Tezcatlipoca
 
Posts: 81
Joined: September 9th, 2014, 11:40 am

Re: CAs that exhibit evolution-like behavior

Postby dvgrn » September 11th, 2014, 11:00 am

Tezcatlipoca wrote:Today I "breed" a 34 x 34 cell self replicator with a stable population in a bounded grid. Sadly it's rather stable. There's not a high rate of mutation, though there is some.

This is a Shapeloop experiment, I take it? Feel free to post actual patterns -- they're much nicer than tantalizing descriptions of things. Just copy a selection out of Golly and paste it into a message inside [code] blocks.

I was reading in Wikipedia this morning that the original problem that John von Neumann was working on was evolvability. Just think what von Neumann might have come up with if he'd had access to a good high-performance computing cluster...!
User avatar
dvgrn
Moderator
 
Posts: 4921
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: CAs that exhibit evolution-like behavior

Postby Tezcatlipoca » September 11th, 2014, 1:17 pm

Check this little guy out! He carries onboard code for a very complicated life cycle with structures or techniques that help the lineage persevere in the midst of similar competitors. The shape reproducing the shape alone doesn't do as well. You'll see that structures like an "interface" where it links with a mirrored shape and flashes red and a dormant blue bud (looks like a protein to me) that sometimes allow the shape to go on reproducing after being "attacked". You'll have to watch it for a while to catch one of these instances, but I have managed to catch them in action several times. There's a yellow flashing interface as well. There's a sort of pinwheel structure (this one was actually hybridization from another replicator if you can believe it). Is this normal in shapeloop?! It is blowing my mind.


x = 19, y = 14, rule = shapeloop
2$3.D3AC2A$3.A5HA$3.D3H.HD3A$3.ADADHJ3HA$6.F4HJA$6.BD4AC$5.HK!
Last edited by Andrew on September 11th, 2014, 6:57 pm, edited 1 time in total.
Reason: removed bounded grid from rule
User avatar
Tezcatlipoca
 
Posts: 81
Joined: September 9th, 2014, 11:40 am

Re: CAs that exhibit evolution-like behavior

Postby Tezcatlipoca » September 11th, 2014, 6:34 pm

Oh, and here's the 34 x 34 replicator

x = 34, y = 34, rule = shapeloop
3.20ADBDAFDA$3.A25HD$3.AH23.HA$3.AH23.HDADAD$4AH24.4HA$A3H28.HA$AH30.
HA$AH30.HD$AH30.HA$AH30.HD$AH30.HA$AH30.HD$AH30.HA$AH30.HD$AH30.HA$AH
30.HD$AH30.HA$AH30.HD$AH30.HA$AH30.HD$AH30.HA$AH30.HD$AH30.HA$AH30.HD
$AH30.HA$AH30.HA$AH30.HA$AH30.HD$AH28.3HA$A4H24.HADAD$5AH23.HD$4.AH
23.HA$4.A25HD$4.11ADAC3ADADADADADAG!


I wish it had a little more mutation. It's pretty stable. I'm not sure why, It' grew up from smaller things and it is not ideal with respect to density compared to the others and it does mutate sometimes on collisions and after interface though not during the replication step that I can tell. Maybe it just needs more time. And I guess there is a reason why there are elephants in the world too!
Last edited by Andrew on September 11th, 2014, 6:58 pm, edited 1 time in total.
Reason: removed bounded grid from rule
User avatar
Tezcatlipoca
 
Posts: 81
Joined: September 9th, 2014, 11:40 am

Re: CAs that exhibit evolution-like behavior

Postby Andrew » September 11th, 2014, 7:05 pm

I edited your patterns to remove the bounded grids from the rule strings. This is so the patterns behave correctly if users enter them into Golly via File > Open Clipboard (which is much quicker and safer than doing a paste).

Dave already mentioned this, but it's worth stating again that patterns run slower in bounded grids. This is because all the current Golly algorithms are designed to work with an unbounded grid, so Golly has to do extra work to simulate a bounded grid.
User avatar
Andrew
Moderator
 
Posts: 678
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia

Re: CAs that exhibit evolution-like behavior

Postby Tezcatlipoca » September 11th, 2014, 8:54 pm

I swear I'm not deaf; I tried it again (excitedly) this time thinking maybe I had done something wrong with unbounded on my first tries. I'd much rather have it unbounded. But try it yourselves with one of my submitted shapes. Put it on hyperspeed and bring it to a population of about 3,000,000. It does pretty good, albeit ever slower at 8^4 but wait too long or switch it down to 8^0 and it freezes. Now I am using the new win 64-bit version. Could that have something to do with it? I just have trouble understanding how an increasingly large and increasingly complex system, even when represented with mathematics won't be increasingly complex. This could easily be a misunderstanding but I'd always assumed more complicated shapes or rather description of a more complicated system would require more complicated formulas at some level, that [0, 0] was smaller on an informational level than [0, 1] Even if that's wrong, once the image gets larger than 1px per cell in the view might it have to do more to come up with the shapes which are now approximations?

Now I guess he did say something about trimming the edges. Is that the component that I'm missing? If so is there a way to do this programmatically? Wouldn't that be tantamount to bounding though? Thanks for bearing with me guys. I know there must be something to what you are saying, but it's not jiving with my experience yet.
User avatar
Tezcatlipoca
 
Posts: 81
Joined: September 9th, 2014, 11:40 am

Re: CAs that exhibit evolution-like behavior

Postby Tezcatlipoca » September 19th, 2014, 4:13 pm

Hey Andrew, my pattern finally got big enough (right at the like ~50,000-60,000 X 50,000-60,000 square grid level) to where it performs much better unbounded. I had been trying both ways because of the tips I was given. Just though I would post just in case that boundary is important to somebody in the future.
User avatar
Tezcatlipoca
 
Posts: 81
Joined: September 9th, 2014, 11:40 am

Re: CAs that exhibit evolution-like behavior

Postby Tropylium » September 23rd, 2014, 5:19 am

A key point in CA evolution is that the main resource almost all replicators compete for is space. In principle any nonexploding CA must have a maximum growth rate; usually a reachable one. So once this has been hit, there's nothing else to do. It's not really a climb upwards as much as a race down, and any interesting stuff going on is not so much about the innovation of entirely novel results, but different paths to reach the peak growth rate.

By contrast, space is an abundant resource in all known biological environments. This is of course due to to the conservation of matter, and the general sparseness of the universe.

So the options for developing "CA biology" come down to either 1) instead simulating an environment where growth is limited by factors other than space, or 2) adjusting our view to not require perfect analogy between CA and biological life. If space is scarce but "matter" is abundant, what other differences does this imply and is the a possibility for other similar analogies? For example — should "population" be measured not by cell or individual count, but by area governed?
User avatar
Tropylium
 
Posts: 406
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: CAs that exhibit evolution-like behavior

Postby alexv » September 23rd, 2014, 5:59 am

Despite of mentioned technical problems, simulation on bounded grid also has some advantages due to
competition for limited space. And even shape of bounds may matter, e.g. in other thread I mentioned
400x225 bounds chosen rather due to occasional reason (16x9 display screen ratio)
http://www.conwaylife.com/forums/viewtopic.php?f=11&t=1446&p=13411#p13411
then quite shortly evolution of five patterns produces four mutations and only one survives.
The same initial conditions with other shapes of bounds produced other kind of mutants, e.g.,
yet another one (after small modification) was used in example of pattern with two arms
http://www.conwaylife.com/forums/viewtopic.php?f=11&t=1440&p=13416#p13416

Alexander
User avatar
alexv
 
Posts: 136
Joined: February 3rd, 2014, 11:14 am

Re: CAs that exhibit evolution-like behavior

Postby calcyman » October 9th, 2018, 9:41 am

Tezcatlipoca wrote:Hey Andrew, my pattern finally got big enough (right at the like ~50,000-60,000 X 50,000-60,000 square grid level) to where it performs much better unbounded. I had been trying both ways because of the tips I was given. Just though I would post just in case that boundary is important to somebody in the future.


Append an extra 'wall' state (which can never be born or change state), and then create a boundary made of cells with that state. This allows you to have arbitrarily-shaped arenas without slowing Golly down.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1748
Joined: June 1st, 2009, 4:32 pm

Re: CAs that exhibit evolution-like behavior

Postby 77topaz » October 9th, 2018, 6:44 pm

calcyman wrote:Append an extra 'wall' state (which can never be born or change state), and then create a boundary made of cells with that state. This allows you to have arbitrarily-shaped arenas without slowing Golly down.


He was also using the 2014 version of Golly, so that may also make a difference. :P
User avatar
77topaz
 
Posts: 859
Joined: January 12th, 2018, 9:19 pm

Re: CAs that exhibit evolution-like behavior

Postby Gamedziner » October 9th, 2018, 7:28 pm

calcyman wrote:Append an extra 'wall' state (which can never be born or change state), and then create a boundary made of cells with that state. This allows you to have arbitrarily-shaped arenas without slowing Golly down.

LifeHistory can do that already:
x = 3, y = 3, rule = LifeHistory
2.F$2A$2A!
Gamedziner
 
Posts: 553
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: CAs that exhibit evolution-like behavior

Postby 77topaz » October 9th, 2018, 11:14 pm

Gamedziner wrote:LifeHistory can do that already:
x = 3, y = 3, rule = LifeHistory
2.F$2A$2A!


That's not quite the same, because those grey cells affect the survival of the normal cells adjacent to them.
User avatar
77topaz
 
Posts: 859
Joined: January 12th, 2018, 9:19 pm

Re: CAs that exhibit evolution-like behavior

Postby Gamedziner » October 10th, 2018, 6:52 am

77topaz wrote:That's not quite the same, because those grey cells affect the survival of the normal cells adjacent to them.

Then just make a rule with another state that does nothing but survive.
Gamedziner
 
Posts: 553
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Next

Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 4 guests