Author Topic: Hyperspeed Mode  (Read 21932 times)

Offline jknilinux

  • Bot Destroyer
  • ***
  • Posts: 468
    • View Profile
Hyperspeed Mode
« Reply #45 on: February 13, 2010, 11:02:59 AM »
Quote from: Houshalter
Has anyone ever created a self replicating pattern in CGoL that isn't completely destroyed by a random mutations. For that matter has anyone ever created a self replicating pattern ever? And what kinds of interesting behaviour are you talking about. Anytime I run the game of life, my starting patterns sizzle out into a bunch of stills and oscillators, most of which are not interesting. I think in order to create any of the interesting patterns your describing, you need to change the rules.


nope, no-one has ever created a self-replicationg CA for the GoL, though there are many CAs with self-replication. There's also a CA that has a known universal constructor, which when programmed with the right code, can replicate itself.

And define "interesting patterns"...

Offline jknilinux

  • Bot Destroyer
  • ***
  • Posts: 468
    • View Profile
Hyperspeed Mode
« Reply #46 on: February 13, 2010, 11:14:31 AM »
Actually, better yet, we should define "interesting behaviour"... there might be some miscommunication here.

I'm referring to any CA where a sort of "physics" develops, similar to the physics required for DB, where moving and stationary objects arise. I'm not suggesting finding a CA with fully self-replicating entities capable of evolution, I'm suggesting just finding a CA to provide a habitat for the bots. I was thinking the bots could be a sort of "black hole" of, say, 100 cells arranged in a circle. According to their DNA, they can change their shape to anything they want, and add or subtract cells from themselves. Any CA entity that is under it, such as a glider that hits it, disappears. Consuming cells of a certain state, say the "dying" cells of Brian's Brain, gives energy. I'm suggesting using dieing cells as energy since, in brian's brain, they indicate novel patterns emerging. And, of course, bots can shoot gliders and excrete still-lifes/oscillators.

EDIT:

Interesting side note: using CA physics eliminates many physics problems we were trying to solve before. For example, since spaceships (aka photons) are so common in brian's brain, plants can easily evolve as stationary bots waiting for spaceships, for example, coming from the top of the screen. Instantly, shadows and other phenomena similar to real-life occur spontaneously, without the need for ray-casting. This is the sort of spontaneously emerging physics I was referring to. Of course, there's gonna need to be some way to feed off of other bots, which I'm not sure of.

All in all, I think a CA-based implementation of DB is much more elegant than our current method of programming in the physics by hand. The goal of DB, after all, is for order and novelty to develop out of chaos. Not to mention that it'll be faster.

EDIT2:

EXAMPLE PLANT DNA

1: expand size into a straight line.                                                                                 //maximize surface area for absorbing spaceships falling from above
2: for each cell:
     1: if hit by photon, then grow upward rand cells                                                        //grow upward, forming plant-like structures, avoiding shadows
3: cond energy>5000, delete 5 middle cells                                                                  //reproduce
4: cond energy<500, delete cells until energy>500 or bot is less than 100 cells long.        //eat body if energy too low


For animals, you can just fire spaceships at still-lifes, and consume the ensuing chaos.

EDIT3:

The best CA rule I've seen is known as starwars, based off of brian's brain but less chaotic, yet more interesting than GoL. Remember, GoL is just the most studied CA, not necessarily the best. Starwars forms interesting growing fractal structures, lots of spaceships, and highly ordered still-lifes with a constantly growing and changing exterior.

Brian's brain is also interesting, but it is really chaotic. Random configurations don't die out after a very long tie, so plants will have it too easy here.
« Last Edit: February 13, 2010, 06:57:44 PM by jknilinux »

Offline Houshalter

  • Bot Destroyer
  • ***
  • Posts: 312
    • View Profile
Hyperspeed Mode
« Reply #47 on: February 13, 2010, 09:37:51 PM »
Space ships should be easy to form since they are so essential to the enviroment. For that matter there should be lots of possible spaceships, not just one or two. Also there should deffinitely be an element of randomness in the sim. How about a cell that changes the states of the cells around it, but is unpredictable of when it will do this and what cells it will change when it does. Universal turing machines should be simpler to build in this sim, maybe there can be logic gate type cells. Also, there could be a way to make a replicating pattern in CGoL. Get an Artificial intelligence like Eurisko to design it.

