Code center > Suggestions

Hyperspeed Mode

(1/15) > >>

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:

--- Quote from: 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.
--- End quote ---

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


--- Quote ---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.
--- End quote ---

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:

--- Quote ---Physics is a really really studied problem. Because it's a billion dollar industry for video games and other things.
--- End quote ---
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?

--- Quote ---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).
--- End quote ---
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.

--- Quote ---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.
--- End quote ---
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.

Navigation

[0] Message Index

[#] Next page