Darwinbots Forum
Code center => Suggestions => Topic started by: Houshalter on January 22, 2010, 08:31:50 PM
-
The no. one constraint for evolution in darwinbots is speed, closley followed by population size. Actually population size might be the biggest constraint, but the only reason you can't have lots of bots is because it slows it down, hense speed is important. I recently came across conways game of life, which im sure most of you are familiar with, and somehow i came across this (http://en.wikipedia.org/wiki/Hashlife). Apparently theres away to make conways game run really really fast. I was wondering if something like that would or could apply to darwinbots. I don't really understand it though. Its kind of beyond me with all the technical terms.
-
Yes and no. The core simulation is physics based, which can't really be effectively hashed like that because the number of patterns is practically infinite.
But the DNA execution, which takes upwards of 30-50% of the execution time depending on what's going on (for zerobot sims it's probably like 70-80% if nothing is going on), could certainly be hashed/cached. If we ran a "compiler" over the raw DNA and got it down to optimized native code it would run much faster. This is very similar to what Java and .NET do to make code that's written for their "virtual machines" run at speeds competitive with native code. If the DNA is completely deterministic (contained no rand commands basically) we could just hash common input sysvar patterns to common output sysvar patterns.
-
Infinite patterns doesn't mean you can't use shortcuts to navigate through the mess. I still don't understand hashing but we aren't the first to try to optimize computer resources. I was thinking along the lines of a genetic algorithm to create an algorithm to create these 'shortcuts' or heuristics. If it made a heuristic that was wrong then it would be punished, but, for example, if it figured out a bot did the same thing every cycle regardless of its input then it could skip executing the bots dna and save proccessing power. The algorithm would be trained for accuracy in creating valid heriustics, and how much time it wasted running itself vs. how much time it saved by creating and applying heuristics. A seprate part of the program would be a heuristic validator which would also be trained with a GA. This would attempt to find invalid heuristics that had been created, therefore being a judge of the first part of the the fitness function. Basicly it would look for a situation where the heuristic is false. As you said there are an infinite number of possible patterns, so it would have to search for the one that proves it wrong with limited cpu cycles. You would have to give the 'invalidator' (for lack of a better name) full control over a miny simulation, with access to every single possible variable, like costs, bot positions, etc. That will be the most complicated part. Once you've evolved the heuristic generator you'd have to hard code it into the program. Preferably youd have the option in db to use the algorithm or not, and an easy update system so you could update your db with the latest version of it. This is a bit far-fetched and way beyond my ability to program, maybe something possible in the future.
-
Infinite patterns doesn't mean you can't use shortcuts to navigate through the mess. I still don't understand hashing but we aren't the first to try to optimize computer resources.
Physics is a really really studied problem. Because it's a billion dollar industry for video games and other things.
The article you linked is basically leveraging the fact that lots of the patterns in the game of life are repetitive. So you can store the results for a particular pattern and use them again and again without needing to recalculate them. In physics simulations, though, patterns practically never repeat themselves.
The exception to that is that physics situations from one frame to the next are usually very similar. So most physics engines cache that information across frames (temporal locality (http://en.wikipedia.org/wiki/Locality_of_reference)).
I was thinking along the lines of a genetic algorithm to create an algorithm to create these 'shortcuts' or heuristics. If it made a heuristic that was wrong then it would be punished, but, for example, if it figured out a bot did the same thing every cycle regardless of its input then it could skip executing the bots dna and save proccessing power. The algorithm would be trained for accuracy in creating valid heriustics, and how much time it wasted running itself vs. how much time it saved by creating and applying heuristics. A seprate part of the program would be a heuristic validator which would also be trained with a GA. This would attempt to find invalid heuristics that had been created, therefore being a judge of the first part of the the fitness function. Basicly it would look for a situation where the heuristic is false. As you said there are an infinite number of possible patterns, so it would have to search for the one that proves it wrong with limited cpu cycles. You would have to give the 'invalidator' (for lack of a better name) full control over a miny simulation, with access to every single possible variable, like costs, bot positions, etc. That will be the most complicated part. Once you've evolved the heuristic generator you'd have to hard code it into the program. Preferably youd have the option in db to use the algorithm or not, and an easy update system so you could update your db with the latest version of it. This is a bit far-fetched and way beyond my ability to program, maybe something possible in the future.
This isn't something genetic algorithms are good at. The core of most physics engines is a "constraint solver", which is basically doing a sparse matrix inversion. Which is a well studied problem with very well studied answers. Genetic algorithms are more for situations where the problem is quite complex and there's a lot of data and a lot of noise in the data and you want to find a good best guess. That just doesn't describe physics.
-
Physics is a really really studied problem. Because it's a billion dollar industry for video games and other things.
But most video games run fast enough to work in real time and could probably run faster. Darwinbots is a bunch of circles moving past each other, sometimes running into each other or shooting at each other. Any chance any of that can be applyed to them?
The exception to that is that physics situations from one frame to the next are usually very similar. So most physics engines cache that information across frames (temporal locality).
Exactly. The bots can change course frequently but things like shots just move in a straight line. You know their direction and speed so you can accuratley calculate where they will be in x cycles. If a shot is drifting through space with no bots around it then why bother calculting its position every cycle. The thing is there are exceptions to this rule, like what if the user places a bot right in front of the shot, what if a teleporter moves another bot into its way. So hard coding all these individual short cuts, including their exeptions gets complicated. A GA could find the optimal way to handle it. Remember where evolving an algorithm to create these heuristics, not the actual heuristics themselves. That way different simulations will have different heuristics. A large sim could easily do the shot thing i just mentioned because most shots just drift into space anyway, but a small sim where the shots are constantly moving and most hit bots anyways, could use a different heuristic to calculate the shots correctly, simmilar to but not the same as the first one. As i understand it, you've already put in shortcuts like these to speed up sim size in larger sims.
This isn't something genetic algorithms are good at. The core of most physics engines is a "constraint solver", which is basically doing a sparse matrix inversion. Which is a well studied problem with very well studied answers. Genetic algorithms are more for situations where the problem is quite complex and there's a lot of data and a lot of noise in the data and you want to find a good best guess. That just doesn't describe physics.
Youre right. DB is essentially a GA, but without a fitness function. How many zerobots have evolved into perfect bots with intelligence and learning. However the problem is kind of complex as you mentioned and noise doesn't make a difference so long as the evolved program is errorless (wich is it's first fitness function.) Given enough time, it could come up with a very good system of speeding up db that a human never would've thought of, maybe couldn't even understand. Thats the beauty of GAs.
-
Physics is a really really studied problem. Because it's a billion dollar industry for video games and other things.
But most video games run fast enough to work in real time and could probably run faster. Darwinbots is a bunch of circles moving past each other, sometimes running into each other or shooting at each other. Any chance any of that can be applyed to them?
Video games can't really run faster. Trust me, games like Uncharted 2 are literally pushing the hardware as hard as it can be pushed. Games might also look complex, but under the hood it's collisions between capsules and triangles and other primitives like that. Not at all different from Darwinbots' collisions between circles. So there's a lot of literature and resources available on physics that I've digested and will use for DB3, and even DB2 isn't doing it that inefficiently.
The exception to that is that physics situations from one frame to the next are usually very similar. So most physics engines cache that information across frames (temporal locality).
Exactly. The bots can change course frequently but things like shots just move in a straight line. You know their direction and speed so you can accuratley calculate where they will be in x cycles. If a shot is drifting through space with no bots around it then why bother calculting its position every cycle. The thing is there are exceptions to this rule, like what if the user places a bot right in front of the shot, what if a teleporter moves another bot into its way. So hard coding all these individual short cuts, including their exeptions gets complicated. A GA could find the optimal way to handle it. Remember where evolving an algorithm to create these heuristics, not the actual heuristics themselves. That way different simulations will have different heuristics. A large sim could easily do the shot thing i just mentioned because most shots just drift into space anyway, but a small sim where the shots are constantly moving and most hit bots anyways, could use a different heuristic to calculate the shots correctly, simmilar to but not the same as the first one. As i understand it, you've already put in shortcuts like these to speed up sim size in larger sims.
This isn't something genetic algorithms are good at. The core of most physics engines is a "constraint solver", which is basically doing a sparse matrix inversion. Which is a well studied problem with very well studied answers. Genetic algorithms are more for situations where the problem is quite complex and there's a lot of data and a lot of noise in the data and you want to find a good best guess. That just doesn't describe physics.
Youre right. DB is essentially a GA, but without a fitness function. How many zerobots have evolved into perfect bots with intelligence and learning. However the problem is kind of complex as you mentioned and noise doesn't make a difference so long as the evolved program is errorless (wich is it's first fitness function.) Given enough time, it could come up with a very good system of speeding up db that a human never would've thought of, maybe couldn't even understand. Thats the beauty of GAs.
It's precisely because you can describe the position of a shot at cycle X that makes it inefficient for a genetic algorithm. Collision detection resolves basically down to numerical root finding, which is a problem with well understood solutions. Collision response is sparse linear algebra, which also has well studied solutions. If there are any shortcuts, they come from making simplifying assumptions about the underlying math (eg: use a quadratic approximation to a sinusoidal curve). So underlying all the physics is just a lot of algebra, calculus, and linear algebra, which humans and machines already know how to do very well. All these problems have well established algorithms to find a solution.
Compare this with something like learning to fly a 747. There are thousands of knobs and readouts, and it takes a human years of study to be able to use these to fly a plane. There isn't even a rote solution to some problems, because they haven't ever come up before. So being a pilot takes a strong combination of improvisation and experience. It's these sorts of problems that genetic algorithms or neural nets are better at than algorithmic/rule-based approaches. Genetic algorithms can sort of figure out how to improvise.
Last, just to clarify any confusion, the hashlife you linked to isn't using any genetic algorithms or anything to speed up the game of life. It's using algorithmic approaches (specifically caching oft used patterns) to speed it up.
-
Video games can't really run faster. Trust me, games like Uncharted 2 are literally pushing the hardware as hard as it can be pushed. Games might also look complex, but under the hood it's collisions between capsules and triangles and other primitives like that. Not at all different from Darwinbots' collisions between circles. So there's a lot of literature and resources available on physics that I've digested and will use for DB3, and even DB2 isn't doing it that inefficiently.
I believe you. How many times have you played a game and half of your characters body gets stuck in a wall. Or worse the ai gets stuck in a wall and can shoot at you but you can't shoot at them. Actually thats kind of rarer now because most games are tested thouroughly before theyre released. Still happens to me sometimes though.
It's precisely because you can describe the position of a shot at cycle X that makes it inefficient for a genetic algorithm. Collision detection resolves basically down to numerical root finding, which is a problem with well understood solutions. Collision response is sparse linear algebra, which also has well studied solutions. If there are any shortcuts, they come from making simplifying assumptions about the underlying math (eg: use a quadratic approximation to a sinusoidal curve). So underlying all the physics is just a lot of algebra, calculus, and linear algebra, which humans and machines already know how to do very well. All these problems have well established algorithms to find a solution.
What i meant by my example was that, why calculate the position of the shot every cycle when you only need to calculate it once, to see if it will colide with an object (of course this is if the graphics are turned off, otherwise you might still have to calculate it every cycle.) This may, however use more computing resources calculating the position of every object to see if its in or could be in the path of the shot, especially if the sim is full of objects. Anyways there may be algebraic solutions but you can still make a program go faster. What i mean is a + a = 2a. But which one runs faster on the computer. Also this doesn't nessacarily apply to soley the phyics in the game, other proccesses in db eat up resources to, like dna execution. Allright i might not be making sense here. Do you get what im trying to say, just cause a problem has one simplified algebraic solution, doesn't mean theres only way to run it on a computer and get the same results. Anyway this whole thing is prety much just hypothetical anyways.
Last, just to clarify any confusion, the hashlife you linked to isn't using any genetic algorithms or anything to speed up the game of life. It's using algorithmic approaches (specifically caching oft used patterns) to speed it up.
Yes i figured it wasn't a GA, not that i understand it. I'll go back to the site and read some more about it.
-
Is it possible to use a cellular automata as a basis for DB physics? See here (http://en.wikipedia.org/wiki/Simulated_reality#Digital_physics_and_cellular_automata) and here (http://en.wikipedia.org/wiki/Digital_physics) .
Digital physics seems to bear a close resemblance to cellular automata, and as such should be easy to use the hashlife algorithm on...
I have always wanted to find a way to combine DB with cellular automata...
-
You can make a universal turing machine in conways game and you can program any immaginable program on a turing machine so, theoretically you could program the whole of db into a turing program and then program that into a game of life seed. Then you can use hashlife on it. I just wonder if you would actually gain any speed doing that. Even if you could, have you ever tried to program anything into a turing machine. Have you ever created super complex patterns in the game of life. Now try combining both of them .
-
What I mean is using DB to simulate a cellular automata, not the other way around...
And the CA would only be for physics simulations.
-
I don't know, maybe if you turn all the bots into cells. That would deffininitly speed it up as well as break every bot ever made and ruing the whole point of a physics engine. It would be interesting to see the evolved behaviors and definatly worth it for a speed advangtage as high as you can get in conways game with hashlife. Why don't we just go and create a new alife sim simialar to db but in CA. That would be cool.
-
What I meant was the bots would exist outside of the CA universe but could still influence or be influenced by the universe.
BTW if you want a cellular automata-like ALife program, check out Evolve 4.0
-
I've done some experimenting with evolve, funny you should bring it up. The dna is to hard to understand but supposedly its more mutation friendly. The guy who made it ran it on an old computer for a year (actually i don't think it was a whole year but it was close.) There aren't alot of settings you can mess around with like with darwinbots so basicly its a watch and enjoy, but don't interfere, type sim. Anyways im curious how the bots would influence or be influenced by a CA universe. Do you mean there'd be some kind of overlapping universe that occasionly collides with db?
-
Is it possible to use a cellular automata as a basis for DB physics? See here (http://en.wikipedia.org/wiki/Simulated_reality#Digital_physics_and_cellular_automata) and here (http://en.wikipedia.org/wiki/Digital_physics) .
Digital physics seems to bear a close resemblance to cellular automata, and as such should be easy to use the hashlife algorithm on...
I have always wanted to find a way to combine DB with cellular automata...
Yes, it's possible to simulate DB on a CA grid, and yes, it would probably make the physics (which is a significant CPU load) much faster. But I think Darwinbots' physically simulated environment is one of its strengths. CA don't quite inspire the imagination since they don't actually resemble anything real. With Darwinbots it's like you're looking through a microscope or at a fish tank.
-
I heard/read somewhere that it was possible to convert a program (like DB) into a hardwired computer chip or something. I know theres sites out that let you order computer chips, they'll make it, you just have to design it. So can you get db hardwired. That would increase speed wouldn't it. My knowledge on electronics is kind of small though, but if you hardwired it you could set the stuff like max bot population to something really high and it should run just as fast. You could have all the bots' dna execute simultaniously. Im guessing the cost to do something like that would be kind of high. And if you discovered a bug youd have to live with it.
-
I heard/read somewhere that it was possible to convert a program (like DB) into a hardwired computer chip or something. I know theres sites out that let you order computer chips, they'll make it, you just have to design it. So can you get db hardwired. That would increase speed wouldn't it. My knowledge on electronics is kind of small though, but if you hardwired it you could set the stuff like max bot population to something really high and it should run just as fast. You could have all the bots' dna execute simultaniously. Im guessing the cost to do something like that would be kind of high. And if you discovered a bug youd have to live with it.
Any software can be converted in to hardware. It's just really expensive. And you always have to ask: if I spent this same amount of money on general purpose CPUs or programmable GPUs, would I get more for my money?
-
Is it possible to use a cellular automata as a basis for DB physics? See here (http://en.wikipedia.org/wiki/Simulated_reality#Digital_physics_and_cellular_automata) and here (http://en.wikipedia.org/wiki/Digital_physics) .
Digital physics seems to bear a close resemblance to cellular automata, and as such should be easy to use the hashlife algorithm on...
I have always wanted to find a way to combine DB with cellular automata...
Yes, it's possible to simulate DB on a CA grid, and yes, it would probably make the physics (which is a significant CPU load) much faster. But I think Darwinbots' physically simulated environment is one of its strengths. CA don't quite inspire the imagination since they don't actually resemble anything real. With Darwinbots it's like you're looking through a microscope or at a fish tank.
How would that work? You obviously can't create the DBs themselves out of the CA grid, can you?
Also, how much easier/harder would it be to use CA physics instead of the one you're working on?
-
Is it possible to use a cellular automata as a basis for DB physics? See here (http://en.wikipedia.org/wiki/Simulated_reality#Digital_physics_and_cellular_automata) and here (http://en.wikipedia.org/wiki/Digital_physics) .
Digital physics seems to bear a close resemblance to cellular automata, and as such should be easy to use the hashlife algorithm on...
I have always wanted to find a way to combine DB with cellular automata...
Yes, it's possible to simulate DB on a CA grid, and yes, it would probably make the physics (which is a significant CPU load) much faster. But I think Darwinbots' physically simulated environment is one of its strengths. CA don't quite inspire the imagination since they don't actually resemble anything real. With Darwinbots it's like you're looking through a microscope or at a fish tank.
How would that work? You obviously can't create the DBs themselves out of the CA grid, can you?
Also, how much easier/harder would it be to use CA physics instead of the one you're working on?
Bots would occupy either a single cell or maybe a fat cross or something like that. Shots would be single cells. Not sure how ties would work. Maybe they just stick two bots' cells together. The physics would then just be updating cells based on "velocity" of each cell. Sort of like the falling sand game (http://chir.ag/stuff/sand/). The physics could be hyper accelerated on graphics cards so we could have hundreds of thousands of cells simulated in real time (not counting DNA execution speed, game logic, etc. But physics is a significant chunk of sim speed so it would be faster).
But what it gains in speed I think it loses in complexity. You can't really simulate things like accelerating (eg: falling), or spinning about your center of mass (for tied bots), and your range of velocity values is strictly limited to either moving to an adjacent cell or not.
Assuming DB3 were all set up, you could probably jury rig a version that used CA physics. The hard part would be figuring out what physical values to feed in to DNA and the game logic.
-
The falling sand game is awesome. I always wanted to see a alife sim int the style of the Powder Game (http://dan-ball.jp/en/javagame/dust/). DB comes close with its physics, but theres no air pressure, and there arnen't any materials to interact with.
-
Bots would occupy either a single cell or maybe a fat cross or something like that. Shots would be single cells. Not sure how ties would work. Maybe they just stick two bots' cells together. The physics would then just be updating cells based on "velocity" of each cell. Sort of like the falling sand game (http://chir.ag/stuff/sand/). The physics could be hyper accelerated on graphics cards so we could have hundreds of thousands of cells simulated in real time (not counting DNA execution speed, game logic, etc. But physics is a significant chunk of sim speed so it would be faster).
But what it gains in speed I think it loses in complexity. You can't really simulate things like accelerating (eg: falling), or spinning about your center of mass (for tied bots), and your range of velocity values is strictly limited to either moving to an adjacent cell or not.
Assuming DB3 were all set up, you could probably jury rig a version that used CA physics. The hard part would be figuring out what physical values to feed in to DNA and the game logic.
That isn't a cellular automata... I quote wikipedia:
" A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood."
Just because the universe is broken up into boxes doesn't make it a cellular automaton. The state of each cell depends solely on the states of the surrounding cells. See conway's game of life.
-
Ya but the state of each cell can be an infinitely large number of possibilitys. The entire bots memory, input, output, dna, velocity, etc. etc.
-
Bots would occupy either a single cell or maybe a fat cross or something like that. Shots would be single cells. Not sure how ties would work. Maybe they just stick two bots' cells together. The physics would then just be updating cells based on "velocity" of each cell. Sort of like the falling sand game (http://chir.ag/stuff/sand/). The physics could be hyper accelerated on graphics cards so we could have hundreds of thousands of cells simulated in real time (not counting DNA execution speed, game logic, etc. But physics is a significant chunk of sim speed so it would be faster).
But what it gains in speed I think it loses in complexity. You can't really simulate things like accelerating (eg: falling), or spinning about your center of mass (for tied bots), and your range of velocity values is strictly limited to either moving to an adjacent cell or not.
Assuming DB3 were all set up, you could probably jury rig a version that used CA physics. The hard part would be figuring out what physical values to feed in to DNA and the game logic.
That isn't a cellular automata... I quote wikipedia:
" A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood."
Just because the universe is broken up into boxes doesn't make it a cellular automaton. The state of each cell depends solely on the states of the surrounding cells. See conway's game of life.
Right, a CA means you can do an update cycle using only local information about cells around the currently updating cell. What I described fits that model perfectly, so I think there's a miscommunication here. What in the system I described makes it not a CA?
-
I reread it and found a problem with this idea. Each cell is updated based on its neiboring cell. Vision would be difficult if you could only see the cells next to you, not the cells 2 or 3 spaces away. You could do some sort of cell vision system where the image 'moves'. In other words every cell next to a bot is updated with the details of the bot and carry it on the the cell next to them, so that the image of a bot can travel a long way. You could have the image 'fade' over time. One more thing, CAs are very mathmatical, not any randomness except mabey the starting seed. You wouldn't be able to do mutations and rnd functions.
-
I reread it and found a problem with this idea. Each cell is updated based on its neiboring cell. Vision would be difficult if you could only see the cells next to you, not the cells 2 or 3 spaces away. You could do some sort of cell vision system where the image 'moves'. In other words every cell next to a bot is updated with the details of the bot and carry it on the the cell next to them, so that the image of a bot can travel a long way. You could have the image 'fade' over time.
CA's don't need to be at most 1 cell away or anything like that. There's this idea of a "neighborhood". The neighborhood can be indefinitely large, as long as it's finite. To qualify as a CA, all that needs to be true is that:
1. You're world is discrete (eg: grid based)
2. Each cell is discrete (eg: finite state machine)
2. The new state of a cell can be entirely determined from its existing state and the states of cells in its "neighborhood".
One more thing, CAs are very mathmatical, not any randomness except mabey the starting seed. You wouldn't be able to do mutations and rnd functions.
I'm not sure if randomness (eg: non-determinism) would make a CA not a CA. I don't think determinism is a requirement. And anyway, random numbers in computers are deterministic anyway, since they use fancy algorithms that always generate the same output given the same seed. So as long as you were careful about giving, say, each cell it's own random number generator, it would work.
-
Alright, so you can do db in CA. Would it then be possible to put a hashlife or similiar algorithm to it. The number of possible states is very large, but in db many bots from the same species have the same dna, or at least very similiar dna, so they will do the same thing in the same situation. You might have to put a special condition in for the randomness factor to.
What I meant was the bots would exist outside of the CA universe but could still influence or be influenced by the universe.
How could/would that be done, because thats a cool idea. I can imagine a giant conways game of life replacing "the big blue screen", and the db universe would overlap it. Bots would be able to have a third sense to see the cells and could manipulate them some how. You could do ant bots by having bots create a walls and tunnels with oscilators and stills.
-
Alright, so you can do db in CA. Would it then be possible to put a hashlife or similiar algorithm to it. The number of possible states is very large, but in db many bots from the same species have the same dna, or at least very similiar dna, so they will do the same thing in the same situation. You might have to put a special condition in for the randomness factor to.
You could probably speed up the physics quite a bit. The DNA is already amenable to caching anyway. It wouldn't be crazy faster like the hashlife is. More like, maybe, 10x faster or something along those lines. Of course, we could cache DNA right now and gain some savings (maybe make the program run 150% as fast or something along those lines. Depends how much work the physics engine is doing).
What I meant was the bots would exist outside of the CA universe but could still influence or be influenced by the universe.
How could/would that be done, because thats a cool idea. I can imagine a giant conways game of life replacing "the big blue screen", and the db universe would overlap it. Bots would be able to have a third sense to see the cells and could manipulate them some how. You could do ant bots by having bots create a walls and tunnels with oscilators and stills.
That's always an option. There was a plan for something like this for a while (environment grid), but it's memory intensive, and has some other issues, too. For DB3 I'm mostly hoping to get away without any grids of any sort, and just use other techniques that are more "organic", but we'll see how it goes.
-
Bots would occupy either a single cell or maybe a fat cross or something like that. Shots would be single cells. Not sure how ties would work. Maybe they just stick two bots' cells together. The physics would then just be updating cells based on "velocity" of each cell. Sort of like the falling sand game (http://chir.ag/stuff/sand/). The physics could be hyper accelerated on graphics cards so we could have hundreds of thousands of cells simulated in real time (not counting DNA execution speed, game logic, etc. But physics is a significant chunk of sim speed so it would be faster).
But what it gains in speed I think it loses in complexity. You can't really simulate things like accelerating (eg: falling), or spinning about your center of mass (for tied bots), and your range of velocity values is strictly limited to either moving to an adjacent cell or not.
Assuming DB3 were all set up, you could probably jury rig a version that used CA physics. The hard part would be figuring out what physical values to feed in to DNA and the game logic.
That isn't a cellular automata... I quote wikipedia:
" A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood."
Just because the universe is broken up into boxes doesn't make it a cellular automaton. The state of each cell depends solely on the states of the surrounding cells. See conway's game of life.
Right, a CA means you can do an update cycle using only local information about cells around the currently updating cell. What I described fits that model perfectly, so I think there's a miscommunication here. What in the system I described makes it not a CA?
Maybe it's that by CA, I mean an automata obeying very simple mathematical rules, such as those used in conway's game of life. Here, a bot, and even shots, are far too complex to be simulated by single cells. The simplest moving pattern in GoL is 5 cells in size, and a replicating pattern has not yet been discovered, probably because it is suspected to be thousands, if not millions of cells in size.
What you're describing sounds like Evolve 4.0, which does use discrete cells but is not a cellular automaton.
Basically, what I'm suggesting is not programming in any sort of physics, and letting the physics itself emerge out of the cellular automata. CGoL didn't have any physics programmed into it, flying and stationary objects emerged naturally.
-
Bots would occupy either a single cell or maybe a fat cross or something like that. Shots would be single cells. Not sure how ties would work. Maybe they just stick two bots' cells together. The physics would then just be updating cells based on "velocity" of each cell. Sort of like the falling sand game (http://chir.ag/stuff/sand/). The physics could be hyper accelerated on graphics cards so we could have hundreds of thousands of cells simulated in real time (not counting DNA execution speed, game logic, etc. But physics is a significant chunk of sim speed so it would be faster).
But what it gains in speed I think it loses in complexity. You can't really simulate things like accelerating (eg: falling), or spinning about your center of mass (for tied bots), and your range of velocity values is strictly limited to either moving to an adjacent cell or not.
Assuming DB3 were all set up, you could probably jury rig a version that used CA physics. The hard part would be figuring out what physical values to feed in to DNA and the game logic.
That isn't a cellular automata... I quote wikipedia:
" A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood."
Just because the universe is broken up into boxes doesn't make it a cellular automaton. The state of each cell depends solely on the states of the surrounding cells. See conway's game of life.
Right, a CA means you can do an update cycle using only local information about cells around the currently updating cell. What I described fits that model perfectly, so I think there's a miscommunication here. What in the system I described makes it not a CA?
Maybe it's that by CA, I mean an automata obeying very simple mathematical rules, such as those used in conway's game of life. Here, a bot, and even shots, are far too complex to be simulated by single cells. The simplest moving pattern in GoL is 5 cells in size, and a replicating pattern has not yet been discovered, probably because it is suspected to be thousands, if not millions of cells in size.
I think you're talking about totalistic CAs (http://en.wikipedia.org/wiki/Cellular_automaton#Totalistic), which are a subset of CAs in general.
What you're describing sounds like Evolve 4.0, which does use discrete cells but is not a cellular automaton.
Yes, Evolve is like that (so are other alife programs). No, it is a cellular automata.
Basically, what I'm suggesting is not programming in any sort of physics, and letting the physics itself emerge out of the cellular automata. CGoL didn't have any physics programmed into it, flying and stationary objects emerged naturally.
The problem when you do that is that it's A) hard to determine a good rule and B ) you don't get to pick and choose behavior you want. Many totalistic CAs are quite boring, for instance, because the rules don't result in interesting behavior. If you choose one that does result in interesting behavior, you have to bend whatever game design you want to do around the limitations and features of that rule. It's much better to decide on the sort of behavior you want to see and design the rules, in a broad way, to cater to that behavior. Then you'll get other emergent behavior from the interaction of the rules that is consistent with your original feature set.
-
Right. If you want to make a CA that fosters movement and self replication, you have to design the rules around it. Most random rules are 'dead ends', and don't do anything interesting at all.
-
I think you're talking about totalistic CAs (http://en.wikipedia.org/wiki/Cellular_automaton#Totalistic), which are a subset of CAs in general.
Basically, what I'm suggesting is not programming in any sort of physics, and letting the physics itself emerge out of the cellular automata. CGoL didn't have any physics programmed into it, flying and stationary objects emerged naturally.
Sorry about that, I was referring to a totalistic CA...
The problem when you do that is that it's A) hard to determine a good rule and B ) you don't get to pick and choose behavior you want. Many totalistic CAs are quite boring, for instance, because the rules don't result in interesting behavior. If you choose one that does result in interesting behavior, you have to bend whatever game design you want to do around the limitations and features of that rule. It's much better to decide on the sort of behavior you want to see and design the rules, in a broad way, to cater to that behavior. Then you'll get other emergent behavior from the interaction of the rules that is consistent with your original feature set.
There are also ALOT of well-known interesting CAs, CGoL is the most well-known example. There are probably thousands of less well-known rules that also result in interesting behavior, you might need more than 2 states though. (By interesting behaviour, I'm referring to wolfram class-4 automata)
Finally, there are other CAs besides totalistic ones that the hashlife algorithm can be used on... for example, an automata where its state depends on the state of the cells around it at t-2. Or an automata where a cell's state depends on the state of the cells around it, but that are not in contact with it...
Basically, I'm saying that you can "design the rules" of the totalistic/other CA, because there are limitless options.
The main problem I'm thinking of is how to interface a bot with the CA world...
-
uh, nums? is something wrong?
-
Oh, sorry.
Like I described above, you can just define a bot as a group of adjacent cells or a single cell, and query near by cells for other bots for vision. And velocity ends up just being to move the cell one left, or right, or whatever. Voila, a CA that meshes nicely with current DB rules.
If you're thinking more in terms of embedding a bot's DNA in to a glider in GoL or something along those lines, then yeah, much harder.
-
but if we make a bot a huge cluster of cells (say... 100), then the universe would be much more analog in nature for the bot. In fact, the larger you make the bot in comparison to single cells in the grid, the more analog it becomes. You just need to find a compromise between speed and detail.
-
but if we make a bot a huge cluster of cells (say... 100), then the universe would be much more analog in nature for the bot. In fact, the larger you make the bot in comparison to single cells in the grid, the more analog it becomes. You just need to find a compromise between speed and detail.
Yes, that's very true.
-
Maybe it's that by CA, I mean an automata obeying very simple mathematical rules, such as those used in conway's game of life. Here, a bot, and even shots, are far too complex to be simulated by single cells. The simplest moving pattern in GoL is 5 cells in size, and a replicating pattern has not yet been discovered, probably because it is suspected to be thousands, if not millions of cells in size.
What you're describing sounds like Evolve 4.0, which does use discrete cells but is not a cellular automaton.
Basically, what I'm suggesting is not programming in any sort of physics, and letting the physics itself emerge out of the cellular automata. CGoL didn't have any physics programmed into it, flying and stationary objects emerged naturally.
CGoL is pretty well studied, but many CA rulesets aren't. My idea is to take a CA, say CGoL, and create a massive, massive random starting seed, as large as is possible. Possibly hundreds of thousands, if not millions, or even billions of cells. Maybe use some kind of compression software. The more rules and states, the more interesting the results will be. Also make sure to have random mutations, like every so often the simulator screws up on purpose. Once you have something so massive you can start to have interesting results. Imagine an outsider examining our own universe, but only by examining several atoms interacting with each other in empty space. They would know nothing of galaxys and planets and life, or any other complex structures in our universe because they only examined a small part of it. Anyways this way you don't have to do the work of programing db into a CA because (hopefully) the rules you started with will allow for a unique kind of life.
-
but if we make a bot a huge cluster of cells (say... 100), then the universe would be much more analog in nature for the bot. In fact, the larger you make the bot in comparison to single cells in the grid, the more analog it becomes. You just need to find a compromise between speed and detail.
Yes, that's very true.
So, is it possible to use the hashlife algorithm on this implementation?
-
Maybe it's that by CA, I mean an automata obeying very simple mathematical rules, such as those used in conway's game of life. Here, a bot, and even shots, are far too complex to be simulated by single cells. The simplest moving pattern in GoL is 5 cells in size, and a replicating pattern has not yet been discovered, probably because it is suspected to be thousands, if not millions of cells in size.
What you're describing sounds like Evolve 4.0, which does use discrete cells but is not a cellular automaton.
Basically, what I'm suggesting is not programming in any sort of physics, and letting the physics itself emerge out of the cellular automata. CGoL didn't have any physics programmed into it, flying and stationary objects emerged naturally.
CGoL is pretty well studied, but many CA rulesets aren't. My idea is to take a CA, say CGoL, and create a massive, massive random starting seed, as large as is possible. Possibly hundreds of thousands, if not millions, or even billions of cells. Maybe use some kind of compression software. The more rules and states, the more interesting the results will be. Also make sure to have random mutations, like every so often the simulator screws up on purpose. Once you have something so massive you can start to have interesting results. Imagine an outsider examining our own universe, but only by examining several atoms interacting with each other in empty space. They would know nothing of galaxys and planets and life, or any other complex structures in our universe because they only examined a small part of it. Anyways this way you don't have to do the work of programing db into a CA because (hopefully) the rules you started with will allow for a unique kind of life.
You could do this with GoL or one of the other so called "class 4" CAs, though it's not really consistent with Darwinbots. So it would be a separate thing altogether.
I would, though, state the "no free lunch" maxim here. No matter how good your hashing, the resulting CA is not going to be able to provide more processing power than the machine it's being run on.
but if we make a bot a huge cluster of cells (say... 100), then the universe would be much more analog in nature for the bot. In fact, the larger you make the bot in comparison to single cells in the grid, the more analog it becomes. You just need to find a compromise between speed and detail.
Yes, that's very true.
So, is it possible to use the hashlife algorithm on this implementation?
Yes, but I imagine the cache thrashing it would cause on modern processors would make it less useful than it sounds. Generally speaking in the time it takes to read from main memory a processor could process lots of instructions. To the point where it's often easier to calculate something instead of looking it up in a large table. In the case of hashlife, it's taking advantage of the fact that the neighborhood is quite small, but for something where you have a larger neighborhood it's usefulness quickly drops off.
-
The neighborhood doesn't necessarily have to be larger... right?
-
nums, what do you mean by having a larger neighborhood? Does it necessarily have to be larger? why?
-
It doesn't have to be larger. But a smaller neighborhood necessarily limits the interactions between cells.
-
This is in regards to totalistic CAs, right? I don't see any limitations of having a small neighborhood of cells that directly in contact with the center cell...
What sort of limitations are you thinking of?
-
Something I found interesting:
-
This is in regards to totalistic CAs, right? I don't see any limitations of having a small neighborhood of cells that directly in contact with the center cell...
What sort of limitations are you thinking of?
What I mean is that the size of the neighborhood creates a very well defined "horizon". Not just a horizon, a "speed of light" type limit on the speed of information transfer from one cell to another, distant one. At the neighborhood sizes that makes something like hashlife useful, I don't think you're going to find interesting behavior, at least not the sort that Darwinbots works with (interaction between two bots, usually). Since at best bots would have to just sort of wander until they happen to be almost on top of another bot.
-
This is in regards to totalistic CAs, right? I don't see any limitations of having a small neighborhood of cells that directly in contact with the center cell...
What sort of limitations are you thinking of?
What I mean is that the size of the neighborhood creates a very well defined "horizon". Not just a horizon, a "speed of light" type limit on the speed of information transfer from one cell to another, distant one. At the neighborhood sizes that makes something like hashlife useful, I don't think you're going to find interesting behavior, at least not the sort that Darwinbots works with (interaction between two bots, usually). Since at best bots would have to just sort of wander until they happen to be almost on top of another bot.
Actually, totalistic CAs with small neighborhoods, such as CGoL, can have communication outside of the neighborhood of a single cell. For example, gliders can represent "photons", such that detecting a large amount of gliders will indicate the presence of a far-away object, etc...
Although this creates a fundamental limit on information transfer, this photon-based communication is actually somewhat more realistic than our current scheme. Also, the speed of light won't be a problem for simulation speed, assuming we use a hashlife-based algorithm.
And what do you mean by not finding interesting behaviour? Do you think the GoL does not exhibit interesting behaviour?
-
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.
-
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"...
-
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.
-
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.
-
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.
-
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.
-
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?
-
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.
-
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.
-
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?
-
Speed of light in a CA is quite slow.
-
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
-
Sorry Nums, I hope we're not annoying you 0:D
A little But I don't mind too much.
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 (http://stauffercom.com/evolve4/) and modify the source to use hashlife techniques, and see the resulting speed differences first hand.
-
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?
-
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.
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.
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 (http://en.wikipedia.org/wiki/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).
-
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!
-
@jknilinux, awesome idea, i don't know how you could program it but if you did it would be awesome. You can defeat the whole speed of light thing just by having the code execute through the entire bot at once, not one cell at a time. I like the idea of bots changing their shape. You could have glider gun bots just by forming a glider shape and filling it with cells. Optimally you could have each cell in the bot have a state. Eg, wether that cell was counted as dead or alive by the simulator. Then each cell change the state of any or all of the eight squares around it each cycle. Bots would also be able to grow new cells in the same way, and any cells unconnected from the main body would die. Also any cells not connected to a group of cells of a certain size (say 100) would die, so reproduction would just be growing a body segment large enough and detaching it. They would be a pain to program manually so maybe some kind of visual programming interface where you could define what each cell should do each cycle? That would be a pain to program in and of itself but it might be worth it.
-
@jknilinux, awesome idea, i don't know how you could program it but if you did it would be awesome. You can defeat the whole speed of light thing just by having the code execute through the entire bot at once, not one cell at a time. I like the idea of bots changing their shape. You could have glider gun bots just by forming a glider shape and filling it with cells. Optimally you could have each cell in the bot have a state. Eg, wether that cell was counted as dead or alive by the simulator. Then each cell change the state of any or all of the eight squares around it each cycle. Bots would also be able to grow new cells in the same way, and any cells unconnected from the main body would die. Also any cells not connected to a group of cells of a certain size (say 100) would die, so reproduction would just be growing a body segment large enough and detaching it. They would be a pain to program manually so maybe some kind of visual programming interface where you could define what each cell should do each cycle? That would be a pain to program in and of itself but it might be worth it.
Yup, that's the plan! The bot is composed of multiple cells, but the cells don't each execute the code themselves, it's the whole organism acting as a single cell that executes the code. Each cell would be better described as a molecule, and a single-celled organism is a large collection of these molecules.
But I'm gonna try to start with a simple version first... maybe I should use DB or E 4.0 as a base, instead of making it from scratch or combining the two... what do you think nums?
Ofc, This is one difficult undertaking... and school is driving me CRAZYY!!!! But I'll try to put in as much work as I can. Expect development to be slow, but it might actually be here sooner than DB3 since CAs are far easier to program than building a physics engine from scratch.
-
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!
I don't know that you can put hard numbers to it. It just sort of depends on the implementations. Professional physics engines, though, usually handle several hundred rigid bodies in real time (eg: at 60 FPS) for video games. I'm not sure what sort of CA speeds are realistic, though the falling sand game programmed in Java (so without any real hardware optimizations) runs a world maybe 640x480 or so in more or less real time. If you moved most of the update to a graphics card (using fragment shaders) you'd probably be looking at more like full 1080p resolution running in real time or faster (probably much faster, since fragment shaders are specifically built for CAs).
Yes, your explanation made sense.
-
Would it be best for me to begin with DB or E 4.0 as a base, or start completely from scratch? Or, alternatively, I could use DB3 as a base.
-
Well you could certainly steal KForth or DB DNA for the language, but for the core CA you're probably better off starting from scratch.
-
How is the dna going to work. Wether you use KFORTH or DB dna, or some weird combination of both, how is the bots input output going to work. If its getting input from every single one of its hundreds of cells, then it will be a pain to write code for it, and even harder for evolution to work with.
-
How easy would it be to just replace the physics engine of DB3? Changed physics is the main idea behind this, I don't think it requires a completely new project...
-
DB3 isn't really a cohesive enough program to where you could "replace" the physics engine. At the moment it's more a rough collection of various modules (physics, graphics, DNA).
You might be able to engineer something with DB2, but then you're dealing with VB6. Ugh.
-
I uh, *ahem... dislike... VB6.
What I meant was once everything but the physics engine is complete, it could be easy to just put in a custom one.... So I'll probably work on it once you're close to finishing DB3.
-
That is part of the design for DB3: that you can hot swap in different modules. Not sure if a CA will just be too different or not, but it might be worth a try once it's that far.
-
Wonderful! I probably wouldn't have had time to work on it anyway just yet.