Percy's Alife Project

Alife stands for Artificial Life.I've always wanted to do my own alife program, but I didn't want to simply duplicate what had already been done in programs like Tierra, Cosmos and others. While I don't kid myself that I could make an original contribution, neither am I interested in reinventing the wheel. Recent discussions about genetic algorithms (GA) caused me to take a look at recent developments on the alife frontier, and I came up with some ideas that may be worth exploring. I outline these ideas here in the hope that people can provide a useful check on their quality and sensibilty.

C E L L S C A P E

The name of the program will be Cellscape. My original choice was Worldscape, but that name is taken. My next choice was Microscape, but a day later I fixed on Cellscape. The name will change again as soon as someone suggests a better one.Obviously, Cellscape will need a logo. TrueCreation did the current EvC logo, we need a similar fine effort for Cellscape. Of course, there are no screenshots yet, but use your imagination.

The Cellscape Universe

The Cellscape universe will be a 3D grid that wraps at the limits. The universe needn't be a cube but will definitely be rectangular and not some irregular shape.Each grid location is characterized by properties. Examples of properties are temperature, density (like of air or water), direction (like wind), and so forth. Each grid location of the universe can also contain a single object. Most of the universe must be empty, though, else there would be too many objects to possibly represent in a PC simulation.

Cellscape Objects

Conceptually, an object is a six sided cube which completely fills a grid location of the universe.I've only identified a few objects so far:

• Cell membrane object
  ​
  Cell membrane objects form the cell containment structure. Cells are contained within a cell wall consisting of many cell membrane objects. The fewest number of these objects that could surround non-zero grid locations would be six, which could surround a single grid location.
  ​
• Metabolic element
  ​
  Metabolic elements process food into energy and waste objects.
  ​
• Energy object
  ​
  Energy objects can be absorbed by other objects to provide the energy required to carry out activities.
  ​
• Food object
  ​
  Food objects are consumed by metabolic elements to process them into energy and waste objects.
  ​
• Waste object
  ​
  Waste objects are produced when a metabolic element processes food into energy.

Every object has one or more algorithms associated with it that govern its behavior.

Cellscape Algorithms

Algorithms are attached to objects. Algorithms control everything that an object does. Every algorithm of an object is executed once per cycle (time slot), and this is how the universe changes over time.While I have a pretty firm idea about what algorithms will do, I don't yet have a clear idea of how they will be represented. I'll probably stay away from PLA-style approaches because even though they're extremely easy to implement and execute, they're very difficult for humans to interpret, and we want people to be able to peek inside and understand what's going on. Hence I'm leaning toward a C-like language that would be interpreted at run-time, but with an efficient non-textual internal representation that the program would use, and which would be de-compiled when users request it.For an example of an algorithm, consider a food object. Food objects drift aimlessly through the universe until they are consumed. The drift algorithm for a food object might be this (this is just C code to get the idea across, not necessarily an implementation proposal):

    // ChooseRandom returns one it's arguments, chosen randomly
xpos += ChooseRandom(-1, 0, 1);
ypos += ChooseRandom(-1, 0, 1);
zpos += ChooseRandom(-1, 0, 1);

One can easily imagine more complex drift algorithms. In this one, the food floats upward if it is warmer than its surroundings, and sinks if it is colder:

    int gridTemp = GetGridTemp(xpos, ypos, zpos);
if (myTemp > gridTemp) {
xpos += 1;
} else if (myTemp < gridTemp) {
xpos -= 1;
}
ypos += ChooseRandom(-1, 0, 1);
zpos += ChooseRandom(-1, 0, 1);

If there are currents, then these, too, could be taken into account:

    int xCurrent = GetXCurrent(xpos, ypos, zpos);
int yCurrent = GetYCurrent(xpos, ypos, zpos);
int zCurrent = GetZCurrent(xpos, ypos, zpos);
int gridTemp = GetGridTemp(xpos, ypos, zpos);
if (myTemp > gridTemp) {
xpos += 1;
} else if (myTemp < gridTemp) {
xpos -= 1;
}
xpos += xCurrent;
ypos += ChooseRandom(-1, 0, 1) + yCurrent;
zpos += ChooseRandom(-1, 0, 1) + zCurrent;

