Percy's Alife Project

Hi, All!I apologize that this email isn't a reply to anyone specifically. It touches on issues raised by many of the responses.

2D Versus 3D

Regarding 2D versus 3D, 2D is just 3D with Z=1. We should be able to design the system so that it works for Z=n, including when n=1. This allows us to debug in the simpler 2D environment and then move to 3D to add greater variability and complexity - or not if we find that 2D is sufficient for our needs.

Object Types

I'm leaning toward having a single C++ object type whose actual type is is the sum of its algorithms and properties. Objects divide by fission into two objects. Both have the possibility of mutation (this is asexual reproduction, where there is really no such thing as parent and offspring).An object's type is the sum of its mutational history. For example, if an object's type is "a", then if one of them mutates during fission then the new type would be "a.a". If "a" mutates again during a subsequent fission then the new type would be "a.b". If "a.b" mutates during fission then the new type would be "a.b.a".A note about the type notation. The letters are unique at each level, just like the sections of a manual. For example, it's as if someone said to read section 1.1.3.1 - you know that each "1" is at a different level of organization. The same is true of my "a.a". The two a's are at different levels of organization and merely represent convenient unique names. I like the "a.a" form as opposed to the 1.1 form because I prefer representing object types as strings rather than variable length integer arrays, or worse, linked lists of some class type.The notation records the history of descent. Object "a.d.c.a" is descended from object "a.d.c". This allows us to easily tell the degree of relatedness of two objects. Object "a.d.c.a" and object "a.d.c.b" are descended from the same "a.d.c" object type. It might be helpful to think of types as species, or perhaps as subspecies, though I think this has the potential to be misleading since actual cells are comprised of many objects, and it is cell types that would be more analogous to species. Of course, a cell is merely the sum of its objects, and since each cell is a potentially unique combination of objects, each cell could be a unique cell type. Deciding when two cells are the same species could be difficult initially, but I expect that populations of cell species will eventually emerge.This approach permits an efficiency. Since all objects of the same type are identical with respect to algorithms and properties, each object type's algorithms and properties can be represented centrally and therefore never need be represented more than once, not only saving space but reducing the possibility of cache misses and going virtual. Naturally each individual object possesses unique parameters, such as available energy, temperature, mass, etc.

Algorithms

Regarding algorithms, I've given some careful thought to this and I think I have some good ideas. Let me describe them and see what people think. What I describe here *does* represent a change, however, and so I begin by first explaining the reason for the change.Our universe is a 3D array where each grid location is a cube. Each cube may be empty or may contain an object. Conceptually one object completely fills a single cube in our universe.Our objects have to be able to sense other objects. While movement can be random, at least some movement must be directed. For example, we want to able to move toward food. We can view our object's position as lying in the center location of a 3x3x3 array. We need to choose one of the 26 cubes adjacent to the center to move to, and we want to move to one which is adjacent to food (assume that none of these 26 cubes in our 3x3x3 array contain food).An algorithm to do this could easily be too complex to be practical. For example, here's an algorithm that looks for food two locations away on the X-axis and then moves to a location directly or diagonally adjacent: This is a big algorithm, and this is only for food two locations away on the X-axis. We need to check for food at all 98 cubes adjacent to the outside of our 3x3x3 cube, so we have to repeat this 97 more times.There's also the problem of the check for unoccupied cubes - there's no particular imperative for that check to emerge through random mutation, and most times it won't, so there would need to be an overseer function to check the result of object functions to make sure they don't move objects to unoccupied squares, or displace objects over ridiculous distances in a single step.Not only are there these problems, but we need such algorithms to *evolve* naturally from a much simpler starting point by random mutation. While this would happen eventually, we want something that simulates before the next millennium. Our operations are too primitive. They're analogous to simulating at the sub-atomic instead of the chemical level. We need higher level primitive operations.What would these primitive operations be? For moving toward food we could have this: It turns out that cell wall objects are the most complex in our universe in the way they move because they have to form themselves into cell walls. We can't have a cell wall object move off towards food while ignoring that it fills a critical role as part of the cell's containment vessel. Therefore what we really want for movement is this: In other words, I'm proposing that the very complex algorithm represented above be reduced to just a single function call: Move. Calling this function moves the object one grid unit, but in which direction? The Cellscape software implements the Move function, but what criteria should it use to decide where to move the object.For the purpose of making such decisions I introduce the concept of properties. Properties are set to values that allow functions like Move to make their decisions. Some proposed properties: And we need to introduce some complexity to perturb these decisions further. There are good reasons for this. For example, we want cell wall objects to move towards food when the food is outside the cell, but to ignore the food when it is inside the cell (the food will be consumed by metabolic objects). In the real world the nature of the outer cell wall is different than the inner cell wall, and we need the equivalent in Cellscape. Our cell wall objects must be asymmetric.So we introduce the concept of orientation. For a cube there are 24 unique orientations. Each of the six faces of a cube can have different properties. Now we're starting to get into some of the complex relationships that I was hoping would accompany 3D. Proposals for those properties: So we now see that objects have three primary components:

