Evolving Strategies for the Prisoner’s Dilemma

A website accompanying this project may be found at http://www.computing.dcu.ie/~aerrity/undergrad.htm. This includes the runnable program, source code, API and other documentation.

2 About the Prisoner's Dilemma

In the Prisoner's Dilemma game two players are faced with a choice, they can either cooperate or defect. Each player is awarded points (called payoff) depending on the choice they made compared to the choice of the opponent. Each player’s decision must be made without knowledge of the other player’s next move. The player’s have no means of communication other than the game choices and there can be no prior agreement between the players concerning the game.

If both players cooperate they both receive a reward, R. If both players defect they both receive a punishment, P. If one player defects and the other cooperates, the defector receives a reward, T the temptation to defect, whilst the player who cooperated is punished with the sucker’s payoff, S. These game rules (and their typical values) are presented in the payoff matrix below

The dilemma here is that the only choice for rational players is to defect.

The name Prisoner's Dilemma comes from the following description of the problem:

The story is that of two prisoners placed in separate cells, with the aim of getting one prisoner to implicate the other. Each prisoner is given the option to defect against the other, by giving evidence against them. If both prisoners defect (give evidence) then the judge, in no doubt over their guilt, will send them both to prison for 3 years. If both prisoners cooperate (don’t give evidence), then the judge, with less clear indication of guilt, will send them both to prison for only 1 year. However if one prisoner defects and the other does not, the judge will take this as a clear sign of guilt, allowing the defector (evidence giver) to walk free whilst sentencing the other prisoner to 5 years.

3 System Requirements

In order to successfully run this program your system will require:

An Operating System capable of running Java
Java version 1.4.1 or greater, available for download at http://java.sun.com/j2se/1.4.1/download.html
A screen resolution of at least 800x600

The recommended hardware specifications are:

Pentium III 500Mhz
128MB RAM

4 Installation Instructions

These instructions assume Java version 1.4.1 or greater is installed on your system.

a. Ensure your system meets the system requirements

b. Obtain the file epd.jar. This is available for download at http://www.computing.dcu.ie/~aerrity/undergrad.htm

c. Save this file to a location on your computer, for example c:\

The epd.jar file is the only file necessary to run the Evolutionary Prisoner's Dilemma program. To run the program, open a command prompt and run the following command,

java –jar <file location>\epd.jar

For example under Windows this might be:

java –jar c:\epd.jar

Whereas under a Unix based OS it might be:

java –jar /home/userid/epd.jar

If jar files have been correctly associated with Java in your Operating System settings you may be able to run the program by simply double clicking the epd.jar file.

5 Getting Started

When the Evolutionary Prisoner's Dilemma program is first run you will be presented with the blank application screen.

Main Window

The menu bar at the top of this window remains in place in all program modes and always provides the following options:

Game Type > Tournament: Opens the Iterated Prisoner's Dilemma Tournament simulation window [described below] [Warning: Selecting this option while running a Spatial Simulation will cause the Spatial Simulation to end]
Game Type > Spatial Society: Opens the Spatial Society simulation window [described below] [Warning: Selecting this option while running a Tournament Simulation will cause the Tournament Simulation to end]
Game Type > Interactive: Opens the interactive strategy analysis window [described below]
Rules > Rules Settings…: Opens a dialog box which allows you to configure the program settings [described below]
Strategies > Strategy Manager…: Opens a dialog box which allows you to view or delete the saved strategies [described below]

6 Rules Settings Dialog

This dialog is accessed by clicking Rules in the menu bar and selecting Rules Settings.

This dialog allows you to configure the program parameters. Any changes made to the rules settings will affect all program windows. Changes made to rules during a simulation will not take effect until the next simulation. Changes made to the rules from the Interactive window will take effect immediately.

The Rules settings dialog box for the Interactive and Tournament windows is shown below. The following parameters may be set using the spinners or text entry:

Rules Dialog

Maximum generations: The upper limit on the number of generations the Genetic Algorithm will produce [not applicable to the Interactive window].
Number of Players: The number of players in the simulation population [not applicable to the Interactive window].
PD Iterations: The number of rounds of the Prisoner's Dilemma played in each Iterated Prisoner's Dilemma game.
Temptation, Reward, Punishment, and Sucker’s Payoff: The T, R, P and S values for the payoff matrix described above.
Mutate Probability: The probability of genetic mutation occurring during the Genetic Algorithm reproduction operations [not applicable to the Interactive window].
Crossover Probability: The probability of genetic crossover occurring during the Genetic Algorithm reproduction operations [not applicable to the Interactive window].
Save Changes: Saves the currently displayed values
Cancel: Discard these values and return to the previous values
Defaults: Loads the program’s preset/recommended rules.

The Rules dialog displayed from the Spatial Society window is shown below:

Rules Dialog - Spatial

This is identical to the previous dialog except for:

Num of Players in each row and column: In the previous dialog this specified the total number of Prisoner’s in the simulation population. Here this value specifies the number of Prisoner’s in each row and column, thus the actual number of prisoners in the population will be the square of this value. This field is limited to 70.

7 Strategy Manager

This dialog is accessed by clicking Strategies in the menu bar and selecting Strategy Manager.

This dialog allows you to manage the currently saved strategies.

Strategy Manager Dialog

At start-up, several preset strategies are stored. These are:

TFT – Tit for Tat, cooperates on first move and will only defect if the opponent defected on the previous move
TFTT – Tit for Two Tats - cooperates on first move and will only defect if the opponent defected on the previous two moves
ALLC – Always cooperates
ALLD – Always defects

