1P5: Iterated Prisoner's Dilemma

This task is part of the First Periodic Premier Programming Puzzle Push and is intended as demonstration of the new challenge-type proposal.

The task is the write a program to play the iterated prisoner's dilemma better than other entrants.

Look, Vinny. We know your cellmate---what's his name? Yeah McWongski, the Nippo-Irish-Ukranian mobster--is up to something and you know what it is.

We're trying to be nice here, Vinnie. Givin' you a chance.

If you tells us what he's plannin' we'll see you get a good work assignment.

And if you don't...

The Rules of the Game

• The contest consists of a full round-robin (all possible pairing) of two contestants at a time (including self plays).
• There are 100 rounds played between each pair
• In each round each player is asked to choose between cooperating with the other player or betraying them, without knowing the other players intentions in the matter, but with a memory of the outcomes of previous rounds played against this opponent.
• Points are awarded for each round based on the combined choice. If both players cooperate they each get 2 points. Mutual betrayal yields 1 point each. In the mixed case, the betraying player is awarded 4 points and the cooperator is penalized by 1.
• An "official" match will be run not sooner than 10 days after posting with all the submissions I can get to work and be used to select the "accepted" winner. I have a Mac OS 10.5 box, so POSIX solutions should work, but there are linuxisms that don't. Likewise, I have no support for the win32 API. I'm willing to make a basic effort to install things, but there is a limit. The limits of my system in no way represent the limits of acceptable responses, simply those that will be included in the "offical" match.

The Programmer's interface

• Entries should be in the form of programs that can be run from the command line; the decision must the (sole!) output of the program on the standard output. The history of previous rounds with this opponent will be presented as a command-line argument.
• Output is either "c" (for clam up) or "t" (for tell all).
• The history is a single string of characters representing previous rounds with the most recent rounds coming earliest in the string. The characters are
• "K" (for kept the faith meaning mutual cooperation)
• "R" (for rat b@st@rd sold me out!)
• "S" (for sucker! meaning you benefited from a betrayal)
• "E" (for everyone is looking out for number one on mutual betrayal)

The bracket

Four players will be provided by the author

• Angel -- always cooperates
• Devil -- always talks
• TitForTat -- Cooperates on the first round then always does as he was done by in the last round
• Random -- 50/50

to which I will add all the entries that I can get to run.

The total score will be the sum score against all opponents (including self-plays only once and using the average score).

Entrants

(current as of 2 May 2011 7:00)

Scorer

#! /usr/bin/python
#
# Iterated prisoner's dilemma King of Hill Script Argument is a
# directory. We find all the executables therein, and run all possible
# binary combinations (including self-plays (which only count once!)).
#
# Author: dmckee (https://codegolf.stackexchange.com/users/78/dmckee)
#
import subprocess
import os
import sys
import random
import py_compile

###
# config
PYTHON_PATH = '/usr/bin/python' #path to python executable

RESULTS = {"cc":(2,"K"), "ct":(-1,"R"), "tc":(4,"S"), "tt":(1,"E")}

def runOne(p,h):
"""Run process p with history h and return the standard output"""
#print "Run '"+p+"' with history '"+h+"'."
process = subprocess.Popen(p+" "+h,stdout=subprocess.PIPE,shell=True)
return process.communicate()[0]

def scoreRound(r1,r2):
return RESULTS.get(r1[0]+r2[0],0)

def runRound(p1,p2,h1,h2):
"""Run both processes, and score the results"""
r1 = runOne(p1,h1)
r2 = runOne(p2,h2)
(s1, L1), (s2, L2) = scoreRound(r1,r2), scoreRound(r2,r1)
return (s1, L1+h1),  (s2, L2+h2)

def runGame(rounds,p1,p2):
sa, sd = 0, 0
ha, hd = '', ''
for a in range(0,rounds):
(na, ha), (nd, hd) = runRound(p1,p2,ha,hd)
sa += na
sd += nd
return sa, sd

def processPlayers(players):
for i,p in enumerate(players):
base,ext = os.path.splitext(p)
if ext == '.py':
py_compile.compile(p)
players[i] = '%s %sc' %( PYTHON_PATH, p)
return players

print "Finding warriors in " + sys.argv[1]
players=[sys.argv[1]+exe for exe in os.listdir(sys.argv[1]) if os.access(sys.argv[1]+exe,os.X_OK)]
players=processPlayers(players)
num_iters = 1
if len(sys.argv) == 3:
num_iters = int(sys.argv[2])
print "Running %s tournament iterations" % (num_iters)
total_scores={}
for p in players:
total_scores[p] = 0
for i in range(1,num_iters+1):
print "Tournament %s" % (i)
scores={}
for p in players:
scores[p] = 0
for i1 in range(0,len(players)):
p1=players[i1];
for i2 in range(i1,len(players)):
p2=players[i2];
#        rounds = random.randint(50,200)
rounds = 100
#print "Running %s against %s (%s rounds)." %(p1,p2,rounds)
s1,s2 = runGame(rounds,p1,p2)
#print (s1, s2)
if (p1 == p2):
scores[p1] += (s1 + s2)/2
else:
scores[p1] += s1
scores[p2] += s2

players_sorted = sorted(scores,key=scores.get)
for p in players_sorted:
print (p, scores[p])
winner = max(scores, key=scores.get)
print "\tWinner is %s" %(winner)
total_scores[p] += 1
print '-'*10
print "Final Results:"
players_sorted = sorted(total_scores,key=total_scores.get)
for p in players_sorted:
print (p, total_scores[p])
winner = max(total_scores, key=total_scores.get)
print "Final Winner is " + winner

• Complaints about my horrible python are welcome, as I am sure this sucks more than one way
• Bug fixes welcome

Scorer Changelog:

