Category Archives: genetic programming

News from egglab

9,000 players, 20,000 games played and 400,000 tested egg patterns later we have over 30 generations complete on most of our artificial egg populations. The overall average egg difficulty has risen from about 0.4 seconds at the start to 2.5 seconds.

Thank you to everyone who contributed their time to playing the game! We spawned 4 brand new populations last week, and we’ll continue running the game for a while yet.

In the meantime, I’ve started working on ways to visualise the 500Mb of pattern generating code that we’ve evolved so far – here are all the eggs for one of the 20 populations, each row is a generation of 127 eggs starting at the top and ordered in fitness score from left to right:

viz-2-cf-0-small

This tree is perhaps more useful. The ancestor egg at the top is the first generation and you can see how mutations happen and successful variants get selected.

viz-2-cf-1-6-tree-small

Egglab – meet Ms Easter Robot Nightjar and her genetically programmed eggs!

roboteasternightjar

We’ve released our latest citizen science camouflage game Egglab! I’ve been reporting on this for a while here so it’s great to have it released in time for Easter – we’ve had coverage in the Economist, which is helping us recruit egg hunters and 165,000 eggs have been tested so far over the last 3 days. At time of writing we’ve turned over 13 generations starting with random pattern programs and evolving them with small mutations, testing them 5 times with different players and picking the best 50% each time.

Here is an image of some of the first generation of eggs:

egglab0

And this shows how they’ve developed 13 generations later with the help of many thousands of players:

egglab

We can also click on an individual egg and see how it’s evolved over time:

egglab2

And we see how on average the time taken to find eggs is changing:

egglab3

Technically this project involves distributed pattern generation on people’s browsers using HTML5 Canvas, making it scalable. Load balancing what is done on the server over three machines and a Facebook enabled subgame – which I’ll use another blog post to explain.

Egglab – pattern generation obsession

I’m putting the final pieces together for the release of the all new Project Nightjar game (due in the run up to Easter, of course!) and the automatic pattern generation has been a focus right up to this stage. The challenge I like most about citizen science is that along with all the ‘normal’ game design creative restrictions (is it fun? will it work on the browser?) you also have to satisfy the fairly whopping constraints of the science itself, determining which decisions impact on the observations you are making – and being sure that they will be robust to peer review in the context of publication – I never had to worry about that with PlayStation games :)

variation

pattern2gen

With this game, similar to the last two, we want to analyse people’s ability to recognise types of pattern in a background image. Crucially, this is a completely different perception process from recognition of a learned pattern (a ‘search image’), so we don’t want to be generating the same exact egg each time from the same description – we don’t want people to ‘learn’ them. This also makes sense in the natural context of course, in that an individual bird’s eggs will not be identical, due to there being many many additional non-deterministic processes happening that create the pattern.

The base images we are using are wrapped Perlin noise at different scales, and with different thresholds applied. These are then rotated and combined with each other and plain colours with the browser’s built in composite operations. Ideally we would generate the noise each time we need it with a different random seed to make them all unique, but this is way too slow for HTML5 Canvas to do (pixel processing in Javascript is still painful at this scale). To get around this we pre-render a set of variations of noise images, the genetic program picks one of four scales, and one of two thresholds (and one without threshold) and we randomly pick a new variation of this each time we render the egg. The image at the top shows the variation that happens across 6 example programs. Below are some of the noise images we’re using:

noise-patterns

Egg camouflage evolution tests in different nest sites

I’ve spent some time testing Project Nightjar EggLab: clicking on algorithmically generated eggs on backgrounds taken from nightjar nest sites and recording the time it takes for each egg. It’s designed for lots of people to play in parallel, but I wanted to test it before coming up with more gameplay mechanic ideas.

The timing is used to rank the eggs, I keep the top 1024 individuals that took longest to find, and generate new ones from them. The idea is that successful traits will increase throughout the population and the average score will increase – from this small test it seems to be the case, a slow but consistent rise over the latest 500 eggs:

fitness

Most of the eggs are still really easy to see, but some of them take a few seconds and every now and again there is a good one that can take longer. These are some nest sites from the fiery-necked nightjar, which seems to consistently favour leafy ground – the last one took me a while to spot:

3

2

4

This are the top 50 eggs for the fiery-necked population, it’s quite noisy with false positives due to the fact that if you get distracted when playing the egg will score highly (this is one of the things to fix):

top50

For comparison, here is the top 50 for the Mozambique nightjar:

top50

These birds nest on a bigger variety of sites, including bare earth – here’s a good one of them:

4

The other project nightjar citizen science games, where you can search for real nightjars and nesting sites can be found here.

Visualising egg pattern genomes

A couple of screenshots from the upcoming Project Nightjar citizen science game – the genetic programming pattern generator is now working in a simple test framework, and even with myself as the only player at the moment, it’s gradually producing eggs that are harder and harder to find against one of the background images from the field site in South Africa. Today I’ve been working on a viewer for the pattern genome itself, which displays all the base images and the operations and intermediate steps as it builds up the final image. Unlike any natural form of genetics, genetic programming is all about growing trees of functions connected together, and here we are interested in combining simple images using HTML5 canvas’s composite operations to make complex patterns.

