Genetic Algorithm Walkers • Hacker News Board

Re: Genetic Algorithm Walkers

#31

Post by sinwave » Mon, Jan 19, 2015, 8:48 PM UTC

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.

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.

Re: Genetic Algorithm Walkers

#32

Post by kendallpark » Mon, Jan 19, 2015, 9:03 PM UTC

Ah. Aiaeca Eeaeci rocking it at 1048.50 at gen 256.

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.

Re: Genetic Algorithm Walkers

#33

Post by codezero » Mon, Jan 19, 2015, 9:05 PM UTC

constexpr wrote: post #30

myrkvid wrote: post #28

Earlier quoted context omitted.

Quite interesting! Is there any source code available publicly for this?

I'm always confused when people ask me this question. All browsers have the ability to view the source code of a web page (View > Developer > View Source in Chrome). The source code is here: http://madebyevan.com/nn-gait/script.js . Is that what you meant?

Most people assume the in-browser code will not be the fully commented, clean and presentable code that is more likely to appear on Github, I think that's what prompts queries like this :)

Re: Genetic Algorithm Walkers

#34

Post by hcarvalhoalves » Mon, Jan 19, 2015, 9:06 PM UTC

Converged pretty fast to the first step on the 10th gen, then got stuck having a seizure and falling on it's head "forever".

I bet this would be interesting evolving a simpler movement mechanic, like in bacteria.

Re: Genetic Algorithm Walkers

#35

Post by gus_massa » Mon, Jan 19, 2015, 9:06 PM UTC

clemsen wrote: post #10

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. EDIT: Grammar.

The simulation of the champions is unnecessary, but it's a nice detail. It gives a visual sense of improvement.

Re: Genetic Algorithm Walkers

#36

Post by lukev » Mon, Jan 19, 2015, 9:09 PM UTC

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.

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

There are pretty massive jumps at generation 36, 48, 73 and 99.

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

Re: Genetic Algorithm Walkers

#37

Post by V-2 » Mon, Jan 19, 2015, 9:35 PM UTC

Reminded me about http://rednuht.org/genetic_cars_2/

If you're disappointed with walkers' performance, try cars, they improve much more. The principle remains the same of course. Attention: addictive.

Re: Genetic Algorithm Walkers

#38

Post by V-2 » Mon, Jan 19, 2015, 9:37 PM UTC

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

Re: Genetic Algorithm Walkers

#39

Post by V-2 » Mon, Jan 19, 2015, 9:47 PM UTC

Houshalter wrote: post #27

Aqwis wrote: post #15

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?

These simulations are very sensitive to the parameters, some of which we don't even have control over (e.g. population size or what method to select the next generation.) And especially the way the genome is represented. 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 see…

Now that's awesome!

Re: Genetic Algorithm Walkers

#40

Post by saganus » Mon, Jan 19, 2015, 9:51 PM UTC

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.

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.