• Print sorted players and scores, and declare a winner (4/29, Casey)
• Optionally run multiple tournaments (./score warriors/ num_tournaments)) default=1 , detect & compile python sources (4/29, Casey)
• Fix particularly dumb bug in which the second player was being passed a incorrect history. (4/30, dmckee; thanks Josh)

Initial warriors

By way of example, and so that the results can be verified

Angel

#include <stdio.h>
int main(int argc, char**argv){
printf("c\n");
return 0;
}


or

#!/bin/sh
echo c


or

#!/usr/bin/python
print 'c'


Devil

#include <stdio.h>
int main(int argc, char**argv){
printf("t\n");
return 0;
}


Random

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
int main(int argc, char**argv){
srandom(time(0)+getpid());
printf("%c\n",(random()%2)?'c':'t');
return 0;
}


Note that the scorer may re-invoke the warrior many times in one second, so a serious effort must be made to insure randomness of the results if time is being used to seed the PRNG.

TitForTat

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char**argv){
char c='c';
if (argv[1] && (
(argv[1][0] == 'R') || (argv[1][0] == 'E')
) ) c='t';
printf("%c\n",c);
return 0;
}


The first one that actually does something with the history.

Running the scorer on only the provided warriors yields

Finding warriors in warriors/
Running warriors/angel against warriors/angel.
Running warriors/angel against warriors/devil.
Running warriors/angel against warriors/random.
Running warriors/angel against warriors/titfortat.
Running warriors/devil against warriors/devil.
Running warriors/devil against warriors/random.
Running warriors/devil against warriors/titfortat.
Running warriors/random against warriors/random.
Running warriors/random against warriors/titfortat.
Running warriors/titfortat against warriors/titfortat.
('warriors/angel', 365)
('warriors/devil', 832)
('warriors/random', 612)
('warriors/titfortat', 652)


That devil, he's a craft one, and nice guys apparently come in last.

Results

of the "official" run

('angel', 2068)
('helpvamp', 2295)
('pavlov', 2542)
('random', 2544)
('littleschemer', 2954)
('devil', 3356)
('simpleton', 3468)
('secrethandshake', 3488)
('antit42t', 3557)
('softmajo', 3747)
('titfor2tats', 3756)
('convergence', 3772)
('probabimatic', 3774)
('mistrust', 3788)
('hyperrationalwasp', 3828)
('bygones', 3831)
('honoramongthieves', 3851)
('titfortat', 3881)
('druid', 3921)
('littlelisper', 3984)
('shark', 4021)
('randomSucker', 4156)

• If my cellmate is Nippo-Irish-Ukrainian, why does his name look Hiberno-Sino-Russian? Apr 29 '11 at 22:32
• @Peter: LOL. The truth? Well, (1) the genealogies aren't clear, but I probably come by my mic'edness by way of the Scotch-Irish; (2) after I'd written "Nippo" I tried out various bits of the names of my friends from the land of the rising sun and didn't like the way they scanned, so I went ahead and used a Chinese surname that sounded good instead, and (3) I wouldn't know the difference if they took turns beating me with tire irons. Which seems likely under the circumstances. Apr 29 '11 at 22:51
• @Josh: Would it be simple to change return (s1, L1+h1), (s2, L2+h1) to return (s1, L1+h1), (s2, L2+h2) [Note L2+h2 instead of L2+h1 at the end]? //Cut-n-paste mistake or something equally idiotic. Sheesh! May 1 '11 at 0:01
• I've spent some time on the test script, and I'm pleased to announce an update here. This update adds a simple shell to the test script, which allows the user to manually run this bot vs. that bot, run tournaments with restricted fields and some other cool stuff. Feel free to make suggestions! Oh. And I owe @josh for the bot-vs-bot idea. It's really just a fancier implementation of his "trainer" script. May 1 '11 at 4:22
• Interesting: There were 23 contestents, so each played 22 rounds. If everyone had played "Angel" every score would have been 4400, but even the best score of 4167 did not match that. If only we lived in a perfect world... :) Sep 9 '11 at 18:19

This strategy is based on a paper by Beaufils, Delahaye and Mathieu. My C really isn't the best, so if anyone has any suggestions to improve/speed up the code, let me know!

 Worth to note is that Gradual was designed to be a strategy that outperforms Tit for Tat. It has similar properties in that it is willing to cooperate and retaliates against a defecting opponent. Unlike Tit for Tat, which only has a memory of the last round played, Gradual will remember the complete interaction and defect the number of times the opponent has defected so far. It will offer mutual cooperation afterwards again, though.

As usual, the performance of the strategy depends a bit on the line-up of other strategies. Also the original paper wasn't really clear on some details.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
if(argc == 1){
printf("c\n");
return 0;
}

size_t l = strlen(argv[1]);
int i;
size_t currentSequence = 0;
size_t totalDefects = 0;
size_t lastDefects = 0;

for(i = l-1; i >= 0; i--){
if(argv[1][i] == 'E' || argv[1][i] == 'R'){
totalDefects++;
currentSequence = 0;
} else if(argv[1][i] == 'S') {
currentSequence++;
}
}

if(currentSequence < totalDefects)
// continue defect sequence
printf("t\n");
else if(argv[1][0] == 'S' || argv[1][0] == 'E' ||
argv[1][1] == 'S' || argv[1][1] == 'E')
// blind cooperation
printf("c\n");
else if(argv[1][0] == 'R')
// start new defect sequence
printf("t\n");
else
printf("c\n");

return 0;
}


The Secret Handshake

#!/usr/bin/python
import sys
import random

def main():
if len(sys.argv) == 1:
hist = ""
else:
hist = sys.argv[1]
if len(hist) <= len(TAG) and hist == TAGMATCH[len(TAG) - len(hist):]:
print TAG[len(TAG) - len(hist) - 1]
return
if hist[-len(TAG):] == TAGMATCH:
print 'c'
return
print "t"

