1P5: Iterated Prisoner's Dilemma
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')
code = f.read().split('\n')
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.
Gradual
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!
[Edit] 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 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
- Added a margin variable which changes Lisper's tolerance for duchebaggery randomly.
- Updated lisper to clam for the first two rounds to get off on the right foot with co-operative opponents
- 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