Evolver rules the 94nop!!!

[Fizmo]

Congratulation bvowk!!!!

His purely evolved warrior Machines Will Rule enters the 94nop hill on
2nd place. That is absolute impressive!!!!

When do we see the first purely evolved koth?

Christian

[Chip Wendell]

> Congratulation bvowk!!!!
>
> His purely evolved warrior Machines Will Rule enters the 94nop hill on
> 2nd place. That is absolute impressive!!!!

Yes, indeed! That represents a lot of hard work and dedication.
Congratulations!

> When do we see the first purely evolved koth?

Very soon, I feel sure. This first one is close already, so it won't
be long. If you could just get those Opterons to spit out a scanner...

[Barkley Vowk]

Fizmo wrote:
> Congratulation bvowk!!!!

Thanks Fizmo :) I'm pretty impressed, but I was hoping for #1 spot. Roy
keeps holding the poor machines down :) My hope is that it sticks on the
hill long enough to make it into the Hall of Fame, at which point I'll
retire from corewars and bore my future grandchildren with stories about
it.

> His purely evolved warrior Machines Will Rule enters the 94nop hill on
> 2nd place. That is absolute impressive!!!!
>
> When do we see the first purely evolved koth?

If anybody is interested in looking at the code, you can find it now at
http://www.math.ualberta.ca/~bvowk/corewar.html

Those interested might also want to look at CoreWarrior 90 for an
article about evolving for the LP hill on SAL.

[pauld...@aol.com]

Wanted to ping this conversation because it was just 10 years ago that an evolved warrior placed high on the 94nop hill. I don't remember another following in it's place.

P. Kline

[inversed]

On Thursday, September 30, 2004 9:13:12 PM UTC+3, fizmo wrote:

> His purely evolved warrior Machines Will Rule enters the 94nop hill on
> 2nd place. That is absolute impressive!!!!

That is absolutely false, no way bvowk's warriors could be called purely evolved. For a warrior to be considered purely evolved, there must be no direct human intervention in the process. One can tweak the genetic algorithm parameters, but not the actual redcode individuals. Bvowk's evolver uses too much prior knowledge to be qualified as a pure evolver. Not just abstract redcode knowledge, but knowledge about actual construction of human-coded warriors in form of instruction chains used for population initialization. The chains are 5 instructions long, so effectively the population is initialized with instruction sequences from human warriors. Which is clearly a direct intervention in the evolution process.

muGP-"evolved" warrior White Noise is a similar case. Not really evolved, but recombined from pieces of existing human-coded warriors. The authors forgot to mention that muGP cannot handle infinite loops and would have been useless without this trick.

So outside of the nano hill, there are very few good purely evolved warriors: bestwar4.red and redrace_lp 1 by Dave Hillis, and RedShift papers on the tiny hill.

I have myself experimented with non-random population initialization techniques. They are a cheap way to speed up the evolution. And they have their downsides. Most importantly, seeding the population with any kind of human-like code dramatically changes the course of evolution by shifting the focus into a specific area of search space. Resulting warriors look very different from purely evolved ones. This is not to say that seeding should not be used, it can produce some very interesting results. But the resulting warriors can only be called semi-evolved.

Seeding based on human code also reduces the population diversity. And in regards to maintaining diversity, bvowk uses the worst replacement scheme possible. Combining these two methods is a sure recipe for premature convergence, one of the biggest problems of the genetic algorithm.

The fact that purely evolved warriors look nothing like handcoded ones is a huge advantage and not a drawback of the evolutionary approach. Instead of coming up with contrived "improvements", evolver authors should focus on the really important stuff: mutation and crossover operations, replacement and selection schemes, diversity maintenance. And don't forget that genetic algorithm is not the only option. Other metaheuristics may work even better.

[Skybuck Flying]

"
Seeding based on human code also reduces the population diversity. And in
regards to maintaining diversity, bvowk uses the worst replacement scheme
possible. Combining these two methods is a sure recipe for premature
convergence, one of the biggest problems of the genetic algorithm.