Offline jknilinux

  • Bot Destroyer
  • ***
  • Posts: 468
    • View Profile
Hyperspeed Mode
« Reply #48 on: February 14, 2010, 10:53:13 AM »
Quote from: Houshalter
Space ships should be easy to form since they are so essential to the enviroment. For that matter there should be lots of possible spaceships, not just one or two. Also there should deffinitely be an element of randomness in the sim. How about a cell that changes the states of the cells around it, but is unpredictable of when it will do this and what cells it will change when it does. Universal turing machines should be simpler to build in this sim, maybe there can be logic gate type cells. Also, there could be a way to make a replicating pattern in CGoL. Get an Artificial intelligence like Eurisko to design it.

I mentioned above that there is no known self-replicating pattern in GoL. Also, there is more than enough randomness in current CA rules for interesting things to happen. And remember, we're not looking for something that produces infinite novelty, it needs to settle into a steady state so it provides a decent environment for bots to evolve in.

Offline Houshalter

  • Bot Destroyer
  • ***
  • Posts: 312
    • View Profile
Hyperspeed Mode
« Reply #49 on: February 14, 2010, 03:58:45 PM »
The biggest problem is the speed of light thing. I notice this in darwinbots to. The larger a creature is, the more time it will take for it to respond to its enviroment. In darwinbots a multibot can't have a brain because it could take ages for info to work its way up through the organism and then be proccesed by dozens of neurons, and then sent back out. Same problem goes in any ca. The only solution I can think of is if the organisms has a brain which constantly pumped info on how to surive in the enviroment to the cells on the outside. One last thing, organisms should be able to thrive in chaotic enviroments, not be easily consumed by them. This is the biggest problem i notice in CGoL.

Offline jknilinux

  • Bot Destroyer
  • ***
  • Posts: 468
    • View Profile
Hyperspeed Mode
« Reply #50 on: February 15, 2010, 11:43:50 AM »
Actually, I don't see a problem with the speed-of-light thing... Having a speed of light makes the sim more realistic, and it won't have a performance penalty assuming we use the hashlife algorithm.

Also, I'm saying that a chaotic environment will be too difficult for a bot to evolve in. They won't get consumed by the CA, since their physical implementation is not bound by the regular CA rules. It's just that you can't evolve consistent behaviour when your environment is too chaotic... we still need still-lifes and consistent moving objects for the bots to interact with.

Numsgil, any input?

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Hyperspeed Mode
« Reply #51 on: February 15, 2010, 12:29:35 PM »
The speed of light thing... the problem is that it's really slow.

A CA based Darwinbots would undoubtedly work, with a bit of tweaking and the like, but I'm just really not a fan of CA.

Offline Houshalter

  • Bot Destroyer
  • ***
  • Posts: 312
    • View Profile
Hyperspeed Mode
« Reply #52 on: February 15, 2010, 04:13:32 PM »
Umm... This has nothing to do with darwinbots really, just the theoretical CA you mentioned. Oh, and tell me if im making any sense with this. I was thinking about using a CA to simulate biology realistically. There would be different "protiens" that could be created by assembling different types of cells. There would be a protien for cell membranes that would be mostly impeneratable. You could have a plant or crystal type cell that would grow like a virus as it collects random flying debris. Then you could have herbivore type organisms which would manufacture special enzymes that would deactivate the cystal and transform it into plain cells, which could be changed and assembled into more protiens. Carnavores would attack the herbivores with more special enzymes which would break through the cell membrane and do chaos to the cells internal machinery. The carnavores would then pull in the different protiens that were flying around in the chaos and use them for its own purposes, or reject them, grabbing on to as many unproccessed cells as possible.

Offline jknilinux

  • Bot Destroyer
  • ***
  • Posts: 468
    • View Profile
Hyperspeed Mode
« Reply #53 on: February 16, 2010, 06:16:02 PM »
Quote from: Numsgil
The speed of light thing... the problem is that it's really slow.

A CA based Darwinbots would undoubtedly work, with a bit of tweaking and the like, but I'm just really not a fan of CA.

