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

61–70 of 75 posts

Re: Genetic Algorithm Walkers

#61

Post by deong »

saganus wrote: post #52
deong wrote: post #49

Earlier quoted context omitted.

There are branches of evolutionary computation that aim to evolve programs. The best known examples are Genetic Programming (GP) and Evolutionary Programming (EP). GP is by far the most popular today, and involves evolving source code, generally in Lisp-like languages where programmatically manipulating source code is a bit easier, but there are also GP approaches that use stack-based languages like Forth or Factor.…

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

Re: Genetic Algorithm Walkers

#62

Post by Houshalter »

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…

What you describe is called local optima and it's well studied. There is no magic way around it, you just need to put resources into exploring a larger area. Methods include selecting really diverse solutions rather than just the best one, restarting the simulation with a new random population, or sometimes throwing away the best solution and letting it wander around randomly longer before converging.

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

Re: Genetic Algorithm Walkers

#63

Post by codys »

im3w1l wrote: post #60
fivedogit wrote: post #41

Earlier quoted context omitted.

This is called punctuated equilibrium. Evolution happens in fits and starts after periods of relative non-change. http://en.wikipedia.org/wiki/Punctuated_equilibrium

If you look at how the scores for the walkers increase as they walk, you will see that it jumps in increments of 100. I guess it is some kind of "milestone bonus".

The page says "bonus points are given for each proper step forward".

So it appears they are optimizing for whatever their idea of a "proper step" is.

Re: Genetic Algorithm Walkers

#64

Post by codys »

V-2 wrote: post #37

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.

Yep, I remember that and http://boxcar2d.com/ ending up on HN some time ago

Re: Genetic Algorithm Walkers

#65

Post by Florin_Andrei »

Houshalter wrote: post #43
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…

Someone made a GA evolve a hello world program in brainfuck. It's definitely possible, but incredibly inefficient.

If you look at the trillions of creatures thrown at the evolutionary game every day in real life, Mother Nature herself is not terribly efficient either.

Re: Genetic Algorithm Walkers

#66

Post by meric »

deong wrote: post #49
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…

There are branches of evolutionary computation that aim to evolve programs. The best known examples are Genetic Programming (GP) and Evolutionary Programming (EP). GP is by far the most popular today, and involves evolving source code, generally in Lisp-like languages where programmatically manipulating source code is a bit easier, but there are also GP approaches that use stack-based languages like Forth or Factor.…

I once experimented with small math calculation programs and found if I added a heuristic for selecting programs with less length, given equal correctness, the former is preferred. This helped evolve shorter more readable programs.

Re: Genetic Algorithm Walkers

#67

Post by rednuht »

codys wrote: post #63
im3w1l wrote: post #60

Earlier quoted context omitted.

If you look at how the scores for the walkers increase as they walk, you will see that it jumps in increments of 100. I guess it is some kind of "milestone bonus".

The page says "bonus points are given for each proper step forward". So it appears they are optimizing for whatever their idea of a "proper step" is.

That's every time the legs switch places. Without that bonus, you'd get a lot of QWOP-ish individuals dragging one foot behind. :)

Re: Genetic Algorithm Walkers

#68

Post by Houshalter »

ColinWright wrote: post #59

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. If not, how are you mapping the genome to the phenome?

In the source code their is a function for mating.

Re: Genetic Algorithm Walkers

#69

Post by happycube »

Houshalter wrote: post #43
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…

Someone made a GA evolve a hello world program in brainfuck. It's definitely possible, but incredibly inefficient.

Would that be like an infinite number of bonobos...?

Re: Genetic Algorithm Walkers

#70

Post by markovbling »

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

Post reply on HN