My best is 802.3

January 28, 2011 4:45 PM

Watch your computer design a 2 dimensional car. What happens when you give a computer, instead of a predefined function to run, a set of parameters, a goal, and the ability to mutate those parameters? You get a genetic algorithm. At its core, genetic algorithms can best be described as Darwinian evolution of computer functions. Is it better to use a streamlined, wide-wheel-base motorcycle to cross terrain, or something that looks like a cross between a fish and a tank? This simplistic simulation shows just what's going to cause the rise of Skynet.
posted by mark242 (90 comments total)

My computer just made a Pontiac Aztek.
posted by hanoixan at 4:50 PM on January 28, 2011 [27 favorites]

Here's something similar.
posted by brundlefly at 4:56 PM on January 28, 2011

My computer made such a good car that I'm going to send it to that guy at the Washington Post to see if it will increase his prospects for sex with a stranger. Fingers crossed!
posted by The World Famous at 5:00 PM on January 28, 2011 [4 favorites]

They need to work on the traction. And wow, those cars have a lot of torque. Or do they just weigh nothing?
posted by dunkadunc at 5:03 PM on January 28, 2011

This is really fun. I'm on generation 6 and it's making cute little dune buggies. It's actually pretty exciting when it throws down this badass car and you're like AW YEAH go go go! Then it goes and flips over and you're like :(
posted by PercussivePaul at 5:06 PM on January 28, 2011 [2 favorites]

I got some vehicle that seemed to be punished for being too successful: if it gets gong too fast and catches air the algorithm cuts the simulation short.
posted by lekvar at 5:13 PM on January 28, 2011

lekvar, are you sure it didn't just reach the max length for that generation? They get cut off at the distance given in the parentheses (which is double the max distance it went in the previous generation), presumably for efficiency reasons.
posted by dorque at 5:16 PM on January 28, 2011

dorque, I'm not sure about that at all now. (I didn't know there was a distance cutoff)
posted by lekvar at 5:26 PM on January 28, 2011

haha, my vehicles are developing vestigial wheels up top.
posted by emeiji at 5:30 PM on January 28, 2011

I have no shame about the fact that I gleefully upvoted the car it bred me with exactly zero wheels.
posted by dorque at 5:32 PM on January 28, 2011 [4 favorites]

I'll just leave this here.

Not to take anything away from this fun little simulation, but too often I've seen people try to (mis)apply genetic algorithms or simulated annealing to problems that can be otherwise solved exactly (e.g.: you don't need these kinds of approximate techniques to solve an assignment problem).
posted by mhum at 5:40 PM on January 28, 2011 [5 favorites]

The fitness function here seems pretty borked, or at least weirdly skewed in early generations by how the cutoff is applied, which I can't quite understand by watching it. Cars that make it to the cutoff quickly seem to be at a disadvantage relative to ones that move in a herky-jerky fashion, even though the former seem like better designs.
posted by RogerB at 5:42 PM on January 28, 2011 [1 favorite]

I wish it wouldn't just drop the cars on their poor, malformed hoods and immediately judge them nonviable. What's wrong with drawing a convex hull around the monstrosity, drawing a line between the hopefully two or more wheels, then rotating the vehicle such that it will land in such a fashion that the suspension could cope with it?
posted by adipocere at 5:43 PM on January 28, 2011

This concept needs to be grafted onto the Gran Turismo engine. that would be cool.
posted by dunkadunc at 5:47 PM on January 28, 2011 [2 favorites]

I can't tell what's better: a car that's designed not to flip itself over or a car that's designed to drive just as well upside down. Based on real-world car design, I'm leaning towards the latter.
posted by Partial Law at 5:50 PM on January 28, 2011 [1 favorite]

The FAQ and algorithm pages are worth reading. They explain why some of the weird stuff happens.

I find this disturbingly fascinating. It's one thing to know, in an academic sense, how evolution works. It is actually quite different to watch it happening at a scale and in a timeframe where you can see it at work and appreciate exactly what is happening.

Oh, and evolution really, really, really doesn't give a rat's ass about individuals.
posted by localroger at 5:54 PM on January 28, 2011 [2 favorites]

The book I read on this was 'Understanding Intelligence,' by the MIT press (which you can find in its entirety here).

