I'm currently stuck at 1233 after 250 generations. The last improvement was at gen 183. Walking gets part way down the first downslope, then falls. The current champions are far better than any of their mutations, so a local maximum has been reached. This is the fate of most evolutionary AI.<p>Once on the downslope, the controller for flat ground won't work, so now it has to jump to something substantially more complex to progress. Making such jumps was an unsolved problem with genetic algorithms 20 years ago, and I commented back then that whoever solved it would win a Nobel Prize. Still waiting.<p>I suspect that a solution lies in work on neural nets where one net is trained, then a second, smaller, net is trained to match the first. This is a form of "abstraction". Somewhere in that space is something very important to AI.
A bit OT, but I remember a very cool Quake2 mod that basically built a neural network so that bots could learn how to play.<p>The useful part was that you could save the NN to a file, and so you could let Q2 run for hours (mostly I left it at night so it wouldn't prevent me from playing :) ) and the hext day I would save the progress.<p>After about a week of doing this everynight, the bots evolved from just jumping around in their spawn points without moving, to actually run around the level and shoot the other bots on sight.<p>They didn't really have a good aim, but sometimes they would land a rocket or a rail. I always wondered how much time would I have to let the bots evolve so that they would become competitive.<p>Unfortunately after some time I lost my NN files and lost the project page. Some time later I found again the project but it was not updated and the download files were broken.<p>Wish I had saved the mod :(<p>Now, honest question: would this kind of approach work for, say, programming a Hello World program? or would the number of variables and possibilities is too big?<p>It would be interesting to put several of these bots to compete against each other, but in different languages and see which one is "easier" to grasp by the bot.
I suspect that the best way to tackle this problem is to treat "learning to walk" as a reinforcement learning problem. This way you can evaluate actions within each episode rather than waiting until the end of each trial to adjust parameters encoding the walking strategy.<p>As karpathy suggests below (and he's certainly much more qualified than me), an evolutionary method such as GA's, while apparently fairly effective, could well be wasting valuable information learned in real time through interaction.
One interesting thing is that progress very much happens by fits and starts, as it waits for the "lucky mutation" that will enable evolution to continue.<p>For example,<p><pre><code> 0 Bedaaa Ceeici 6.07
1 Bocodo Bidobo 105.93
3 Aibebe Docoeo 107.74
7 Diaebe Eocoeu 107.88
10 Ciaabe Eocoeo 107.95
25 Diaebe Facodu 108.19
28 Biaebe Eocoeo 108.20
30 Biaeae Eacoeo 108.47
35 Beaebi Fucieo 109.88
36 Biaebi Eucici 203.60
42 Biaibi Fuceci 204.65
45 Aiaibi Fuceeo 206.30
47 Aiaibi Fucici 206.60
48 Aeaebe Eoceeo 412.96
56 Beaebe Euceeo 414.05
59 Beaebi Fubiei 415.76
73 Beaebi Focieu 519.01
75 Beaebi Eocido 519.39
96 Baaebi Gidido 521.00
99 Baaebe Focedo 627.14
</code></pre>
There are pretty massive jumps at generation 36, 48, 73 and 99.<p>By the way, this is at 50% mutation probability and 25% mutation amount. It got stuck way earlier with large less frequent mutations (as one would expect, if the probability of a beneficial mutation occurring is the limiting factor).
Ah. Aiaeca Eeaeci rocking it at 1048.50 at gen 256.<p>EDIT I've heavily tweaked my config throughout depending on whether I thought I was trapped at a local maxima, etc. Right now I think I've settled on for late-game:<p>10% mutation prob
1% mutation amount
3 to copy<p>Currently: 1056.91 @ 338.
With a Core i7, I wasn't expecting the simulation to run so slow, even at the lowest settings.. Maybe Firefox on RHEL 6 isn't the optimal platform for this little toy?<p>--edit: it runs much, much faster on Firefox with Windows 8.1. Not a Core i7, but an AMD 8-core thing. Must be Firefox on Linux's implementation, unless it's a video card/driver thing.
Fun, but even after hundreds of generations the walkers are still pretty bad. How good would they be after thousands or millions of generations? Is it even feasible to create a decent walker using genetic algorithms?
I'd like to see a genetic algorithm evolutionarily figuring out what parameters give you best performing walkers in shortest time ;) Meta-genetic if you will
I was just about to give up at 70th generation, when the walkers suddenly evolved from 1 to 4 steps in 5 generations.<p>Currently at generation 120 with 7 steps, looks like it is "evolving" in bursts, with long periods of nothing.<p>Well it is stuck at 9 steps at gen 400+.<p><pre><code> 327 aibobe baeado 948.93
>> 548 aibobe baeado 1058.76
</code></pre>
I wonder if the author got any further. I would say this is close to the limit.
So is this really a genetic algorithm, or is it hill-climbing? Are you combining genomes from different individuals? Or are you just mutating a single genome? There are no controls for crossing genomes, so it seems likely to be hill-climbing.<p>If not, how are you mapping the genome to the phenome?
Reminds me of this really fantastic video of finding the gaits of different sized/legged 'animals' at different speeds:
<a href="http://vimeo.com/79098420" rel="nofollow">http://vimeo.com/79098420</a>
I just got one that evolved kneeling to last a few more seconds: <a href="http://imgur.com/mii9N8J" rel="nofollow">http://imgur.com/mii9N8J</a>
Reminded me about <a href="http://rednuht.org/genetic_cars_2/" rel="nofollow">http://rednuht.org/genetic_cars_2/</a><p>If you're disappointed with walkers' performance, try cars, they improve much more. The principle remains the same of course. Attention: addictive.
You seem to have some bugs with the copying of champions and/or the identical reproduction of walks at the very short simulation length. Without having adjusted simulation parameters I no longer have my highest scoring walker saved as a champion.
Very cool! I did my master thesis in Genetic Algorithms and bipedal robots. You can watch the results here: <a href="https://www.youtube.com/watch?v=SYONnbvsxz0" rel="nofollow">https://www.youtube.com/watch?v=SYONnbvsxz0</a>
This looks like fun!
It seems that the copied champions are simulated in every run. As long there is no random influence you can probably skip this simulation, as the simulation of the champions is also most likely the most CPU intensive.<p>EDIT: Grammar.
Converged pretty fast to the first step on the 10th gen, then got stuck having a seizure and falling on it's head "forever".<p>I bet this would be interesting evolving a simpler movement mechanic, like in bacteria.
This is how NaturalMotion started. I remember their CEO Torsten evolving muscle controllers on the Mathengine physics engine (1999?). Get it right, and you get to build a pretty nice business out of it!