In this question, a game was devised in which players would face each other off pair by pair in the Prisoner's Dilemma, to determine which iterative strategy scored the highest against others.

In this question, I devised a way for multiple people to play the Prisoners' Dilemma against each other all at the same time. In this variation, the payoff matrix is unnecessary, with each outcome between each pair of two players being the sum of two functionally independent decisions.

Your task is to build an AI to play this symmetric, generalized version of the multiplayer Prisoner's Dilemma that will achieve the highest score possible.

Rules of the Game

In each round of this multiplayer, multi-round Prisoner's Dilemma, a player $A$ can decide to "take 1" from some other player $B$. In this circumstance, $A$'s score increases by 1, while $B$'s score decreases by 2. This decision is allowed to happen between each ordered pair of players.

This is the only decision made for each player – either to "take 1" or not to "take 1" from each other player, which are homologous to defection and cooperation respectively. The effective payoff matrix between two players $P_1$ and $P_2$ looks as follows:

  P1/P2     P1 Take1   P1 Don't
P2 Take1     -1/-1      -2/+1
P2 Don't     +1/-2       0/ 0

Tournament Procedure

The game will consist of $P \times 25$ rounds, where $P$ is the number of participating players. All players start with a score of $0$. Each round will consist of the following procedure:

At the beginning of a round, each program will be given a history of the previous rounds from standard input, in the following format:

• One line containing 3 numbers, $P$, $D$, and $N$.

• $P$ is the total number of players in the game. Each player is randomly assigned an ID number from $1$ to $P$ at the beginning of the game.

• $D$ is the ID of the current player.

• $N$ is the number of rounds that have been played.

• $N$ lines, each line representing the outcomes of a round. On line $k$ of $N$, there will be some number $n_k$ of ordered pairs $(a, b)$, separated by spaces, which represent that the player with ID $a$ "took 1" from the player with ID $b$ in that round.

• A uniformly random number $R$ from $0$ to $(2^{64}-1)$, to act as a pseudorandom seed. These numbers will be read from a pre-generated file, which will be released at the end of the tournament so that people can verify the results for themselves.

• One extra line that represents some form of state to be read into your program, if your program produced such an output in the previous round. At the beginning of the game, this line will always be empty. This line will not be modified by either the scoring code or other programs.

Each program will then use its strategy to produce the following to standard output:

• A list of $K$ numbers, which are the IDs of the programs it will "take 1" from this round. An empty output means it will do nothing.

• Optionally, one extra line representing some form of state to pass on to later rounds. This exact line will be fed back to the program in the next round.

Below is an example input for the beginning of the game for a player of ID $3$ in a 4-player game:

4 3 0
4696634734863777023

Below is an example input for the same game with a few rounds already played:

4 3 2
(1, 2) (1, 3) (1, 4) (4, 2)
(1, 3) (2, 1) (2, 4) (3, 1) (4, 1)
4675881156406346380

Each program will be fed exactly the same input for a round except for the ID number D which is unique to each program.

Below is an example output in which player $3$ takes 1 from everybody else:

1 2 4

At the end of all the required rounds, the player with the highest final score will be the winner.

Timeline

The coding for this tournament will last for a total of 7 days. The deadline for submissions is 2014-05-09 00:00 UTC.

