Saturday, April 12, 2008

The Pinocchio Function, Part 4: Two Steps Forward, Two Parts Chaos

The story I'm telling here is true. The dates are approximate and the events are summarized, but I'm not making this shit up. This is part four of the recap of the story so far. You can find part 1 here, part 2 here, and part 3 here.

The path before me was clear. I needed to restep down this lonely path of code and reshape my vision to conform to their reality if I was ever going to get their reality to conform to my vision.

So I did. I spent several late nights coding an evolutionary computational engine, which the specific details of the architecture will not be disclosed here for numerous reasons. Sufficient to say that the first night I got it going and solving problems was nothing short of elating, despite the fact that the problems it was solving were trivial. It really didn't matter: I had succeeded in harnessing nature's wisdom of tapping evolution as a process by which order comes out of chaos, and I'd done it by standing on the shoulders of giants who came before me.

And like the aforementioned giants must have at some point, I ran into glass ceilings; a point after which you can see there's further onward to go, but cannot escape your present confines to advance. For me these ceilings presented themselves in what can basically be described as a lack of biodiversity, because even as my understanding and the resulting complexity of the code base grew, I kept running into the same problem: The code would evolve to the point it's fitness function agreed it should evolve to, and then stop. This is analogous to a goldfish growing to the size of it's bowl, and what I realized was that I needed to stop treating the thing like a goldfish.

If life really were to evolve from with a digital landscape, it would be the resulting emergent behavior that happens when you have lots and lots of biodiversity co-evolving on a shared landscape, not one goldfish growing to the size of it's bowl. In fact the landscape would need to support an ever increasing amounts of biodiversity AND increasing population sizes.

The other thing that I realized is that intelligence and life itself provides it's own fitness function, because that which is more capable of applying intelligence to it's existence is by definition better at surviving, and that this is especially true when we're talking about organisms co-evolving on a competitive landscape. This is a gross oversimplification of the real process, but the underlying logic is sound in that emergent behaviors provide their own set of challenges to be overcome by individuals in a population. What this means is that simply by subjecting an evolving process to evolutionary competition with another evolving process you end up with co-evolving processes which should impose new evolutionary challenges as a result of being in competition with each other.

In other words if you create a landscape which is increasingly expansive and find a way to populate it with organisms which are capable of evolution and put them in competition with each other for survival, evolution will do it's task of enforcing that only changes which are beneficial to survival continue.

The idea actually came to me when watching videos of other evolutionary computational engines running with the fitness function removed. These runs would often display the most extraordinary examples of what can only be described as evolutionary epochs as these little programs first discovered ways to dominate the landscape and then began competing with each other, each successive generation displaying increasingly aggressive behavior as swarms of similarly colonies of code swept across the landscape, in turn displaying increasingly complex behavior to enhance it's survival prospects.

It would start simply, with just whatever was fastest at propagating, and soon one variation of code would dominate the landscape. But eventually something that didn't replicate over code that was like itself mutated into existence, and this proved to be better because it was able to replicate with greater consistency than it's inferior parents and it would soon dominate. And then something which attacked code which checked it's neighbor took over because once again it was better at survival. And this process kept repeating and repeating until a few very virulent strains were all that survived, forever locked in this war of constantly overwriting each other as fast as their virtual CPU's would allow them.

But from looking at the resulting code when I did this on my own, I didn't get this right away. Because each simulation consists of a very large number of CPU's executing in parallel all networked together it was the interaction between them that gave rise to what was most interesting. I kept on looking at things from the perspective of what a CPU is doing, and what code it was executing, like we do now with computers. But what I realized was that this was not really a useful way to envision what was happening at all, and instead I needed to follow the code as it replicated from CPU to CPU.

And this turned out to be an interesting problem indeed! Little did I know the life and death of a piece of evolving code would hold the key to my understanding of the Pinocchio Function.

Coming up in part 5: Amazing Technicolor Dreamcode

Labels: , , , , , , , ,

Saturday, December 08, 2007

The Genesis of Design

I met a neat guy the other day.

This guy had a pretty crazy claim. He said had created a program which did for computing what evolution does for life: It adapts to what ever problem it faces.