Do you mean slow in the real world, for us? Or for the bots?

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Hyperspeed Mode
« Reply #54 on: February 16, 2010, 07:08:30 PM »
Speed of light in a CA is quite slow.

Offline jknilinux

  • Bot Destroyer
  • ***
  • Posts: 468
    • View Profile
Hyperspeed Mode
« Reply #55 on: February 16, 2010, 10:46:51 PM »
Quote from: Numsgil
Speed of light in a CA is quite slow.

What I meant is, if it won't have a performance impact since we're using the hashlife algorithm, the only problem will be for the bots. And if the bots' DNA execution runs at a similar rate to the speed of light, it won't affect the bots either. Remember, these sims run into quadrillions and quintillions of cycles quickly, so long as you use hashlife. If anything, the DNA execution might not be able to keep up with the speed of light in the sim. Alternatively, we could execute the bot's DNA every, say, 10 cycles instead of every cycle. That way the speed of light will be much faster for the bots.

Sorry Nums, I hope we're not annoying you 0:D
« Last Edit: February 16, 2010, 10:50:31 PM by jknilinux »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Hyperspeed Mode
« Reply #56 on: February 17, 2010, 12:51:36 PM »
Quote from: jknilinux
Sorry Nums, I hope we're not annoying you 0:D

A little   But I don't mind too much.

Quote
What I meant is, if it won't have a performance impact since we're using the hashlife algorithm, the only problem will be for the bots. And if the bots' DNA execution runs at a similar rate to the speed of light, it won't affect the bots either. Remember, these sims run into quadrillions and quintillions of cycles quickly, so long as you use hashlife. If anything, the DNA execution might not be able to keep up with the speed of light in the sim. Alternatively, we could execute the bot's DNA every, say, 10 cycles instead of every cycle. That way the speed of light will be much faster for the bots.

Hashlife for GoL can run in to crazy large numbers of cycles, but if you try to hashlife Darwinbots you're not going to get that large number of cycles.  Even if you made the physics free, DNA execution and other stuff (body management, dead/alive checks, etc.) would turn up as performance bottlenecks.  A super optimized CA running something as complex as Darwinbots might achieve maybe 1000 cycles/sec or something like that.  That's an educated guess on my part, though, so take it with a grain of salt.

But I don't think you could make it even that awesome.  See, GoL has binary states for the cells.  But you need more info than that for something like Darwinbots.  You need empty cell, cell for bot 1, cell for bot 2, cell for static geometry, etc.  GoL scales well because of common patterns you can find, but as you increase the number of states a cell can have that number quickly balloons.

So it would work, but I don't think it's necessarily the magic bullet you're making it out to be.  But you could always take Evolve 4.0 and modify the source to use hashlife techniques, and see the resulting speed differences first hand.

Offline jknilinux

  • Bot Destroyer
  • ***
  • Posts: 468
    • View Profile
Hyperspeed Mode
« Reply #57 on: February 17, 2010, 06:34:43 PM »
OK, so here's a port of DB I'm thinking of:

a 2D grid running a cellular automata and, using the hashlife algorithm, will run at (with conservative estimates) 100 cps

A third dimension contains the actual bots and their DNA, with no totalistic cellular automata requirements. However, the bots move and interact in the cellular automata dimension. It's not so much a third dimension as a parallel second dimension.

Bots are, by default, a large cluster of cells (say, 100), but can change their shape and size to anything possible, regardless of if the shape is viable in the rules of the cellular automata, because any shape a bot takes on is stable

The speed of light is, somehow, fast enough compared to the bots DNA execution to be realistic. For example, let's assume we have a plant like A. minimalis that has a very small genome. Once the DNA has been assembled/compiled, 10 cycles passed by in the sim. So, the bots' DNA is executed once every 10 cycles. A more advanced bot, like seasnake, might take 100 cycles to finish assembling, at which point the bot will finally execute the DNA. Or, all DNA is executed every 100 cycles. There are many ways to speed up the speed of light compared to the bots, without a performance penalty.

Bots gain energy by "eating" cells

Bots can create structures out of cells. For example, an herbivore might create spaceships and fire them at still-lifes. The resulting chaos creates many new cells for it to feed on. Or, a bot firing a spaceship at an herbivore causes a larger spaceship to bounce back, similar to the shooting method we currently use in DB.