The fact that purely evolved warriors look nothing like handcoded ones is a
huge advantage and not a drawback of the evolutionary approach. Instead of
coming up with contrived "improvements", evolver authors should focus on the
really important stuff: mutation and crossover operations, replacement and
selection schemes, diversity maintenance. And don't forget that genetic
algorithm is not the only option. Other metaheuristics may work even better.
"

Perhaps "breeding" young and old might solve the convergence/diversity
problem somewhat ;)

Bye,
Skybuck.

[pauld...@aol.com]

My take on evolving. Until someone is willing to invest gazillions of cycles to evolve some new warrior plan out of random bits, you either seed with existing code fragments, or stick to the more restricted hills.

Maybe you could breed for the small hills and cross the winners over to the larger hills.

For the moment it is more practical to write plans by hand and use the machine to find good constants.

I think one of the challenges is that to-date no one plan has been demonstrated to be effective against all other plans. There are anti-plans for pretty much everything published so far. Which leads evolvers to lock in on warriors that are highly optimal against a subset of opponents but fail miserably against others. They are pretty good at generating p-components.

P. Kline

[Zul Nadzri]

On Thursday, 4 December 2014 18:26:20 UTC+8, inversed wrote:

> muGP-"evolved" warrior White Noise is a similar case. Not really evolved, but recombined from pieces of existing human-coded warriors. The authors forgot to mention that muGP cannot handle infinite loops and would have been useless without this trick.

In my opinion, uGP did evolve random warriors and benchmarks against a set of warriors to rank the newly generated warrior. uGP never 'see' or 'copy' from the benchmark warriors but it only see the scores against them. From these score, uGP do the normal GA routines i.e. ranks the evolved warriors and gets children from these parents.

Regarding infinite loop, I think I need to check the 'dynamic' option for uGP vs static warrior benchmark... I only experienced using the benchmark against other warriors option since dynamic would make the evolving much slower on my machine.

[Roy van Rijn]

> uGP never 'see' or 'copy' from the benchmark warriors but it only see the scores against them.

I haven't looked at how it works exactly, but the description of MicroGP clearly says that it: "was extended with the ability to assimilate existing code"

This means it has the ability to borrow knowledge from existing warriors, reading the code (not just the scores). White Noise for example is very similar to Sneaky Spike (assimilated that code?)...

Zul, you should know this because you've created 'White Spikes Sneaky Noise' stripping some evolved lines from White Noise making it look again more like Sneaky Spike ;-)

I don't think this is a bad thing per se, but IMHO you can't call those warriors 'purely evolved'. Most of the time they are heavily based on existing plans, like Paul mentions. Most optimizers I've written myself also include other mutations than just step size, for example trying different types of bombs etc, all automatic. I still see those things as optimizers, not evolvers.

The big problem with evolvers I think is that lines and loops depend on each other making the warrior quite fragile. Evolvers should learn to use those labels, inserting or removing a line updates the references to other lines, but that is hard, this is something microGP does pretty well I think.

[John Metcalf]

White Noise appears to be evolved from S774++ by Michał Janeczek (published 2002). The step, gap and first scan location are the same.

http://corewar.co.uk/ss2002/round1/S774.RED

John

[pauld...@aol.com]

On Monday, December 8, 2014 2:48:30 AM UTC-6, Roy van Rijn wrote:
...

> The big problem with evolvers I think is that lines and loops depend on each other making the warrior quite fragile. Evolvers should learn to use those labels, inserting or removing a line updates the references to other lines, but that is hard, this is something microGP does pretty well I think.

One way to accomplish that is to generate a small set of 'reference' numbers, and a label on every line. Then operands are generated using either the references or the labels, which will increase the likelihood of cooperating instructions. The reference numbers mutate along with the instructions.

P. Kline

[Zul Nadzri]