genome1

genome2

This will be useful for debugging mutations, where the sub-trees are jumbled up, but as we’re building a citizen science game, we’re also going to be exposing as much as possible about how it’s working – from the game mechanics like this to the underlying camouflage theories we’ll be testing. If you recognise the graph drawing algorithm, I’ve been plundering a long forgotten project: fastbreeder.

More procedurally rendered eggs in HTML5 canvas

The first Project Nightjar game was a big success, with 6 thousand players in the first few days – so we’ll have lots of visual perception data to get through! Today I’ve been doing a bit more work on the egg generator for the next citizen science camouflage game:

egglab3

I’ve made 24 new, more naturalistic base images than the abstract ones I was testing with before, and implemented the start of the genetic programming system – each block of 4×4 eggs here are children of a single randomly created parent, each child is created with a 1% mutation rate. The programs trees themselves are 6 levels deep, so a maximum of 64 binary composite operations.

All the genetic programming effort will happen in HTML5, thus neatly scaling the processing with the number of players, which is going to be important if this game proves as popular as the last – all the server has to do then is keep a record of the genotypes (the program trees) and their corresponding fitness.

One catch with this approach is the implementation of globalCompositeOperation in HTML5, the core of the image synthesis technique I’m using, is far from perfect across all browsers. Having the same genotype look different to different people would be a disaster, so I’m having to restrict the operations to the ones consistently supported – “source-over”,”source-atop”,”destination-over”,”destination-out”,”lighter” and “xor”.

Genetic programming egg patterns in HTML5 canvas

Part of the ‘Project Nightjar’ camouflage work I’m doing for the Sensory Ecology group at Exeter University is to design citizen science games we can build to do some research. One plan is to create lots of patterns in the browser that we can run perceptual models on for different predator animals, and use an online game to compare them with human perception.

The problem is that using per-pixel processing in order to generate the variety of patterns we need is hard to do quickly in Javascript, so I’m looking at using genetic programming to build image processing trees using the HTML5 canvas image composition modes. You can see it in action here, and the source is here. Here are some example eggs built from very simple test images blended together, these are just random programs, but a couple of them are pretty good:

random-eggs

A nice aspect of this is that it’s easy to artistically control the patterns by changing the starting images, for example much more naturalistic patterns would result from noisier, less geometric base images and more earthy colours. This way we can have different ‘themes’ for levels in a game, for example.

I’m using the scheme compiler I wrote for planet fluxus to do this, and building trees that look like this:


'("op"
  "lighter"
  ("op"
   "source-in"
   ("op"
    "source-out"
    ("terminal" (124 57 0 1) "stripe-6")
    ("terminal" (42 23 0 1) "dots-6"))
   ("op"
    "copy"
    ("terminal" (36 47 0 1) "stripe-7")
    ("terminal" (8 90 1.5705 1) "red")))
  ("terminal" (108 69 0 1) "green"))

Ops are the blend mode operations, and terminals are images, which include translation and scale (not currently used). The egg trees get drawn with the function below, which shows the curious hybrid mix of HTML5 canvas and Scheme I’m using these days (and some people may find offensive :) Next up is to actually do the genetic programming part, so mutating and doing crossover on the trees.


(define (draw-egg ctx x y program)
  (if (eq? (program-type program) "terminal")
      (begin
        (set! ctx.fillStyle
              (ctx.createPattern
               (find-image (terminal-image program) 
                           image-lib) "repeat"))

        ;; centre the rotation
        (ctx.translate 64 64)
        (ctx.rotate 
            (transform-rotate (terminal-transform program)))
        (ctx.translate -64 -64)

        ;; make the pattern translate by moving, 
        ;; drawing then moving back
        (ctx.translate 
            (transform-x (terminal-transform program))
             (transform-y (terminal-transform program)))

        (ctx.fillRect 
            (- 0 (transform-x (terminal-transform program)))
            (- 0 (transform-y (terminal-transform program)))
            (* 127 2) (* 127 2))

        (ctx.translate 
            (- 0 (transform-x (terminal-transform program)))
            (- 0 (transform-y (terminal-transform program)))))
      (begin
        ;; slightly overzealous context saving/restoring
        (ctx.save)
        ;; set the composite operation
        (set! ctx.globalCompositeOperation (operator-type program))
        (ctx.save)
        (draw-egg ctx x y (operator-operand-a program))
        (ctx.restore)
        (ctx.save)
        (draw-egg ctx x y (operator-operand-b program))
        (ctx.restore)
        (ctx.restore))))

Spork Factory: Amorphous Computing

