Genetic cars in HTML5

This is cool. I'm always a sucker for these things.

Evolving regexps

This is neat.

Graphical generation

Just a note for my later amusement: I've been thinking of the automatic generation of graphical forms - specifically, 19th-century masonry.  I want a city generator that does for me what London or Richmond, Indiana give me - shivers down my spine that I don't even understand.

Evolution of pictures again

Remember that evolution of images last year or whenever? Here's a guy who got really beautifully obsessed with investigating how that might be used as an image compression algorithm. Verdict: not such a hot image compression algorithm, but quite interesting nonetheless.

AI game design

So AI game design is a thing: given a set of possible games defined by the pieces available, board, etc., come up with a "good" set of rules. What a "good" game is seems ... really human, but some exploration of using AI programming techniques to augment human game design has been done.

Here's a neat article. It's about exploring a very small game set using "Shibumi" equipment (released in October of 2011), which consists of a 4x4 set of holes and three colors of marbles to be played on those holes and stacked on one another to make pyramids. That totals up to 30 possible positions, which can be empty, white, black, or red (two bits each), so the set of possible board positions is encoded in 60 bits.

Turns out evolution isn't so hot for game design - the universe is too uneven to allow much gradual improvement. They've been having success with "Monte Carlo tree search", building trees using a semi-random process. Kind of neat. They want to compare it with GA in finding new games in this universe.

Their fitness function has to be playability as judged by a human.

Here's a notion: judge playability by determining how challenging it is to evolve a good player. Or something. That is to say, automate both ends of the process.

Evolved to Win

Ebook about GA evolution of gameplaying algorithms or strategies. Interesting stuff!

Evolutionary program repair

Oh my God this makes me salivate.

The concept: use GA to perturb a syntax tree for a C program, use unit tests as the fitness criteria, sit back and watch code arise that meets all requirements. The link goes to fixed code. In real projects, apparently.

The mind boggles!

Tetris AI

Here's a fun post: the author wrote an AI to play Tetris (OK, I have this same urge, of course), and that AI had a set of parameters he guessed at. The logical next step was to run a genetic algorithm to try out different values for those parameters.

That's cool!

Angry Birds on Chrome + evolution = WIN!!

So Angry Birds is now available in a Javascript port on Chrome. I have yet to really study it beyond, you know, playing it for a couple of days to see what all the fuss is about (and yeah, it's a pretty addictive game!) So I had this cool idea, as one does.

Back when tower defense games were all the rage, I spent a little time developing some tools to play tower defense for me. It was more challenging than it sounds - but only because TD games are all in Flash, and Flash has no machine-accessible output or state beyond its actual screen output. Screen capture is slow. So actually responding to screen output is essentially impossible. (Not to mention the shocking dearth of easy-to-use OCR libraries, which seems still not to have been resolved - and it's 2011!)

Anyway, the description of a level is presumably in a nice little string. That string could be evolved with a GA - making new levels that people could play in a Web2.0 fashion, providing grist for the evolution! But that would require a lot of people.

So why not evolve playing strategies as well? This would consist of a list of pullback coordinates and delays. The ease with which a given population could evolve a playing strategy would allow the calculation of a "playability metric" - and that in turn would be an evolutionary metric for the new levels.

So by harnessing two levels of evolution, you could (maybe) generate an arbitrary number of entertaining Angry Birds levels.

Cool, huh?

Boxcar2d.com: Flash GA using physics

A neat site with a Flash GA algorithm. Some thoughts.

Box2d seems to be AS v3 and thus probably not compatible with Ming. Darn. So doing this easy in Declarative seems to be out. (Update: maybe not!)

The GA is irritating. Watching this, I'm thinking that first of all, always throwing the old generation away is a mistake. You get close to a good solution then you lose it. Some ways around that would be to keep the old generation around; good solutions stay there until something manages to beat them. You could vary the mutation rate according to how stagnant the solution pool seems. A larger population than 20 might be more resilient to loss, as well.

Genetic programming article

Interesting synopsis of some basic LISPy GP.

More GA and machine learning

Link-dumping continues. First, "Using GA to find Starcraft 2 build orders". Second, a useful overview of machine learning techniques I just haven't had the time to finish.