IPD for Species

IPD for Species : The Evolution of Cooperation

The purpose of this competition is to study the evolution of cooperation between self-interested agents. It is based on the Iterated Prisoner's Dilemma (IPD) - the classic model of cooperation.

Previous Iterated Prisoner's Dilemma competitions have challenged competitors to design individual agents to play IPD. Axelrod organised the 1979/1980 competitions that famously brought IPD to the attention of the world and at CEC 2004 and CIG 2005, Kendall, Darwen and Yao organised two competitions to celebrate the 20th anniversary of Axelrod's book "The Evolution of Cooperation".

The IPD is one of the most well-studied mathematical games in existence. It has applications in many fields, such as biology, psychology, commerce and politics. One of the key aspects of the problem is to understand how cooperation can evolve amongst self-interested individuals. While previous competitions have focussed on how an individual in a population can do well at playing IPD, this competition is about how these successful individuals can evolve.

Entrants are challenged to design a species of IPD playing agents and submit a set of Java classes implementing their design. The submitted species will compete for survival in a simulation of evolution.

Contact

ipd4species AT philiphingston DOT com

The competitions

There will be two competitions, a restricted one and an unrestricted one. Competitors can enter either or both.

• The restricted competition is intended to simulate non-Lamarkian evolution, with no communication between players aside from the moves they play, and no modification of the genome except by random mutation when offspring are created. Rules are provided to ensure this. The API makes it possible to break the rules, but competitors are required not to do so if entering this competition.
• In the unrestricted competition the rules need not be obeyed.

An important note on collusion. Collusion between species is allowed in both competitions. There is no limit on collusion between players of the same species. Competitors who wish to enter a coalition of colluding species are required to advise the organisers, and will need to specify how many of each species should be in the initial population.

Important dates

30th June 2010 - submissions

Submission by emailing their java source files (as described below) to ipd4species AT philiphingston DOT com

Evaluation

The evaluation run will take place during the conference. A web page will be provided to display live progress results

Announcement of winners

Winners will be announced at a special session

Submission details

Competitors must submit sources for Java classes implementing their design for a species of IPD playing agents. The classes must include classes implementing the interfaces Genotype and Phenotype, as defined below. The Genotype class must provide a constructor taking no parameters (used to generate the initial population of agents). To avoid name clashes, all the classes should be placed in a uniquely named package.

One class must implement this interface:

public interface Genotype
{
	public Genotype copy();
	public void mutate();
	public Phenotype develop();
}

The Genotype interface encapsulates the representation of the genetic material and the genetic operators. The methods are as follows:

copy()

This method is used during "reproduction" to make a clone of a genotype. Rule: This should be a faithful copy of the caller.

mutate()

This method is used to simulate mutation of the genome during reproduction and should modify the caller. Rule: The result should be determined only by the genotype and chance.

develop()

This method is used to simulate morphogenesis by creating a phenotype based on the information in the genotype. Rules: The resulting phenotype should be determined only by the genotype. The genotype should not be altered by this call - in particular, the genotype should not retain a reference to the phenotype.

Additional rule: there should be no communication of information between players, except implicitly by the moves they play. For example, you should not use static fields to share information.

Note that the there is no requirement that mutation actually has any effect. It would be possible to enter a player that does not undergo any evolution, using genotype with no fields and a no-op mutation method. This is allowed.

Another class must implement the Phenotype interface, encapsulating the IPD strategy of one agent:

public interface Phenotype
{  
	public Move getFirstMove(Class opponentClass);  
	public Move getNextMove(Class opponentClass, Move oppLastMove);  
}  

getFirstMove()

This method is used to determine the player's first move in a game against a new opponent. The class of the opponent is provided to facilitate collusion.

getNextMove()

This method is used to determine a subsequent move by the player. The current opponent's previous move is passed, and it is up to the player to remember his own previous move, and the history of previous moves if desired. The class of the opponent is provided to facilitate collusion.

The evolutionary simulation will manage a collection of "organisms" constructed from instances of these classes:

public class Organism
{
	public Genotype genotype;
	public Phenotype phenotype;
	public double fitness;
} 

Download

The supporting Java classes and some example species can be downloaded from here.

Evaluation

Entries will be evaluated by running a series of evolutionary simulations, in which species of IPD players will compete for survival.

In each simulation, an initial population of players will consist of fixed number of players of each species (or coalition of species). This number will be at least 10, and may be more if the number of entries is not too high. In each generation, each player will play each other player in a round-robin IPD tournament. Each game of IPD will be played with a discount factor of 0.98 (i.e. the probability of the game ending before each move is 0.98). The fitness of each player will be their total score in the tournament. Baker's stochastic universal sampling will be used to select parents for the next generation. Each selected parent will produce one offspring by cloning and mutation. The numbers of each species in the population will thus go up or down from one generation to the next. Eventually, less successful species will go extinct.

100 simulations, each for 1000 generations, will be run. The winner will be the species that survives 1000 generations most often. Ties will be broken using the mean number of generations survived (to 2 decimal places). The pseudo-code below shows one simulation run.

1.	Create initial population of Organisms
2.	While not done do
3.	    For each pair of Organisms Org1 and Org2
4.	        Play Org1 against Org2 in a game of IPD
5.	        Org1.fitness += Org1's average payoff
6.	        Org2.fitness += Org2's average payoff
7.	    Start a new population
8.	    While new population not complete
9.	        Select a parent Org 
10.	        C = Org.genotype.copy()
11.	        C.mutate()
12.	        P = C.develop()
13.	        Add a new Organism(C, P, 0.0) to the population
14.	    End While
15.	End While

Reasonable limit on thinking time: In order to facilitate the evaluation of the entries, it may be necessary to limit the computational resources that each agent can use. If a species of agent uses an inordinate amount of time to play its moves, it may be necessary to exclude that species from the competition.