Thursday, June 17, 2010

Published!

Just a quick note to say that my paper "Twitter as a Vector for Disinformation" was published in the Journal of Information Warfare last month. This is my first academic publication and I'm very excited about it. The paper is also available right from this very blog!

Wednesday, June 16, 2010

The Origin of the Species


I finished Dinosaur Island managing to exceed the score required to 'win'. Silliosaurus, most majestic of the Imbecephalosaurians thrived on Dinoisland unperturbed by the predators and rocks and only occasionally abandoning their herbivorous tendencies to engage in cannibalism (5th on the high score chart with 315,000 points). This success lead to overpopulation which created an evolutionary pressure that spawned Crazyodon which rose to a level of glory only seen by 3 previous species (4th on the high score chart with 895,750 points).

The breakthrough came when I realised that you could not convert a column, row coordinate system to an (x, y) without first accounting for the fact that in a column row system the direction 'UP' or 'NORTH' corresponds to the negative direction rather than the positive. This wasn't an easy mistake to spot because the column part worked flawlessly and my interface was consistent so the only visible symptom was that plants rarely were where Silliosaurus thought. 

After that bug got straightened out Silliosaurus flew past the 100,000 points required to win but managed to show an alarming tendency towards cannibalism. When two Silliosaurs collide one will die and since they are herbivorous the surviving dinosaur would not gain any calories. Since a new born Silliosaur would start adjacent to its parent and they shared the same path finding algorithm they often collided while hunting the same piece of food. My first attempts at fixing the problem didn't help all that much, I introduced a factor into the decision making code that would make food regions that contained another Silliosaur or that another Silliosaur was moving into less attractive. This factor was just a negative weighting that subtracted a value from the expected profit calculation that I hoped would encourage Silliosaurs to spread out. It did help but not a lot and increasing the weighting over and over didn't improve things a lot. This is when Silliosaurus plateaued at around 300,000.

I decided that I'd need some drastic changes to head off this problem and forked Silliosaurus to create Crazyodon. Crazyodon uses a prescriptive model where there is a strict set of criteria that a plant has to pass before even being considered for its food value. A Crazydon will mark its favourite unclaimed plant and all the plants within a given radius of it off limits to other Crazydon. This had a much more dramatic effect leading to a diverging behaviour where two Crazydons would often go in completely opposite directions. This didn't fix the problem entirely because only destinations were being considered rather than paths so two Crazyodons would still sometimes collide on their way to different regions. This didn't faze me too much as Crazyodon far exceeded my performance expectations and would even lead me to revising my graphical interface.

Crazyodons were so fecund and so good at roaming that they would often leave my (admittedly small) display area. I tried a few automated routines that would progressively zoom out the view when objects were detected outside the bounds. This actually was quite easy to do with pygame but I couldn't find a solution that I was happy with. In the end I implemented proper keyboard event handling to allow the user to pan the screen as well as zoom in and out. Very fancy.

Right now I think I'm dinosaured out for the moment but I hope in a few weeks I might get enthused about creating a carnivorous dino. In the mean time I'm turning my attention back to Xbox 360 forensics.

P.S The Crazyodon run I did to generate the above screenshot ended up scoring 827,000 points and took as long to run as writing this blog post did. Full screenshot here.

Sunday, June 13, 2010

Dinoisland and pygame

Facebook has a series of puzzles they use to evaluate potential engineering employees or for the enjoyment of anyone curious. I've worked through quite a few of them and in the process learnt that I really need to brush up on my algorithms.

At the moment I'm working through Dinosaur Island which is an AI exercise which surprisingly is about dinosaurs on an island. You need to create an AI that pilots a species of dinosaur to prosperity on the island, either a herbivore dodging nasty carnivores to get at tasty foliage or a species of carnivores hunting down everything that moves. The environment is persistent and multiplayer so it's almost like a little Dino-MMO.

Interactions with the server are done via the Apache Thrift RPC framework, where each action that your dinosaur can take is an RPC method. Your dinosaur has a limited life span so after avoiding predators and starvation your dinosaur needs to reproduce (apparently asexually) to prolong the species. The species itself has a limited life expectancy after which an extinction event kills all your remaining dinosaurs ('rocks fall everybody dies'). Every action that your dinosaur takes costs calories (move, look, grow, reproduce) and takes a turn, you get calories by eating ('moving into') stuff. This is important because it means that during a turn your dinosaur can either look in a direction OR move in a direction.

I'm currently working on a species of herbivore I call 'Silliosaurus' which fairly naively hunts out the densest areas of foliage to eat while only spending a cursory amount of time avoiding predators. To 'win' your species needs to score 100,000 points (which I think you accumulate mostly by eating stuff) and there's a leaderboard. Currently Silliosaurus is averaging less than 10,000 point a run with a current best of 25,000 points or so. The main flaw seems to be that Silliosaurii move into a square expecting to eat something only to find it empty and sometimes expects to move into empty space and accidentally acquires a cornucopia of vegetation. This makes me think that there's a problem with how I process and store sight information but I haven't tracked it down yet.

In the process of debugging Silliosaurus I wanted to build a graphical representation of Dinoisland to help me visualise the behaviour of each Silliosaur. I ended up using pygame which is a python game development library the wraps SDL. Pygame is total overkill for my needs but turns out to be dead simple to use. In fact below is a slightly simplified sample of what it takes to draw the screen visible in the attached screenshot:

import pygame


pygame.init()
screen = pygame.display.set_mode((800, 800))
pygame.display('Dinoisland: Silliosaurus')
plant = pygame.Surface((10,10))
dino = pygame.Surface((10,10))
bg = pygame.Surface((self.screen.get_size()))
plant.fill((0, 255, 0))
dino.fill((0, 0, 255))


screen.blit(bg, (0, 0))
for location in plantlist:
    screen.blit(plant, location)
for location in dinolist:
    screen.blit(dino, location)
pygame.display.flip()


So while Silliosaurus still wanders about lost and confused, occasionally starving to death or eaten by a Daisyysaurus, I have learnt a valuable lesson about how to create quick and easy graphics.


P.S Here's a link to the full sized screenshot