text:
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 king-of-the-hill 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)
The Secret Handshake |
Anti-T42T Missile |
Mistrust (variant) |
Anti-Handshake |
The Little Lisper |
Convergence |
Shark |
Probabimatic |
Pavlov - Win Stay, Lose Switch |
Honor Among Thieves |
Help Vampire |
Druid |
Little Schemer |
Bygones |
Tit for Two Tats |
Simpleton |
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)
('gradual', 4167)
        Winner is ./gradual

If my cellmate is Nippo-Irish-Ukrainian, why does his name look Hiberno-Sino-Russian?

Is it allowed to submit a strategy similar or identical to one of your "default warriors"? I.e., can I submit Tit-for-tat myself? (Cf. Rapaport in Axelrod's IPD tourney.) Or is this just boring?

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

@Josh: ::shrug:: I haven't thought about it. I included it in the defaults because it is a well known simple-but-strong player. You'll note that Joey has submitted a nearly as simple variant, and that suggests one way to go forward.

@dmckee What's the policy on multiple submissions?

@Casey: Make sure they are distinct, but go ahead.

Hey guys, I've been hacking a lot on the scoring script. In particular I've added python and lisp compilation to speed things up, as well as parallelized the matches according to your cpu count. I've added some of the changes to the score script in @dmckee's post, but I don't want to intrude to much as not everyone may want these changes. Here is a link to the latest version.

Okay, I really did find a bug this time. I'm not sure what causes it, possibly something weird about tuple assignment. I was running all-C against all-D and displaying the history. All-D's history v. all-C was wrong; it always had 'S' in the most recent position, and 'R' for the rest. The fix against the version in question body as of this comment (wish I didn't have to do this in a comment): Rewrite the following lines: 35:     return (s1, L1),  (s2, L2) 41:     (na, nha), (nd, nhd) = runRound(p1,p2,ha,hd) Add two lines after 43:     ha = nha + ha and     hd = nha + hd

Sorry, for "all-C", read "Angel" and for "all-D" read "Devil". Using the old terminology.

@Josh Hm, there is definitely something screwy there, but I don't think your changes fix it.. shouldn't you expect to see all 'S' for the devil when he is playing the angel?

@Casey: That's what I'm seeing here with my change. Should I make a suggested edit to the post to make it more clear?

@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!

@dmckee: I was hopping you would set a random number of rounds :)

@Eelvex: That's just the kind of input I could have used when I was tinkering with this in the Sand Box.

@dmckee: I know but, unfortunately, wasn't available till now :(

@dmckee: That looks like the bug! Sheesh, I haven't gotten enough sleep lately or something.

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.

I've just posted a half-dozen new warriors. If anyone's concerned that I am "flooding the field" or something like that, I'm perfectly okay with only my first two or three entries going in to the actual tournament. I'm just having fun coming up with ideas.

@rmckenzie, I was thinking of doing that, so thanks for doing it first.

@mckenzie, if I run your score.py with one argument I get a warning about NUM_ROUNDS being assigned to before global declaration and an NameError because num_games is not defined.

@Josh: My only concern is that running the whole round-robin goes by O(N^2). I'm prepared to let the "official" math run for a while, but at some point it could get to be ridiculous.

@peter - thanks for pointing that out, I got it fixed. Updated on github.

@rmckenzie Nice changes! Wanna make a pull request on github?

@mckenzie, I tried implementing the -v option of match by making a copy of runGame which adds print "\n", ha, "\n", hd after the line which prints the score. If I run angel vs devil for a 5-round match I get RRRRR for the angel (correct) and SRRRR for the devil (should be SSSSS). The last line of runRound has a bug. Should be return (s1, L1+h1),  (s2, L2+h2)

@Peter It is fixed in the most recent commit

@dmckee: I certainly understand that. At this point, I just walk away from the computer every time I run a tournament!

@dmckee: What was your reason for only counting the mirror match once? To reduce benefits of collusion? Not complaining, just curious. Every other match gets run twice. E.g., in a tourney of Angel and Devil, we have A v. D and D v. A.

@peter - Thanks. I just saw that... turns out my Lisper was doing so well in part because of that bug sigh but yeah, casey's repo and mine both have that fixed. @josh - I think that's a bug in the iteration generator. A v. D == D v. A, so there's no reason to run that round. Fixing that would halve the runtime....

@Josh, my scorer only runs one of A vs. D or D vs. A. Look at how the loops index. The reason for that was to keep the time down as rmckenzie says. If I was running both versions of the non-identical pairing then you are right: I would need to count both sides of the self-plays.

@dmckee: I must've knocked something out of whack when I made the ProvingGrounds script. My bug. Is your version still official? Are you planning to use either Casey or rmckenzie's changes?

@Josh some of Casey's changes have been applied to the version in the post here. I have not been watching the other versions very closely. I was going to grab the pre-compiling bits for the "official" version. Note that I keep putting "official" in quotes, 'cause I figure anyone can set a bounty, run their own version, and declare their own winner. Maybe a multi-round elimination tournament to support multiple matches and random numbers of rounds (since the "official" version is very much at he mercy of chance due to the randomness employed by some warriors and the short length).

That said, I'm sticking by the posted rules for the purposes of the green check-mark.

I'm voting for every entry as soon as I get it working on my machine. Gotta do Josh's new one soon.

Yet another update to the scoring code if you care... added some population manipulation controls. same github

I am seeing extremely incorrect round-by-round score results using the @Casey/@rmckenzie scorer. It's most noticeable using Angel or Devil and a bot that won't defect first. Examples: Devil v. Shark (200, 200), should not be a C-tie; Handshake v. Pavlov (200, 200), likewise; Angel v. Pavlov (103, 98), should be a C-tie; Angel v. Probabimatic (400, -100), just plain impossible. I would guess it's the threading screwing up just the printing, except that the final results of the tournaments are also off  somewhat compared to what I'm seeing with the "official" scorer. Anyone else seeing this?

@Josh, I'm not seeing that precisely, but some results aren't what I'd expect. E.g. handshake beats anti-handshake 109-94 (although if either has been updated recently I'm out of date).