And he challenged me to test it out. So I did. Over the next few weeks I'm going to blog what I find out.

So just imagine for one second you had a time machine, and you traveled into the future 2000 years, and you purchased a kid's biology teaching toy, an Insta-Biomatic 3000. It allowed you to create little populations of simple organisms that you could evolve into different things by telling them what you wanted them to do, and feeding the ones who work towards your goal, while starving the ones who rebel. Now imagine for a second this product exists today, and I own one. Yeah, sounds like crap, right? Wait and see...

So I decide I'm gonna start out simple. The claim is it can be trained to do any task from image recognition to signal processing, but I need to understand it first. I start by seeing if it can figure out how to multiply a number by itself. Easy to express, easy to know when it's right. I create a new set of organisms, and I give them all random numbers to work with, and I let it run for a bit, and at first it's just fail fail fail across the board. I smile to myself and think, "Oh sure. It's gonna do what now?" and the best part it I'm not telling it the right answer at all, I'm just telling it, "Nope, you got it wrong." It's a bit like asking 10,000 people "The question is: 8485832451, what's the answer?" and then telling them they're all dead wrong, thanks for playing, no you don't get to know what the answer was.

But after about a minute and a half of just completely random guessing, one of them got it right just by sheer luck. Then a few seconds later he got it right again. And then he missed, but his neighbor got it. On the next try they both got it, and soon after that it was a small chorus of consistently right answers. After 3 minutes I had a small population of organisms whom 90% of them would consistently get the answer right, no matter what number I handed them.

Ok, big deal. It can multiply a random number by itself consistantly. More to the point it can evolve a solution where 90% of the population arrives at the right answer 100% of the time. Multiplying 64 bit integers isn't exactly super amazing, let's do something harder.

So I start over with a new population who's never solved any problem, and I change the problem from "n times n" to "n times (n plus 1)". So now they have to add 1 to the number before multiplying. The problem is harder, and it takes them a little longer to arrive at a solution, but they do.

So then I figure I'm gonna get tricky on them, and change the problem in mid stream. I make it so once we've played the game 150 times, I'm going to add one to the number I'm adding. So it starts "n times (n plus 1)" but goes to "n times (n plus 2)" after 150 tries.

Well, just like before, they all arrive at a consensus and are quite pleased with themselves, until all of the sudden the 151st time happens, and I go, "No. You're all wrong.". Well they kept trying, and pretty quick one of guesses the new number and spreads the word around, and soon enough we're back up to 90% of the population getting it right... until the 301st time comes around and I do it again, and they all have to guess the new number again. And wouldn't you know it, they find it much quicker too! In fact by the 7th time I've played this number changing game, they've figured out that I change the number every 150 times, and they've accounted for this in their DNA so they start guessing the new number right away. Ok, this was the promise, right? It adapts to it's environment, even while it's in mid-stride. Pretty neat, but I still think I can trick it.

So I change the game again. This time I add one to the number when they've arrived at a 60% consensus. I figure right around the time word is starting to spread around, I'm gonna switch it out on them. But this doesn't deter them; the carefully play the game until 60% of them are also incrementing the number every time, and therefore staying in step with my guess. Clever!

Alright, well how about this: Every time they grow the consensus of right answers more than 0.003% in a single round of guesses, I change the number to something completely random.

Well, this does stump them a bit more because they're unable to come up with a really solid solution for how the number is changing, since it's changing at random.

But after about 10 minutes, I realize they've devised a way to cheat: They've evolved a completely stable population that gets the answer right a low enough percentage of the time, and gives wrong answers the rest of the time that it doesn't tip the consensus and change the number any more! In this way they stay the most happy, because they've learned that growing the consensus too fast means they won't be rewarded until they guess the new random number. Meanwhile they slowly grow the number getting it right, but keep this conspiracy amongst them to keep giving wrong answers most of the time, until 90% are doing exactly the same thing, yet the size of the consensus never grows by more than 0.003% in a single round.

Clearly Orgel's Second Rule is hard at work here: Evolution is cleverer than you are.

Stay tuned for more, because this is just the very beginning of what this thing is capable of.

Labels: , ,