Prisoner's Dilemma v.2 - Battle Royale

Question

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. (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.

Answer 1

The Regular

The version of this entry I have chosen for the tournament (SHA-256: ggeo+G2psAnLAevepmUlGIX6uqD0MbD1aQxkcys64oc=) uses Joey's "Random sucker" strategy (albeit with a minor and likely insignificant change), which came in second place in the last contest. Unfortunately, a newer, more effective version submitted just 3 minutes 25 seconds before the deadline has a serious bug, so it could not be used. Nevertheless, this version still fares relatively well.

<?php

$secretKey = '95CFE71F76CF4CD2';
$hashOutput = '';
$hashSeq = 0;
$hashIndex = 64;

function psRand($min = null, $max = null) {
    global $secretKey, $state, $hashOutput, $hashSeq, $hashIndex;
    if ($hashIndex > 56) {
        $hashOutput = hash_hmac('sha256', ++$hashSeq . ' ' . $state['rand'], $secretKey);
        $hashIndex = 0;
    }

    $num = (int)(hexdec(substr($hashOutput, $hashIndex, 8)) / 2);
    $hashIndex += 8;

    return $min === null ? $num : (int)($min + $num * ($max - $min + 1) / 2147483648);
}

$line = fgets(STDIN);
sscanf($line, "%d %d %d", $numPlayers, $myPlayerId, $roundsPlayed);
$roundsCount = 25 * $numPlayers;
$roundsRemaining = $roundsCount - $roundsPlayed - 1;

$betrayalCount = array_fill(1, $numPlayers, 0);
for ($round = 0; $round < $roundsPlayed; ++$round) {
    $line = fgets(STDIN);
    preg_match_all('/\((\d+), (\d+)\)/', $line, $matches, PREG_SET_ORDER);
    foreach ($matches as $m) {
        $defector = (int)$m[1];
        $victim = (int)$m[2];
        if ($victim === $myPlayerId) {
            ++$betrayalCount[$defector];
        }
    }
}

$hashOutput = rtrim(fgets(STDIN), "\n");
$state = unserialize(rtrim(fgets(STDIN), "\n"));
if (!$state) {
    $state = ['rand' => ''];
}

$state['rand'] = hash_hmac('sha256', $state['rand'] . $line, $secretKey);
$victims = [];

if ($roundsPlayed > 1) {
    for ($other = 1; $other <= $numPlayers; ++$other) {
        if ( $other === $myPlayerId) {
            continue;
        }

        if ($betrayalCount[$other] > 7 || psRand() % 1024 < 32 || !$roundsRemaining ) {
            $victims[] = $other;
        }
    }
}

echo implode(' ', $victims), "\n", serialize($state), "\n";

The buggy version has an SHA-256 hash of 2hNVloFt9W7/uA5aQXg+naG9o6WNmrZzRf9VsQNTMwo=:

<?php

$secretKey = '95CFE71F76CF4CD2';
$hashOutput = '';
$hashSeq = 0;
$hashIndex = 64;

function psRand($min = null, $max = null) {
    global $secretKey, $state, $hashOutput, $hashSeq, $hashIndex;
    if ($hashIndex > 56) {
        $hashOutput = hash_hmac('sha256', ++$hashSeq . ' ' . $state['rand'], $secretKey);
        $hashIndex = 0;
    }

    $num = (int)(hexdec(substr($hashOutput, $hashIndex, 8)) / 2);
    $hashIndex += 8;

    return $min === null ? $num : (int)($min + $num * ($max - $min + 1) / 2147483648);
}

$line = fgets(STDIN);
sscanf($line, "%d %d %d", $numPlayers, $myPlayerId, $roundsPlayed);
$roundsCount = 25 * $numPlayers;
$roundsRemaining = $roundsCount - $roundsPlayed - 1;

$betrayalCount = array_fill(1, $numPlayers, 0);
$scoreWindow = array_fill(1, $numPlayers, array_fill(1, $numPlayers, 0));
$lastMove = array_fill(1, $numPlayers, array_fill(1, $numPlayers, false));
for ($round = 0; $round < $roundsPlayed; ++$round) {
    $line = fgets(STDIN);
    preg_match_all('/\((\d+), (\d+)\)/', $line, $matches, PREG_SET_ORDER);
    foreach ($matches as $m) {
        $defector = (int)$m[1];
        $victim = (int)$m[2];
        if ($victim === $myPlayerId) {
            ++$betrayalCount[$defector];
        }
TAB>TAB>if ($round >= $roundsPlayed - 10) {
TAB>TAB>TAB>$scoreWindow[$defector][$victim] -= 2;
TAB>TAB>TAB>$scoreWindow[$victim][$defector] += 1;
TAB>TAB>}
TAB>TAB>if ($round === $roundsPlayed - 1) {
TAB>TAB>TAB>$lastMove[$defector][$victim] = true;
TAB>TAB>}
    }
}

$line .= fgets(STDIN);
$state = unserialize(rtrim(fgets(STDIN), "\n"));
if (!$state) {
    $state = ['rand' => '', 'copying' => array_fill(1, $numPlayers, 0)];
}

$state['rand'] = hash_hmac('sha256', $state['rand'] . $line, $secretKey);
$victims = [];

if ($roundsPlayed > 1) {
    for ($other = 1; $other <= $numPlayers; ++$other) {
        if ($other === $myPlayerId) {
            continue;
        }

TAB>TAB>if ($roundsPlayed >= 10) {
TAB>TAB>TAB>$myScore = $scoreWindow[$other][$myPlayerId];
TAB>TAB>TAB>foreach ($scoreWindow[$other] as $betterPlayer => $betterScore) {
TAB>TAB>TAB>TAB>if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {
TAB>TAB>TAB>TAB>TAB>$state['copying'][$other] = $betterPlayer;
TAB>TAB>TAB>TAB>}
TAB>TAB>TAB>}
TAB>TAB>}

TAB>TAB>if ($state['copying'][$other]) {
TAB>TAB>TAB>if ($lastMove[$state['copying'][$other]][$other]) {
TAB>TAB>TAB>TAB>$victims[] = $other;
TAB>TAB>TAB>}
        } elseif ($betrayalCount[$other] > 7 || psRand() % 1024 < 32 || !$roundsRemaining ) {
            $victims[] = $other;
        }
    }
}

echo implode(' ', $victims), "\n", serialize($state), "\n";

To fix it, make these replacements:

• Replace $hashOutput = rtrim(fgets(STDIN), "\n"); with $line .= fgets(STDIN); (not that that really matters).
• Replace if ($betterScore >= 3 * $myScore) { with if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) { (this is what killed it).

Answer 2

One Percent

b61189399ae9494b333df8a71e36039f64f1d2932b838d354c688593d8f09477

Looks down on those prisoners he considers beneath him.

---

Simply takes from everyone that has points less than or equal to himself. The assumption is that those prisoners are less likely to take in return (or they'd have more). I don't know how good of an assumption that is, but that's what he's operating on.

Also takes from everyone on the last round. There is literally no downside to this, since nobody can revenge-steal after that.

If you have problems getting the hash because of tab/spaces from pasted code, here's a link to the file itself.

import java.io.BufferedReader;
import java.io.InputStreamReader;

class OnePercent {

    static int numPlayers;
    static int me;
    static int turn;
    static int[] values;

    public static void main(String[] args) {
        if(!readInput())
            return;
        String out = "";
        for(int i=1;i<values.length;i++){
            if(i != me && (values[i] <= values[me] || turn > (numPlayers*25-2)))
                out += i + " ";
        }
        out.trim();
        System.out.print(out);
    }

    static boolean readInput(){
        try {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String line = reader.readLine();
            if(line == null)
                return false;
            String[] tokens = line.split(" ");
            if(tokens.length < 3)
                return false;
            numPlayers = Integer.valueOf(tokens[0]);
            me = Integer.valueOf(tokens[1]);
            turn = Integer.valueOf(tokens[2]);
            values = new int[numPlayers+1];
            for(int i=0;i<values.length;i++)
                values[i]=0;

            for(int i=0;i<turn;i++){
                line = reader.readLine();
                line = line.replaceAll("[)]",",");
                line = line.replaceAll("[( ]", "");
                tokens = line.split(",");
                for(int j=0;j<tokens.length-1;j+=2){
                    int thief = Integer.valueOf(tokens[j]);
                    int poor = Integer.valueOf(tokens[j+1]);
                    if(thief<1||poor<1||thief>numPlayers||poor>numPlayers)
                        continue;
                    values[thief]++;
                    values[poor] -= 2;
                }
            }
            reader.close();
        } catch(Exception e) {
            return false;
        }
        return true;
    }

}

Answer 3

Here are a few more plants that will be participating in the game. These ones are more advanced, and their source code will not be revealed until the end of the coding phase.

Just like the four plants in the question, if they manage to score higher than all other players, only the highest score achieved by an actual contestant will be considered a winner.

---

The Bully

29AGVpvJmDEDI5Efe/afmMJRLaJ+TpjwVcz1GkxgYZs=

Picks on people.

---

The Judge

yjdCQ3uQ4YKe7xAKxdTFLF4d72fD4ACYpDLwkbzdISI=

Punishes wrongdoers.

---

The Lunatic

m3FsRPocekCcK6GDswgnobV2CYOxX8LquChnKxrx1Wo=

Has no idea what it's doing.

---

The Patient

nd7Pt3bVpFnuvDVeHQ5T9EPTq7KjNraVzp/KGtI73Vo=

Never makes the first move.

Answer 4

Tit-for-tat

9GkjtTDD2jrnMYg/LSs2osiVWxDDoSOgLCpWvuqVmSM=

Similar to Wrathful, with a few (hopefully) performance-enhancing changes.

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:
    print
elif rounds == 25 * players - 1:
    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

Answer 5

Backstab

Python 3

Despite the name, this bot is actually quite gracious. But don't tick it off.

import sys, math

inp = [int(i) for i in sys.stdin.readline().split()]
inp.append([])
for i in range(inp[2]):
    inp[3].append(
        [eval(i+')') for i in sys.stdin.readline().split(')')[:-1]]
    )
inp += sys.stdin.readline()

# inp is [P, D, N, [M1, M2...], R]

dat = [[], inp[2] % 2] # average runlength take and don't per player, parity of round

lastatk = []

for i in range(inp[0]):
    dat[0].append([])
    lastatk.append(0)

for i,r in enumerate(inp[3]): # each round
    for m in r: # each move
        if m[1] == inp[1]:
            dat[0][m[0]-1].append(i) # round num they attacked
            lastatk[m[0]-1] = i # keep track of last attack

# now that we know who attacked me when, i can do some stats

nav = []
rl = []

for i in range(inp[0]):
    nav.append([[0], False])
    rl.append([[], []]) # attack, don't

for i in range(inp[2]): # each round
    for p in range(1, inp[0]+1): # each player
        if p != inp[1]: # let's not judge ourselves
            if i in dat[0][p-1]: # p attacked me in round i
                if nav[p-1][1]: # attack chain?
                    nav[p-1][0][-1] += 1
                else: # start attack chain!
                    rl[p-1][1] += [nav[p-1][0][-1]] # copy peace chain
                    nav[p-1][0].append(1)
                    nav[p-1][1] = True
            else: # peace!
                if not nav[p-1][1]: # peace chain?
                    nav[p-1][0][-1] += 1
                else: # peace to all!
                    rl[p-1][0] += [nav[p-1][0][-1]] # copy atk chain
                    nav[p-1][0].append(1)
                    nav[p-1][1] = False

print(nav)

print(inp[3])

# now, rl has runlengths for each player.

print(rl)

rl = [[sum(i[0])/len(i[0]+[0]), sum(i[1])/len(i[1]+[0])] for i in rl]

# rl now contains the averages w/ added zero.

# So, now we have average runtime and last attack. Let's quickly make some descisions.

out = []

for p in range(1, inp[0]+1): # each player
    if p != inp[1]: # again, let's not judge ourselves
        if lastatk[p-1] == inp[0]-1: # they attacked us!
            out.append(p)
        else: # whew, we can recover
            if inp[0] - lastatk[p-1] > rl[p-1][0]: # they're due to defend!
                out.append(p)
            elif int(__import__('binascii').b2a_hex(inp[-1].encode()), 16) % 4 == 0: # 1 in 4 chance of doing this
                out.append(p) # backstab!!1!!1one!!!1!!

print(*out)

EDIT 2: Posted source. Yay.

EDIT: After some testing I fixed some flaws I found. They aren't algorithmic, just some issues reading the input.

Answer 6

The Begrudger

g1TXBu2EfVz/uM/RS24VeJuYMKLOaRatLxsA+DN1Mto=

Code

I will admit that I did not spend much time on this...

import sys
p, d, n, o = input().split(' ') + ['']
p, d, n = int(p), int(d), int(n)
for i in range(n):
    r = input()
    r = r[1:len(r)-1].split(') (')
    for a in r:
        if int(a.split(', ')[1]) == d and not a.split(', ')[0] in o:
            o += a.split(', ')[0] + " "

input()
print(o)