@josh - I thought I was seeing funny results but wrote it off as just me. thanks for the heads up. will investigate those cases as soon as I have time.

Okay. for a 1v1 with debugging on, shark vs. devil shows this:devil EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEES
shark EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEER. Looks fine. Angel-pavlov is also a c-tie as it should be. no unexpected results whatsoever.

Okay. Last post in defense of the new scoring code, I swear. Running the same round-robin tests on the "official" code above and on the casey/rmckenzie scorer, the average difference in the performance of individual strategies is 18 points in 2300 point average scores. The population was constant between tests.

I think there must be some system difference. The official results seem to agree with @rmckenzie, but I see about the same results with the official scoring code as with his scorer - Random Sucker wins, gradual comes second, then Wasp, Druid and Shark fight it out for third. Anyone got any ideas? The best that I can speculate is a difference in random number quality between python implementations.

@Peter: The full set includes several warriors that use randomness. To test for consistency of scorers we should test with the set of deterministic warriors. I make that to be: angle antiT4T bygones devil druid gradual helpvamp honor.. hyperrat.. littlelisper mistrust pavlov proba.. secret.. shark softmajo T42T T4T. I'll run mine now.

@dmckee, ok. I'll leave it running 5 tournament iterations overnight and post a summary of results tomorrow.

@dmckee - good point. I'll do my own test just for grins.

In 5 runs, Wasp is always first, Gradual is always second, T42T and Mistrust are 3rd and 4th in some order, T4T is 5th. There is some slight fluctuation, so unless one of them is in fact partially random there's a bug somewhere. Edit: of course, handshake now generates a random secret.

Peter: There are plenty of strategies in the field that don't behave deterministic. And they can easily affect the score of the top scorers.

I am relieved to see that Help Vampire came in second to last, only above Angel! Thanks for running this tournament, dmckee; it was fun!

@Josh: It was fun, and most of the credit goes to the many and enthusiastic participants.

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... :)

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

But how does your doppelganger know to make itself a devil?

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

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))

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

New version should prevent parasites.  In order to hold on to the efficiencies I built in to the original tag, the final character (first move) must be a 't' (can't remember why this mattered...) and exactly 3 'c's will occur in the sequence.

Nicely done! (You forgot import random though.)

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

@Josh Good catch.  I had it in my code, but I only edited in the diffs and apparently missed that one.  @Joey I must say, I didn't see that coming.  Hmmmm...

@Aaron: Joey's move is the clear next step. This is fun to watch!

Aaron: Don't fear, I won't. The stateless nature of execution makes writing code a little painful and I'm not really good in thinking about actual strategies :-)

@Joey: Don't fear either. If you're not going to do it, expect "The Handshake Virus" in Python to appear later in the week! :p (You still get original credit, of course!)

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

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.

fink install clisp ::tapping fingers repeatedly::

BTW-- I think that that optimal strategy actual depends on the behavior of the other competitors. Enough warriors that default to good, but detect bad faith can mean that devil averages little more than 1 point per round, while the goody-twoshoes brigade averages closer to 2 points per round. But the balance is presumably delicate, and it doesn't take many bad apples to spoil the fun.

@dmckee: optimal strategy is greatly affected by the population. You've seen IPD's where population changes round to round? Tit for Tat can never do better on its own than Devil, but Tit for Tat plus another strategy that will cooperate always do better than two Devils.

@josh, d - I can't wait to see the final results... I suspect that "statistical devils" which randomly rat with some P < .25 could do quite well, beating out some of the above "trust" plans, depending on the devil detector standards. T42T and T4T are very vulnerable to this. Bygones should loose to this too.

@dmckee - you are invoking this as $ ./foo.lsp (str) where str is something like krsskskeees without quotes, ya?

@Arrdem: Ah! the history is in capitals, and on the first round no argument is passed (because of the line Popen(p+" "+h,stdout=subprocess.PIPE,shell=True) with h = ''). The second one may be a defeatable, but I haven't figured it out yet.

@Arrdem: I fully expect to see Bygones somewhere in the lower-middle of the pack; I just want the data! :) Have you read Hofstadter's discussion of Axelrod's two IPD tourneys? It's funny, I was just looking at it last week. There's a special mention of JOSS, which rats with a small random probability -- it lost to T4T. T4T won both of Axelrod's tourneys, in fact. Not that it always will, of course; T42T apparently would have won the first had it been entered (according to "subjunctive replay"), but was actually 24th in the second. The score matrix is different here, for one of many things.

@josh - nope. high school senior hear, all I've read is the mythical man-month and a sh*t load of programming/unix books. Thanks for the pointer! I'm surprised that the T4T series did so well, but I guess we'll see.

The essay is: "The Prisoner's Dilemma Computer Tournaments and the Evolution of Cooperation" by Douglas Hofstadter (cool guy!); it was originally from his Scientific American column "Metamagical Themas" and is reprinted in his book of the same name. The whole book is a good read. BTW, nice analysis of the tournament; I didn't mention that before.