One of the advantages of adaptive algorithms is that they can adapt to situations that fall outside of easy human perception. The classical example is with sonar on submarines; adaptive computer algorithms are much more reliable than the old human operators because they have a wider range of hearing, but they also learn to react to things that would otherise just be drowned out in the background noise, without anyone necessarily solving the hard problem of figuring out how to best filter that background noise.
posted by kaibutsu at 5:56 PM on January 28, 2011

This thing should be required in schools. It really brings home the numerous mis-steps that evolution takes, as well as the surprisingly 'optimal' results.
posted by ChurchHatesTucker at 5:56 PM on January 28, 2011

I love this thing. I remember seeing an earlier version at some point, and I'm enjoying it just as much the second time around.

My current stock is heavily favoring a bizarre little three-wheeled prototype that looks like what you'd get if Louis Wain drew a rhinoceros in LOGO. Just a terrible stupid little thing, but it keeps leading the pack every generation. Go, stupid evolved little guy, go!
posted by cortex at 5:57 PM on January 28, 2011 [1 favorite]

Well, my cat loved the hell out of it, but didn't do very well....
posted by HuronBob at 6:03 PM on January 28, 2011 [5 favorites]

I swear I've seen this on the blue before, but I can't find it right now. Anyway, the first time I saw this, I thought I should program a little primordial ooze and have my computer evolve some cellular life. How cool would that be!

I wish I was a better programmer. Even so, we're probably a bit far from that in terms of computer horsepower. This thing is evolving with only like 5 parameters.
posted by Popular Ethics at 6:04 PM on January 28, 2011

Folks who like this might also be interested in watching Karl Sims's video full of neat Evolved Virtual Creatures and/or playing with similar stuff in breve.
posted by RogerB at 6:05 PM on January 28, 2011 [2 favorites]

This thing should be required in schools. It really brings home the numerous mis-steps that evolution takes, as well as the surprisingly 'optimal' results.

Funnily enough, I just saw this thing yesterday in my Evolutionary Computation class. The thing that boggles my mind about evolutionary computing is the enormous search spaces. The thing that makes me want to pull my hair out is that it's so hard to work out what parameters to feed the algorithm to make it do what I want it to.

PicBreeder: Evolutionary art!
Human-competitive results: When evolutionary algorithms match or beat our algorithms.

This stuff really is neat, but it's not a nicely packaged black box you can throw any problem at. You really have to pick your algorithms and parameters to get anything good. At least, unless we invent strong AI who feels like cooperating.
posted by BungaDunga at 6:22 PM on January 28, 2011 [3 favorites]

I'm rocking Tron light cycles.
posted by monkeymadness at 6:28 PM on January 28, 2011

Genetic algorithm? Seems like hill climbing would be a more natural fit. har har har

I used to work with Serious Optimization Guys. They hated genetic algorithms, because the laity are often enamored with them so you get pointy-haired managers saying things like, "Let's use a genetic algorithm!", when actually genetic algorithms aren't usually the best choice for the kinds of things we were doing (well behaved continuous surfaces).
posted by qxntpqbbbqxl at 6:37 PM on January 28, 2011 [3 favorites]

They're so creative at that stage, bless their little electrical hearts.
posted by anigbrowl at 6:39 PM on January 28, 2011 [1 favorite]

Mine made a lumpy box with a wheel on top, and then a pretty bitchin' trike, and then a glowy guy who kinda looks like Jeff Bridges. Again! Stupid computer...
posted by vorfeed at 6:40 PM on January 28, 2011

It knows from wheelie bars (which is good) but it doesn't know from longer wheel bases (which is bad)
posted by Trochanter at 6:43 PM on January 28, 2011

Lowering the mutation factor a lot, thus increasing inbreeding, appropriately enough seems to produce farm equipment, mostly tractors.
posted by Joakim Ziegler at 6:56 PM on January 28, 2011 [3 favorites]

One of the interesting things here is that the terrain generator is as big a part of the problem as the car generator; it creates the cars. And it's random. So you think you can design a better car with your massive human intelligence? Long wheel base == getting stuck on a peak. Big wheels == not enough torque to get up a peak. Short wheel base == flips easily. Small wheels == more torque but != flip-proofness. It's not as simple as it looks. Given the problem space he's given the cars, I'm really not sure I could do a better design than the generative algorithm will.
posted by localroger at 6:56 PM on January 28, 2011

