Aineopintojen harjoitustyö: AI Odyssey 2012 : Challenge II
Challenge II: Prisoner's Dilemma - deadline 26.11. 10:00 am.
Update: the second phase is over. The results of PvP tournament are as follows:
- 1885 ovare
- 2010 pantsu
- 2053 Elefantti
- 2176 dosto
- 2187 ent-
- 3670 Daolamis
- 4774 Tormentor
- 5194 psaikko
- 5336 Micco
- 7321 joonniet
Prisoner's dilemma is a simple two-player non-zero-sum game. The idea is that two criminals (the players) have been arrested and are kept in separate cells, and the police interrogates each of them separately. The players may either stay silent ("cooperate") or betray ("defect") the other player. Depending on whether each player cooperated or defected, the players are given the following prison sentences:
- If both playeres cooperated, they both get 2 years in prison.
- If both players defected, they both get 5 years.
- If one player cooperated and the other one defected, the player who cooperated goes to prison for 10 years and the player who defected gets free.
The possibles choises and the prison sentences they lead to can be illustrated by the following payoff matrix:
| Player 2 cooperates | Player 2 defects | |
| Player 1 cooperates | 2,2 | 10,0 |
| Player 1 defects | 0,10 | 5,5 |
The game has a simple optimal strategy: it can be seen from the payoff matrix that defect is always better choise, now matter how the other player plays. This results in score 5 for both players. Note that if instead of choosing the optimal move, both players would have cooperated, both of their scores would be 2, which is much better than 5.
The game gets more complex when you play it for several rounds: if you defect on the first round, the other player may defect for revenge on latter rounds. This game is called the iterated prisoner's dilemma. In theory defecting on every round is still the optimal choise, but practice doesn't always work like theory, and against most players this is a very bad strategy.
The task
Your task is to create an AI that playes iterated prisoner's dilemma. Your bot will play the game with several AIs defined by the organizers, and your goal is to minimize your total prison sentence. At the end of the two-week phase all the submitted bots will also play against each other in a tournament.
Your program will play against 8 bots created by the organizers. Your AI will play 100 rounds against each bot. To pass the challenge, you must get total prison sentence less than 2300 years.
The predefined bots use the following strategies:
- Always cooperate.
- Always defect.
- Cooperate on the first move, then repeat opponent's last move ("tit-for-tat").
- Defect on the first move, then repeat opponent's last move.
- Cooperate on the first move, then do opposite of what the opponent did.
- Always choose randomly.
- Two bots using secret strategies.
Technical details
Your bot should work as following:
- Each game consists of 100 rounds; on each round both players output their move (either cooperate or defect) and read the opponent's move.
- Write your moves to standard output (System.out)
- After each turn, read the opponents move from the standard input (System.in)
- To cooperate, write line "cooperate", and to defect, write line "defect" to standard output (without quotes).
- Make sure to end all your commands with a line break and flush the output.
- Your bot will be automatically terminated when the game is over.
- Your bot may use at most 5 seconds of running time per game.
Submitting solutions
The submissions are done to the submission service using zip-based submission format where the source code, run.sh and compile.sh are in the root of the zip-archive (see below prisoner.zip for example). Note: There should be no folders in your submission! You can also send compiled submissions, but make sure that your program runs on the server as required.
Note: Make sure that your run.sh script is marked executable and starts with line: #!/bin/sh
Send submission to the online submission service at http://t-avihavai.users.cs.helsinki.fi/ai-challenges/index.htm
In addition to submitting to the submission server, you should send a report where you briefly describe what you did to sysikask@cs.helsinki.fi. You don't have to send and code by mail if you have already submitted it to the system.
Sample code
The following archive is an example of a solution that you might send to the submission system. It contains a simple sample solution Example.java and the necessary scripts compile.sh and run.sh.
The following script allows you to test the bots you create offline agains other bots you create (bot not the organizers' bots). Use it by giving it two program names as parameters and it runs them for 100 rounds and prints the result.
Links
Prisoner's dilemma, New advances in prisoner's dilemma, Game theory
Printer-friendly version