I've got the tourney loaded up on my linux box and I'm running all the contenders.... I'm interested to see that with one instance of each contender, T4T is currently coming in fourth behind (from 3rd up) lisper, handshake (WTF?) and convergence. your bygones is actually 5th.

I've been running them as they come in. Convergence is not always that good. There is a surprising amount of variation from round to round (from the players the include randomness). If you're interested you can use the multiple tournaments feature @casey provided to examine it. Very interesting.

@dmckee yea, I am experiencing lots of variation too. It is interesting to see how the results are changing as the population changes. Before lisper and handshake, Pavlov seemed to do pretty well, but now he's down in 7th. What gets me is random seems to be doing extraordinarily well!

@dmckee: One interesting thing to try if you have the inclination is changing the population; e.g., three Devils, half a dozen Random, and one of everything else. It could be hard to vary that in such a way as to be able to extract useful information, however.

@Casey: @dmckee: Have you noticed that Handshake has a bug? It doesn't recognize itself. I left a comment about it.

@josh yeah. I saw that too...... fail.

Well... there's no reason it can't be fixed. All it takes is changing the TAGMATCH. I've got it running fixed here, and it works.

@josh - but how well? I just made some changes to lisper, and it's now taking 1st consistently. will post changes.

Yes, this is quite a robust strategy. Well done!

@josh - thanks! I tried a bunch of more "evil" variants which featured random backstabbing, and I was interested to find that this strategy which is really just a more intelligent T4T does better by playing nice... Maybe Axelrod had something right after all.

If you haven't looked at the Wikipedia page for the Prisoner's Dilemma, you should -- it describes Axelrod's analysis of characteristics of a successful strategy: Nice, Retaliating, Forgiving, Non-envious.

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

True, but since the code's open, parasites can use that knowledge too. I'll be interested to see what Aaron comes up with as a countermeasure. I haven't had any good ideas along those lines yet.

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.

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.

Actually looks like almost 1/5 of the time?

@josh - I hadn't noticed that.... well it's the price I pay for not being that rigorous when I threw the margin bit together. I'll patch it in a minute. Oh. I've got a new version of the scoring code out, it adds some cool stuff like running tournaments with custom population contents. Also fixes the AvD DvA bug.

@rmckenzie: I've had quite a few tournaments crash on me because of it. I changed it to set *margin* to (max 0.09 calculated-value) as a stopgap. I'll incorporate your official fix now. I look forward to your upgraded scoring script! You should know, though, that the mistake was on my end regarding the AvD DvA. I had munged the code when I created my ProvingGrounds version and didn't realize it. dmckee's original code correctly runs only one match for each pairing.

I saw your meta-programming efforts. How did it go, and which is the new official version?

say what? Oh. The genetic algorithm crap on the repo? I wrote generators that varied the two constants which control the random number generator, then iteratively graded each variant based on its performance against the rest of the field. Right now, there isn't an official version. I will be posting an updated lisper shortly which will include the optimal constants shortly. If that's not the meta work you are referring to, please clarify.

Seems to have got worse. I'm now seeing it around the 60th percentile.

Okay. then we have a problem... with my scorer, Lisper is in the lead fairly comfortably... debugging time

And there was much confusion.... my scorer is within 1% or less of the official scorer on all champions. At that level, the randomness in some of the champs is to blame, I can't imagine a programmatic failure which would cause such little deviation. You sure your software is good/up-to-date? (no offense....)

@rmckenzie, I think it was the latest version of your scorer. Although I'm running your lisper with the old #!/usr/bin/env clisp shebang and a .lisp extension because it wasn't working for me with the .lsp extension and precompilation.

@rmckenzie, I've downloaded the absolute latest version of your scorer and run 5 tournaments with the full 24-warrior field. Lisper scores an average of 157.5 points per match, which puts it 13th (the addition of random_sucker has shaken things up a bit). The top 4 average over 170 points per match. Is this not what you observe?

Okay. Step 1 - reverted to dabb8aca. Step 2 - empty warriors and re-add all champions by copying from this page. Step 3 - run the score code from dabb8aca as "./score.py 5 100". Step 4 - use grep -e "^lisper [0-9]\{4\}" to isolate final scores. Step 5 - calculate the average of the values spat out by grep, avg of 4022 pts/iteration, or 168 pts/match. Will analyze other bots next.

FROM THE SAME RUNS AS ABOVE - the winner was random-sucker averaging 170.7 pts/game. The worst was Angel at 83.7 pts/game. Population average: 144.7 pts/game, std. dev of 25.82 pts/game. That puts Lisper in the 86th percentile, or 4th place. dear lord.... what's going on here?

@rmckenzie, only just saw your reply. The current version of score.py is broken (NameError at line 75 because global name 'scores' is not defined). I'm leaving a 5x100 tourney running with an old version of score.py and when it done I'll zip up all the files plus the log of the tournaments and give you a link.

Thanks peter. I confess your bad-results bug is driving me nuts because I can't replicate it. I'll have the global bug fixed asap, thanks for the heads-up.

@peter - could you please include a) the scoring code you used FOR THE LOGGED 5x100, b) the version OF MY SCORING CODE used for the other results. I just want as much context as I can get in whacking this bug. Thanks!

@rmckenzie, the zip is at http://www.cheddarmonk.org/prisoners.zip . I used the same version of your scoring code as used for other results - I'll grab the latest now and run it, just in case it changes things. I've also included a copy of /proc/cpuinfo in case that helps. I wonder whether it might be a multithreading issue, but I don't know anything about thread safety in Python. FWIW I've run all my tests on a quad-core machine.