don't bean-plate this, it's a friggin' cat toy.
posted by HuronBob at 6:59 PM on January 28, 2011

Crank the max wheels up. Then you start to get some pretty awesome reversible tank-car things.
posted by axiom at 7:07 PM on January 28, 2011

Am I supposed to help? Does voting help?
posted by Trochanter at 7:14 PM on January 28, 2011

I think I found the perfect car:

One wheel, no chassis.
posted by jet_manifesto at 7:25 PM on January 28, 2011 [4 favorites]

Hmmm. What if each generation of The Universe tested different combinations of elements according to some algo for a few dozen billion years, then collapsed into nothing except the results, and 'exploded' again.

Clearly the criteria are important to us. Are we still in the 'third wheel gets stuck on the pointy hill' generation?
posted by Twang at 7:25 PM on January 28, 2011 [1 favorite]

Now we need to point this algorithm at Jelly Car.
posted by Space Coyote at 7:32 PM on January 28, 2011

The author of this has been responding to feedback and explaining stuff over on this Reddit Thread. I've been letting it run in a second browser window for the past hour. it's oddly hypnotic.
posted by inthe80s at 7:43 PM on January 28, 2011 [2 favorites]

Heh, I've been obsessed with this thing recently. Mostly, the issue is with their mutation algorithm -- I'm currently working on a physics engine to run at full processor speed (as opposed to realtime) so that you can see what 100,000 generations (and a reasonable mutation to get out of local optima) can do.
posted by spiderskull at 7:44 PM on January 28, 2011

By the way, we noticed one interesting phenomenon -- with a big wheel and small wheel, this things actually emulates a transmission with two ratios. On the larger hills, the smaller wheel prevents the car from stalling because it has to exert less torque.
posted by spiderskull at 7:47 PM on January 28, 2011

Am I the only one who gets a strong visceral reaction to seeing the malformed, cancerous-looking cars? I had to stop the simulation because it was turning my stomach. I have no idea what that means...
posted by danb at 7:50 PM on January 28, 2011 [1 favorite]

"I have no idea what that means" It means you should be glad that you never owned an AMC Pacer.
posted by HuronBob at 8:06 PM on January 28, 2011 [2 favorites]

Is there any way to get all 20 children in each generation to run in parallel? Even if that means they run much slower. It'd probably be less efficient. Regardless I think it would hold value for education. (Along with some basic Tivo controls :)

Let the car run overnight but I forgot to check on the car before shutting down. I hope I didn't accidentally throw away a solution to zero point energy!
posted by crysflame at 8:14 PM on January 28, 2011

I made one that was my friend.
posted by jimmythefish at 8:15 PM on January 28, 2011 [1 favorite]

Mine keeps creating the Time Cube.
posted by tmt at 8:26 PM on January 28, 2011