Do not post actual programs before this date – post the SHA256 hash of the source code of your program as a commitment. You may change this hash any time before the deadline, but commitments posted after the deadline will not be accepted for judgment. (Please use base 64 notation for your hashes, as my verification program spits out base 64 and it's a more compact notation.)

After the deadline is over, you will have 1 day (until 2014-05-10 00:00 UTC) to post the actual source code of your program for your submission. If the SHA256 hash of your posted source code does not match any hash that you posted before the deadline, your code will not be accepted into the tournament.

After this, I will download all the submissions onto my own computer, and run all the tournament entries in this battle royale, hopefully posting the results within 2 days from then, by 2014-05-12 00:00 UTC.

I will accept the answer with the highest score, and award a bounty of +100 to that answer if its final score is greater than 0.

After the tournament is over, I will post the random seed file used to run the competition, and people may start posting other solutions trying to top the ones used in the tournament. However, they will not count for acceptance or the bounty.

The Host Machine

I will be running these solutions on a virtual machine on my computer. This virtual machine will run Ubuntu Linux 14.04, with 2 gigabytes of RAM. My base machine has an Intel i7-2600K processor running at 3.40 GHz.

Requirements

Your program must be written in a language for which a compiler or interpreter that will compile your program exists and is readily available for the latest version of Ubuntu Linux, so that I can run all the submissions and judge them in a virtual machine.

Your program must not take more than 2.000 seconds to run each round. If your program runs out of time or produces an error, its output will be considered empty for that round.

Your program must be deterministic; that is, it must always return the same output for the same input. Pseudorandom solutions are allowed; however, their randomness must depend on the random seed given to it as input and nothing else. The seed file was generated using Python's os.urandom. It contains a total of 500 lines (more will be generated if necessary), and its SHA256 hash is K+ics+sFq82lgiLanEnL/PABQKnn7rDAGmO48oiYxZk=. It will be uploaded here once the tournament is over.

Plants

To kick things off, there will be four "plants", representing initial naïve strategies. These will be playing in the tournament along with your submissions. However, in the unlikely case that one of them wins, the highest score obtained by a player other than a plant will be considered the winner.

To calculate the hash of each plant's file, replace every group of 4 spaces with a tab, since the formatter here doesn't seem to like tab characters.

The Lazy — never does anything.

n1bnYdeb/bNDBKASWGywTRa0Ne9hMAkal3AuVZJgovI=

pass

The Greedy — always takes 1 from everybody else.

+k0L8NF27b8+Xf50quRaZFFuflZhZuTCQOR5t5b0nMI=

import sys

line1 = sys.stdin.readline()
n = [int(i) for i in line1.split()]
for i in range(n[0]):
    if i+1 != n[1]:
        print i+1,
print

The Wrathful — takes 1 from everybody else on the first round, and takes 1 from everybody who took 1 from it the previous round afterwards.

Ya2dIv8TCh0zWzRfzUIdFKWj1DF9GXWhbq/uN7+CzrY=

import sys
import re

line1 = [int(i) for i in sys.stdin.readline().split()]

players = line1[0]
pid = line1[1]
rounds = line1[2]

lines = []

if rounds == 0:
    for i in range(players):
        if i+1 != pid:
            print i+1,
    print
else:
    for i in range(rounds):
        lines.append(sys.stdin.readline())
    lastline = lines[-1]
    takes = re.findall(r'\([0-9]+, [0-9]+\)', lastline)
    for take in takes:
        sides = [int(i) for i in re.findall(r'[0-9]+', take)]
        if sides[1] == pid:
            print sides[0],
    print

The Envious — takes 1 from the 50% of players with the current highest score excluding itself, rounding down.

YhLgqrz1Cm2pEcFlsiIL4b4MX9QiTxuIOBJF+wvukNk=

import sys
import re

line1 = [int(i) for i in sys.stdin.readline().split()]

players = line1[0]
pid = line1[1]
rounds = line1[2]

lines = []
scores = [0] * players

if rounds == 0:
    for i in range(players):
        if i+1 != pid:
            print i+1,
    print
else:
    for i in range(rounds):
        takes = re.findall(r'\([0-9]+, [0-9]+\)', sys.stdin.readline())
        for take in takes:
            sides = [int(i) for i in re.findall(r'[0-9]+', take)]
            scores[sides[0] - 1] += 1
            scores[sides[1] - 1] -= 2
    score_pairs = [(i+1, scores[i]) for i in range(players)]
    score_pairs.sort(key=lambda x:(x[1], x[0]))
    score_pairs.reverse()
    taken = 0
    j = 0
    while taken < (players) / 2:
        if score_pairs[j][0] != pid:
            print score_pairs[j][0],
            taken += 1
        j += 1

In a tournament of 100 rounds just amongst these four, they receive scores of:

Lazy: -204
Greedy: -100
Wrathful: -199
Envious: -199

Judging Program

I've posted the judge program I'll be using at Github. Download it and test it out. (And maybe fix a bug or two if you find one. :P)

It doesn't have compilation options for anything other than Python at the moment. I'll be including those later - if people could contribute compilation or interpretation scripts for other languages, I'd be much obliged.

Phase 2: Source Code Submission

I've posted a new branch tournament to the Github repository for the contest, containing the pd_rand file and other plant entries. You can either post your source code here or submit it to that branch as a pull request.

The order of the contestants will be as follows:

'begrudger'
'regular'
'patient'
'lazy'
'backstab'
'bully'
'lunatic'
'envious'
'titfortat'
'greedy'
'wrathful'
'judge'
'onepercent'

Final Scores

The output of my testing program:

Final scores:
begrudger -2862
regular -204
patient -994
lazy -2886
backstab -1311
bully -1393
lunatic -1539
envious -2448
titfortat -985
greedy -724
wrathful -1478
judge -365
onepercent -1921

Rankings:

 1. regular      -204
 2. judge        -365
 3. greedy       -724
 4. titfortat    -985
 5. patient      -994
 6. backstab    -1311
 7. bully       -1393
 8. wrathful    -1478
 9. lunatic     -1539
10. onepercent  -1921
11. envious     -2448
12. begrudger   -2862
13. lazy        -2886

So it turns out that the winner is indeed a player - it's The Regular, with -204 points!

Unfortunately, its score wasn't positive, but we can hardly expect that in a simulation of the Iterated Prisoner's Dilemma where everybody's playing to win.

Some surprising results (at least that I thought were surprising):

• The Greedy scored more than Tit for Tat, and in fact, generally higher than most scorers at all.

• The Judge, which was meant to be a sort of "morality enforcer" character (it basically took 1 from whoever had taken 1 from anybody an above-average number of times) ended up scoring rather high, while in simulation testing, it would actually get a rather low score.

And others that (I thought) weren't so surprising:

• The Patient scored a full 484 points more than The Wrathful. It really pays to cooperate that first time.

• One Percent very quickly had almost nobody to kick while they were down. Seems that the 1% is only able to stay that way because they have more players in the game.

Anyway, now that the tournament is over, feel free to post as many extra players as you'd like, and test around with them using the judge program.