@peter - thanks for the zip. you'll love this: when I run the score.py file included in the zip unmodified I see lisper coming in fourth every match. As the only difference between the code's execution is that it runs four threads on your box and two on mine (one thread per cpu), I'm inclined to call it a parallel processing bug. @casey - sorry for the necro, but you got any ideas here?

@rmckenzie, I changed .Pool(None) to .Pool(1), which I presume means that it single-threads it. First of 5 tournaments just finished with lisper 13th...

@peter - great. just great. I did some test too... racked threads all the way up to 16 and was unable to replicate your lisper score. Ignoring lisper, how do the other champions do are their scores constant between versions? If so, then the bug is somewhere in lisper or a difference between clisp on our boxes, not a bug in the scoring code.

@rmckenzie, have you tried racking the threads down to 1? I don't see a significant difference between the quad-thread and the single-thread results. (Image to follow in a few hours)

@peter - I just tried that too, and I can confirm on that count. Idea. I'm running some rounds and will post a zip file with my code, bots and output once I'm done. What I would like you to try and do is to verify that on your box as well as mine, my scoring code squares with the "official" code. I will have a friend of mine do the same test. If you both have good results, then the bug is in clisp. I will also be re-implimenting lisper in python to see how that changes the game (it shouldn't).

The reasoning that the devil might be best is as incorrect in this contest as it is in real life. It assumes all rounds are independent, but since there are 100 rounds in a row they aren't. And non-devils will gain more points in their competitions when both mostly cooperate.

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.

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.

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.

I think I'll play it safe and leave that like it's right now ;-)

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.

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

@Peter: Yes, you're absolutely right. I wonder what I was thinking of?

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...
        KSSRSSRSS...
"""
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.

@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?

Er, that was an accident. I'll add it back.

@Casey: no problem. I'll do it. Need to add a doc string anyways.

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?

:) Seize the fools.

+1 for holding a consistent 2nd place in the current field.

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.

Peter: Eek, sorry; fixed.

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.

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.

Gradual and druid both score about 200 against Wasp; random sucker will score about 83.

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)?

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.

"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!

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.

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.

Seems to be the strongest in a tourney run of the current field.

Actually, no, Druid is now that I've fixed the bug in the scorer.

@rmckenzie, @Peter: Geez, really? I was just going for personality.

@josh - not any more.... on the new scoring code @casey's scoring code Lisper is back on top followed by shark.

@rmckenzie: Druid is (quite surprisingly to me) top in every one of the last 12 full-field tournaments I've run, using the official scoring code (in the question body), and Rand-Margin Little Lisper. Has Casey changed something about the scoring?

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.

@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).

@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

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)

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

@rmckenzie, supplied as a patch against your REPO as of 20 minutes ago.

Okay. Thanks for the code, I made the updates... however I found a bug in your source code that makes automagically building it via score.py a real bitch. If you would be so kind, can you ditch the package statement? Causes all kinds of hell with javac expecting a folder layout, and it doesn't add to the code's functionality. edit: I made this change already, I'm just updating you as it's you software.

@rmckenzie, check the edit history of this post. I already did that when I added the patch.

heh. I'm slow on the uptake, my apologies.

I haven't been paying attention to this for a few days, and haven't gotten around to running your Wasp. How is it doing in your trials? I'm quite impressed with the idea; I'd give it another +1 if I could, for being the most artificially-intelligent strategy if nothing else.

@Josh, it was winning most of my trials until Joey created Random sucker. But that's a bad matchup for both of us, and a good matchup for gradual and druid, so I'm now tending to come in 4th. I need to tweak a bit to try to handle soft_majo well too - my prologue means that that ends up being mutual destruction when fundamentally both warriors are fairly cooperative.

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
suckering, feel bad and cooperate.
"""

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' }

# Reply in kind.
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.

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?

Defeated this bugger.... randomized the threshold in Lisper.

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

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.

@rmckenzie: Very good! I'll give it a spin.

@rmckenzie: I'm still seeing Little Schemer beat Random-Margin Little Lisper head-to-head every time (by around 100 points to 250). It's lower in the overall ranking, of course. Do you see different results?

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.

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

You may have left out the len(history)<2 clause, because that last one looks like the else part.

@Casey @dmckee Thank you for the bug fixes. "Duh" on me for return especially!

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

@Josh: I saw your Bygones entry briefly, did you delete it? It looked interested.

@Casey: yes, I realized it had many of the same troubles. It'll be back up soonish. Thanks!


text:
Fastest python code to find a set of winning words in this game
This is a word game from a set of activity cards for children.  Below the rules is code to find the best triplet using /usr/share/dict/words.  I thought it was an interesting optimization problem, and am wondering if people can find improvements.
Rules

Choose one letter from each of the sets below.
Choose a word using the letters chosen (and any others).
Score the word.

Each letter from the chosen set gets the number shown with the set (repeats included).
AEIOU count 0
All other letters are -2

Repeat steps 1-3 above (no reusing letters in step 1) twice more.
Final score is the sum of the three word scores.

Sets
(set 1 scores 1 point, set 2 scores 2 points, etc.)

LTN
RDS
GBM
CHP
FWV
YKJ
QXZ

Code:
from itertools import permutations
import numpy as np

points = {'LTN' : 1,
          'RDS' : 2,
          'GBM' : 3,
          'CHP' : 4,
          'FWV' : 5,
          'YKJ' : 6,
          'QXZ' : 7}

def tonum(word):
    word_array = np.zeros(26, dtype=np.int)
    for l in word:
        word_array[ord(l) - ord('A')] += 1
    return word_array.reshape((26, 1))