Wow... I haven't thought about breveCreatures in years. I used to have so much fun at work watching thousands of generations of mutations fly by, each more Godzilla-like than the last. In retrospect, I can't believe I used to have brain cycles available for such creative fun at work. :(
posted by tapesonthefloor at 8:30 PM on January 28, 2011

I made one that was my friend.

You're doing real good, Jimmy
posted by codswallop at 8:44 PM on January 28, 2011

All of my cars just seemed to scream "WHY WAS I????!?!?"
posted by RobotVoodooPower at 9:16 PM on January 28, 2011 [6 favorites]

Around generation 30 or so, I noticed that my cars have evolved rudimentary suspension systems.
posted by Uncle Ira at 9:59 PM on January 28, 2011

Alright, so we need to beat SkyNet in about the first 10 generations. After that organics are in serious trouble.

Do we kill all of the robots in the early generations, or just the hyper effective slaughter-bots? Because if we can manipulate the algorithm to breed just the dopey robots that land on their faces, I think we'll be OK.

Let's also consider the entertainment value of watching poorly bred killbots trying to swim in the desert, beating up rocks, and shooting themselves repeatedly. Can a genetic algorithm be written for a self-destructive bot, weighed for comedy value? Is this what god did?

P.S. If someone would like to write this program/game for me I will pay you dollars. I foresee an endless run of Ow My Balls.
posted by Abehammerb Lincoln at 10:06 PM on January 28, 2011 [4 favorites]

So after 30 generations I've got 3 main tribes, plus a bunch of odd mutations thrown every now and then. Most successful are the Tron bikes but they tend to have too big of rear wheels to climb the hills. I loathe the boxy things with the rear wheel more in the middle: the CG is too far aft, but they succeed through dog-ass perseverance because the overhang prevents flip over. I'm rooting for the 3-wheelers that work either side up; if only they could develop a longer wheel base.

The mutants I cull mercilessly.
posted by Mei's lost sandal at 10:38 PM on January 28, 2011

On a similar note, here's a genetic algorithm that generates the Mona Lisa.
posted by rahulrg at 11:19 PM on January 28, 2011

Can't get over the darn hill at 421. Two big wheels at the ends and a little one in the middle is doing well by me so far, though.
posted by cthuljew at 11:49 PM on January 28, 2011

my computer is stupid.
posted by lampshade at 12:01 AM on January 29, 2011

I seem to have breed a strain that starts out standing upright on it's tail with two or more wheels on the right-hand side. If the balance is right, it will tip over to the right and take off. If not, it will just sit there or fall over on it's back.
posted by thecjm at 12:35 AM on January 29, 2011

A week or two ago when the first version of this turned up on the programming subreddit I left it running overnight and progress had pretty much stalled, I think I was over 100 generations. That version only allowed two wheels and the best seemed to be a big front wheel to get over bumps, a small back wheel for torque up the hills, and maybe a bit of a wheelie bar to prevent flipping.

I saw this new version this morning and instantly maxed out the number of wheels and I was beating my previous best cars within 6-10 generations. You were just far more likely to have at least one decent driving wheel to get you up hills, and way, way more likely not to bottom out. I had one that basically did a backflip off every bump.

This utterly needs a multiplayer game were you have some sliders to fiddle and then classes based on number of generations and you race other players in your class with your best car.
posted by markr at 12:38 AM on January 29, 2011

My only problem with this is that I have a wide view of intelligence and I consider a genetic algorithm like this running equivalent in consciousness to a standard fly. I don't want to close the browser window and kill it for no reason when it's been trying so hard to satisfy me.
posted by Dillonlikescookies at 3:05 AM on January 29, 2011 [2 favorites]

I would like to see the mutation rate as one of the variables changed by mutation.

And I'd like to see some kind of speciation added to the mix. Does speciation help or hinder the algorithm?
posted by seanyboy at 3:21 AM on January 29, 2011 [1 favorite]

I swear I've seen this on the blue before, but I can't find it right now

This was probably what you saw, but I don't think either has been on metafilter previously.
posted by Jpfed at 3:23 AM on January 29, 2011

GA's are pretty cool, but usually not the most efficient way to solve problems. Still, people have used them for things like the Traveling Salesman problem. They work pretty well with graph theoretic optimization problems where you're not looking for a "best" solution, but just a pretty good one, since it's not so hard to slice up graphs and mix up the pieces. GARLI is another one, using a GA to come up with possible phylogenetic trees given nucleotide data. Framsticks is another package, similar to Breve. It seems like we have enough computing power by now to build a good-sized 2-D world that we could populate with pretty basic organisms capable of mating, mutating, dying off, and eating each other that might result in some pretty cool organisms and activities, (like scavenging or pack hunting). I guess we would also need to simulate different materials in order have things like armor and teeth develop. I think Framsticks includes simple neural networks, as well, which is a step in the right direction.

Still, 2-D is cool because it really drops the cycles needed for physics. Thanks for sharing.
posted by monkeymadness at 5:40 AM on January 29, 2011

I am like HuronBobs cat with this. See you in a couple of weeks...
posted by troll on a pony at 6:13 AM on January 29, 2011

Am I the only one who gets a strong visceral reaction to seeing the malformed, cancerous-looking cars? I had to stop the simulation because it was turning my stomach. I have no idea what that means...

I absolutely loved the early stages when it kept plopping down unwheeled rocks.

"Howsabout.... THIS rock.."
"... no"
"OH OH how about THIS rock..."
"... no"
"alrightalrightalright... this rock?"
posted by odinsdream at 7:47 AM on January 29, 2011 [2 favorites]

I find this thing absolutely hilarious. I'm getting lots of cars with enormous extra wheels sticking out of the roof, just revving away constantly, and tiny stabilising wheels on booms off the back.
posted by lucidium at 8:27 AM on January 29, 2011

Left it running overnight; at generation 37 there's a dominant two-wheeled model that is shockingly stable in its performance, running into trouble at one of three specific double-dips around the 400 point. It's not super fast, and it just can't get up past that hill, but it can get there every time.

Which works well as a model for extinction level events: if the thing my population needs to survive is a plant that grows at 425, all that 400-level fitness isn't worth much.
posted by cortex at 9:16 AM on January 29, 2011 [3 favorites]

Am I the only one who gets a strong visceral reaction to seeing the malformed, cancerous-looking cars?

I actually found them kind of tragically lovable, especially when they would sort of flop over and rev their misplaced wheels uselessly. It sort of evoked "puppy on ice skating rink" for me.
posted by en forme de poire at 9:18 AM on January 29, 2011

This is super fun, even for my layperson's understanding of artificial genetics. Left it running while I made breakfast - came back to discover the algorithm working out the basics of shocks and front-wheel drive.

The designs it works through reminds me a lot of early BattleBots - there were the bots who were super dangerous but useless the moment they flipped over, and the bots who were designed to wedge underneath other bots and tip them.

My best-performing cars were designed to go as well upside down as right side up - not a great commuter car, but the jagged environment they're pitched against seems to favor the creation of dunebuggys.
posted by The demon that lives in the air at 9:49 AM on January 29, 2011

Reduced the maximum number of wheels to one. Trying to evolve a unicycle.
posted by Scientist at 10:10 AM on January 29, 2011

Couple things: You get a design working that's great until that %&^#% trough at 460, and you can see that the great design is just plain not going to get past it, so you change things up and never get back to four sixty again.

Or, you finally get one certain design that does clear the trough at 460, but whatever the innovation was, it gets bred right back out again.

Definitely a cool widget. Thanks, mark242.

You DO kind of feel bad for all the crippled critters and the hopeful monsters. "Kill me! Please Kill me now!"
posted by Trochanter at 11:02 AM on January 29, 2011

Reduced the maximum number of wheels to one. Trying to evolve a unicycle.

One time when I let it run it apparently decided the successful species was a wide "V" with a unicycle at the point, like a teeter-totter -- all 20 descendents were a variation on it, with its center of gravity and wheel size varying. It would lean forward and bounce the front point off the ground, then it was swing back and hit on its 'wheelie-bar'. it does OK until a steep downhill, when it pops over onto its top. This was using their default settings and an evolution of 3, and it had all but given up on having more than one wheel at about generation 7.
posted by AzraelBrown at 11:05 AM on January 29, 2011

(927.3) though. Read 'em and weep.
posted by Trochanter at 11:07 AM on January 29, 2011

So far my best one-wheelers have a short wheelie bar in the front to prevent flips and a long wheelie bar in the back which lets the car glide along without too much friction. This is on a medium-sized wheel that gives a bit of clearance without sacrificing too much torque. They can get to 141 pretty well (there's a steep hill there that's almost too much for the wheel) and some of them can get to 157 (where there's a hill that's slightly steeper again).
posted by Scientist at 11:14 AM on January 29, 2011

And just after I wrote that I just got my first 166.7! Progress, baby! (OK, with a little artificial selection in the form of Up/Down votes).
posted by Scientist at 11:15 AM on January 29, 2011

I'm on my 208th generation (left it running last night) and while it peaked around generation 40, it does slowly seem to be getting better. Then again, it just put a wheel on backwards so the shock was touching the ground and the wheel was spinning in the carriage, so maybe not.
posted by [insert clever name here] at 11:19 AM on January 29, 2011

That's the target, not the achievement. I got past 460 once. Like I said, on mine there's a trough there that I call the widow maker. (full disclosure: I don't call it the widow maker)
posted by Trochanter at 11:21 AM on January 29, 2011 [1 favorite]

Left it running last night. With default settings after 116 generations, mine has settled on all designs being long and thin three wheels in parallel. Occasionally they have a tail to keep them from flipping over. Neat to see convergent evolution in action.
posted by rouftop at 11:26 AM on January 29, 2011

What are the score like when you get into that many generations?
posted by Trochanter at 11:36 AM on January 29, 2011

I love how this can illustrate somewhat un-obvious concepts in evolution:

Whatever that doohicky is that gets you past that hump at 65? That's going to be highly conserved. (Unless you find something else that can handle it.)

With a low mutation rate, the population will converge to getting stuck in that valley at 270... until one of them shrinks a wheel to get out of it, hitting that giant downward slope, and starting off a new era of variety, until they all get stuck at the next obstacle... punctuated equilibrium, baby.

Play along at home!
posted by PMdixon at 11:53 AM on January 29, 2011 [1 favorite]

What's also neat is how long non-functional, vestigial stuff will persevere. I had a two wheeler that went through all sorts of designs but through them all it kept this particular really cool set of steer horns.
posted by Trochanter at 12:03 PM on January 29, 2011

So far, the distance the cars can go hasn't drastically improved. However, the overall generations put out more cars that can go a significant distance.
posted by [insert clever name here] at 12:28 PM on January 29, 2011

My results seem oddly similar to technological development in the real world. They become functional pretty quickly, and then the good features are suddenly thrown away and all available models are complete rubbish for a couple of hardware generations.
posted by ikalliom at 6:08 AM on January 30, 2011 [2 favorites]

what makes this strangely hypnotic for me (I'm another person whose reaction is more or less like HuronBob's cat's) is that something in the back of my mind is absolutely convinced that sooner or later the algorithm will come up with an immortal car. of course, it never does...
posted by You Can't Tip a Buick at 12:32 PM on January 30, 2011 [1 favorite]

I right now have a run of this going that seems to be evolving towards having one giant wheel.
posted by madcaptenor at 6:27 PM on January 30, 2011

I've been sick all weekend and enjoying boxcar2d, thanks for the link. I've let mine run nonstop for a couple days and got up to 700 something.

Someone else not only did the same, but took screenshots every 5 seconds and made a cool timelapse carvolution video.
posted by mapinduzi at 8:34 PM on January 30, 2011

Can someone tell me what the % Frequency slider next to the max wheel # box does?
posted by vapidave at 11:41 PM on January 30, 2011

Aaaaaand to answer my own damn question, via the Reddit thread: "the frequency controls the chance of a car spawning with a wheel in each of the position determined by max wheels."
posted by vapidave at 12:07 AM on January 31, 2011

Someone else not only did the same, but took screenshots every 5 seconds and made a cool timelapse carvolution video.

Heh. Apparently at around the seven minute mark they got bored and checked facebook or something.
posted by ChurchHatesTucker at 10:43 AM on January 31, 2011

Two nice tracks in recent evolutions:
A giant triangle with a wheel at each point. Due to the intricacies of the algorithm, these triangle cars tend to have a jutting bit which screws up the design, but the car can orient itself any way and keep on rolling.

The other pretty successful model was a giant mass of wheels that entirely encloses the chassis with the exception of a very pointy rear roll bar.
posted by kaibutsu at 1:54 PM on January 31, 2011

It also occurs to me that the 'vestigial' front wheels on the front of a car may not be all that vestigial. In particular, they may be affecting the angular momentum of the rest of the car, keeping it from flipping over as readily. Also, I've seen designs come up where the vestigial wheel acts as a bumper, due to the shocks, while also providing a bit of roll upwards against the obstacle that it hits.
posted by kaibutsu at 3:52 PM on January 31, 2011

The new version is now up - cars are breakable!
posted by zamboni at 6:29 AM on February 24, 2011

I've got the new version running. I'm curious as to whether the breakable aspect can be advantageous. As in, a car would evolve that would shed mass for a particularly steep climbing part of the course.
posted by Trochanter at 10:22 AM on February 25, 2011

The breakage just adds to the pathos of the whole exercise.
posted by lekvar at 1:04 PM on February 25, 2011