Monthly Archives: October 2011

Germination X – designing for cooperation

Over the last week I’ve been designing and implementing a lot more game mechanics for Germination X which are needed for an upcoming visit to the Mobile Life Lab in Stockholm. The more interesting ones involve some direct player – player interaction. The thing I’m trying to balance is keeping the central design simple (what you have to do), but adding just enough for it to be taken further by players (how you do it). One important part of this is emphasising cooperation without making it mandatory – something I think is a mistake to do, and leaving the way that people interact online as open to interpretation as possible. Tale of Tale’s Endless Forest is a good reference point here.

The focus is adding a kind of “levelup” system for players to progress through the game in a longer term way than currently, along with some surprises. Also adding a way for players to send fruit they pick to other players as gifts, or to the plant spirits as a kind of “offering”.

The other major change is updating the game to use MongoDB to store all it’s data. I’m using congomongo as the Clojure wrapper, and it’s been fairly simple to integrate with the existing game code as I can replace normal Clojure functions like reduce with versions that iterate over records in the database. These can also be written to load data and work on it in chunks, to keep the memory overhead fixed:

(defn db-reduce
  "run f on each item in the collection, return the result"
  [f ret coll]
  (loop [skip 0 ret ret]
    (let [limit 200 ; limit to loading 200 records at a time
          items (fetch coll :limit limit :skip skip)] ; do the fetch
      (if (not (empty? items)) ; are there any items?
        (recur (+ skip limit) ; do the next chunk
               (reduce f ret items)) ; reduce f over the items

Evolving musical bytecode #3

For the next attempt in BetaBlocker bytecode evolution I wanted to favour patterns that had a rhythmic nature by measuring them with this function:

(defn freq [l n]
  (defn _ [c]
     (>= (+ c n) (count l)) 0
     (= (nth l c) (nth l (+ c n))) (+ 1 (_ (+ c 1)))
     :else (_ (+ c 1))))
  (_ 0))

Which looks for repeating values spaced apart by “n” positions, so (freq ‘(100 1 2 3 100 4 5 6 100 7 8 9 100) 4) returns 3, as it finds 3 pairs of equal values (100) distanced by the specified 4 positions.

With this fitness function:

(+ (* 50 (count (num-unique res))) ; unique notes are very good
   (freq res 4) ; equal notes every 4 beats are good
   (freq res 6)) ; equal notes every 6 beats are good

We favour rhythmic components of 4 or 6 beats and boost the uniqueness score by multiplying it by 50. After some generations, we get a high scoring individual: 23 23 13 22 7 12 17 20 12 23 23 5 0 7 12 3

Which disassembles as:

    note    ; play & remove top of stack (zero when empty)
    note    ; play & remove top of stack
    dec     ; decrement top of stack
    dup     ; duplicate - pushes a copy of stack top 
    pshi 12 ; push the value pointed at by address at 12 (self read)
    not     ; performs bitwise not on stack top
    pip 12  ; increment value at address 12
    note    ; play & remove top of stack
    note    ; play & remove top of stack
    pshl 0  ; pushes this literal number (the 0 is at address 12)
    pshi 12 ; push the value pointed at by 12 (self read)
    jmp loop

This program creates a pattern from 4 separate sources, using all 16 bytes of code:

A descending scale using the stack to store the current position.
A rising scale by self modifying address 12 (the 0 in “pshl 0”).
Playing it’s own code as a pattern of notes by using address 12 as a pointer.
Playing the bitwise NOT of it’s own code at the same time.

The result: “0 0 232 255 23 1 232 254 13 2 242 253 22 3 233 252 7 4 248 251 12 5 243 250 17 6 238 249 20 7 235 248 12 8” scores poorly for it’s rhythmic patterns, but it’s probable that this surprising local maxima was found by the early influence of the rhythmic fitness criteria on it’s ancestor populations.

This one was strange enough to warrant dialing into Betablocker DS to see how it actually sounded. Here it is in Hungarian Gypsy scale:

Evolving musical bytecode #2

Following on from the first BetaBlocker genetic algorithm bytecode experiments, in addition to the “most different notes” fitness function I added a similar calculation for the first derivative (ie. the difference between the notes in time order). This was an attempt to steer the evolution away from simple scales and into more complex patterns.

(defn deriv [l]
   (empty? l) '()
   (empty? (rest l)) '()
   :else (cons (- (first (rest l)) (first l))
               (deriv (rest l)))))

The code to find the first derivative of a sequence of notes – eg. (deriv ‘(1 2 3 2 6 7)) => (1 1 -1 4 1). We then add this to the fitness function which looks like this:

(+ (count (num-unique res)) ; unique notes are good
   (count (num-unique (deriv res))) ; unique gaps between notes are good
   (min (count res) 20)) ; lots of notes are good (stop at 20)

This resulted in the following bytecode to emerge from the primordial soup: 23 17 7 6 23 21 9 23 8 212 3 2 4 2 180 124 – which disassembles to:

The arrows show the indirection which helps as this one is a bit tricky to pull apart. It’s the first time I’ve seen self modification emerge – it decrements the “212” and uses it as a variable for the note sequence. Combining the pshi and pdp like this is a nice trick I can make use of when programming betablocker myself.

The program is self destructive – the “pop” which otherwise does nothing of use will eventually write zeros over the program itself if it’s run for a few more cycles than the 100 I’m testing the programs for.

The output looks like this:

0 212 255 211 0 210 0 209 0 208 0 207 0 206 0 205 0 204 0 203 0 202 0 201 0 200 0 199 0 198 0 197 0 196

According to our fitness function, the interleaved zeros give it a very high scoring derivative list:

212 43 -44 -211 210 -210 209 -209 208 -208 207 -207 206 -206 205 -205 204 -204 203 -203 202 -202 201 -201 200 -200 199 -199 198 -198 197 -197 196

However the actual pattern is not so interesting, so still more work needed on the fitness criteria.

Evolving musical bytecode

At it’s core, Betablocker provides a simple virtual machine for playing with music which is ‘unstoppable’ (any combination of instructions can be executed). It started off originally as a Fluxus scheme program, then got rewritten in C++ for the Nintendo DS, and has now been ported to Supercollider. I’ve built yet another Linux commandline version, and glued it to the Java Genetic Algorithms Package via Clojure.

This means I can continue with the genetic programming experiments and try evolving programs using a real genetic algorithm framework, using the betablocker instruction set. This is mainly just for kicks, but it’s also partly to “grow” new strategies for livecoding betablocker and researching instruction sets more generally.

The first test was to try and find a program to just play note 99. I would write this in betablocker like this (using a text representation of the icon interface for convenience):

    pshl 99 ; push the literal value 99 on to the stack
    note    ; play the top of the stack as a note 

First we need a fitness function to score the results from the programs which are generated:

(defn fitness [notes]
    (- 255 (Math/abs (- (first notes) 99))))

It takes a list of the notes played by a candidate program, and measures how far away the first element is from 99 – the bigger the number, the fitter the individual program is. I gave it 8 instructions to work with and a population of 500 individuals – after just a couple of generations, this chromosome/program popped up with a top fitness of 255 – meaning it was successfully playing note 99:

99 46 213 89 7 142 23 168

Which when disassembled looks something like this:

    99       ; <-- address 0 
    pshi 142 ; pushes contents of address at location 142 (which is 0)
    note     ; play the note

This program has grown taking advantage of the fact that the memory is initialised to zero, so if it dereferences a large address like 142 it will be zero and load the contents of the first byte - 99. It's this kind of wacked out approach genetic algorithms are great at finding/abusing.

The next problem, something a bit more general - create a sequence of notes which are all different to one another. The fitness function:

(defn list-contains? [l i]
   (empty? l) false
   (= (first l) i) true
   :else (recur (rest l) i)))

(defn fitness [a]
    (fn [r v]
      (if (not (list-contains? r v))
        (cons v r)

This just counts the number of unique elements in the list - again, the higher the better. This one took longer, but eventually came up with this:

139 246 1 23 12 22 23 12 20 95 22 3

Which when disassembled:

    note      ; play a note
    inc       ; increment top stack byte
    dup       ; duplicate top stack byte
    note      ; play a note (consumes 1 stack byte)
    inc       ; increment again
    pip 95    ; increment address 95 (junk - doesn't have any effect)
    dup       ; duplicate again
    jmp start ; return to the start

Which plays a rising sequence of notes, with none repeated, so the highest fitness achievable:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

This is already doing much better than the genetic programming I was mucking about with before - indeed there seems to be some literature on evolving java bytecode, but with betablocker there is an advantage that you don't need to enforce the correctness of the programs before they can be run.

Lirec meeting in Bamberg

Last week was another Lirec meeting in Bamberg, where I was able to present an in depth description of how Germination X works. I also had the chance to talk with SICS/mobile life lab (one of the other project partners) about how we can take the game forward with the aim to provide some studies for how people relate to Lirec’s companion/characters/plant spirits – and hopefully also other players.

The game’s main mechanics are as follows:

Germination X is similar to other farming games except for the third factor – that plants may get ill if their ecosystem cannot provide them with what they need. The other thing that makes Germination X unique in the socal games space is of course the addition of the plant spirits.

Each spirit represents a group of plants – the more specific permaculture term is a “layer”, as the groups represent the layers of a forest, from the root level (called rhizosphere) all the way up to the canopy trees.

Note: dandelions are more correctly part of the herbaceous layer, but we are taking artistic licence here, and lending it to the ground cover spirit for the moment.

In the FAtiMA rules for the game, the spirits have relationships defined for each of the plants in their group, and relationships defined between themselves. This allows us to use the way FAtiMA models emotions to get some nice results, for example if a player plants an apple tree the Tree Spirit may experience “Joy”. However, the Ground Cover Spirit doesn’t like the Tree Spirit as it’s plants shade it’s clover and dandelions too much – this action will cause it to express “Resentment”. Such processes, so the theory goes, create more understandable and believable characters.