def to_score_array(letters):
    score_array = np.zeros(26, dtype=np.int) - 2
    for v in 'AEIOU':
        score_array[ord(v) - ord('A')] = 0
    for idx, l in enumerate(letters):
        score_array[ord(l) - ord('A')] = idx + 1
    return np.matrix(score_array.reshape(1, 26))

def find_best_words():
    wlist = [l.strip().upper() for l in open('/usr/share/dict/words') if l[0].lower() == l[0]]
    wlist = [l for l in wlist if len(l) > 4]
    orig = [l for l in wlist]
    for rep in 'AEIOU':
        wlist = [l.replace(rep, '') for l in wlist]
    wlist = np.hstack([tonum(w) for w in wlist])

    best = 0
    ct = 0
    bestwords = ()
    for c1 in ['LTN']:
        for c2 in permutations('RDS'):
            for c3 in permutations('GBM'):
                for c4 in permutations('CHP'):
                    for c5 in permutations('FWV'):
                        for c6 in permutations('YJK'):
                            for c7 in permutations('QZX'):
                                vals = [to_score_array(''.join(s)) for s in zip(c1, c2, c3, c4, c5, c6, c7)]
                                ct += 1
                                print ct, 6**6
                                scores1 = (vals[0] * wlist).A.flatten()
                                scores2 = (vals[1] * wlist).A.flatten()
                                scores3 = (vals[2] * wlist).A.flatten()
                                m1 = max(scores1)
                                m2 = max(scores2)
                                m3 = max(scores3)
                                if m1 + m2 + m3 > best:
                                    print orig[scores1.argmax()], orig[scores2.argmax()], orig[scores3.argmax()], m1 + m2 + m3
                                    best = m1 + m2 + m3
                                    bestwords = (orig[scores1.argmax()], orig[scores2.argmax()], orig[scores3.argmax()])
    return bestwords, best

if __name__ == '__main__':
    import timeit
    print timeit.timeit('print find_best_words()', 'from __main__ import find_best_words', number=1)

The matrix version is what I came up with after writing one in pure python (using dictionaries and scoring each word independently), and another in numpy but using indexing rather than matrix multiplication.
The next optimization would be to remove the vowels from the scoring entirely (and use a modified ord() function), but I wonder if there are even faster approaches.
EDIT: added timeit.timeit code
EDIT: I'm adding a bounty, which I'll give to whichever improvement I most like (or possibly multiple answers, but I'll have to accrue some more reputation if that's the case).

BTW, I wrote the code to give my eight-year-old three words to memorize for when he played the game against his mother.  Now I know what xylopyrography means.

This is a fun question.  I think you could make it more likely to get responses if you provide the following: (1) A link to an online word list so everyone works with the same data set.  (2) Put your solution in a single function.  (3) Run that function using the time-it module to show timings.  (4)  Make sure to put the loading of dictionary data outside of the function so that we are not testing disk speed.  People then can use the existing code as a framework for comparing their solutions.

I'll rewrite to use timeit, but for fair comparisons I'd have to use my own machine (which I'm happy to do for people posting solutions).  A word list should be available on most systems, but if not, there are several here: http://wordlist.sourceforge.net/

Fair comparisons can be had if each user times your solution and any other posted solutions against their own on their own machine.  There will be some differences cross platform, but in general this method works.

Good point.  I've added the timeit code.  For testing, I suggest trimming the word list to 100 or so entries.

Why is this python specific? There seems to be no need for it.

@Juan: It came from SO; this wasn't originally intended to be a code challenge/puzzle.

@Joey:  Exactly.  @Juan: I'm interested in any new methods for solving the problem, but more in algorithmic improvements than particular implementations.

Hm, in that case I wonder whether this is the correct site. I think SO would have been the best fit.

Feel free to flag it to be moved back...  I'm not sure why it got moved in the first place.

thouis: Because some mod (one who I have never seen here, though) thought it would fit better here than on SO. I guess it was more an outside-this-site decision. At the very least it could have been discussed :)

Using Keith's idea of precomputing the best possible score for each word, I managed to reduce the execution time to about 0.7 seconds on my computer (using a list of 75,288 words).
The trick is to go through the combinations of words to be played instead of all combinations of letters picked.  We can ignore all but a few combinations of words (203 using my word list) because they can't get a higher score than we've already found.  Nearly all of the execution time is spent precomputing word scores.
Python 2.7:
import collections
import itertools

WORDS_SOURCE = '../word lists/wordsinf.txt'

WORDS_PER_ROUND = 3
LETTER_GROUP_STRS = ['LTN', 'RDS', 'GBM', 'CHP', 'FWV', 'YKJ', 'QXZ']
LETTER_GROUPS = [list(group) for group in LETTER_GROUP_STRS]
GROUP_POINTS = [(group, i+1) for i, group in enumerate(LETTER_GROUPS)]
POINTS_IF_NOT_CHOSEN = -2

def best_word_score(word):
    """Return the best possible score for a given word."""

    word_score = 0

    # Score the letters that are in groups, chosing the best letter for each
    # group of letters.
    total_not_chosen = 0
    for group, points_if_chosen in GROUP_POINTS:
        letter_counts_sum = 0
        max_letter_count = 0
        for letter in group:
            if letter in word:
                count = word.count(letter)
                letter_counts_sum += count
                if count > max_letter_count:
                    max_letter_count = count
        if letter_counts_sum:
            word_score += points_if_chosen * max_letter_count
            total_not_chosen += letter_counts_sum - max_letter_count
    word_score += POINTS_IF_NOT_CHOSEN * total_not_chosen

    return word_score