Departing in a new direction after evolved light follower robots, take 500 processor cores spread out in space. Give them a simple instruction set which includes a instruction to copy (DMA) 8 bytes of their code/data to nearby cores (with an error rate of 0.5%). Fill the cores with random junk and set them running. If we graph the bandwidth used (the amount of data transmitted per cycle by the whole system) we get a plot like this:

bandwidth

This explosion in bandwidth use is due to implicit emergence of programs which replicate themselves. There is no fitness function, it’s not a genetic algorithm and there is no guided convergence to a single solution – no ‘telling it what to do’. Programs may arise that cooperate with each other or may exhibit parasitic behaviour as in alife experiments like Tierra, and this could be seen as a kind of self modifying, emergent Amorphous computing – and eventually, perhaps a way of evolving programs in parallel on cheap attiny processor hardware.

In order to replicate, the code needs to push a value onto the stack as the address to start the copy from, and then call the dma instruction to broadcast it. This is one of the 500 cores visualised using Betablocker DS emulator display, the new “up” arrow icon is the dma instruction.

Thinking more physically, the arrangements of the processors in space is a key factor – here are some visualisations. The size of each core increases when it transmits, and it’s colour is set by a hash of the last data transmission – so we can see the rise of communication and the propagation of different strains of successful code.

The source is here and includes the visualisation software which requires fluxus.

Spork Factory: evolving a light follower robot

Continuing with the structured procrastination R&D project on evolvable hardware, I’m proud to report a pretty decent light following robot – this is a video of the first real-world test, with a program grown from primordial soup chasing me around:

After creating a software model simulation of the robot in the last post, I added some new bytecode instructions for the virtual machine: LEYE and REYE push 1 on the stack if we are detecting light from the left or right photoresistor, zero if it’s dark. LMOT and RMOT pop the top byte of the stack to turn the motors on and off. The strategy for the genetic algorithm’s fitness function is running each 16 byte generated program on the robot for 1000 cycles, moving the robot to a new random location and facing direction 10 times without stopping the program. At the end of each run the position of the robot was compared to the light position, and the distances were averaged as the fitness. Note that we’re not assigning fitness to how fast we get to the light.

This is pretty simple stuff, but it’s still interesting to look at what happens over time in the genetic algorithm. Both motors are running at startup by default, so the first successful programs learn how turn one motor off – otherwise the robot just shoots off and scores really low. So the first generations tend to just go round in circles. Then they start to learn how to plug the eyes in, one by one edging them closer to the goal – then it’s a case of improving the sample rate to improve accuracy, usually by using jmps and optimising the loops.

This is an example of a fairly simple and effective solution, the final generation shown in the animation above:

loop:
  leye 
  rmot 
  nop nop nop nop nop 
  reye 
  lmot 
  or 
  nop nop nop nop
  rmot 
  jmpz loop

Some explanation, the right and left eyes are plugged into the left and right motors, which is the essential bit making it work, the ‘nop’s are all values that are not executable. The ‘rmot’ before the ‘jmpz’ makes the robot scan around in circles if there is no light detected (strangely, a case which doesn’t happen in the simulation). The argumant to ‘jmpz’ is 0 (loop) which is actually the 17th byte – so it’s cheekily using memory which has been initialised to zero as part of it’s program.

This is a more complicated and stranger program which evolved after 70 generations with a high fitness, I haven’t worked out what it’s up to yet:

  pshl 171 
loop:
  lmot 
  leye 
  pip 111 
  pip 30 
  rmot 
  reye 
  pshl 214 
  nop 
  lmot 
  jmp loop

Evolvable hardware

I’m modding a robot toy for the next Spork Factory experiment, the chassis provides twin motor driven wheels and I’m replacing it’s brains with a circuit based on the ATtiny85 for running the results of the genetic algorithm, and a pair of light dependant resistors for ‘seeing’ with.

Here’s the circuit (made in about 20 minutes after installing Fritzing for the first time). It’s quite simple – two LDR’s provide input, and some transistors are needed to provide enough power to the robot’s motors (it’s using PNP transistors as they were the first matching pair I could find, which means logical 0 is ‘on’ and 1 is ‘off’ in the code).

The robot needs to be emulated in software so the genetic algorithm can measure the fitness of hundreds of thousands of candidate programs. We need to simulate the effect of motor speeds on it’s position and velocity – here is a test running the right motor at a constant rate, and gradually increasing the speed of the left motor.

This is the code snippet that calculates the velocity from the 2 motor speeds – more work is needed to plug in the correct values for the distance between the wheels and the actual rotational speeds of the motor drives.

// update dir and pos from current motor speed
float relative_speed_diff=m_left_motor-m_right_motor;
float angle=atan(relative_speed_diff);
    
// rotate the direction by the angle
float nx=(m_dir.x*cos(angle))-(m_dir.y*sin(angle));
float ny=(m_dir.x*sin(angle))+(m_dir.y*cos(angle));
m_dir.x=nx;
m_dir.y=ny;
    
// update the position
m_pos=m_pos.add(m_dir);