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 P1 and P2 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 * 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 18446744073709551615 (2⁶⁴ - 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.

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.

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

For these four submissions, the hash was calculated with tabs instead of spaces at the beginning of each line, because that's how the file was written. For some reason, this isn't being reflected in the editor, so a raw copy-and-paste will not give you a file with the same hash. Replace each group of 4 spaces with a tab character and it should be the same.