def best_total_score(words):
    """Return the best score possible for a given list of words.

    It is fine if the number of words provided is not WORDS_PER_ROUND. Only the
    words provided are scored."""

    num_words = len(words)
    total_score = 0

    # Score the letters that are in groups, chosing the best permutation of
    # letters for each group of letters.
    total_not_chosen = 0
    for group, points_if_chosen in GROUP_POINTS:
        letter_counts = []
        # Structure:  letter_counts[word_index][letter] = count
        letter_counts_sum = 0
        for word in words:
            this_word_letter_counts = {}
            for letter in group:
                count = word.count(letter)
                this_word_letter_counts[letter] = count
                letter_counts_sum += count
            letter_counts.append(this_word_letter_counts)

        max_chosen = None
        for letters in itertools.permutations(group, num_words):
            num_chosen = 0
            for word_index, letter in enumerate(letters):
                num_chosen += letter_counts[word_index][letter]
            if num_chosen > max_chosen:
                max_chosen = num_chosen

        total_score += points_if_chosen * max_chosen
        total_not_chosen += letter_counts_sum - max_chosen
    total_score += POINTS_IF_NOT_CHOSEN * total_not_chosen

    return total_score

def get_words():
    """Return the list of valid words."""
    with open(WORDS_SOURCE, 'r') as source:
        return [line.rstrip().upper() for line in source]

def get_words_by_score():
    """Return a dictionary mapping each score to a list of words.

    The key is the best possible score for each word in the corresponding
    list."""

    words = get_words()
    words_by_score = collections.defaultdict(list)
    for word in words:
        words_by_score[best_word_score(word)].append(word)
    return words_by_score

def get_winning_words():
    """Return a list of words for an optimal play."""

    # A word's position is a tuple of its score's index and the index of the
    # word within the list of words with this score.
    #
    # word played: A word in the context of a combination of words to be played
    # word chosen: A word in the context of the list it was picked from

    words_by_score = get_words_by_score()
    num_word_scores = len(words_by_score)
    word_scores = sorted(words_by_score, reverse=True)
    words_by_position = []
    # Structure:  words_by_position[score_index][word_index] = word
    num_words_for_scores = []
    for score in word_scores:
        words = words_by_score[score]
        words_by_position.append(words)
        num_words_for_scores.append(len(words))

    # Go through the combinations of words in lexicographic order by word
    # position to find the best combination.
    best_score = None
    positions = [(0, 0)] * WORDS_PER_ROUND
    words = [words_by_position[0][0]] * WORDS_PER_ROUND
    scores_before_words = []
    for i in xrange(WORDS_PER_ROUND):
        scores_before_words.append(best_total_score(words[:i]))
    while True:
        # Keep track of the best possible combination of words so far.
        score = best_total_score(words)
        if score > best_score:
            best_score = score
            best_words = words[:]

        # Go to the next combination of words that could get a new best score.
        for word_played_index in reversed(xrange(WORDS_PER_ROUND)):
            # Go to the next valid word position.
            score_index, word_chosen_index = positions[word_played_index]
            word_chosen_index += 1
            if word_chosen_index == num_words_for_scores[score_index]:
                score_index += 1
                if score_index == num_word_scores:
                    continue
                word_chosen_index = 0

            # Check whether the new combination of words could possibly get a
            # new best score.
            num_words_changed = WORDS_PER_ROUND - word_played_index
            score_before_this_word = scores_before_words[word_played_index]
            further_points_limit = word_scores[score_index] * num_words_changed
            score_limit = score_before_this_word + further_points_limit
            if score_limit <= best_score:
                continue

            # Update to the new combination of words.
            position = score_index, word_chosen_index
            positions[word_played_index:] = [position] * num_words_changed
            word = words_by_position[score_index][word_chosen_index]
            words[word_played_index:] = [word] * num_words_changed
            for i in xrange(word_played_index+1, WORDS_PER_ROUND):
                scores_before_words[i] = best_total_score(words[:i])
            break
        else:
            # None of the remaining combinations of words can get a new best
            # score.
            break

    return best_words

def main():
    winning_words = get_winning_words()
    print winning_words
    print best_total_score(winning_words)

if __name__ == '__main__':
    main()

This returns the solution ['KNICKKNACK', 'RAZZMATAZZ', 'POLYSYLLABLES'] with a score of 95.  With the words from Keith's solution added to the word list I get the same result as him.  With thouis's "xylopyrography" added, I get ['XYLOPYROGRAPHY', 'KNICKKNACKS', 'RAZZMATAZZ'] with a score of 105.

Here's an idea - you can avoid checking lots of words by noticing that most words have awful scores.  Say you have found a pretty good scoring play that gets you 50 points.  Then any play with more than 50 points must have a word of at least ceil(51/3)=17 points.  So any word that can't possibly generate 17 points can be ignored.
Here's some code that does the above.  We compute the best possible score for each word in the dictionary, and store it in an array indexed by score.  Then we use that array to check only words that have the required minimum score.
from itertools import permutations
import time

S={'A':0,'E':0,'I':0,'O':0,'U':0,
   'L':1,'T':1,'N':1,
   'R':2,'D':2,'S':2,
   'G':3,'B':3,'M':3,
   'C':4,'H':4,'P':4,
   'F':5,'W':5,'V':5,
   'Y':6,'K':6,'J':6,
   'Q':7,'X':7,'Z':7,
   }

