|
Register | Sign In |
|
QuickSearch
EvC Forum active members: 45 (9208 total) |
| |
anil dahar | |
Total: 919,519 Year: 6,776/9,624 Month: 116/238 Week: 33/83 Day: 3/6 Hour: 0/0 |
Thread ▼ Details |
|
Thread Info
|
|
|
Author | Topic: Percy's Alife Project | |||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
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.
Technical Issue: Since a universe of reasonable size (say, a million by a million by a million grid units) could contain a gazillion grid locations, this represents a serious software design issue. Each grid location of a large universe cannot be explicitly represented and still fit in available memory, so we must use a sparse array for the universe, but how would one represent, for example, varying temperature across the universe using a sparse array? It seems as if you would need explicit representation of the temperature of each grid location, but imagine the amount of memory required if you did this. For example, if the universe has 1018 cells you would need 1018 bytes to represent the temperature uniquely for each grid location. Since this is 9 orders of magnitude larger than the amount of physical memory in most PCs, this wouldn't be possible. And it's probably more than 7 or 8 orders of magnitude larger than the amount of virtual memory in most PCs, so even if going virtual were acceptable it still wouldn't be possible. So we have to use sparse arrays, but the temperature and other properties must be represented using some broad brush approach. For example, one could imagine a function where you pass it the address of the grid location and it returns the requested property value which it derives by some means, probably from an equation or function or approximation of some type. 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:
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 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 there are currents, then these, too, could be taken into account: int xCurrent = GetXCurrent(xpos, ypos, zpos); 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)) { There's plenty more, but that's all I have time to type in for now. --Percy
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
Syamsu writes: So are you going to put a comparison between the digital organisms in the program as part of how the world functions? (other then just for providing comparitive information to the user) 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
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
IrishRockhound writes: Percy, what language are you using? It looks almost like Java. 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.
Are you doing a website to show it off, or are you just keeping people updated on EvC? 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.
Do you want help programming? 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
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
Parasomnium writes: If I may make a few suggestions: try to keep things simple at first, don't begin with a whole universe full of diverse complicated objects. Instead, prove the concept first, by creating a 'test tube' with a limited number of simple objects, then gradually increasing the number of parameters and the number and complexity of objects. A house was within his means, but he wanted a mansion, and so in the end he had neither. 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.
One of the cheapest ways of keeping the memory and processing demand in check is to give up the third dimension. An added bonus of that approach is that you need not worry about 3D representation on screen. You want to concentrate on the principles of A-life after all. 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...
Also, I think you should not program too much behaviour; let some, if not most behaviour emerge on its own. First of all, it's much more interesting that way. And secondly, if you try to program all behaviour, you'll probably be tinkering with it endlessly and it'll never work quite the way you expected. Better just give the objects some properties and see how they interact. Let 'nature' run its course. You do need a certain minimum of algorithms of course, or nothing much would happen, but you should try to limit the algorithms to a set of generic 'laws of nature' rather than give specific, detailed descriptions of how things should behave. 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.
Some questions you should also consider:
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
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
Mr Jack writes: I strongly recommend giving the food particles some kind of 'inertia', purely random walking tends to just produce little squiggly 'knots'. 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.
Looks very cool. How long do you think it'll take? 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
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
awinkisas writes: Sounds like an exhausting but fun project. 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.
I hope this helps and if you need any additional help I would be glad to assist. For me programming is a hobby as well as a job. I've done some work in C++ but have stuck with VB for my bread and butter. 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."
Lately in my spare time I've been working on a NLP chatterbot. I've been wanting to hook up a chatterbot to a thread here. Ever heard of Leo? Is your chatterbot better? --Percy
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
NosyNed writes: It's been a few years, I wouldn't mind a chance to brush up on my C++. And, btw, Java is solidly OO and has most of what C++ has. (It is a hell of a lot simpler too) 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
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
If you need any help with the programming, I egotistically offer my assistance. (What with being a working C++ programmer and all that). Thanks! I better start a list. People who have offered assitance so far:
awinkisas IrishRockHound Mr Jack NosyNed --Percy
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
awinkisas writes: I hadn't heard of Leo but I checked it out. It's amazing that very simple rules, compounded, can create complex results. If only it was somewhat self-aware (the holy-grail of AI programmers). My bot is more complex... Right - I was looking for something a bit more capable than Leo. Let me know when you've got something to look at.
Some image compression algorithms average all the colors over a small area and then infer the gradient between adjacent areas when rendering. Smaller areas are used near regions where there are steep gradients i.e. near object edges. A 3D temperature gradient could be treated similarly but using a local max or min rather than averaging. Okay, now I see the relationship.
How do food objects get into cells? 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.
Instead of logically separating food and waste objects, how about making them the same object, say a matter object. This way cells could potentially treat all matter as food. 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.
Each matter object could have an energy object bound to it and this would be the maximum amount of energy the cell could extract. 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
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
Cthulhu writes: How about Lifescape? Taken. Keep trying! --Percy
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
Hi Awinkisas!
I don't have time for a good reply now, but I did want to briefly touch on this:
Static classes can be derived from the base class but how would new properties be added to create new objects. In post #1 you talked about attaching algorithms to objects. As far as I know C++ does not allow for dynamically adding new methods to classes at runtime. You could have an array of pointers to functions but each function would have to return the same value. This could work if the functions only returned a boolean indicating success but had side-effects on parameters. 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
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
Hi, Awinkisas!
I did some research and found that java as well as languages using the .NET framework expose a compiler class. If the algorithms are written using any of these languages they can be compiled on the fly and executed. The compilers they implement are probably better than anything we could come up with. Ideally the algorithms would be compiled once and only recompiled if they are modified. Something to think about. 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
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
awinikisas writes: There might be a way to eliminate the need for dynamic compilation altogether. I propose that we create a set of simple algorithms, encoded as functions/methods, that can be used in combination to perform more complex tasks. Similar to the 4 base pairs of DNA that can be ordered differently to create different proteins. This way we don’t have to worry about recompiling modified algorithms. Instead larger algorithms are built up out of the smaller base set of predefined algorithms. Sort of like a RISC computing approach. The ordering of the base set algorithms could be modified using the GA paradigm as described above. 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:
Is this close to what you were thinking? --Percy
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
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
|
|||||||||||||||||||||||||||||||||||||||||||||
Percy Member Posts: 22955 From: New Hampshire Joined: Member Rating: 7.1 |
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
|
|
|
Do Nothing Button
Copyright 2001-2023 by EvC Forum, All Rights Reserved
Version 4.2
Innovative software from Qwixotic © 2024