1. Algorithms that consist of calls to relatively high level functions like Move.
   ​
2. Properties, where properties can be attached to the entire object, or just to certain faces of the object. Properies have fixed values across all objects of the same type. A better term might be global properties.
   ​
3. Parameters, where just as with properties, parameters can be attached to the entire object, or just to certain faces of the object. Parameters can have different values for each object of the same type. A better term might be local properties.

Since each object possesses a type, we can define food, indeed any property or parameter, in terms of object type, eg: This means that the "goodness" of any cube is incremented by 10 by the Move function if it contains an object of type "b.d.a.b". However, objects of type "b.d.a" and "b.d.a.b.*" would also cause an increment in "goodness", but adjusted downward by some amount since the match isn't exact. This is like a wolf wanting to prey on deer, but a cow will do.Properties and parameters can, of course, mutate. For example, say the value of Food mutates: There may be no such object type as "b.e.a.b", which would make this a bad mutation. Or maybe "b.e.a.b" is a very common object type, making this a good mutation (unless "b.e.a.b" is a feared predator object which will turn the tables and make you food).

Emergent Properties and Parameters

Both properties and parameters can be thought of as name/value pairs. The only difference between them is that property values are global across all objects of type, while parameter values are potentially unique for each object of type. Clearly the above discussion assumes a number of predetermined properties and parameters, but what about allowing properties and parameters not anticipated by the programmers, and certainly not having any real world analogues, except by accident.I don't have any ideas on this to propose right now, but I throw it out there for comment.--Percy [Fix too-long line, grammar, and garbled presentation of ideas on algorithms. --Percy][This message has been edited by Percipient, 10-18-2003][This message has been edited by Percipient, 10-18-2003]