def best_word(min, s):
    global score_to_words
    best_score = 0
    best_word = ''
    for i in xrange(min, 100):
        for w in score_to_words[i]:
            score = (-2*len(w)+2*(w.count('A')+w.count('E')+w.count('I')+w.count('O')+w.count('U')) +
                      3*w.count(s[0])+4*w.count(s[1])+5*w.count(s[2])+6*w.count(s[3])+7*w.count(s[4])+
                      8*w.count(s[5])+9*w.count(s[6]))
            if score > best_score:
                best_score = score
                best_word = w
    return (best_score, best_word)

def load_words():
    global score_to_words
    wlist = [l.strip().upper() for l in open('/usr/share/dict/words') if l[0].lower() == l[0]]
    score_to_words = [[] for i in xrange(100)]
    for w in wlist: score_to_words[sum(S[c] for c in w)].append(w)
    for i in xrange(100):
        if score_to_words[i]: print i, len(score_to_words[i])

def find_best_words():
    load_words()
    best = 0
    bestwords = ()
    for c1 in permutations('LTN'):
        for c2 in permutations('RDS'):
            for c3 in permutations('GBM'):
            print time.ctime(),c1,c2,c3
                for c4 in permutations('CHP'):
                    for c5 in permutations('FWV'):
                        for c6 in permutations('YJK'):
                            for c7 in permutations('QZX'):
                                sets = zip(c1, c2, c3, c4, c5, c6, c7)
                                (s1, w1) = best_word((best + 3) / 3, sets[0])
                                (s2, w2) = best_word((best - s1 + 2) / 2, sets[1])
                                (s3, w3) = best_word(best - s1 - s2 + 1, sets[2])
                                score = s1 + s2 + s3
                                if score > best:
                                    best = score
                                    bestwords = (w1, w2, w3)
                                    print score, w1, w2, w3
    return bestwords, best

if __name__ == '__main__':
    import timeit
    print timeit.timeit('print find_best_words()', 'from __main__ import find_best_words', number=1)

The minimum score gets rapidly up to 100, which means we need only consider 33+ point words, which is a very small fraction of the overall total (my /usr/share/dict/words has 208662 valid words, only 1723 of which are 33+ points = 0.8%).  Runs in about half an hour on my machine and generates:
(('MAXILLOPREMAXILLARY', 'KNICKKNACKED', 'ZIGZAGWISE'), 101)

Nice.  I'll add that to the matrix solution (removing words as their score falls too low), but this is significantly better than any of the pure python solutions I had come up with.

I'm not sure I've ever seen that many nested for loops before.

Combining your idea with matrix scoring (and a tighter upper bound on best possible score) trims the time down to about 80 seconds on my machine (from around an hour).  code here

A good portion of that time is in the precomputation of best-possible-scores, which could be made a lot faster.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Self replicating Hello World program
Create a self-replicating Hello World Program. (The program has the ability to use the compiler, if you want).
For example:
void main()
{
    printf("Hello, World!");
    DuplicateFile("main.exe", "main2.exe");
}

Alternate challenge: A "quine" Hello World Program.

Whose computer do you suggest the binary be prepared for?!? And who do you suppose is going to run a batch of executable they simply downloaded from the internet?!?

@dmckee I meant to post the source code. When compiled, it should make a self replicating program.

Ah!. I think I can show you an interpreted program that meets the spec if I have time. At least on a unix system where scripts can be executable.

Do you mean a quine? Or a program that copies its file on disk?

This is neither well-specified nor a particular interesting task, imho. −1.

Bash - 43
echo $(echo Hello, World! >&2)$BASH_COMMAND

This prints "Hello, World!" on standard error, and itself on standard output.
For fun:
$ ./replicate-hello.bash
Hello, World!
echo $(echo Hello, World! >&2)$BASH_COMMAND
$ ./replicate-hello.bash | bash
Hello, World!
Hello, World!
echo $(echo Hello, World! >&2)$BASH_COMMAND
$ ./replicate-hello.bash | bash | bash
Hello, World!
Hello, World!
Hello, World!
echo $(echo Hello, World! >&2)$BASH_COMMAND
$ bash <<< $(echo ./replicate-hello.bash; \
             for ((i=0;i<100;i++)) ; do echo "| bash"; done)
Hello, World!
Hello, World!
Hello, World!
Hello, World!
... snip ...
Hello, World!
Hello, World!
Hello, World!
echo $(echo Hello, World! >&2)$BASH_COMMAND

lol nice recursion & simplicity +1

PHP, 13
Hello, world!

The only way to have a program that prints both "Hello, world!" and itself is this.
Edit: note that the question was not quite as clear when I wrote this.

Windows Batch file
@echo Hello World
@copy "%~dpnx0" "%~dpn02%~x0" >nul 2>&1

Erlang 1342 chars, 3 lines
Not sure if I've understood the question correctly here, I ended up writing a quine that writes to another file...
-module(hi).
-export([h/0]).
h()->io:fwrite("Hello World!"),P=[45,109,111,100,117,108,101,40,104,105,41,46,10,45,101,120,112,111,114,116,40,91,104,47,48,93,41,46,10,104,40,41,45,62,105,111,58,102,119,114,105,116,101,40,34,72,101,108,108,111,32,87,111,114,108,100,33,34,41,44,80,61],Q=[44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,80,41,44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,105,111,95,108,105,98,58,102,119,114,105,116,101,40,34,126,119,34,44,91,80,93,41,44,91,97,112,112,101,110,100,93,41,44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,32,34,44,81,61,34,44,91,97,112,112,101,110,100,93,41,44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,105,111,95,108,105,98,58,102,119,114,105,116,101,40,34,126,119,34,44,91,81,93,41,44,91,97,112,112,101,110,100,93,41,44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,81,44,91,97,112,112,101,110,100,93,41,46],file:write_file("hi2.erl",P),file:write_file("hi2.erl",io_lib:fwrite("~w",[P]),[append]),file:write_file("hi2.erl", ",Q=",[append]),file:write_file("hi2.erl",io_lib:fwrite("~w",[Q]),[append]),file:write_file("hi2.erl",Q,[append]).