On Monday, 8 December 2014 16:48:30 UTC+8, Roy van Rijn wrote:
> I haven't looked at how it works exactly, but the description of MicroGP clearly says that it: "was extended with the ability to assimilate existing code"

From what I experienced with uGP, the first many generations of warriors were nothing like the benchmark warriors. So random, I wish uGP could take some codes from the benchmark warriors to quickly generate good warriors. Mor often that not, I need to reset the run. May be "assimilate existing code" refer to the previous generations. Could be also the way I set up uGP that it is not optimised as what the uGP team has done.

> Zul, you should know this because you've created 'White Spikes Sneaky Noise' stripping some evolved lines from White Noise making it look again more like Sneaky Spike ;-)

I noticed the similarity ...proceed to test if the main code without decoy at the bottom can improve the score. May be White Noise taking advantage of many forward scanning/clear warriors to get to the top.

[inversed]

On Friday, December 5, 2014 6:32:37 PM UTC+3, pauld...@aol.com wrote:
> My take on evolving. Until someone is willing to invest gazillions of cycles to evolve some new warrior plan out of random bits, you either seed with existing code fragments, or stick to the more restricted hills.

When I wrote RedShift, I did not have enough computing power to use it for anything larger than nano. But this time things are totally different with only a basic quad-core CPU. I have obtained excellent results for the tiny hill in a matter of few days. And tiny is not radically different from 94nop, the strategies are comparable. So I expect interesting purely evolved warriors without gazillions of cycles. I'll start evolving for 94nop after I'm done with tiny and maybe LP.

> Maybe you could breed for the small hills and cross the winners over to the larger hills.

Yes, this might save a lot of time. But again, diversity will likely suffer.

> I think one of the challenges is that to-date no one plan has been demonstrated to be effective against all other plans.

I hope it remains that way :)

> There are anti-plans for pretty much everything published so far. Which leads evolvers to lock in on warriors that are highly optimal against a subset of opponents but fail miserably against others. They are pretty good at generating p-components.

This often happens in early evolution stages when djn streams may start to dominate the population because they have very high scores against certain scanners. However, once things progress beyond such trivial warriors, I do not experience overspecialization. The problem might be solved by using a contraharmonic-like score mean instead of the arithmetic one. For now, I just manually remove benchmark warriors that contribute high scores to trivial warriors if I see that the evolution is getting stuck.

On Monday, December 8, 2014 10:20:18 AM UTC+3, Zul Nadzri wrote:

> Regarding infinite loop, I think I need to check the 'dynamic' option for uGP vs static warrior benchmark.

It has nothing to do with benchmarking, only with handling control flow instructions. Vanilla muGP is incapable of evolving something as simple as nop 0 / jmp -1. Read the papers.

On Monday, December 8, 2014 11:48:30 AM UTC+3, Roy van Rijn wrote:

> The big problem with evolvers I think is that lines and loops depend on each other making the warrior quite fragile. Evolvers should learn to use those labels, inserting or removing a line updates the references to other lines, but that is hard, this is something microGP does pretty well I think.

Not hard at all, RedShift detects labels and updates references with certain probability.

[pauld...@aol.com]

On Wednesday, December 10, 2014 9:35:14 AM UTC-6, inversed wrote:
...
> This often happens in early evolution stages when djn streams may start to dominate the population because they have very high scores against certain scanners. However, once things progress beyond such trivial warriors, I do not experience overspecialization. The problem might be solved by using a contraharmonic-like score mean instead of the arithmetic one. ...

I found this link useful in comparing various means:
http://jwilson.coe.uga.edu/EMT668/EMAT6680.2000/Umberger/EMAT6690smu/Essay3smu/Essay3smu.html#anchor423180

I guess that if you have more than 2 variables it becomes a multi-dimensional trapezoid. My mathematical education doesn't extend far enough to give me a word for that :-) But the calculation is still simple. I've been using RMS in my evolver and relying on random 'disruptive epochs' during which mutation rates rise and cause it to unstick.

P. Kline