Objects can sense their surroundings. For example, here's the algorithm for a metabolic element checking for food in the adjacent grid locations (there are 26, and since checking the adjacent grid locations will be an extremely common operation, functions are provided to make this very easy):

    foreach adjacentLocation (AdjacentLocations(xpos, ypos, zpos)) {
if (ContainsFood(adjacentLocation) {
EatFood(adjacentLocation);
}
}

There's plenty more, but that's all I have time to type in for now.--Percy

There will be no software function that decides relative fitness of organisms. The comparison will be an emergent function deriving from competition for resources among organisms. Direct competition between organisms is a possibility, but it won't be designed in - if it happens (and I hope it does) it will be an emergent behavior.Providing information about organisms to the user is one thing, making sense of that information is another. If the user notices that one organism is outcompeting another, how will he be able to tell why? Looking at the algorithms (the genetic code) of the organisms is probably a difficult way to figure it out. Watching the behavior of the organisms is probably a better way, and I hope to be able to provide that capability. A replay capability would also be extremely useful.--Percy

I was just writing in C pseudocode. While I'm not up on the details of Java syntax, I know they're pretty similar, so if you know Java then whatever I write should look pretty familiar to you. It's important not to forget I'm writing pseudocode, though. For implementation there has to be a much more efficient internal representation. I'll probably do whatever makes sense. Right now I could use a healthy exchange of ideas, and so this thread is working fine. In fact I'm extremely gratified at the responses - not having a good gauge of the level of interest in alife software among members, I figured there was a good chance this thread would be ignored. Yes, I'm writing it in C++. I've already designed the base object, and as soon as I've designed the derived objects (like food and metabolic elements) I'll post them all in a new directory here at EvC. That way people will be able to see where I'm coming from from a software standpoint. If you already know Java then I'm guessing you're already familiar with object oriented concepts, and with methods being associated with objects, but I'm not familiar enough with Java to know if it has analogs to the C++ concepts of base classes, derived classes, method flavors, constructors and destructors, inheritance, templates and operator overrides. Let me know how you feel about C++, we'll go from there.--Percy

Keep telling me this. I keep telling myself the same thing, but I keep responding that I *am* keeping things simple, and of course I believe myself. This feedback is important.I *think* the objects I've identified so far are a fairly small set, but keep working on me, maybe I'll waver. I share the concern, but I felt 2D was a fairly severe weakness of alife worlds I have read about so far. The primary criticism of the results of alife efforts so far is that the level and kinds of complex interactions and behaviors that characterize real life that they hoped would emerge simply failed to happen. I don't believe this failure can be laid solely at the door of 2D, but I *do* believe it is a factor.That being said, while 3D increases the complexity of some of the underlying algorithms (like just determining adjacent grid locations) and thereby making the programming job much tougher, I believe it astronomically increases the possibility of emergent complexity. I can't prove this, of course... I agree with you so much I could have written that paragraph for you. Some of my ideas started to solidify while reading Emergence: The Connected Lives of Ants, Brains, Cities, and Software by Steven Johnson. I'm actually still in the first couple chapters (I'm ashamed to admit how long ago I began reading this book, but I'll admit that months is not too large a unit), but it got me thinking about how one might use emergent behavior to design digital systems, and I rapidly came to the conclusion that if the final result was preordained then the concepts surrounding emergent behavior were unlikely to be helpful. So I started trying to come up with applications where emergent behavior would be just what you want, even though you don't know in advance what specific behaviors might emerge, and of course evolution was one of the possibilities. Then the GA discussions started in some threads here, I started updating myself about alife, and then it just felt like I had enough ideas to get started. You're anticipating some things I was intending to discuss when I posted my next installment, but jumping ahead is fine.Any object can be food. What defines an object as food is whether another object is able to consume it. I'm hopeful that a food cycle will emerge where one organism's waste is another oranism's food. Naturally this means that organisms can possibly view each other as food. Don't ask me more details of how this will be realized. If you have some ideas I'd love to hear them.But there *does* need to be an initial source of food. Naturally the initial state of the universe will include food just floating around, but is it replenished? I don't see why it can't be. While there's probably many ways this could be accomplished, only one comes to mind just at the moment. Our universe could be "bathed" in energy, analagous to the sun, and energy striking a raw material, say something analogous to debris at the bottom of a tidal pool, breaks it away and turns it into free floating food. I'm hopeful that an emergent behavior will be cells that attach themselves to inanimate raw material objects ("rocks" or "mineral deposits") and turn them into food. There's also the issue of whether there can be different types of food that provide something analogous to different nutrients, forcing organisms to seek out more than one food type. Yes. Hopefully. Yes.Death and reproduction will be an emergent behavior. Death is easy - it happens when enough of the objects comprising a cell simply cease to have enough available energy to execute their algorithms, turning them into free-floating objects.In my view of things, growth, reproduction and mutation are intertwined, and the manner in which they are intertwined is important. The conceptual framework in which I'm currently thinking has mutation associated with growth. For example, if a cell wall object has enough energy and resources to "grow" (ie, produce another cell wall object), then there is a small but finite possibility that the algorithms inherited by the new cell wall object will be mutated in some way (there will be a large variety of mutation types, but discussion on that can wait). I know this isn't precisely analogous to the way life here on earth mutates, but this is where I think it helps to take another interpretation of the "alife" label and keep in mind that what we're trying to create is "a life", not "the life".Reproduction occurs when one cell becomes two simply because the cell wall objects have become numerous enough to make this happen, and because they move in such a way as to divide the cell into two parts which then move away from each other. The cells would not be exact duplicates of each other, as the algorithms each cell ends up with are those associated with the objects each new cell ended up with.I'm open to ideas that can improve upon this approach by bringing it closer to the way real life actually mutates, but I'm pretty happy to come this close, and I actually like it a lot because it feels like this may be closer to the way pre-life actually operated. And this brings me to perhaps my most ambitious goal. I'll just mention it and end there.I'm hoping to drop bare objects into my universe, just cell wall objects, metabolic objects, food objects, etc, that aren't already gathered together into cells and just let cells happen as an emergent behavior.--Percy

Good idea. Things like mass and temperature can be properties of objects. I'm still debating what the list of properties should be, and if the system is properly designed then new properties should be easy to add, anyway. Conceptually I think Cellscape is pretty simple so far, but there are some significant programming challenges, and some of the choices about properties and algorithms will be key. When people are discussing how come our universe has just the right physical constants for life to emerge it is often mentioned that if just one physical constant were just a little different (I forget which one) then the universe would just be a big cloud of hydrogen gas. The same applies to the Cellscape universe - poor choices for initial underlying parameters could cause little or nothing to happen. Whether this will prove to be a significant problem or not is too early to tell.--Percy

Doesn't it, though!I didn't follow the reference to compression technology, but the part about tracking local min/max's and infering the value for other locations seems good.Density and conductivity could definitely be additional properties, and I agree about introducing the more complex properties later rather than sooner.I *have* thought about energy sources. I'm not sure at this point whether it needs to be part of the early universe (ie, the debugging phase), but it seems like a critical component of any self-sustaining universe. There have been a few others who have offered help, and it would be great if we had several people working on this. To keep it fun my inclination is just to keep discussing details and issues, and whenever anybody sees something they'd like to do they should just pipe up and say, "Hey, I'll do that part." I've been wanting to hook up a chatterbot to a thread here. Ever heard of Leo? Is your chatterbot better?--Percy

No argument from me.Thanks for the offer of help - I can use all I can get.As I said to Awinkisas, we'll just take an ad hoc approach to coding assignments and see what happens. We'll need a place to post code, but I don't have a good suggestion for how to do that other than posting it in this thread and having me add it to the local repository (when it exists). Maybe somebody knows of some free webware that addresses the needs of web-based code development teams?--Percy

Thanks! I better start a list. People who have offered assitance so far: --Percy

Right - I was looking for something a bit more capable than Leo. Let me know when you've got something to look at. Okay, now I see the relationship. Current thinking is that they drift in through pores in the cell membrane. Pores are created whenever movement of the cell wall objects create non-adjacency. I'm expecting this behavior, creation of pores, to emerge. Cell wall objects that evolve motions that, as part of a coordinated effort with other cell wall objects, do a better job capturing food objects should compete better. This is behavior I've been taking a hard look at. The significant question is whether there should be one type of object that can take on different attributes, or whether there should be inherently different types of objects. If the former, then assuming attributes aren't fixed there is nothing to prevent a food object from changing into a waste object, or even a cell wall object or metabolic object.My current concept already assumes some of this type of behavior. For example, if a cell "dies" in that too many of its component objects have insufficent energy to execute their algorithems, then they simply follow the default drift algorithm and in effect become food.Ultimately I would like to achieve a design in which the properties of the objects emerge without ever having been anticipated by the designers. Not sure what you mean by "bound". I'm hoping for a conceptually clean design where objects feel like they have a physical manifestation. Depending upon the conceptualization, some of this disappears if objects can become bound to other objects as if they were properties or attributes.--Percy

Taken. Keep trying!--Percy

Hi Awinkisas!I don't have time for a good reply now, but I did want to briefly touch on this: I'm having real problems conceptualizing how one might have object type be a function of its properties, rather than having explicit object classes. But I've also convinced myself that it isn't necessary to figure out how to do this at the outset. If we figure out an effective way to do it down the road then we can add it in at that time, but for now having explicit object classes for each entity in the universe should work.The algorithms associated with objects will be algorithm objects rather than methods. I was planning to put them in lists which are traversed with iterators, but I'm open to other ideas, especially if they're more efficient. Probably the most important part of the program affecting efficiency is the interpretation of the algoriths - it had better be fast.Just as the algorithm list is not fixed (and neither are the algorithms themselves), the properthies or attributes won't be fixed either, and these, also, can be placed in lists, though if they're always just property/value pairs there's more efficient approaches. The important factor is that the properties of an object are not fixed - they can change during reproduction.I don't think there's such a thing as mutable classes in C++, but I'm not sure. What's a mutable class to you, and what does it look like in C++?--Percy

Hi, Awinkisas! I know you're talking about object algorithms, but this raises questions about my choice of C++ for implementation. Can you say more about this? There were two reasons I focused on C++ for implementation: I'm familiar with it, and it compiles to object code. But I'm not Java-familiar, and perhaps my assumption that Java is interpreted (ie, slow) is incorrect. A best case scenario would a an alife that can be distributed across the net because it is implemented in Java. And naturally if Java is compilable then it makes sense as the algorithm language, too, though by necessity for simplicity and efficiency we'd use only a subset.--Percy

I think you've hit upon the right approach. Are you at a point where you could enumerate a list of what some of these primitive functions might be? I can think of a few, but I'm unsure what level of granularity you had in mind:

• Increment(int& x)
• Decrement(int& x)
• Assign(int &x, Expression)
• Expression(...)
• Conditional(Expression(...))

Is this close to what you were thinking?--Percy

The neat thing about a sparse array is that only occupied locations are represented. The sparse array implementation has overhead, and so if you fully populate a sparse array it will take far more space than a normal array, but in that case you shouldn't be using a sparse array. You have to decide ahead of time whether your array is sparsely or densely populated. This was Mr Jack's point.Is our universe sparsely populated? At least initially, I think, the answer is yes. It would be neat to see organisms moving to occupy formerly empty regions.If in a sparsely populated universe you do not use a sparse array but instead just assign objects coordinates with 3D space, then determining adjacency becomes a significant issue, at its simplest involving iterating across all objects checking their position to see if you've collided with them or not, but naturally efficiencies are possible. But determining adjacency in a sparse array is easy.The drawback with a sparse array comes when which locations are occupied is dynamic, which is exactly our situation. I've played with sparse arrays before, but not of this type. But the sparse arrays I've played with have been implemented from associative arrays which are in turn implemented from hash tables, and it feels to me that nulling out a hash location should be easy. In other words, if an object moves from one grid location to an adjacent grid location leaving the former grid location empty, it should be possible to simply change the association in the hash table. Any grid location with a null hash reference is, of course, empty.I'm no expert on sparse arrays. Perhaps someone has experience with more efficient implementations?--Percy

I just wanted to let people know that I appreciate the responses and hope to reply soon. I seem to be in a busy period at both home and work, but though I haven't had time to respond I have been able to give a little thought to the feedback. I'm giving the cautions about being overly aggressive serious consideration, and I'm thinking about the design and implementation of the genetic algorithms and of sparse arrays.One brief comment about performance. I've been associated with many projects where performance was a significant concern, and some are still revenue products. Experience says you can eek out a performance improvement of about an order of magnitude every 4 or 5 years. This isn't necessarily good news for Cellscape, because since performance is a critical comparison criteria in the product area I work in, most of the effort goes into performance improvements. For Cellscape we probably want to focus our effort elsewhere. For this reason it makes sense to make design decisions that make performance as small an issue as possible while maintaining other design goals.--Percy