I'm currently learning Erlang, so it was a good learning experience anyway.

Javascript, 89 bytes
I'm not quite sure if this is what you're asking, but this program has "hello world" in it and outputs itself.
//hello world
var f=function (){return "//hello world\nvar f="+f.toString()+";f();"};f();

Java (1045)
I've done this before.
import java.io.*;
import javax.tools.*;
class H1 {
  static final char Q=34;
  static final int N=1;
  public static void main(String[]a)throws Exception{
    String fn="H"+(N+1)+".java";
    BufferedWriter out=new BufferedWriter(new FileWriter(fn));
    String s="import java.io.*;import javax.tools.*;class H%d{static final char Q=34;static final int N=%d;public static void main(String[]a)throws Exception{String fn=%cH%c+(N-1)+%c.java%c;BufferedWriter out=new BufferedWriter(new FileWriter(fn));String s=%c%s%c;out.write(String.format(s,N+1,N+1,Q,Q,Q,Q,Q,s,Q,Q,Q,Q,Q));out.close();JavaCompiler c=ToolProvider.getSystemJavaCompiler();c.run(null,null,null,fn);Class.forName(%cH%c+(N+1)).getMethod(%cmain%c,a.getClass()).invoke(null,new Object[]{new String[]{}});}}";
    out.write(String.format(s,N+1,N+1,Q,Q,Q,Q,Q,s,Q,Q,Q,Q,Q));
    out.close();
    JavaCompiler c=ToolProvider.getSystemJavaCompiler();
    c.run(null,null,null,fn);
    Class.forName("H"+(N+1)).getMethod("main",a.getClass()).invoke(null,new Object[]{new String[]{}});
  }
}

It floods the directory with H*.java and H*.class files. It somehow stops by itself with a huge stack trace after 500 compilations. I don't know how to fix that problem.
Here is what a flooded desktop looks like:
https://www.dropbox.com/s/iy8ggzps7s55z4e/java2.png?dl=0
https://www.dropbox.com/s/jrauw3igjiwrpmd/java1.png?dl=0

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
April Fools Jokes
Figure out how to mess up another programmer's project by making a subtle, hard to find (but "harmless") "bug". (Double quotes FTW!)
Try to keep them short; shorter ~= subtle.

For example:
#define true false

Don't actually destroy the code directly. For example, from this:
for(size_t i = 0; i < 10; ++i)

To:
for(size_t *i = new size_t; ++i; delete i)

Or even:
for(size_t i = 0; i <= 10; ++i)

Is not OK. If a language actually allows you to change < to <= without changing that code "directly", then it's alright. (You know what I mean. Deleting all the code is just

Voting
Up vote the most original/creative/subtle solutions.
On Mother's Day (May 8, 2011), the most up voted answer will be chosen as the winner.

They did this on TheDailyWTF about a month and a half ago.

My favourite was setting String.Empty to another value :)

Subjective? http://meta.codegolf.stackexchange.com/questions/305/what-makes-winning-criteria-objective

I don’t understand why “number of votes” is considered a subjective criterion. One would have thought that most people can read the vote-counts and determine, objectively, which is highest?

Deleting all the code is just??  I don't think so :)

It's just because it's impossible to do in most languages, I think... but still a bit of a silly statement ;)

@Timwi: "Number of votes" is subjective because many people use subjective criteria to decide whether to upvote, downvote, or neither. It's not "indisputable".

#define if(x) if(random(100) > 0 && (x))

For C, I think you'd need to say random() % 100.

No... not with stdlib.h.

Haskell
module UnsafePrelude where

import Prelude hiding ((.), (+), (-), sum, map, foldl)
import qualified Prelude as P

import Unsafe.Coerce

-- disallow (f . g . h)
infix 9 .
(.) = (P..)

-- Make arithmetic a bit more exciting.
-- These actually work correctly for trivial Int and Integer cases,
-- at least in GHC 6.12.1 on x86.
(+), (-) :: (Num a) => a -> a -> a
(+) = unsafeCoerce ((P.+) :: Float -> Float -> Float)
(-) = unsafeCoerce ((P.-) :: Float -> Float -> Float)

sum :: (Num a, Num b) => [a] -> b
sum = unsafeCoerce (P.sum :: [Float] -> Float)

-- Make map a little less type-safe.
map :: (a -> b) -> [c] -> [b]
map   = unsafeCoerce P.map

-- Make foldl associate the wrong way, but still have the same type.
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f = foldr (flip f)

GolfScript
1:

Note there is a space after the colon. This assigns the value 1 to the space character. All further code that uses the space for readability will find unexpected extra ones on its stack!
Alternatively,
0:1

assigns the value 0 to the character 1.

Of course, I'm not quite sure why you'd be coding in GolfScript for any 'project' other than golf... :)

Ruby
class Fixnum
    alias add +
    def + (n)
        add n.add 1
    end
end

And now, like in 1984...
(33):0>  2 + 2 == 5
>>> true
(36):0>

I prefer this: class Fixnum; alias - +; end

@Matma Rex: That's a bit easier to notice...

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/