Maybe someone more versed in the state-of-the-art can help me: has the concept of "speciation" ever been applied to genetic algorithms?
In my instance, there are two predominant "types" of cars that are doing approximately equally well--the "rhinoboat" and the "assdragger". But when these two solutions are combined in the crossover, I think they make an offspring that is terrible.
If the algorithm would mate only the rhinoboats with rhinoboats and assdraggers with assdraggers, I'm convinced we'd end up with some superrhinoboats and superassdraggers, but instead I just get an unhappy compromise.
Maybe make "similarity to self" one of the genotype parameters. A high rating here would mean the phenotype would have a bias against being combined with dissimilar creatures. This allows the propensity towards speciation to develop evolutionarily, too.
Actually, the thing genetic algorithms try to do is break out of this local maximum, mutating past a trait correlated with poor performance in hopes of finding a more fit solution.
In my hypothetcial algorithm, of course mutation would still take place.
But my current instace of the web page is at a point where it's wasting a lot of time on unfit 'mutts' and it seems like I could get to a "best rhinoboat" and "best assdragger" solution faster if it would stop wasting time exploring the mediocre blend.
Yeah, most effective genetic algorithms take a hybrid approach where they only do more dramatic mutations for some of the population, and then optimize the rest with a regular fitness function and small variations. The goal with these systems is to have several different but effective breeds emerge.
I didn't dig into this implementation, but it seems like it doesn't carry many (more than one?) individuals between cycles.
Also, I found these algorithms could always go more and more meta. For instance, in some situations a large "clone fraction" was optimal, or large "mutation rate", whilst in other cases it brought chaos and degraded the population.
Successful parameters could also become more immune to mutation with time, a nice improvement along with "speciation" you cited.
> Also, I found these algorithms could always go more and more meta.
Haha, I've had this same thought before. I wrote a genetic algorithm to work on the sphere packing problem (in a periodic box) and I kept thinking about how I could mutate the settings within the program and optimize them, and then mutate the rate at which those settings themselves changed, and so on. I wonder if there's an optimal point to stop being "meta"?
There are information theoretic aspects behind this. You're essentially searching the design space for the fittest and want a fast way to get your answer -- this 'fastest way' is related to the way that 'grants' maximum information.
I say this because this reminded me of a wonderful (and acessible) discussion I once glanced over on the following book: http://www.cs.toronto.edu/~mackay/itprnn/book.pdf
(Page 269, pdf 281) -- it offers answers to this sort of question :)
This happens in nature, actually. When there's a genetic disparity between individuals, although offspring is possible, it ends up infertile. That's nature's way of doing a U-turn.
When the hybridization is managed by humans though, it can be useful (e.g.: citrus, mules).
Well it's a bit more difficult, but you could let the organisms themselves decide who to mate with. Or you could have a smarter genetic algorithm that keeps sufficiently different organisms and tries evolving them for a few generations and see which type is superior.
There is really no advantage in speciation if you only want the single best solution, but it does make sense to try different evolutionary paths as they can end up in totally different places.
That's a bit of a weird assertion. Genetic algorithms are always a greedy heuristic to find a solution for a problem. It is not guaranteed at all that it will find the single best solution faster than straight bruteforcing solutions.
If speciation is a better heuristic for finding a better solution faster than the algorithm used here then its advantage is real and useful in any case.
What I meant by that dividing the population has a cost. Only one evolutionary path is going to end up with the best solution. By best I mean the best one you find, not necessarily the most optimal solution possible, which may never be found.
If you divide the population in two, at least half of your resources are wasted on doing tests and evolving traits which will just be discarded. Resources which could have been used to speed up the evolution of the other population. Even if the evolutionary path you choose isn't the optimal one, by putting twice as much resources too it, it still might end up further. And if you divide it into more than 2 species than it's just getting insane.
That's not to say that speciation isn't a useful heuristic, just that it's a costly one. However there are a lot of cases where just throwing more resources at the problem doesn't help, because it's stuck in a local maxima. In that case, going back to an earlier point in the simulation and running it to see if it ends up somewhere else isn't a bad idea, and that's exactly the same as what speciation is (except that you are doing it after the fact, rather than testing both evolutionary paths simultaneously.)
It's not fancy hmtml, but it's the best genetic simulation I've seen. The "swimmers" exist in 2d space, seek out food and mate. Only the best will reach the food fast enough, and there are colors which a given swimmer will prefer to mate with, and space separating different populations. It's very possible to get several distinct populations which behave in entirely different ways.
seriously I got 2 downvotes for saying I thought HN wasn't very funny? what?? It's not like there arn't plenty of other silly comments in this thread, why am I the one being singled-out, I guess it's probable that a comment like that would only offend people who even have the ability to downvote, since it takes 500rep to do so, but what? it wasn't even that offensive...
You're supposing that there is "sex" - i.e. two genders - in this simulation. I can't see that though?
I suspect - would be interested in anyone who's worked it out - that each individual is mutated between each generation.
I tried 10 Elites with high rate of mutation. I'd have expected this to have more "breeding" from the Elites, but it doesn't. It tends to plateau. Occasionally an outlier jumps into the "10", but it's pretty flat.
So.. Is there any concept of "fitness"? If so, it ends up being pretty random, since there is no penalty for a less adaptive mutation.
Sex does not mean two genders, neither in the simulation nor in real life. It just means that offspring inherit genes from two (or more!) parents rather than one.
Yes it has, it's one of the core things you adjust in most real applications.
It's a trade-off between exploration and exploitation. If you speciate then you have little sub-populations exploiting the local maxima, so they might do better. However, now you're not searching such a wide area so you're more likely to spend your time struggling to the top of the molehill that's next to the mountain.
In nature this also happens. Not having crossovers between ludicrously different things is generally a good idea because the landscape is full of tiny maxima. If you change a load of base pairs in your DNA you're less likely to be able to do things like form cells or process glucose than you are to add some awesome new power (unless we're in comic books).
One of the major differences for nature is that it can run all this jazz in parallel. If there are resources, it can happily have 10 trillion bacteria rather than 5 without any cost. When we're simulating, every fitness measurement on a piss-poor crossover is a waste that we should have spent on a more likely solution.
It all depends on the fitness landscape, but both approaches can be better on different real world problems.
You could introduce speciation by only allowing relatively similar genomes to successfully breed. My guess is that such an operator would be quite expensive, and its benefits would need to be weight against that.
A typical work-around for scenarios like this would be to have the various parameters change as the simulation carries on; e.g. later on it might make more sense to increase the number of elites as a way of limiting crossover.
Actually, the existence of the person is inferred only by the presence of the text.
As an aside, if this were a dream the inference would still work, but the conclusion would be false (as the poster obviously has no existence independent of the dreamer). But, unfortunately, you will be able to provide no conclusive evidences that this world is not as illusory as the dream world is, as your only sources of evidence are your senses, which are also apparently available to you in the dream state (which you are not able to perceive as illusory whilst dreaming).
I remember having lots of fun with a Windows program that doesn't seem to be available anymore... just to give you an idea (not that I ever had anything this cool in my zoo)
That program was really awesome, the things could even have sensors that made muscles move on ground contact; and I so hoped for "underwater movement" to be implemented fully, but it never came to that :(
We now have WebGL, we have local storage... Anyone? I think it's beyond my ken, but for those who know this stuff, the question basically is if you have free time and want to be a superhero. If 2D cars on a canvas can be this fun, imagine sharing 3D virtual creatures with just a link, or even better, having them cooperate or fight each other ^^
Observation: The cars tend to optimize to get over a challenging hurdle (while it's being worked on, the cars converge to a single solution: which works well), but then are no longer general enough to get over later hurdles.
If only we could move freely in four dimensions, as to navigate around events that are difficult hurdles to overcome, such as comet strikes and nuclear holocausts.
that would still be a third dimension since you're just choosing to avoid something entirely within our realm, ever advancing technology is still not advanced compared to forever... or something like that =)
That somewhat depends on the mutation rate. I have it set to 20% and the cars are optimizing down to big wheels connected by what can only be described as a bar, which means they can drive in any orientation and are clearing later and later challenges quite effectively.
Brute force doesn't necessarily mean testing in a dumb way (testing all options).
If you try to crack a password with a wordlist, would you do it randomly, or would you order by word frequency? The later is smarter, but it's still brute forcing (resource/time intensive).
It's a bit smarter still than that though. Brute force still covers the whole space. GAs are far closer to a hill climbing search which I don't think qualifies as anything near a brute force search.
I see the religious implication. But that system indeed has a designer. Somebody spent weeks making sure that features are combined and evaluated in a certain way in which the cars can evolve.
Have people actually had the course completed? I've been using 'genghisKhan' as my track seed and they always stop around 2/3 to 3/4 of the way it seems.
Oh man...some hilarious iterations there. Especially funny after playing with the normal version for a while. All of a sudden: "PARDON ME HUGE WHEELS HAULIN' ASS COMIN' THROUGH"
Unless you actually enter a seed string it generates a 256 byte random string each time you open it for the first time. I used firefox debugger to retrieve the string, it is stored in a variable called "floorseed".
The author mentions it's based on that, but totally rewritten.
"The program uses a simple genetic algorithm to evolve random two-wheeled shapes into cars over generations. Loosely based on BoxCar2D, but written from scratch, only using the same physics engine (box2d).
seedrandom.js written by David Bau. (thanks!)"
I've been iterating over sequential seeds looking for one that contains the most downhill terrain, so far the best is: 24427169 - it descends very rapidly in the later part of the track.
I'll keep this running over night and post results.
Edit: 71044092 beats that (declines 47 units in the distance of the track, which is 220 units long).
This is ridiculously entertaining, and bringing back some fond college lecture memories.
Feature request: Ability to hover over the "Top Scores" and see a snapshot of what the Car looked like.
I am not ashamed to say I was adding dragster sounds, squealing tires, grinding metal, crash sounds, and little driver sounds in my head. Those guys were striving soooo hard to get up that hill. "Ooh ooh ooh, I can make it, I can make it!"
There really is something to this that needs exploration as a multiplayer game. The aleatoric quality makes it infinitely watchable for me. GenetExcitebike.
Yes, and specifically Roger Caillois's use of the term in Man, Play and Games[1]. And I suppose if you want to be technical about it, this simulation appears to have a little piece of each of his four categories of games, to include agon, mimicry, and ilinx with the aforementioned alea.
I was a little confused that you feel that chance isn't a strong enough factor in multiplayer games. It's so widespread and pervasive that I'm willing to "omnipresent" is only a minor exaggeration.
I'm sorry. I did not mean to convey that multiplayer games have no elements of chance, or alea. I was trying to say that I thought this simulation would benefit from adding a multiplayer element to it. And there are probably many implementations of multiplayer-ness that could be explored.
The "aleatoric" part was a separate observation about a quality of the simulation that made it more enjoyable for me. And then upon further reflection, it seemed to me that this simulation had (or could have) all the elements of a game, as classified by Caillois.
Boxcar2d let you save the genome of the car. I spent months running multiple instances, trying to develop a car to beat those tracks (and the others on the forum).
This one has some amazing features. Hopefully Rafael will give us some way to compete!
It says at the bottom: "Create new world with seed: The same seed always creates the same track, so you can agree on a seed with your friends and compete. :) "
Sadly, that is pretty much the only bit I understood, ish...
This is fantastic. There should be a place to enter your own inputs though. The point of genetic algorithms is to find solutions that you can't engineer yourself, right? I'd like to try my hand against evolution.
178.43 at generation 16. That stupid wall at 171 is ridiculous!
199.47 @ gen 22. Now it is just a matter of luck whether or not they get a good jump in.
At the 190 mark the world goes all glitchy and half the track disappears.
It's a shame it's not as deterministic as it could be (according to the blurb at the bottom of the page), since this [probably] means the genetic algorithm can't exploit quirks and things being "just right" optimally. Rather, it has to build something that is a bit more generalised.
Believe it or not, my cars evolved into "Flying Cars" (They start with one wheel stuck in the terrain, moving slowly forward, then it releases and goes flying over the track)
Either there's a glitch in the game, or I'm calling JS console shenanigans. The red line on the chart gives it away, as does the mini map since it draws lazily. Playing the same level my top score is 221.12, and my mini map looks the same as yours.
Nah, no shenanigans. It was definitely a glitch, but I'm not sure if I can explain it much better. The "flying cars" start with one wheel on top of the track, and one wheel below the track. As the wheels turn, it makes very little/slow progress, but you can see the car sort of shaking/struggling to release. That release eventually happens as the lower wheel gets to a point where it can cross back to the top of the track, and that twisting motion flings the car up and forward very quickly. The cars never even see the track again. I'm not sure what actually causes the car to stop... the replay wasn't very interesting to watch after the initial 'launch', as it just spins in whitespace for a little while and then eventually just stops spinning in an upright position while travelling forward.
That was the longest run I've done, somewhere between 24 and 36 hours left mostly untouched and forgotten on the settings you can see in the picture (with Surprise! mode on to speed things up). Unfortunately I did mess with it a couple times when I got bored with its progress, cranking up the Mutation rate for a few runs to bring in some extra variety; so it would probably be tricky to reproduce intentionally. I've got a new version up and running again, since this one did eventually crash.
Definitely weird and interesting. The funny thing to me was that it is sort of a "realistic" evolution, since flying cars could be an eventual next step for real-life transportation. Although hopefully with a less violent launch system :)
This is awesome! When a handful of cars actually make for a good race it's especially mesmerizing.
I feel like it's only a matter of time before some startup implements a genetic driven visualization of the data from their app. If the effect is as compelling, I'd be staring at their marketing page for a long time.
Ha, you laugh, but human-in-the-loop evolutionary algorithms are well established. And the research communities involved are now looking at applications to cloud computing. So it's just a matter of time before this... recombination.
Forgive my wording, but I mean that whatever data is visualized is what would be subjected to fitness test, not the visualization itself.
Just like the shapes of the chassis and the size of the wheels in this demo are essentially numeric data visualized into a series of canvases, some hypothetical startup's data could be visualized in a potentially compelling manner. That's presuming, ofc, that the original data is already suitable for genetic manipulation.
What that data/startup would be? I don't know, just casting an idea.
This seed: "Enter sdfsdfs string" has an almost impossible hill at the end. I've been watching for 20 mins
Edit: This app is very well put together. The "winner"(one that got the furthest) of the previous round is up front for the next and I believes becomes the zero car
The road will be harder and harder in the end. The code said so:
for(var k = 0; k < maxFloorTiles; k++) {
last_tile = cw_createFloorTile(tile_position, (Math.random()3 - 1.5) 1.5*k/maxFloorTiles);
By design, every world has an almost impossible hill at the "end". The world keeps extending in a procedurally generated manner (based on the seed) as long as any car keeps moving. And what other than a tough hill will stop a car.
It took only about 9 generations to the evolve the Tron lightcycle. Way too cool. This is like the marble races down hotwheels tracks we used to do as kids while recording the times, only way less work.
I'm using 5% mutation rate and have 1 elite clone. I thought that meant that the whole population would be based on the winner with a 5% mutation chance (so all 19 are children of the winner). However, I have a track with an "impossible" hill and every round there's one car that almost makes it over but it's never that one which is blue next round.
How does this work exactly?
EDIT: It seems the one that almost made it was a replay ghost or something and not part of the population. Still wondering if I understood it correct though.
No, because it combines cars to generate new ones. Better performing cars have a larger chance to become a 'parent'. You should check out the source, it's suprisingly readable
Speedup improvement should be possible by not actually evaluating the clones as we already know their results - or maybe just show one as a placeholder.
At the moment, if you add "elite clones", the camera follows the stack (but all are exactly on top of each other) and it's a bit slow.
This is very fun, I love playing around with genetic algorithms and watching them evolve. How exactly does the simulation work? Does it stop after a certain amount of time, or do they burn fuel or something? Are they selected for distance, or how long they survive, or what?
I can't answer all the questions but it seems that the current generation is tested until it can no longer make progress for a certain amount of time (displayed as the bar next to its number decreasing, only to be refilled when exceeding its current maximum distance.)
For those of you interested in GAs, I built a small Ruby gem to make building genetic algorithms a little easier: https://github.com/dorkrawk/darwinning
That's my favourite genetic algorithm page , also worth check is this http://boxcar2d.com/index.html where you can create your car and see the best created.
This was a lot of fun. A suggestion for improvement might be to weight where the changes can come (so more or less likely to change wheelbase, or more or less likely to change height, etc) But overall very nicely done.
Hmmm mine just grew into giant two wheels essentially. Started with high mutation, then when I saw one reach about 160 put it to 3% mutations with 5 clones and slowly increasing every time
Awesome! A really cool version of this would let the user write their own algorithm and then have users compete against each other for whose algorithm can evolve the best car.
World seed "schnoo" has a particularly tough hill from 125-145 that several different models can almost but not quite overcome. Anyone able to get over it?
As mentioned already you mean gene, but yes you can and he does already with the wheel density, giving the darker ones more mass than the lighter ones.
Maybe someone more versed in the state-of-the-art can help me: has the concept of "speciation" ever been applied to genetic algorithms?
In my instance, there are two predominant "types" of cars that are doing approximately equally well--the "rhinoboat" and the "assdragger". But when these two solutions are combined in the crossover, I think they make an offspring that is terrible.
If the algorithm would mate only the rhinoboats with rhinoboats and assdraggers with assdraggers, I'm convinced we'd end up with some superrhinoboats and superassdraggers, but instead I just get an unhappy compromise.
Maybe make "similarity to self" one of the genotype parameters. A high rating here would mean the phenotype would have a bias against being combined with dissimilar creatures. This allows the propensity towards speciation to develop evolutionarily, too.
Actually, the thing genetic algorithms try to do is break out of this local maximum, mutating past a trait correlated with poor performance in hopes of finding a more fit solution.
In my hypothetcial algorithm, of course mutation would still take place.
But my current instace of the web page is at a point where it's wasting a lot of time on unfit 'mutts' and it seems like I could get to a "best rhinoboat" and "best assdragger" solution faster if it would stop wasting time exploring the mediocre blend.
Yeah, most effective genetic algorithms take a hybrid approach where they only do more dramatic mutations for some of the population, and then optimize the rest with a regular fitness function and small variations. The goal with these systems is to have several different but effective breeds emerge.
I didn't dig into this implementation, but it seems like it doesn't carry many (more than one?) individuals between cycles.
Yes, what you're describing is niching. See, e.g., http://architects.dzone.com/articles/algorithm-week-niching-...
That's it--thanks!
You, sir, have mastered at least one of the two hard problems in computer science.
Seriously. I knew right away that I also had "rhinobat"s and "assdragger"s.
Two more to go!
Also, I found these algorithms could always go more and more meta. For instance, in some situations a large "clone fraction" was optimal, or large "mutation rate", whilst in other cases it brought chaos and degraded the population.
Successful parameters could also become more immune to mutation with time, a nice improvement along with "speciation" you cited.
> Also, I found these algorithms could always go more and more meta.
Haha, I've had this same thought before. I wrote a genetic algorithm to work on the sphere packing problem (in a periodic box) and I kept thinking about how I could mutate the settings within the program and optimize them, and then mutate the rate at which those settings themselves changed, and so on. I wonder if there's an optimal point to stop being "meta"?
We could probably find it with some kind of Monte-Carlo technique...
There are information theoretic aspects behind this. You're essentially searching the design space for the fittest and want a fast way to get your answer -- this 'fastest way' is related to the way that 'grants' maximum information.
I say this because this reminded me of a wonderful (and acessible) discussion I once glanced over on the following book: http://www.cs.toronto.edu/~mackay/itprnn/book.pdf (Page 269, pdf 281) -- it offers answers to this sort of question :)
You're looking for "hyper-heuristics."
So called, because unfortunately GAs etc. had already taken the name "meta-heuristics".
> I wonder if there's an optimal point to stop being "meta"?
Perhaps this will help your thinking in the right direction: http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_opt...
Successful parameters could also become more immune to mutation with time
I believe this happens in nature. DNA has lots of error correcting stuff to reduce errors.
This happens in nature, actually. When there's a genetic disparity between individuals, although offspring is possible, it ends up infertile. That's nature's way of doing a U-turn.
When the hybridization is managed by humans though, it can be useful (e.g.: citrus, mules).
Well it's a bit more difficult, but you could let the organisms themselves decide who to mate with. Or you could have a smarter genetic algorithm that keeps sufficiently different organisms and tries evolving them for a few generations and see which type is superior.
There is really no advantage in speciation if you only want the single best solution, but it does make sense to try different evolutionary paths as they can end up in totally different places.
That's a bit of a weird assertion. Genetic algorithms are always a greedy heuristic to find a solution for a problem. It is not guaranteed at all that it will find the single best solution faster than straight bruteforcing solutions.
If speciation is a better heuristic for finding a better solution faster than the algorithm used here then its advantage is real and useful in any case.
What I meant by that dividing the population has a cost. Only one evolutionary path is going to end up with the best solution. By best I mean the best one you find, not necessarily the most optimal solution possible, which may never be found.
If you divide the population in two, at least half of your resources are wasted on doing tests and evolving traits which will just be discarded. Resources which could have been used to speed up the evolution of the other population. Even if the evolutionary path you choose isn't the optimal one, by putting twice as much resources too it, it still might end up further. And if you divide it into more than 2 species than it's just getting insane.
That's not to say that speciation isn't a useful heuristic, just that it's a costly one. However there are a lot of cases where just throwing more resources at the problem doesn't help, because it's stuck in a local maxima. In that case, going back to an earlier point in the simulation and running it to see if it ends up somewhere else isn't a bad idea, and that's exactly the same as what speciation is (except that you are doing it after the fact, rather than testing both evolutionary paths simultaneously.)
Check out darwin pond: http://www.ventrella.com/darwin/darwin.html
It's not fancy hmtml, but it's the best genetic simulation I've seen. The "swimmers" exist in 2d space, seek out food and mate. Only the best will reach the food fast enough, and there are colors which a given swimmer will prefer to mate with, and space separating different populations. It's very possible to get several distinct populations which behave in entirely different ways.
I'm just fascinated with a program that isn't full screen, yet resizes my entire desktop down to 800x600 even still. Fancy HTML it is not.
Darwninbots is a pretty good alife simulator if you are interested http://wiki.darwinbots.com/w/Main_Page
honestly I started crying a little bit at how funny I found your description. funniest thing i've read on HN
seriously I got 2 downvotes for saying I thought HN wasn't very funny? what?? It's not like there arn't plenty of other silly comments in this thread, why am I the one being singled-out, I guess it's probable that a comment like that would only offend people who even have the ability to downvote, since it takes 500rep to do so, but what? it wasn't even that offensive...
alright, whatever I'll stop commenting
You're supposing that there is "sex" - i.e. two genders - in this simulation. I can't see that though?
I suspect - would be interested in anyone who's worked it out - that each individual is mutated between each generation.
I tried 10 Elites with high rate of mutation. I'd have expected this to have more "breeding" from the Elites, but it doesn't. It tends to plateau. Occasionally an outlier jumps into the "10", but it's pretty flat.
So.. Is there any concept of "fitness"? If so, it ends up being pretty random, since there is no penalty for a less adaptive mutation.
Sex does not mean two genders, neither in the simulation nor in real life. It just means that offspring inherit genes from two (or more!) parents rather than one.
Yes it has, it's one of the core things you adjust in most real applications.
It's a trade-off between exploration and exploitation. If you speciate then you have little sub-populations exploiting the local maxima, so they might do better. However, now you're not searching such a wide area so you're more likely to spend your time struggling to the top of the molehill that's next to the mountain.
In nature this also happens. Not having crossovers between ludicrously different things is generally a good idea because the landscape is full of tiny maxima. If you change a load of base pairs in your DNA you're less likely to be able to do things like form cells or process glucose than you are to add some awesome new power (unless we're in comic books).
One of the major differences for nature is that it can run all this jazz in parallel. If there are resources, it can happily have 10 trillion bacteria rather than 5 without any cost. When we're simulating, every fitness measurement on a piss-poor crossover is a waste that we should have spent on a more likely solution.
It all depends on the fitness landscape, but both approaches can be better on different real world problems.
You could introduce speciation by only allowing relatively similar genomes to successfully breed. My guess is that such an operator would be quite expensive, and its benefits would need to be weight against that.
A typical work-around for scenarios like this would be to have the various parameters change as the simulation carries on; e.g. later on it might make more sense to increase the number of elites as a way of limiting crossover.
I just spent half an hour of my life rooting for imaginary cars that ceased to exist as soon as I closed the tab.
Didn't Voltaire say something like that?
Virtualized NASCAR?
http://schwitzsplinters.blogspot.com/2013/04/adam-and-eve-in...
On the cosmic scale, rooting for any sports team isn't much different... ;P
Even from practical frames of reference, it has about the same effect on most of the spectators.
Several hours here, twiddling parameters. Lordy do I love enhanced stochastic optimization problems.
http://www.penny-arcade.com/comic/2009/9/25/
I just replied to someone that ceased to exist as soon as I closed the tab.
Not true. You'll check back later to see if someone replied to your comment.
Actually, the existence of the person is inferred only by the presence of the text.
As an aside, if this were a dream the inference would still work, but the conclusion would be false (as the poster obviously has no existence independent of the dreamer). But, unfortunately, you will be able to provide no conclusive evidences that this world is not as illusory as the dream world is, as your only sources of evidence are your senses, which are also apparently available to you in the dream state (which you are not able to perceive as illusory whilst dreaming).
Reality? lol.
Not all senses are available in dream state, however.
Really? I've not found that to be true. What sense are unavailable?
I remember having lots of fun with a Windows program that doesn't seem to be available anymore... just to give you an idea (not that I ever had anything this cool in my zoo)
http://www.youtube.com/watch?v=l-qOBi2tAnI http://www.youtube.com/watch?v=AUXc6mckGLE
That program was really awesome, the things could even have sensors that made muscles move on ground contact; and I so hoped for "underwater movement" to be implemented fully, but it never came to that :(
We now have WebGL, we have local storage... Anyone? I think it's beyond my ken, but for those who know this stuff, the question basically is if you have free time and want to be a superhero. If 2D cars on a canvas can be this fun, imagine sharing 3D virtual creatures with just a link, or even better, having them cooperate or fight each other ^^
I wish that app shared the state with some central server and you could always start with the "best evolved" state.
It would also be nice if the designs could be more complex, and not just a random star-shaped polygon + two wheels.
Yes, this is eerily lifelike.
Observation: The cars tend to optimize to get over a challenging hurdle (while it's being worked on, the cars converge to a single solution: which works well), but then are no longer general enough to get over later hurdles.
I found my life to be strikingly similar
Unlike those cars we can move in three dimensions, so you're free to find another set of hurdles to overcome. :)
If only we could move freely in four dimensions, as to navigate around events that are difficult hurdles to overcome, such as comet strikes and nuclear holocausts.
that would still be a third dimension since you're just choosing to avoid something entirely within our realm, ever advancing technology is still not advanced compared to forever... or something like that =)
Remind me Fringe!
That somewhat depends on the mutation rate. I have it set to 20% and the cars are optimizing down to big wheels connected by what can only be described as a bar, which means they can drive in any orientation and are clearing later and later challenges quite effectively.
That system is too complex not to have an intelligent designer.
Even if it is, who designed the designer?
And thus we (I) infer the existence of the big G in the infinity of intelligent designers required to keep going down that rabbit hole.
Time is cyclic, don't you know?
Complex? You can't get simpler than brute forcing a problem.
GAs are a good bit above brute forcing. Brute forcing this would be enumerating ever possible car and testing them all.
Brute force doesn't necessarily mean testing in a dumb way (testing all options).
If you try to crack a password with a wordlist, would you do it randomly, or would you order by word frequency? The later is smarter, but it's still brute forcing (resource/time intensive).
It's a bit smarter still than that though. Brute force still covers the whole space. GAs are far closer to a hill climbing search which I don't think qualifies as anything near a brute force search.
I see the religious implication. But that system indeed has a designer. Somebody spent weeks making sure that features are combined and evaluated in a certain way in which the cars can evolve.
It twas a joke.
sorry, my joke detection algorithm sucks.
Is there a way to save the current world seed?
I have a layout that is defeating all cars even after 50 generations and counting. Would love to keep on testing against this world.
The world seed is the string in the text input.
Have people actually had the course completed? I've been using 'genghisKhan' as my track seed and they always stop around 2/3 to 3/4 of the way it seems.
The "course" always gets longer. No matter how long it currently is.
deep man.
No, it stops at around ~220 after which the car just falls into the void.
I got to around 200 without hacking after about 300 generations but then the terrain just gets too much for any of the little guys.
So if you want to beef them up a little, type this in javascript console:
and hit New Population
Oh man...some hilarious iterations there. Especially funny after playing with the normal version for a while. All of a sudden: "PARDON ME HUGE WHEELS HAULIN' ASS COMIN' THROUGH"
I can't even see the track now.
Thank you for this, this is the car that I got! http://imgur.com/376PB6X
So great ahahahaha
At first all my successful cars on genghisKhan looked like knight's helmets, now they are experimenting with looking like shrimp.
Unless you actually enter a seed string it generates a 256 byte random string each time you open it for the first time. I used firefox debugger to retrieve the string, it is stored in a variable called "floorseed".
This looks very similar to something that was posted on reddit a couple of years ago.
http://boxcar2d.com/
The author mentions it's based on that, but totally rewritten.
"The program uses a simple genetic algorithm to evolve random two-wheeled shapes into cars over generations. Loosely based on BoxCar2D, but written from scratch, only using the same physics engine (box2d). seedrandom.js written by David Bau. (thanks!)"
boxcar2d is much more fun as it lets the number of wheels evolve.
I've been iterating over sequential seeds looking for one that contains the most downhill terrain, so far the best is: 24427169 - it descends very rapidly in the later part of the track. I'll keep this running over night and post results.
Edit: 71044092 beats that (declines 47 units in the distance of the track, which is 220 units long).
I used your seed and my cars have fallen off the track...
Yeah after 220 platforms the terrain on all seeds ends, which is a shame.
My best car seemed to get past 300 before the road ran out: http://imgur.com/f1Gr25d
Although I think this was because it fell off the edge and kept moving forwards as it fell.
thanks, I'll try your level. I saw a really cool looking car on the world "sail" after 1219 generations https://dl.dropboxusercontent.com/u/14074521/genetic-cars.pn...
The problem is that once your car makes it to "the end", it keeps falling forever, not losing any forward momentum, so the level never ends.
This is ridiculously entertaining, and bringing back some fond college lecture memories. Feature request: Ability to hover over the "Top Scores" and see a snapshot of what the Car looked like.
If this were a screensaver, I'd never get anything done.
This is great, desperately needs sounds! VROOOOOOM
I am not ashamed to say I was adding dragster sounds, squealing tires, grinding metal, crash sounds, and little driver sounds in my head. Those guys were striving soooo hard to get up that hill. "Ooh ooh ooh, I can make it, I can make it!"
There really is something to this that needs exploration as a multiplayer game. The aleatoric quality makes it infinitely watchable for me. GenetExcitebike.
+1 for the word "aleatoric"
> There really is something to this that needs exploration as a multiplayer game. The aleatoric quality makes it infinitely watchable for me.
This quality?
http://darthsanddroids.net/episodes/0038.html
Yes, and specifically Roger Caillois's use of the term in Man, Play and Games[1]. And I suppose if you want to be technical about it, this simulation appears to have a little piece of each of his four categories of games, to include agon, mimicry, and ilinx with the aforementioned alea.
http://en.wikipedia.org/wiki/Man,_Play_and_Games
I was a little confused that you feel that chance isn't a strong enough factor in multiplayer games. It's so widespread and pervasive that I'm willing to "omnipresent" is only a minor exaggeration.
I'm sorry. I did not mean to convey that multiplayer games have no elements of chance, or alea. I was trying to say that I thought this simulation would benefit from adding a multiplayer element to it. And there are probably many implementations of multiplayer-ness that could be explored.
The "aleatoric" part was a separate observation about a quality of the simulation that made it more enjoyable for me. And then upon further reflection, it seemed to me that this simulation had (or could have) all the elements of a game, as classified by Caillois.
Oh what I would give to pit my genetically-superior boxcar against a challenger.
Boxcar2d let you save the genome of the car. I spent months running multiple instances, trying to develop a car to beat those tracks (and the others on the forum).
This one has some amazing features. Hopefully Rafael will give us some way to compete!
It says at the bottom: "Create new world with seed: The same seed always creates the same track, so you can agree on a seed with your friends and compete. :) "
Sadly, that is pretty much the only bit I understood, ish...
This is fantastic. There should be a place to enter your own inputs though. The point of genetic algorithms is to find solutions that you can't engineer yourself, right? I'd like to try my hand against evolution.
Just burned a couple of hours of developer time as everyone crowded around my monitor rooting for imaginary cars. Oops.
The seed "HN" produces a fairly stable world (1 car makes it quite far). Eventually crashes.
Can we standardize on a seed to compare scores? HN sounds good to me.
Highscore 188.23, that wall at the end just proves too high..
My cars were able to jump over it at the 342nd generation. Although later in the range of 1100 generations they were still having trouble.
I got past that wall, but the track goes completely crazy after that and it's impossible to proceed.
http://i.imgur.com/KPfKdab.png
We need a high-scores page with levels :)
Level: marc - 172.68
178.43 at generation 16. That stupid wall at 171 is ridiculous! 199.47 @ gen 22. Now it is just a matter of luck whether or not they get a good jump in.
#1: 166.15 d:161.48 h:-4.4/4.12m (gen 195)
It was a very tough track...
I have a 200.24 d:196.51 h:-17.24/3.29m (gen 55).
At the 190 mark the world goes all glitchy and half the track disappears.
It's a shame it's not as deterministic as it could be (according to the blurb at the bottom of the page), since this [probably] means the genetic algorithm can't exploit quirks and things being "just right" optimally. Rather, it has to build something that is a bit more generalised.
score: 512.85 d:507.31 h:-5432.59/1.7m (gen 5) level: 71044092
The car made it thru the whole level and just kept falling forever. I think it was a very lucky fluke.
screenshot https://www.dropbox.com/s/8777mtx2g6maf96/Screen%20Shot%2020...
Level: HN - 2667.94
Believe it or not, my cars evolved into "Flying Cars" (They start with one wheel stuck in the terrain, moving slowly forward, then it releases and goes flying over the track)
http://imgur.com/n6g8VRH
Either there's a glitch in the game, or I'm calling JS console shenanigans. The red line on the chart gives it away, as does the mini map since it draws lazily. Playing the same level my top score is 221.12, and my mini map looks the same as yours.
Nah, no shenanigans. It was definitely a glitch, but I'm not sure if I can explain it much better. The "flying cars" start with one wheel on top of the track, and one wheel below the track. As the wheels turn, it makes very little/slow progress, but you can see the car sort of shaking/struggling to release. That release eventually happens as the lower wheel gets to a point where it can cross back to the top of the track, and that twisting motion flings the car up and forward very quickly. The cars never even see the track again. I'm not sure what actually causes the car to stop... the replay wasn't very interesting to watch after the initial 'launch', as it just spins in whitespace for a little while and then eventually just stops spinning in an upright position while travelling forward.
Weird, but interesting bug. Have you reloaded it and ran it long enough to determine if it's reproducible?
That was the longest run I've done, somewhere between 24 and 36 hours left mostly untouched and forgotten on the settings you can see in the picture (with Surprise! mode on to speed things up). Unfortunately I did mess with it a couple times when I got bored with its progress, cranking up the Mutation rate for a few runs to bring in some extra variety; so it would probably be tricky to reproduce intentionally. I've got a new version up and running again, since this one did eventually crash.
Definitely weird and interesting. The funny thing to me was that it is sort of a "realistic" evolution, since flying cars could be an eventual next step for real-life transportation. Although hopefully with a less violent launch system :)
Kudos -- that's awesome :D
I had the same thing happen for one of my cars. It seems like it has to be a glitch.
This is awesome! When a handful of cars actually make for a good race it's especially mesmerizing.
I feel like it's only a matter of time before some startup implements a genetic driven visualization of the data from their app. If the effect is as compelling, I'd be staring at their marketing page for a long time.
How would you determine the fitness of a "visualization" programatically?
record time-on-page maybe?
Genetic A/B Testing!
Ha, you laugh, but human-in-the-loop evolutionary algorithms are well established. And the research communities involved are now looking at applications to cloud computing. So it's just a matter of time before this... recombination.
Mechanical Turk?
Forgive my wording, but I mean that whatever data is visualized is what would be subjected to fitness test, not the visualization itself.
Just like the shapes of the chassis and the size of the wheels in this demo are essentially numeric data visualized into a series of canvases, some hypothetical startup's data could be visualized in a potentially compelling manner. That's presuming, ofc, that the original data is already suitable for genetic manipulation.
What that data/startup would be? I don't know, just casting an idea.
This seed: "Enter sdfsdfs string" has an almost impossible hill at the end. I've been watching for 20 mins
Edit: This app is very well put together. The "winner"(one that got the furthest) of the previous round is up front for the next and I believes becomes the zero car
The road will be harder and harder in the end. The code said so: for(var k = 0; k < maxFloorTiles; k++) { last_tile = cw_createFloorTile(tile_position, (Math.random()3 - 1.5) 1.5*k/maxFloorTiles);
Last parameter is the angle
By design, every world has an almost impossible hill at the "end". The world keeps extending in a procedurally generated manner (based on the seed) as long as any car keeps moving. And what other than a tough hill will stop a car.
This put a smile on my face. There's something nice and simple about it.
It took only about 9 generations to the evolve the Tron lightcycle. Way too cool. This is like the marble races down hotwheels tracks we used to do as kids while recording the times, only way less work.
I'm using 5% mutation rate and have 1 elite clone. I thought that meant that the whole population would be based on the winner with a 5% mutation chance (so all 19 are children of the winner). However, I have a track with an "impossible" hill and every round there's one car that almost makes it over but it's never that one which is blue next round.
How does this work exactly?
EDIT: It seems the one that almost made it was a replay ghost or something and not part of the population. Still wondering if I understood it correct though.
I recommend a smaller mutation rate. You see the inheritance of the previous winner a lot better.
I'd like to also have an "intelligent design" button. You'd set the vertices and radii and compete against the evolved cars.
I've also experimented a bit with this type of simulation quite some time ago, you can find the result here http://lifesoup.sourceforge.net/
This tries to simulate simple "swimmers" where the fastest survives and spawn new entities with slight variations.
(Note: this is not my best code :-))
Shouldn't 0% mutation rate and 1 elite clone mean that all cars in the next generation will look the same?
No, because it combines cars to generate new ones. Better performing cars have a larger chance to become a 'parent'. You should check out the source, it's suprisingly readable
For anyone who is interested it is probably worth checking out this - http://www.rockpapershotgun.com/2013/06/24/darwinning-specie...
Speedup improvement should be possible by not actually evaluating the clones as we already know their results - or maybe just show one as a placeholder.
At the moment, if you add "elite clones", the camera follows the stack (but all are exactly on top of each other) and it's a bit slow.
This is very fun, I love playing around with genetic algorithms and watching them evolve. How exactly does the simulation work? Does it stop after a certain amount of time, or do they burn fuel or something? Are they selected for distance, or how long they survive, or what?
I can't answer all the questions but it seems that the current generation is tested until it can no longer make progress for a certain amount of time (displayed as the bar next to its number decreasing, only to be refilled when exceeding its current maximum distance.)
What is equally amazing is that the author is a world yo-yo champion, and truly a yo-yo ninja: http://www.youtube.com/watch?v=Y5DeyIScwzg
That seems his past time, when not coding genetic algorithms...
For those of you interested in GAs, I built a small Ruby gem to make building genetic algorithms a little easier: https://github.com/dorkrawk/darwinning
That's my favourite genetic algorithm page , also worth check is this http://boxcar2d.com/index.html where you can create your car and see the best created.
This was a lot of fun. A suggestion for improvement might be to weight where the changes can come (so more or less likely to change wheelbase, or more or less likely to change height, etc) But overall very nicely done.
Let's compare results/stats on the map "Hacker News"
That seed has an amazingly difficult part at around 156
I switched to "Hacker News Cars" and my master race of fishmobiles are now at: #1: 183.44 d:178.09 h:-5.26/2.87m (gen 22)
There is an epic hill at 180..... Will give it another 10 generations and see what they can do.
That was a tough one. Finally, at gen 669, one of the cars managed to jump it.
#1: 200.72 d:195.95 h:-5.38/6.55m (gen 669)
156 is tough but doable. A couple of my populations have cleared it. 175, however, looks fairly impossible :)
http://imgur.com/iIIcGnJ
Edit: 175 has been cleared by one of my populations at generation 155! 187 is definitely impassable, though. http://imgur.com/GwO4j4W
Hmmm mine just grew into giant two wheels essentially. Started with high mutation, then when I saw one reach about 160 put it to 3% mutations with 5 clones and slowly increasing every time
Awesome! A really cool version of this would let the user write their own algorithm and then have users compete against each other for whose algorithm can evolve the best car.
World seed "schnoo" has a particularly tough hill from 125-145 that several different models can almost but not quite overcome. Anyone able to get over it?
Yes. Small body car, low density but large wheels.
I freaking love this.
There didn't appear to be anyway to send a small donation to the creators.
People competing against each other on a variety of pre-made tracks would be amazing.
That worked surprisingly well on my blackberry z10.
It sort of reminds me of Dukes of Hazard. It seemed that they would always go off a jump in the car chase scenes.
Could you add a genome for "weight"? Some cars seem so light that they overturn easily.
A _gene_ for weight.
As mentioned already you mean gene, but yes you can and he does already with the wheel density, giving the darker ones more mass than the lighter ones.
Cool. Now make a version with legs and you'll freak some people out.
I watched this shit for like 30 minutes
is there always a wall around 200?
This is a lot of fun to watch, great idea
this is well done
vbbvyubeuyfvefeojfeiojf
at 200, there's a bloody wall!!!
beautiful
Awesome!
holy batmobile.... awesome
Fantastic!
it's the 10th time this one pops up in HN.
Please stay on topic, by implementing a genetic Edward Snowden who runs as far as possible from the NSA. This is HN, after all.