Light-Bot Again / 2009-11-16

Sometime back in high school my programming teacher let me borrow a book about math or computing or something, and all I remember from it now was a chapter on genetic programming. It described a way to “grow” a “program” that could predict the numbers in a repeating sequence, by starting with a bunch of random “programs” (they were essentially finite automata), ranking them based on how well they predicted the sequence, and then simulating biological evolution with these programs as the organisms, and their “code” as the DNA. Simulating evolution is done through three mechanisms: mutation, recombination, and natural selection. For mutation we randomly change part of the program. For recombination, we take two programs and mix their code together to make a new one. For natural selection, we rank the programs based on how well they predict the sequence, and discard the worst ones. We iterate through the process over and over again, and slowly the fitness of the population improves, and eventually we hope to grow a program that does what we want.

Of course I had never heard of this before, but I thought it was terribly fascinating. I implemented the example the book described on my TI-83+ calculator, and had a little fun with that, but eventually put it up on my mind’s shelf.

Many years later (and also just several months ago) I was poking around on the internet and found a simple flash game called Light-Bot (which I described in this post, which I quickly realized would make a good way to experiment with genetic programming again.

I fiddled around with it some initially (at the time my employer wanted me to learn Scala, so I took that as an opportunity to get paid to mess around with Light-Bot and hacked together an implementation in Scala), but didn’t get too far until I had the opportunity to speak at the local IEEE chapter, so for a couple weeks I did a bunch of coding to get together some good examples for an hour long presentation.

Since I like posting interactive things that I’m interested in on my website, after the presentation I spent another few weeks twisting what I had made into a decent public website that displays my results and allows the user to interactively experiment with it in much the same way I do. I hope it’s user-friendly enough to be interesting to people. I included a good amount of explanations and thoughts on the main page (much more than in this post), so hopefully it will also be clear enough to use. Any questions, suggestions, or comments are welcome.

Anyways, it’s here.