You can select a saved strategy from the drop down-list on the left and perform one of the following actions:

View – Displays the strategy string in separate dialog box. For example the TFT strategy shown below.

Delete – Removes the saved strategy

Close - Closes the dialog box

[Warning: When the application is closed any strategies saved in the strategy manager will be lost.]

8 Game Types

The following section describes the three separate game windows which may be viewed. These windows may be viewed one at a time using the menu bar Game Type option.

[Warning: Switching between a Tournament Simulation and Spatial Simulation will cause any active simulations to end]

8.1 Tournament

The tournament window allows you to run evolution simulations on populations of Prisoners playing an Iterated Prisoner’s Dilemma tournament.

When you first open a tournament window the following will be displayed:

Tournament Initial Window

This window consists of the following components:

Main Display: This displays a representation of the current population during evolution; each Prisoner in the population is represented by a narrow rectangle. The colour of this rectangle indicates the player’s strategy type.
Player Type: Provides a legend to the colours displayed on the main display and also provides strategy population percentage information
Population Fitness Stats: This pane displays the maximum, minimum and average payoffs of individuals in the population.
Graph: Provides a line graph charting the maximum, minimum and average payoffs for each generation of evolution [Legend appears in upper right corner].

Tournament Window

This window provides the following controls (in addition to the Rules Settings):

Start – Clears the current population and statistics and starts the evolution of a new random population of prisoners playing an Iterated Prisoner's Dilemma tournament.
Stop – Stops the current evolution but leaves all displays and statistics intact.
View Fittest Individual – Opens a dialog box showing the strategy which currently has the highest score.
View Weakest Individual - Opens a dialog box showing the strategy which currently has the lowest score.

The strategy dialog boxes which open to display the fit/weak strategies update dynamically with population changes.

These dialogs allow you to save a Prisoner’s strategy in the strategy manager. Clicking save in this dialog will open a dialog box [see below] which allows you to enter a name under which to save the strategy. The strategy that was visible when you clicked save will be the one added to the strategy manager.

Having entered a strategy name clicking save will add the strategy to the strategy manager for later use.

[Warning: The strategy will be saved in the next free position in the strategy manager; if no empty spaces exist the strategy will not be saved]

[Warning: When the application is closed any strategies saved in the strategy manager will be lost.]

8.2 Spatial Society

The spatial society window allows you to run evolution simulations on populations of Prisoners playing an Iterated Prisoner’s Dilemma tournament on a spatial grid.

When you first open a spatial society window the following will be displayed:

Spatial Society Initial Window

This window consists of the following components:

Main Display: This displays a representation of the current population during evolution; each Prisoner in the population is represented by a small rectangle. The colour of this rectangle indicates the player’s strategy type.
Player Type: Provides a legend to the colours displayed on the main display and also provides strategy population percentage information
Population Fitness Stats: This pane displays the maximum, minimum and average payoffs of individuals in the population.
Graph: Provides a line graph charting the maximum, minimum and average payoffs for each generation of evolution [Legend appears in upper right corner].

Spatial Society Window

This window provides the following controls (in addition to the Rules Settings):

Start – Clears the current population and statistics and starts the evolution of a new random population of prisoners playing an Iterated Prisoner's Dilemma on a spatial grid.
Stop – Stops the current evolution but leaves all displays and statistics intact.
Evolutionary Algorithm/Genetic Algorithm: Allows you to choose which type of algorithm to use for evolution.
View Fittest Individual – Opens a dialog box showing the strategy which currently has the highest score.
View Weakest Individual - Opens a dialog box showing the strategy which currently has the lowest score.

The strategy dialog boxes which open to display the fit/weak strategies update dynamically with population changes.

Having entered a strategy name clicking save will add the strategy to the strategy manager for later use.

[Warning: The strategy will be saved in the next free position in the strategy manager; if no empty spaces exist the strategy will not be saved]

[Warning: When the application is closed any strategies saved in the strategy manager will be lost.]

8.3 Interactive

This window allows you to play games of the Prisoner's Dilemma against saved strategies and pit saved strategies against one another

When first opened this window will display the following:

Interactive Window

The sub-windows which make up this window are:

Scores: Displays the total payoffs received by each player. Also displays the results of the last game move. Any status messages, such as errors or warnings will also be displayed in this window.
Game History: Displays a record of the moves played by both players in a scrollable list.
Payoff matrix: Displays the payoff matrix for the current rule settings. This is aimed to aid the understanding of the Prisoner's Dilemma.
Game Controls: Allow you to do the following

Choose a “Human vs. Computer” or “Computer vs. Computer” game.
Select the strategies to compete. These strategies are loaded from the strategy manager and may be viewed by clicking the View Button. You should select one strategy from the drop down box for “Human vs. Computer”, this strategy will be your opponent. For “Computer vs. Computer” you should select two strategies to compete.
Start – Clicking start in “Computer vs. Computer” mode will play the Iterated Prisoner’s Dilemma between the selected players as specified by the Rules Settings. The status of this game will be displayed in the panels described above.
Start – In “Human vs. Computer” mode this will start a game of IPD between you and the computer strategy. You may select your game move by clicking the cooperate or defect button. The opponents corresponding move will be displayed in the scores panel.
Stop – Clicking stop will end the active game but leave all displays and statistics intact.

Human vs. Computer

Computer vs. Computer