Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Genetic Algorithm Walkers

rednuht.org

Post reply on HN
Print view View original

71–75 of 75 posts

Re: Genetic Algorithm Walkers

#71

Post by Animats »

Animats wrote: post #54

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. Once on the downslope, the controller for flat ground won't work, so now it has to jump to something substantially more complex…

Just to see if any further improvement was possible, I left this running for over 18,000 generations. 98% of the improvement had happened by gen 183. The last minor improvement was at gen 7313. There's no sign of a controller evolving that can handle non-flat terrain.

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.

Re: Genetic Algorithm Walkers

#72

Post by saganus »

deong wrote: post #61
saganus wrote: post #52

Earlier quoted context omitted.

I Was thinking for example, how hard would it be to let an algorithm pick a random number of valid tokens from a language (say java) and the suyccess metric be something like, the amount (or score) of errors that the compiler returns. 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…

Number of syntax errors is extremely weakly predictive of program correctness, and figuring out correctness of arbitrary source code is extremely difficult. 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 minim…

That's very interesting.

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!

Re: Genetic Algorithm Walkers

#73

Post by saganus »

markovbling wrote: post #70
saganus wrote: post #40

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 aroun…

Reminds me of the 'bot armistice' where a guy let a bot-vs-bot match run for 4 years and the steady state was 'the bots on both teams are simply standing still, not doing anything. The server is running and the game isn’t frozen. The bots are simply standing there, not killing one another.' http://www.forbes.com/sites/erikkain/2013/07/02/quake-iii-ar... Could be urban legend but fun story nonetheless :)

So basically, a WOPR's "the only winning move is not to play" moment?

Re: Genetic Algorithm Walkers

#74

Post by hellbanner »

maaaats wrote: post #44
hellbanner wrote: post #42

Please make one for QWOP http://www.foddy.net/Athletics.html

There already is, actually. I read the paper a while back. Video: https://www.youtube.com/watch?v=eWxFI3NHtT8 Paper: http://dl.acm.org/citation.cfm?id=2598248

You made my day. Nice find!

Re: Genetic Algorithm Walkers

#75

Post by deong »

saganus wrote: post #72
deong wrote: post #61

Earlier quoted context omitted.

Number of syntax errors is extremely weakly predictive of program correctness, and figuring out correctness of arbitrary source code is extremely difficult. 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 minim…

That's very interesting. 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…

I don't have any references for it, but evolving correct syntax should be doable I think, at least for smallish scale problems.

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.

Post reply on HN