def getTag():
global TAG
filename = sys.argv[0]
filename = filename.replace(".pyc", ".py")
f = open(filename, 'r')
f.close()
if len(code[1]) == 0 or code[1][0] != '#':
random.seed()
newtag = 't' * 10
cs = 0
while cs < 3:
pos = random.randint(0, 8)
if newtag[pos] == 't':
newtag = newtag[:pos] + 'c' + newtag[pos+1:]
cs += 1
code.insert(1, '#%s' % newtag)
f = open(filename, 'w')
f.write('\n'.join(code))
f.close()
TAG = newtag
else:
TAG = code[1][1:]
global TAGMATCH
TAGMATCH = TAG.replace('c', 'K').replace('t', 'E')

if __name__ == "__main__":
getTag()
main()


The strategy here is to sacrifice the first 10 rounds to performing a "secret" handshake. If I'm celled with myself, I then recognize the history of the first 10 moves and put on my Angel cap for the rest of the game. As soon as I recognize that my cellmate isn't myself, I transform into a Devil in an attempt to take advantage of overly cooperative cellmates.

Whether sacrificing the first 10 rounds will allow me to edge out the Devil itself depends strongly on how many entries there are. To minimize the damage, only 3 cooperates show up in the handshake.

Edit: TAGMATCH dynamic now to prevent stupid errors like changing only one of them and so I can make TAG dynamic at some point in the future.

Edit 2: Now randomly generates the tag on the first run and stores it in the file specified by sys.argv[0] (.pyc replaced by .py so it goes to the code, not bytecode, file). I think this is the only information all of my instances have that no one else has, so it seems like the only option for avoiding parasites.

• But how does your doppelganger know to make itself a devil? Apr 30 '11 at 3:44
• (I feel like a parrot, saying "Tit for Tat" all the time...) Note that T4T will beat your strategy in a pairing against: T4T (cooperates earlier) and Devil (fewer Rat results), and will tie with your strategy. Of course, the grand total, not the pairing total, is what counts in the end. As you say, the population is important.
– jscs
Apr 30 '11 at 4:16
• Oh, no, you get one extra S out of Tit for Tat. Nice. I didn't realize TAG was being played backwards. However, shouldn't your TAGMATCH be 'KEEEKEEEKE'? "".join({('c', 'c'):'K', ('t', 't'): 'E'}[moves] for moves in zip(TAG, TAG))
– jscs
Apr 30 '11 at 5:25
• @John Good point - I originally had a different TAG and when I changed it to minimize cooperation, I forgot to update TAGMATCH. @Arrdem The idea is that if I'm playing against myself, the best thing to do is for both to cooperate all the time to maximize the sum of their scores. Apr 30 '11 at 18:28
• Aww, damn it. So now I have to search all the .py files for your code and extract the TAG. I won't do that in C, though ...
– Joey
May 2 '11 at 8:18

The Little Lisper

(setf *margin* (/ (+ 40 (random 11)) 100))
(setf *r* 0.0)
(setf *s* 0.0)
(setf *k* 0.0)
(setf *e* 0.0)

;; step 1 - cout up all the games results