Hi, Rei, thanks for the feedback. Much appreciated.First I have to apologize. Evidently while changing the order of presentation I left out a paragraph or two that set the stage for presenting my algorithm ideas. I've already edited the post and it reads better than it did before I garbled it. What got lost was that I was only presenting the ridiculously complex algorithm in order to justify a move to higher level functions that would permit increased simplicity. I proposed replacing the complex algorithm with a single function call, Move, which draws upon properties and parameters of the object. Not sure what you mean by zero-indexed in the context of sparse arrays - I'm probably being dense. As described in earlier posts, I'm planning to use a sparse array, but feedback (that I haven't replied to yet but will soon) convinced me there are better sparse approaches than what I originally had in mind. Typical sparse arrays assume a fairly random scattering of occupied locations around the array space, while the situation in Cellscape is much different. It will frequently be the case that there will be both densely and sparsely populated regions. An occupied cube means it is highly likely that adjacent cubes are also occupied, and this can be taken into account in the implementation. This will still be a sparse array, but I now plan to implement it using a hierarchical clumping approach. Someone mentioned octants - I haven't investigated this yet, but just guessing at what it means the concept seems good. What I'd like to do is represent every unique evolutionary pathway. Oftentimes many objects would have the same pathway, and all such objects would include a pointer to a class holding both the pathway name and the functions and parameters representing that object type. I'm not planning to have any compilation step as part of the simulation. I was planning on using an associative array, but they're implemented using hash tables, so we're thinking along the same lines. I'm proposing both predefined parameters and arbitrary metadata (I like that term). Near the end of my post I think I indicated my desire for including arbitrary metadata (I called them emergent properties), but that I didn't have any specific implementation ideas along those lines at present.I probably wasn't clear that I plan to have both properties (same value for all objects of type) and parameters (unique value per object). Perhaps better terms would be global and local properties.My experience has been that careful design allows you to move more efficient implementations beneath well designed interfaces. I work in an industry whose products tend to have hundreds of thousands of lines of code, and which are used on machines with gigabytes of RAM and terabytes of disk, and which nonetheless oftentimes take a week to run. Adding efficiency and performance to a new feature after initial introduction is something we often do. I share the memory and performance concerns, but would prefer not to let such considerations overly influence the initial specification. You're making me feel like I just proposed a perpertual motion machine! Let me know if my responses indicate I'm just as delusional. While I don't find the field of cellular automata particularly illuminating to what I'm trying to do, the similarity of my approach has not escaped me. While I find it interesting that complex behaviors and structures can emerge from simple rules, and that these have been found to in many cases recreate behaviors and structures found in real life, the fact of the matter is that nothing about real life is simple. It's interesting that simple rules can replicate some things about real life, but that doesn't mean that real life is following anything like the same rules. The positive results of cellular automata in helping us understand some aspects of life notwithstanding, I personally don't believe that the immense variety and sheer richness of real life cell behavior emerges from cellular automata. What a wonderful image, and this is exactly the problem I've been struggling with. I think the approach I've developed while wrestling with this problem will be valuable in helping attain an emergent result. The idea is to let behaviors and structures emerge, and not to design them in ahead of time.I *would* like to implement *some* physics. Temperature is one possibility I find appealing, since organisms can evolve behavior to follow temperature gradients, be affected by temperature, and can die at the extremes.That being said, I should probably repeat something I said in an earlier post, that what I'm proposing is "a life", not "the life". In other words, I hope that evolving lifeforms and a self-sustaining ecology will result, but I'm not expecting nor attempting lifeforms as realized by life on earth.So by the same token, while I would like to have *a* physics, it wouldn't be *the* physics. And it is important that properties of compounds emerge and not be predetermined. I don't know how to do this yet, but I haven't yet given it any thought. It doesn't seem impossible, and probably has even been done before. Hopefully my correction to the algorithm section of my earlier post alleviates some of this concern. The feeling of complexity may also be because the approach has evolved during the discussion on this thread, which is a good thing. The very useful feedback I'm getting from you and others is not what I anticipated when I originally began the thread. I actually thought there was a strong possibility it would be ignored. Anyway, the current approach feels pretty simple to me at this point, and when I finally am able to release the base object definitions I think that will be pretty clear.Thanks again for the feedback - this is really helpful.--Percy

Will do! Current project staff, in alphabetical order:

• awinkisas
• IrishRockHound
• Mr Jack
• NosyNed
• Percy
• TheoMorphic

I haven't touched on this yet, but in the back of my mind I've been assuming that truly interesting simulations could only be carried out using distributed computing. I believe one of the early alife programs, maybe it was Tierra, had a distributed Internet version, and there must be others as well. I share Rei's concern about internode bandwidth, and to be honest I hadn't thought about an Internet version so much as just a network version. My company has 3000 PCs on a dedicated high-bandwidth network, and I thought it would be kind of neat to use them. After all, the PCs don't do much at night - almost all our nightly regression tests run on workstations. One important factor would be dividing the simulated universe at boundaries where bandwidth requirements are minimal. It feels very similar to the problem of distributed simulation of digital systems where there are certain rules of thumb that you follow, such as not splitting the simulation at the instruction cache bus. So I guess you would divide simulated universes at the equivalent of mountain ranges and deserts. I can see a couple problems with this approach:

1. It doesn't address checking the adjacency of an unoccupied cube. When assessing whether the adjacent unoccupied cube is a good candidate to move to, you have to determine whether food or danger or whatever is adjacent to that cube.
   ​
2. It only works for direct adjacency and not diagonal adjacency.

Let me know if you think of ways around these issues.I'll make a short comment about my current thinking (notice I say "thinking" and not "conclusions") about representing the universe. Someone earlier made reference to something they called an octant. I don't really know what this is, but my guess is that it's an 8x8x8 cube. And it's a real array, not a sparse array, which makes it very efficient, as opposed to a sparse array where every location has to be referenced through the hash table, even if its an adjacent location. And you could have a hierarchy of octants, where you could have an 8x8x8 array of octants, in this case sparsely occupied and probably implemented with a hash table.My thinking hasn't gone beyond trying to imagine what was meant by octants (a quick Google wasn't helpful) - I haven't made any serious effort to assess how successful this approach might be, but it *feels* promising and worth assessing.--Percy

I should comment that I will be returning to this effort as soon as demands in a couple other areas of my life settle down a bit, probably within a few weeks. Thanks again to everyone for the very helpful feedback and offers of help.--Percy