One important difference between this and evolve 4.0 is that the bots live in a much more "analog" world; the bots cannot occupy single cells, but must occupy at least, say, several hundred. I think one of the major drawbacks with E 4.0 is that most bots were made up of just dozens of cells.

Basically, if you want it summarized in a single sentence, it'll combine the interesting, analog environment of DB with the speed of a CA.

I'm wondering if you think this is a viable project, and if it will fail like E 4.0 (last I heard, it was abandoned). How difficult is this? How difficult is it to merge completely different projects, such as DB and E 4.0, into a single program? Why doesn't evolve 4.0 run at 1000 cps?

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Hyperspeed Mode
« Reply #58 on: February 17, 2010, 08:45:48 PM »
Quote
I'm wondering if you think this is a viable project, and if it will fail like E 4.0 (last I heard, it was abandoned).

It's a totally reasonable project a single dedicated coder could probably complete.  I think Evolve died because Stauffer lost interest or had real life intervene, etc.

Quote
How difficult is it to merge completely different projects, such as DB and E 4.0, into a single program?

Practically impossible.  You'd be much better off starting from scratch.

Quote
Why doesn't evolve 4.0 run at 1000 cps?

How fast did it run?  I never really played with it enough to get a sense of its speed.

I'd have to profile the program to tell you for sure (which, let's be honest, I'm not going to do ) but my guess is that either:

1.  Stauffer wasn't as aggressive with optimizations as he could have been.  
2.  Or that executing KFORTH for each organism was the bottleneck.

#2 seems more likely to me, though it's probably a combination.  See,the problem with optimization is that even if you super optimize the program's bottleneck, it just means another part of the code becomes the bottleneck.  There's always a exponential distribution for time spent executing different functions.  So when you make a certain area of the program 10x faster, it means the program as a whole is maybe 30% faster and the bottleneck has moved to some other completely unrelated function.  If you make that function a million times faster, the program as a whole is now 35% faster.  There's this level of diminishing returns.

There are probably optimizations to be made in the execution of KFORTH programs.  Same for Darwinbots DNA code.  But then you delve in to something like compiler design and writing a JIT compiler, which are not trivial tasks at all.  Just by themselves, they'd be ambitious single programmer tasks.

Likewise with the CA aspects of Evolve, some clever programming could probably make the CA update part of Evolve much faster, but the data structures and algorithms involved can quickly become a whole project in themselves.

But let's assume that you have unlimited programming resources (you're some AAA game studio) and you want to make an ALife sim.  The CA approach and the continuous physics approach have different inherent strengths and weaknesses.  Basically CAs scale with the size of the universe, more or less linearly.  While physics scales with the number of rigid bodies (naively O(n^2), but if you're smart it can also be a linear scaling).  For small sized DB sims, CA would probably be faster.  For a monster sized universe with a few rigid bodies, the physics is much faster (for sparse worlds, I mean).  The CA approach also parallelizes much easier, so it lends itself well to using graphics cards, for instance.

It's very similar to rasterizing vs. ray tracing for graphics actually.

For Darwinbots, I'm specifically avoiding CA related anything.  Even things like substances diffusing through the environment won't be handled by CAs (even though they are admittedly quite common in fluid sims).  Because I wanted to allow for arbitrary sized universes.  But for alife in general, CAs are actually far more common than physically based sims (I'm thinking Framsticks vs. Avida).
« Last Edit: February 17, 2010, 08:47:05 PM by Numsgil »

Offline jknilinux

  • Bot Destroyer
  • ***
  • Posts: 468
    • View Profile
Hyperspeed Mode
« Reply #59 on: February 17, 2010, 09:12:57 PM »
How many bodies does it take for a physics approach to be faster than a CA? Also, are you referring to a very complex pattern in a CS versus few bodies in the large sim? If you don't want to explain it, maybe you could give me a keyword to search on google/wiki? Thanks!

BTW did my explanation of the possible implementation make any sense?

Also, thanks for putting up with all my annoying questions, I swear I'm almost done!
« Last Edit: February 17, 2010, 09:15:02 PM by jknilinux »