Genetic Algorithm Walkers
rednuht.org
rednuht.org
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.
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.
>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.
Neural nets have a lot of desirable properties for this kind of stuff. Mainly that they can be trained with reinforcement learning. Instead of randomly testing which solutions work better, you have them try to predict how good each action is.
I used to work on legged locomotion. Once you get off the flat, traction control ("anti-slip") starts to dominate the problem. It looks like this simulation isn't going to evolve anti-slip control.
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.
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.
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.
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.
Wish I had saved the mod :(
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?
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.
EP is about evolving finite state machines, and from there, you could presumably infer a program in the conventional way, although it might not be particularly nice for humans to read. Neither are the programs learned by GP though, for that matter.
Presumably I would expect to see the first few iterations produce nonsense, but maybe after a while, a bot is able to correctly write a variable assignment.
The first obvious problem I see comes from the fact that we know we can have a completely valid piece of code after gibberish and the compiler won't notice the difference.
But what about if there's a compiler able to "score" the "correctness" of the program? that would solve that issue and in theory be able to "learn" how to program, albeit slowly and like you say, most likely not human readable.
This is why the bread-and-butter of GP is in symbolic regression. Rather than deal with programs that do literally anything, we focus on evolving mathematical expressions. Given a set of data points, can you find a regression equation of some variables that minimize the error on the training data? There are no syntax errors to worry about, no early termination, no control flow, just a small fixed set of arithmetic operators, numbers, and variables. And by keeping the domain in numeric functions, you get a free error metric that is generally sensible.
There is talk in the field about the future -- can you evolve a web browser, for instance -- but this is very futuristic at the moment at least.
But then, I remember doing some work on college about Gödel number (https://en.wikipedia.org/wiki/G%C3%B6del_numbering). Would it be possible for example, to use this as a form of encoding instructions?
Maybe if arbitrary programs are too broad of scope, how about specifically getting only one instruction correct? e.g. to evolve the correct print(message) syntax. Do you have any references to this? it's a fascinating subject!
Others have mentioned that people have evolved "Hello world" in Brainfuck, so it's definitely possible to do interesting things. It's just too ambitious right now to shoot for actually useful programs.
http://www.forbes.com/sites/erikkain/2013/07/02/quake-iii-ar...
Could be urban legend but fun story nonetheless :)
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.
For example,
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
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).
So it appears they are optimizing for whatever their idea of a "proper step" is.
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:
10% mutation prob 1% mutation amount 3 to copy
Currently: 1056.91 @ 338.
--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.
It's probably the physics simulation. Though random JS benchmarks show Chrome and Firefox to be approximately equal in JS performance on my computer, Chrome beating FF slighly on sunspider and the other way around with Octane.
The rotation speed for each joint on each simulation step is given by:
x * cos(y + z * simulation_steps);
This is also an important feature in the SIMBICON controller, which is arguably the simplest and most robust walker system. (http://www.cs.ubc.ca/~van/papers/Simbicon.htm)
EDIT: and yes, Reinforcement Learning is much more effective way of attacking this type of problem (e.g. see some recent work from Sergey Levine http://www.eecs.berkeley.edu/~svlevine/), but I also agree with the author that GA are fun :)
It doesn't really say how it works, but it doesn't seem like a very natural way to do walking. E.g. here is are evolved walkers in a more complicated 3d simulation: http://vimeo.com/79098420 They seem to get very good after just a few generations compared to this.
Currently at generation 120 with 7 steps, looks like it is "evolving" in bursts, with long periods of nothing.
Well it is stuck at 9 steps at gen 400+.
327 aibobe baeado 948.93
>> 548 aibobe baeado 1058.76
Some gait branches seem to reach a dead-end where any improvement would need to come from a major overhaul of the gene combination instead of small mutations.
The terrain starts to get more variation as the distance increases, so that's another piece of evil against the walkers. :D Maybe I should turn that off.
I've let it run for a couple of days. I don't think I got past 12 steps, but it looked pretty regular walking for a while. :)
3 floats for each joint, to be precise. Then those are combined to set the speed of the motor in each joint on every simulation step.
I tried more complex genomes, but it just takes way too long to get any kind of improvement. It didn't make for a fun casual browser experience. :)
0 Cicebi Bicedi 206.20
1 Cibebi Dibodi 208.03
4 Cobebi Bibedi 208.54
6 Cobebi Bobedi 208.68
8 Cocebi Boaedi 209.53
14 Cocibi Boaedi 310.47
20 Cocebi Boaedi 312.73
36 Cocebi Boaedi 312.85
38 Cocebi Biaedi 312.89
40 Cocebi Bobedi 314.06
58 Cocebi Bobedi 417.71
119 Cicebi Bibodi 522.37
331 Cicebi Bibuei 624.26
And at ~500 generations the champions are still the same 3. I have fiddled with the parameters several times to no avail. I've tried very little mutation probability (1-5%) with low mutation amount (1-10%) but also 75-100 mut. prob with 1-5% mutation amount and any figures in between and nothing seems to make it go out of the local minima.
Is there any way to get out of this? or when this happens in nature the species simply goes extinct or gets eaten by everyone else?
I guess it kinda stuck into an inbreeding sort of loop.
If not, how are you mapping the genome to the phenome?
If you're disappointed with walkers' performance, try cars, they improve much more. The principle remains the same of course. Attention: addictive.
EDIT: Grammar.
I bet this would be interesting evolving a simpler movement mechanic, like in bacteria.