Hyperspeed Mode

[Houshalter]

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. 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.

[Numsgil]

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.

[Houshalter]

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.

[Numsgil]

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).

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.

[Houshalter]

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.

[Numsgil]

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.

[Houshalter]

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.

[jknilinux]

Is it possible to use a cellular automata as a basis for DB physics? See here and here .

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...

[Houshalter]

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  .

[jknilinux]

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.

[Houshalter]

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.

[jknilinux]

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

[Houshalter]

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?

[Numsgil]

Is it possible to use a cellular automata as a basis for DB physics? See here and here .

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.

[Houshalter]

 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.