(loop for i from 1 to (length(car *args*)) do
(setf foo (char (car *args*) (1- i)))
(cond
((equal foo #\R) (setf *r* (1+ *r*)))
((equal foo #\S) (setf *s* (1+ *s*)))
((equal foo #\K) (setf *k* (1+ *k*)))
((equal foo #\E) (setf *e* (1+ *e*)))
)
)

(setf *sum* (+ *r* *s* *k* *e*))

;; step 2 - rate trustworthiness
(if (> *sum* 0)
(progn
(setf *dbag* (/ (+ *r* *e*) *sum*)) ; percentage chance he rats
(setf *trust* (/ (+ *s* *k*) *sum*)); percentage chance he clams
)
(progn
(setf *dbag* 0) ; percentage chance he rats
(setf *trust* 0); percentage chance he clams
)
)

;; step 3 - make a decision (the hard part....)

(write-char
(cond
((> *sum* 3) (cond
((or (= *dbag* 1) (= *trust* 1)) #\t) ; maximizes both cases
; takes advantage of the angel, crockblocks the devil
((> (+ *dbag* *margin*) *trust*) #\t) ; crockblock statistical jerks
((< *dbag* *trust*) #\c)              ; reward the trusting (WARN - BACKSTABBING WOULD IMPROVE SCORE)
((and
(= (floor *dbag* *margin*) (floor *trust* *margin*))
(not (= 0 *dbag* *trust*)))
#\t)                              ; try to backstab a purely random opponent, avoid opening w/ a backstab
)
)
(t #\c)                                            ; defalt case - altruism
)
)


The Devil

Consider the following, format (Player1, Player2)

• (C, T) - P2 gains FOUR POINTS for his treachery, while P1 LOOSES ONE
• (T, T) - P2 AND P1 GAIN 1

Assuming that P2 is the devil, there is no way that the devil can ever loose points, in fact the worst that he can do is gain only one point. Up against a purely random opponent therefore, the devil's worst possible score will be exactly (5/2)*n where n is the number of "games" played. His absolute worst-case is against himself, where his score will be n, and his best-case is against an angel, which will be 4*n

Assert : optimal_strat = devil

this is a tourney. Backstabbing my cell-mate is a much better strategy than cooperation because it helps MY SCORE more (+4). BONUS - he gets slammed (-1)! If I stick my neck out for him, I stand to gain (+2) and loose (-1). Therefor statistically backstabbing is rewarded.

But Is It Optimal?

There is no reason to EVER (under this scoring system) co-operate.

• If you chose the wrong time to clam up, you loose out.
• If you rat, at least you don't loose anything.
• If you rat and he's dumb, you gain 2x more than if you had been a good pall.

In the KOTH system, maximization of returns is essential. Even if you have two bots who get perfectly synced and co-operate, their individuals scores will still only get boosted by 200 points for their sportsmanship. A devil on the other hand will earn at least 100 points, with an average case of 200 and a maximum of 400, and cost his opponents up to 100 points each! So practically, the devil really scores an average game of 300, spiking to 500.

Bottom line - time will tell

To me, it looks like the scoring should be re-considered lest the devil take the day. Increasing the co-operation score to 3 all might do it. It is possible however to detect devils and prevent them from scoring their full 400, as pavlov and spite show. Can I prove that either one will pick up enough points for their cooperation to justify their faith? no. All of that is dependent on the final field of contenders.

GL, HF!

And please do your worst to this post. I wanna write my senior paper on this when all's said and done.

Version history

1. Added a margin variable which changes Lisper's tolerance for duchebaggery randomly.
2. Updated lisper to clam for the first two rounds to get off on the right foot with co-operative opponents
3. Used a genetic algorithm to find the most robust values for the random threshold generator based on their maximum cumulative score against a standard set of opponents. Posted update including them.

OFFICIAL VERSION OF LISPER

DEVEL VERSION OF LISPER

• The scoring varies in different variants of the game. I did play around with increasing the cooperation incentive, and I agree that it will have an effect on the strategies chosen. The good news: you can grab the scorer, set your own rules and try it. In principle you could even offer a bounty. Apr 30 '11 at 2:16
• fink install clisp ::tapping fingers repeatedly:: Apr 30 '11 at 2:19
• @josh - thanks for the link. I read some other wikipedia pages on this dilemma, but I missed that section. A rules bug I just noticed, there are no rules against entries using the filesystem. this creates the potential for much more efficient co-operation along the lines of the handshake. Apr 30 '11 at 19:26
• There is no reason to EVER (under this scoring system) co-operate is only half-correct. If you know that your opponent doesn't take the history into account (angel, devil, random) then you should always defect. If your opponent does take the history into account and you can sync then you can do better. I have a couple of ideas which revolve around detecting whether the opponent is rational or superrational. May 1 '11 at 11:29
• Aren't you getting divide-by-zero errors 3/20ths of the time with the latest version? Whenever (random 20) gives 2, 5, or 8, (/ (+1 rand-num) 10) is 0.3, 0.6, 0.9, and the remainder of division with 0.3 is 0; so (floor *dbag* *margin*) dies.
– jscs
May 1 '11 at 23:38

Mistrust (variant)

This one came out first in my own tests years ago (back then I was in 11th grade and did a tiny thesis on exactly this, using strategies devised by other students as well). It starts out with the sequence tcc ( and plays like Tit for Tat after that.

Apologies for the horrible code; if someone can make that shorter while not exactly golfing it, I'd be grateful :-)

#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[]) {
if (argc == 1)
printf("t\n");
else switch (strlen(argv[1])) {
case 0:
printf("t\n");
break;
case 1:
case 2:
printf("c\n");
break;
default:
if (argv[1][0] == 'R' || argv[1][0] == 'E')
printf("t\n");
else
printf("c\n");
break;
}

return 0;
}

• No need for duplicate code on length 1 and 2. Use fall through: case 1: case2: printf(...); break;. And gcc wants an explicit declaration of string.h to use strlen. In any case I have it running. Apr 29 '11 at 21:36
• Ah, true that. I wasn't sure how to detect the very first round, though, whether there is an empty first argument (history) or just none.
– Joey
Apr 29 '11 at 21:41
• I'm not sure. It's whatever python does with Popen(p+" "+h,stdout=subprocess.PIPE,shell=True) when h = ''. I'm guessing argc=1. Apr 29 '11 at 21:46
• That initial sequence is quite a good idea, aiming squarely at Tit for Tat's weakness. You get a tiny lead on it, then play its way thereafter.
– jscs
Apr 30 '11 at 2:32
• @Josh, where's the tiny lead? Against T4T this starts out SRK and then continues with K. But SR is worth 3 points to each player. Apr 30 '11 at 10:24

Anti-T42T Missile

#!/usr/bin/python

"""
Anti-T42T Missile, by Josh Caswell

That Tit-for-two-tats, what a push-over!
T42T: ccctcctcc...
AT42TM: cttcttctt...
"""
import sys
try:
history = sys.argv[1]
except IndexError:
print 'c'
sys.exit(0)

if history[:2] == 'SS':
print 'c'
else:
print 't'


Does reasonably well against the base set of warriors: kills Angel, slightly beaten by Devil (but keeps his score low), generally beats RAND handily, and just barely beats Tit for Tat. Does poorly when playing against itself.

• I submitted an edit that makes this one actually work :) It needs to be approved. Apr 30 '11 at 18:40
• @Casey: good lord, I'm making so many stupid mistakes in my enthusiasm for this problem! Thanks, but why did you eliminate the sh-bang?
– jscs
Apr 30 '11 at 19:02
• Er, that was an accident. I'll add it back. Apr 30 '11 at 19:34
• @Casey: no problem. I'll do it. Need to add a doc string anyways.
– jscs
Apr 30 '11 at 19:35

Convergence

Initially nice, then plays randomly with an eye on the opponent's history.

/* convergence
*
* A iterated prisoners dilemma warrior for
*
* Strategy is to randomly chose an action based on the opponent's
* history, weighting recent rounds most heavily. Important fixed
* point, we should never be the first to betray.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <string.h>

int main(int argc, char**argv){
srandom(time(0)+getpid()); /* seed the PRNG */
unsigned long m=(1LL<<31)-1,q,p=m;
if (argc>1) {
size_t i,l=strlen(argv[1]);
for (i=l; --i<l; ){
switch (argv[1][i]) {
case 'R':
case 'E':
q = 0;
break;
case 'K':
case 'S':
q = m/3;
break;
}
p/=3;
p=2*p+q;
}
}
/* printf("Probability of '%s' is %g.\n",argv[1],(double)p/(double)m); */
printf("%c\n",(random()>p)?'t':'c');
return 0;
}


I've tried diddling the weighting on the history, but haven't properly optimized it.

Shark

#!/usr/bin/env python

"""
Shark, by Josh Caswell

Carpe stultores.
"""

import sys

HUNGER = 12

try:
history = sys.argv[1]
except IndexError:
print 'c'
sys.exit(0)

if history.count('S') > HUNGER:
print 't'
else:
print 'c' if history[0] in "SK" else 't'


Does quite well against the base roster.

• ... seize the clam? May 1 '11 at 14:59
• :) Seize the fools.
– jscs
May 1 '11 at 17:30
• +1 for holding a consistent 2nd place in the current field. May 1 '11 at 17:40

Pavlov - Win Stay, Lose Switch

On the first turn it cooperates, and then it cooperates if and only if both players opted for the same choice in the previous move.

#!/usr/bin/python
import sys

if len(sys.argv) == 1:
print 'c'
else:
hist = sys.argv[1]
if hist[0] == 'K' or hist[0] == 'E':
print 'c'
else:
print 't'

• Shouldn't this use hist[0] (hist[-1] is always the first move of the round)?
– jscs
Apr 30 '11 at 17:07
• Oh wow, you're right. I assumed that the input string had the most recent rounds at the end of the string, not the beginning. Fixed. Apr 30 '11 at 17:13

Honor Among Thieves

#!/usr/bin/env python

"""
Honor Among Thieves, by Josh Caswell

I'd never sell out a fellow thief, but I'll fleece a plump mark,
and I'll cut your throat if you try to cross me.
"""

from __future__ import division
import sys

PLUMPNESS_FACTOR = .33
WARINESS = 10

THIEVES_CANT = "E" + ("K" * WARINESS)

try:
history = sys.argv[1]
except IndexError:
history = ""

if history:
sucker_ratio = (history.count('K') + history.count('S')) / len(history)
seem_to_have_a_sucker = sucker_ratio > PLUMPNESS_FACTOR

# "Hey, nice t' meetcha."
if len(history) < WARINESS:
#"Nice day, right?"
if not set(history).intersection("RE"):
print 'c'
# "You sunnuvab..."
else:
print 't'

# "Hey, lemme show ya this game. Watch the queen..."
elif len(history) == WARINESS and seem_to_have_a_sucker:
print 't'

# "Oh, s#!t, McWongski, I swear I din't know dat were you."
elif history[-len(THIEVES_CANT):] == THIEVES_CANT:

# "Nobody does dat t' me!"
if set(history[:-len(THIEVES_CANT)]).intersection("RE"):
print 't'
# "Hey, McWongski, I got dis job we could do..."
else:
print 'c'

# "Do you know who I am?!"
elif set(history).intersection("RE"):
print 't'

# "Ah, ya almos' had da queen dat time. One more try, free, hey? G'head!"
elif seem_to_have_a_sucker:
print 't'

# "Boy, you don't say much, do ya?"
else:
print 'c'


Note that the THIEVES_CANT is essentially a handshake, though it will only emerge when playing against a cooperator. However, it avoids the parasite problem by checking for later crosses. Does quite well against the base roster.

• +1 for being the first strat to reliably trounce lisper. Average margin of victory - 300 pts. May 1 '11 at 15:02
• Seems to be the strongest in a tourney run of the current field. May 1 '11 at 16:23
• Actually, no, Druid is now that I've fixed the bug in the scorer. May 1 '11 at 16:56
• @rmckenzie, @Peter: Geez, really? I was just going for personality.
– jscs
May 1 '11 at 17:17
• @josh - not any more.... on the new scoring code @casey's scoring code Lisper is back on top followed by shark. May 1 '11 at 17:32

"Probabimatic"

Starts by cooperating, then picks whichever option gives it the highest expected value. Simple.

#include <stdio.h>

void counts(char* str, int* k, int* r, int* s, int* e) {
*k = *r = *s = *e = 0;
char c;
for (c = *str; c = *str; str++) {
switch (c) {
case 'K': (*k)++; break;
case 'R': (*r)++; break;
case 'S': (*s)++; break;
case 'E': (*e)++; break;
}
}
}

// Calculates the expected value of cooperating and defecting in this round. If we haven't cooperated/defected yet, a 50% chance of the opponent defecting is assumed.
void expval(int k, int r, int s, int e, float* coop, float* def) {
if (!k && !r) {
*coop = .5;
} else {
*coop = 2 * (float)k / (k + r) - (float)r / (k + r);
}
if (!s && !e) {
*def = 2.5;
} else {
*def = 4 * (float)s / (s + e) + (float)e / (s + e);
}
}

int main(int argc, char** argv) {
if (argc == 1) {
// Always start out nice.
putchar('c');
} else {
int k, r, s, e;
counts(argv[1], &k, &r, &s, &e);
float coop, def;
expval(k, r, s, e, &coop, &def);
if (coop > def) {
putchar('c');
} else {
// If the expected values are the same, we can do whatever we want.
putchar('t');
}
}
return 0;
}


Used to start by cooperating, but now it seems that defecting actually works better. EDIT: Oh wait, it actually doesn't.

• Another statistician! Let's see how this plays against its fellow calculators!
– jscs
Apr 30 '11 at 21:16
• By the way, if you change for (char c = *str; to char c; for (c = *str; then gcc will compile this without complaining that it needs to be put into C99 mode. May 2 '11 at 20:12

Hyperrational Wasp

Implemented in Java because I wasn't sure how complex the data structures were going to end up. If this is a problem for someone then I think I can port it to bash without too many problems because in the end it only really uses simple associative arrays.

Note: I've removed this from a package in line with the latest version of my patch to the scorer to handle Java. If you want to post a Java solution which uses inner classes then you'll have to patch the patch.

import java.util.*;

public class HyperrationalWasp
{
// I'm avoiding enums so as not to clutter up the warriors directory with extra class files.
private static String Clam = "c";
private static String Rat = "t";
private static String Ambiguous = "x";

private static final String PROLOGUE = "ttc";

private static int n;
private static String myActions;
private static String hisActions;

private static String decideMove() {
if (n < PROLOGUE.length()) return PROLOGUE.substring(n, n+1);

// KISS - rather an easy special case here than a complex one later
if (mirrorMatch()) return Clam;
if (n == 99) return Rat; // This is rational rather than superrational

int memory = estimateMemory();
if (memory == 0) return Rat; // I don't think the opponent will punish me
if (memory > 0) {
Map<String, String> memoryModel = buildMemoryModel(memory);
String myRecentHistory = myActions.substring(0, memory - 1);
// I don't think the opponent will punish me.
if (Clam.equals(memoryModel.get(Rat + myRecentHistory))) return Rat;
// I think the opponent will defect whatever I do.
if (Rat.equals(memoryModel.get(Clam + myRecentHistory))) return Rat;
// Opponent will cooperate unless I defect.
return Clam;
}

// Haven't figured out opponent's strategy. Tit for tat is a reasonable fallback.
return hisAction(0);
}

private static int estimateMemory() {
if (hisActions.substring(0, n-1).equals(hisActions.substring(1, n))) return 0;

int memory = -1; // Superrational?
for (int probe = 1; probe < 5; probe++) {
Map<String, String> memoryModel = buildMemoryModel(probe);
if (memoryModel.size() <= 1 || memoryModel.values().contains(Ambiguous)) {
break;
}
memory = probe;
}

if (memory == -1 && isOpponentRandom()) return 0;

return memory;
}

private static boolean isOpponentRandom() {
// We only call this if the opponent appears not have have a small fixed memory,
// so there's no point trying anything complicated. This is supposed to be a Wilson
// confidence test, although my stats is so rusty there's a 50/50 chance that I've
// got the two probabilities (null hypothesis of 0.5 and observed) the wrong way round.
if (n < 10) return false; // Not enough data.
double p = count(hisActions, Clam) / (double)n;
double z = 2;
double d = 1 + z*z/n;
double e = p + z*z/(2*n);
double var = z * Math.sqrt(p*(1-p)/n + z*z/(4*n*n));
return (e - var) <= 0.5 * d && 0.5 * d <= (e + var);
}

private static Map<String, String> buildMemoryModel(int memory) {
// It's reasonable to have a hard-coded prologue to probe opponent's behaviour,
// and that shouldn't be taken into account.
int skip = 0;
if (n > 10) skip = n / 2;
if (skip > 12) skip = 12;

Map<String, String> memoryModel = buildMemoryModel(memory, skip);
// If we're not getting any useful information after skipping prologue, take it into account.
if (memoryModel.size() <= 1 && !memoryModel.values().contains(Ambiguous)) {
memoryModel = buildMemoryModel(memory, 0);
}
return memoryModel;
}

private static Map<String, String> buildMemoryModel(int memory, int skip) {
Map<String, String> model = new HashMap<String, String>();
for (int off = 0; off < n - memory - 1 - skip; off++) {
String result = hisAction(off);
String hypotheticalCause = myActions.substring(off+1, off+1+memory);
String prev = model.put(hypotheticalCause, result);
if (prev != null && !prev.equals(result)) model.put(hypotheticalCause, Ambiguous);
}
return model;
}

private static boolean mirrorMatch() { return hisActions.matches("c*ctt"); }
private static String myAction(int idx) { return myActions.substring(idx, idx+1).intern(); }
private static String hisAction(int idx) { return hisActions.substring(idx, idx+1).intern(); }
private static int count(String actions, String action) {
int count = 0;
for (int idx = 0; idx < actions.length(); ) {
int off = actions.indexOf(action, idx);
if (off < 0) break;
count++;
idx = off + 1;
}
return count;
}

public static void main(String[] args) {
if (args.length == 0) {
hisActions = myActions = "";
n = 0;
}
else {
n = args[0].length();
myActions = args[0].replaceAll("[KR]", Clam).replaceAll("[SE]", Rat);
hisActions = args[0].replaceAll("[KS]", Clam).replaceAll("[RE]", Rat);
}

System.out.println(decideMove());
}

}


The changes I made to the scorer to run this are:

17a18
> import re
22a24
> GCC_PATH = 'gcc'                #path to c compiler
24c26
< JAVA_PATH = '/usr/bin/java'   #path to java vm
---
> JAVA_PATH = '/usr/bin/java'     #path to java vm
50,55c52,59
<         elif ext == '.java':
<             if subprocess.call([JAVAC_PATH, self.filename]) == 0:
<                 print 'compiled java: ' + self.filename
<                 classname = re.sub('\.java$', '', self.filename) < classname = re.sub('/', '.', classname); < return JAVA_PATH + " " + classname --- > elif ext == '.class': > # We assume further down in compilation and here that Java classes are in the default package > classname = re.sub('.*[/\\\\]', '', self.filename) > dir = self.filename[0:(len(self.filename)-len(classname))] > if (len(dir) > 0): > dir = "-cp " + dir + " " > classname = re.sub('\\.class$', '', classname);
>             return JAVA_PATH + " " + dir + classname
196c200,201
<         if os.path.isdir(sys.argv[1]):
---
>         warriors_dir = re.sub('/$', '', sys.argv[1]) > if os.path.isdir(warriors_dir): 198,200c203,211 < for foo in os.listdir("./src/"): # build all c/c++ champs first. < os.system(str("gcc -o ./warriors/" + os.path.splitext(os.path.split(foo)[1])[0] + " ./src/" + foo )) < #print str("gcc -o ./warriors/" + os.path.splitext(os.path.split(foo)[1])[0] + " ./src/" + foo ) --- > for foo in os.listdir("./src/"): # build all c/c++/java champs first. > filename = os.path.split(foo)[-1] > base, ext = os.path.splitext(filename) > if (ext == '.c') or (ext == '.cpp'): > subprocess.call(["gcc", "-o", warriors_dir + "/" + base, "./src/" + foo]) > elif (ext == '.java'): > subprocess.call([JAVAC_PATH, "-d", warriors_dir, "./src/" + foo]) > else: > print "No compiler registered for ", foo 202,203c213,214 < print "Finding warriors in " + sys.argv[1] < players = [sys.argv[1]+exe for exe in os.listdir(sys.argv[1]) if os.access(sys.argv[1]+exe,os.X_OK)] --- > print "Finding warriors in " + warriors_dir > players = [warriors_dir+"/"+exe for exe in os.listdir(warriors_dir) if (os.access(warriors_dir+"/"+exe,os.X_OK) or os.path.splitext(exe)[-1] == '.class')]  Thanks to @rmckenzie for folding in my challenger function. • Just a matter of style.... should the .java file be considered "source" and moved to the ./src directory and the final .class placed in the ./warriors folder by the same subscript used on .c files, or is java interpreted and as such the .java and .class stay together? Nice changes to the scorer in any case... will have them in the repo stat. May 2 '11 at 20:57 • @rmckenzie, good point: yes, technically it's compiled. The reason I had the source file in the warriors directory is that the python files are there too - and they're compiled. If you want I can check what changes are required to compile it from ./src to ./warriors - but it's going to require a few compiler arguments, because Java by default assumes that the directory structure reflects the package (namespace). May 2 '11 at 21:26 • @peter, I was just wondering... the warriors are found in ./warriors by virtue of being *nix 777, or otherwise executable. The Python and Lisp scripts are NOMINALLY compiled for performance, but are executable in their natural (source) state. TO MY KNOWLEDGE AS A NON-JAVA PERSON, .java files don't have those permissions and hence won't show up. That's what the c hack exists for... because compilation is a separate step. So yeah. I would greatly appreciate it if you would look into making that change. REPO LINK May 2 '11 at 21:30 • Using your code and a chmod 777'd wasp, the JVM threw this beauty.Exception in thread "main" java.lang.NoClassDefFoundError: //warriors/HyperrationalWasp Caused by: java.lang.ClassNotFoundException: ..warriors.HyperrationalWasp at java.net.URLClassLoader$1.run(URLClassLoader.java:217) at java.security.AccessController.doPrivileged(Native Method) at java.net.URLClassLoader.findClass(URLClassLoader.java:205) at java.lang.ClassLoader.loadClass(ClassLoader.java:321) at sun.misc.Launcher\$AppClassLoader.loadClass(Launcher.java:294) at java.lang.ClassLoader.loadClass(ClassLoader.java:266)  May 2 '11 at 21:55
• @rmckenzie, that's odd. Anyway, I think I'll have a patch for you very shortly. I've had to hack the loading code, because class files aren't executable. And if any other Java entries use inner classes it will break. May 2 '11 at 22:11

Soft_majo

Ah well, another one of the standard strategies, just to complete the line-up.

This one picks the move the opponent has made most; if equal it cooperates.

#include <stdio.h>
#include <string.h>

int main(int argc, char * argv[]) {
int d = 0, i, l;

if (argc == 1) {
printf("c\n");
} else {
l = strlen(argv[1]);

for (i = 0; i < l; i++)
if (argv[1][i] == 'R' || argv[1][i] == 'E')
d++;

printf("%c\n", d > l/2 ? 't' : 'c');
}
}

• Your code is soft_majo, but your description is hard_majo. May 3 '11 at 12:59
• Peter: Eek, sorry; fixed.
– Joey
May 3 '11 at 13:18

Random sucker

This one will defect if the opponent defects too often (threshold), but will randomly try backstabbing every now and then.

Does fairly well against everyone except the Java and Lisp players (which I cannot get to run, due to neither Java nor Lisp on the test machine); most of the time at least.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#define THRESHOLD 7
#define RAND 32

int main(int c, char * a []) {
int r;
char * x;
int d = 0;

srandom(time(0) + getpid());

if (c == 1) {
printf("c\n");
return 0;
}

for (x = a[1]; *x; x++)
if (*x == 'R' || *x == 'E') d++;

if (d > THRESHOLD || random() % 1024 < RAND || strlen(a[1]) == 99)
printf("t\n");
else
printf("c\n");

return 0;
}

• Against HyperrationalWasp it will generally do roughly as against the devil. It starts out just cooperating all the time, so I assume it's the angel and go on the attack. Then when it hits the threshold you'll switch into devil mode and I'll switch into t4t. If it randomly backstabs in the first 6 moves then I'll switch into t4t before you switch into devil, but the odds of that aren't high. May 4 '11 at 11:59
• Peter: Well, I rarely test the strategies directly against each other, as the overall field has quite some influence on strategy performance. Currently it mostly battles with gradual and druid for the first place in my tests.
– Joey
May 4 '11 at 12:11
• Gradual and druid both score about 200 against Wasp; random sucker will score about 83. May 4 '11 at 12:17

BYGONES

#!/usr/bin/env python

"""
BYGONES, entry to 1P5 Iterated Prisoner's Dilemma, by Josh Caswell

Cooperates at first, plays as Tit for Tat for bygones * 2 rounds, then checks
history: if there's too much ratting, get mad and defect; too much
"""

bygones = 5

import sys

# React to strangers with trust.
try:
history = sys.argv[1]
except IndexError:
print 'c'
sys.exit(0)

replies = { 'K' : 'c', 'S' : 'c',
'R' : 't', 'E' : 't' }

if len(history) < bygones * 2:
print replies[history[0]]
sys.exit(0)

# Reflect on past interactions.
faithful_count = history.count('K')
sucker_count = history.count('S')
rat_count = history.count('R')

# Reprisal.
if rat_count > faithful_count + bygones:
# Screw you!
print 't'
sys.exit(0)

# Reparation.
if sucker_count > faithful_count + bygones:
# Geez, I've really been mean.
print 'c'
sys.exit(0)

# Resolve to be more forgiving.
two_tats = ("RR", "RE", "ER", "EE")
print 't' if history[:2] in two_tats else 'c'


Haven't worked out the best value for bygones yet. I don't expect this to be a winning strategy, but I'm interested in the performance of a strategy something like what I think is "good" in real life. A future revision may include checking the number of mutual defections, too.

Help Vampire

#!/usr/bin/env python

"""
Help Vampire, entry to 1P5 Iterated Prisoner's Dilemma,
by Josh Caswell.

1. Appear Cooperative 2. Acknowledge Chastisement
3. Act contritely 4. Abuse charity 5. Continual affliction
"""

import sys
from os import urandom

LEN_ABASHMENT = 5

try:
history = sys.argv[1]
except IndexError:
print 'c'    # Appear cooperative
sys.exit(0)

# Acknowledge chastisement
if history[0] in "RE":
print 'c'
# Act contritely
elif set(history[:LEN_ABASHMENT]).intersection(set("RE")):
print 'c'
# Abuse charity
elif history[0] == 'S':
print 't'
# Continual affliction
else:
print 't' if ord(urandom(1)) % 3 else 'c'


Has an amusingly asymmetrical result when pitted against itself. If only this solution could be applied in real life.

Druid

#!/usr/bin/env python

"""
Druid, by Josh Caswell

Druids are slow to anger, but do not forget.
"""

import sys
from itertools import groupby

FORBEARANCE = 7
TOLERANCE = FORBEARANCE + 5

try:
history = sys.argv[1]
except IndexError:
history = ""

# If there's been too much defection overall, defect
if (history.count('E') > TOLERANCE) or (history.count('R') > TOLERANCE):
print 't'
# Too much consecutively, defect
elif max([0] + [len(list(g)) for k,g in     # The 0 prevents dying on []
groupby(history) if k in 'ER']) > FORBEARANCE:
print 't'
# Otherwise, be nice
else:
print 'c'


Does reasonably well against the base roster.

Simpleton

#!/usr/bin/env python

"""
Simpleton, by Josh Caswell

Quick to anger, quick to forget, unable to take advantage of opportunity.
"""

import sys
from os import urandom

WHIMSY = 17

try:
history = sys.argv[1]
except IndexError:
if not ord(urandom(1)) % WHIMSY:
print 't'
else:
print 'c'
sys.exit(0)

if history[0] in "RE":
print 't'
elif not ord(urandom(1)) % WHIMSY:
print 't'
else:
print 'c'


Does okay against the base roster.

Little Schemer

#!/usr/bin/env python

"""
The Little Schemer, by Josh Caswell

No relation to the book. Keeps opponent's trust > suspicion
by at least 10%, trying to ride the line.
"""

from __future__ import division
import sys
from os import urandom

out = sys.stderr.write

def randrange(n):
if n == 0:
return 0
else:
return ord(urandom(1)) % n

try:
history = sys.argv[1]
except IndexError:
print 'c'
sys.exit(0)

R_count = history.count('R')
S_count = history.count('S')
K_count = history.count('K')
E_count = history.count('E')

# Suspicion is _S_ and E because it's _opponent's_ suspicion
suspicion = (S_count + E_count) / len(history)
# Likewise trust
trust = (K_count + R_count) / len(history)

if suspicion > trust:
print 'c'
else:
projected_suspicion = (1 + S_count + E_count) / (len(history) + 1)
projected_trust = (1 + K_count + R_count) / (len(history) + 1)

leeway = projected_trust - projected_suspicion
odds = int(divmod(leeway, 0.1)[0])

print 't' if randrange(odds) else 'c'


Does poorly against the base set, but quite well against its target. Obviously, not written in Scheme.

• Why do I sense a challenge? May 1 '11 at 14:47
• Defeated this bugger.... randomized the threshold in Lisper. May 1 '11 at 16:37
• @rmckenzie: but how did that affect your play against the rest of the field? With enough cooperators working with each other, paranoid or envious strategies will start to do worse. You've still got a fixed upper limit, too, which could be exploited.
– jscs
May 1 '11 at 17:35
• If you read through the current lisper, it's more defensive than envious. It tries to detect opponents who are pursuing statistically treacherous strats like this, and only then returns fire. It's CC opening is designed to get off on the right foot with Thieves, and has the added benefit of convincing most of the cooperative strats to play along. May 1 '11 at 17:43
• @rmckenzie: Very good! I'll give it a spin.
– jscs
May 1 '11 at 17:56

Tit for Two Tats

another old favorite

#!/usr/bin/env python

"""
Tit For Two Tats, entry to 1P5 Iterated Prisoner's Dilemma,
by Josh Caswell (not an original idea).

Cooperates unless opponent has defected in the last two rounds.
"""

import sys
try:
history = sys.argv[1]
except IndexError:
history = ""

two_tats = ("RR", "RE", "ER", "EE")

if len(history) < 2:
print 'c'
else:
print 't' if history[:2] in two_tats else 'c'

• You can't do a return unless you're inside a function. Maybe use sys.exit(0) ? Or just let it finish. Edit: Also the first invocation to your program is without any history which causes an IndexError when you do argv[1]. Apr 30 '11 at 1:42
• You may have left out the len(history)<2 clause, because that last one looks like the else part. Apr 30 '11 at 1:44
• @Casey @dmckee Thank you for the bug fixes. "Duh" on me for return especially!
– jscs
Apr 30 '11 at 1:47
• @dmckee: This started out as part of a more complicated thingy, and then I realize I had re-written Tit for Two Tats and decided to enter that. Copy-paste user error.
– jscs
Apr 30 '11 at 1:48
• @Josh: I saw your Bygones entry briefly, did you delete it? It looked interested. Apr 30 '11 at 1:55