Sunday, December 4, 2011

Distributed tournaments for the Google AI Challenge

As I noted a couple of posts ago, I am taking part in the Google AI Challenge again this year (my entry). The challenge this year is Ants, a game which requires entries (agents) to control a number of ants in an environment made up of land, water, food and enemy ants.

The design of my agent is fairly simple and has a large number of parameters that are a adjustable (e.g. distance between an enemy ant and my base that is considered a "threat"). This made it a perfect candidate for trialling out some Genetic Algorithms (GA) theory to tune those parameters, as well as to evalute some algorithmic design decisions.

To start using GA one must generate an initial batch of solutions to the problem. This is currently in the form of 12 versions of my agent.

Once an initial set of solutions has been generated, the next step is the evaluation of the fitness of each solution. Each agent I design is a different "solution" to the problem of being the best agent - the best agent is the fittest.

I decided the simplest way to evaluate the fitness of each agent is for it to compete against other agents that I have made, and sample agents, in the standard game format that is used on the official servers.

As I have a number of laptops and computers, none of which super-powerful, I decided to try and make a distributed tournament system so that I could play as many games as possible to get the best idea of fitness - my setup is as follows.

  • Each machine is running Ubuntu 11.10, with Dropbox installed. The game's Dropbox folder contains the game engine, maps and all the agents that are currently being tested.
    • This allows for new agents to be added at any point and all machines to be immediately updated.
  • Each machine continuously:
    1. Selects a random map
    2. Selects a random set of agents to play on that map
    3. Plays the game
    4. Writes the score to a file based on it's host name - eg "log-ubuntubox.txt". These files are also in the Dropbox folder.
  • Any machine can run a shared script that aggregates the results from all log-*.txt files, computing the average points/game for each agent. This is used as the fitness.
Because I am using Python 2.7 (installed by default on Ubuntu 11.10) for the game engine, agents and extra scripting the provisioning of a new machine is this simple:
  1. Install Ubuntu
  2. Install Dropbox
  3. Run "python play.py"
So far this is working quiet well with quiet dramatic and unexpected performance differences between some nearly identical agents. Once each agent has played at least 30 games I will remove some of the lowest scoring agents and add some new versions based on combining the traits that are the most successful.

With any luck this should result in a pretty competitive entry in this year's Challenge - I will keep you posted!

3 comments:

  1. Hey thanks for the blog entry, after reading this I entered the competition and achieved rank 1025 (out of Australians that's 26th) with a week and a bit of work (late nights and weekends outside my real job).

    I was programming in C and I'm happy with the overall speed and efficiency I was achieving (pathfinding, mapping, etc) but I never got high quality battle code into it so my ants died badly when confronted by an opponent with better front-line formations.

    ReplyDelete
  2. Hi Kettling, thanks for the comment!

    I guess, strictly speaking, I shot myself in the foot with the post, since you beat me (1577) ;-)

    I ended up getting a loooot of timeouts due to inefficient map handling code - but I really enjoyed the competition anyway.

    Cheers,
    Robert

    ReplyDelete
  3. I'm a bit over the ants game now (they are still playing on tcpants.com and I'm getting beaten even after I studied runevision's code and the xathis code as well). There's a lot of little details and I just haven't got the patience to fine tune it.

    I did have a go with a neural-network style ruleset that can be optimized by repeated games and simulated annealing. It does handle micro-optimizations quite well (e.g. balancing off several weighting factors) but the CPU required is large and to some extent a game can go either way just by random chance, so to run it properly would probably require a full fledged genetic algorithm, a large population and a lot more electricity than I can afford.

    Hey this is off topic but can I get you interested in PIC programming? I've had some USB boards designed around PIC18LF2455 chips and 20MHz clock crystals. It was one of those projects that seemed a great idea long ago but other things (job, life, etc) took it over. I did get as far as getting libusb (on linux) to talk with the chip so you could toggle a few lights and stuff.

    There's on-chip timers for PWM and stuff, I was thinking of motor control or perhaps a security system. Anyhow, I've got gear that's been sitting in the shed for years if you want to run with it.

    ReplyDelete