Essa tarefa faz parte do Primeiro envio periódico de quebra-cabeça de programação Premier e tem como objetivo demonstrar a nova proposta de desafio do tipo rei da colina .

A tarefa é escrever um programa para reproduzir melhor o dilema do prisioneiro iterado do que outros participantes.

Olha Vinny. Conhecemos seu colega de cela --- como é o nome dele? Sim, McWongski, o mafioso nippo-irlandês-ucraniano - está tramando algo e você sabe o que é.

Estamos tentando ser legais aqui, Vinnie. Dando uma chance a você.

Se você nos contar o que ele está planejando, veremos uma boa tarefa de trabalho.

E se você não ...

As regras do jogo

• O concurso consiste em um round-robin completo (todos os pares possíveis) de dois competidores por vez (incluindo jogadas automáticas).
• Há 100 rodadas disputadas entre cada par
• Em cada rodada, pede-se a cada jogador que escolha entre cooperar ou traí-lo, sem conhecer as intenções dos outros jogadores, mas com uma memória dos resultados das rodadas anteriores disputadas contra esse oponente.
• Os pontos são concedidos para cada rodada com base na escolha combinada. Se ambos os jogadores cooperam, cada um ganha 2 pontos. Traição mútua rende 1 ponto cada. No caso misto, o jogador traidor recebe 4 pontos e o cooperador é penalizado por 1.
• Uma partida "oficial" será realizada no máximo 10 dias após a postagem com todos os envios que eu possa começar a trabalhar e ser usado para selecionar o vencedor "aceito". Como tenho uma caixa do Mac OS 10.5, as soluções POSIX devem funcionar, mas existem linuxismos que não. Da mesma forma, não tenho suporte para a API win32. Estou disposto a fazer um esforço básico para instalar as coisas, mas há um limite. Os limites do meu sistema não representam de forma alguma os limites das respostas aceitáveis, simplesmente aquelas que serão incluídas na partida "oficial".

A interface do programador

• As entradas devem estar na forma de programas que podem ser executados na linha de comando; a decisão deve a saída (exclusiva!) do programa na saída padrão. O histórico das rodadas anteriores com esse oponente será apresentado como um argumento na linha de comando.
• A saída é "c" (para fechar ) ou "t" (para dizer tudo ).
• O histórico é uma única sequência de caracteres que representa as rodadas anteriores, com as rodadas mais recentes ocorrendo mais cedo na sequência. Os personagens são
  • "K" (para manter a fé que significa cooperação mútua)
  • "R" (para ratos b @ st @ rd me esgotou! )
  • "S" (para otário! Significa que você se beneficiou de uma traição)
  • "E" (para todo mundo está procurando o número um na traição mútua)

O suporte

Quatro jogadores serão fornecidos pelo autor

• Anjo - sempre coopera
• Diabo - sempre fala
• TitForTat - Coopera na primeira rodada e sempre faz como ele fez na última rodada
• Aleatório - 50/50

ao qual adicionarei todas as entradas que puder executar.

A pontuação total será a soma da soma de todos os oponentes (incluindo jogadas automáticas apenas uma vez e usando a pontuação média).

Participantes

(atual em 2 de maio de 2011 às 7:00)

O aperto de mão secreto | Míssil Anti-T42T | Desconfiança (variante) | Anti-aperto de mão | O pouco lisper | convergência | tubarão | Probabimatic | Pavlov - Ganhe estadia, perca o interruptor | Honra entre ladrões | Ajude o vampiro | Druid | Pequeno planejador | bygones | Peitos para duas tatuagens | simplório |

Marcador

#! /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

• Reclamações sobre o meu horrível python são bem-vindas, pois tenho certeza de que isso é uma droga mais do que uma maneira
• Bug fixes welcome

Registro de Mudanças do Artilheiro:

• Imprima jogadores e pontuações classificadas e declare um vencedor (29/4, Casey)
• Opcionalmente, execute vários torneios ( ./score warriors/ num_tournaments)) padrão = 1, detecte e compile fontes python (4/29, Casey)
• Correção de um bug particularmente estúpido no qual o segundo jogador estava passando por um histórico incorreto. (30/4, dmckee; obrigado Josh)

Guerreiros iniciais

A título de exemplo, e para que os resultados possam ser verificados

Anjo

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

ou

#!/bin/sh
echo c

ou

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

Diabo

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

Aleatória

#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;
}

Observe que o apontador pode re-invocar o guerreiro várias vezes em um segundo; portanto, um esforço sério deve ser feito para garantir a aleatoriedade dos resultados se o tempo estiver sendo usado para propagar o 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;
}

O primeiro que realmente faz algo com a história.

Executar o apontador apenas nos guerreiros fornecidos gera

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)

Aquele diabo, ele é um profissional, e caras legais aparentemente aparecem por último.

Resultados

da corrida "oficial"

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

Gradual

Essa estratégia é baseada em um artigo de Beaufils, Delahaye e Mathieu . Meu C realmente não é o melhor, por isso, se alguém tiver alguma sugestão para melhorar / acelerar o código, me avise!

[Editar] Vale a pena notar é que o Gradual foi projetado para ser uma estratégia que supera Tit for Tat. Tem propriedades semelhantes, pois está disposto a cooperar e retaliar contra um oponente desertor. Ao contrário do Tit for Tat, que só tem memória da última rodada jogada, o Gradual lembrará a interação completa e desertará o número de vezes que o oponente desertou até agora. No entanto, oferecerá cooperação mútua mais tarde.

Como sempre, o desempenho da estratégia depende um pouco da formação de outras estratégias. Além disso, o documento original não estava muito claro em alguns detalhes.

#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;
}

O aperto de mão secreto

#!/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()

A estratégia aqui é sacrificar as 10 primeiras rodadas para realizar um aperto de mão "secreto". Se eu estiver no meu quarto, reconheço a história dos 10 primeiros movimentos e ponho meu boné de anjo pelo resto do jogo. Assim que reconheço que meu colega de cela não sou eu, me transformo em um diabo na tentativa de tirar vantagem de colegas de cela excessivamente cooperativos.

Se o sacrifício das primeiras 10 rodadas me permitirá superar o próprio diabo depende fortemente de quantas entradas existem. Para minimizar os danos, apenas três cooperações aparecem no aperto de mão.

Edit: TAGMATCH dinâmico agora para evitar erros estúpidos, como alterar apenas um deles, para que eu possa tornar o TAG dinâmico em algum momento no futuro.

Edit 2: Agora gera aleatoriamente a tag na primeira execução e a armazena no arquivo especificado por sys.argv[0]( .pycsubstituído por .pypara que ele vá para o arquivo de código, não o código de bytes). Penso que esta é a única informação que todas as minhas instâncias têm e que ninguém mais tem, por isso parece ser a única opção para evitar parasitas.

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

O diabo

Considere o seguinte formato (Player1, Player2)

• (C, T) - P2 ganha QUATRO PONTOS por sua traição, enquanto P1 PERDE UM
• (T, T) - GANHO P2 E P1 1

Supondo que P2 seja o diabo, não há como o diabo perder pontos; de fato, o pior que ele pode fazer é ganhar apenas um ponto. Portanto, contra um oponente puramente aleatório, a pior pontuação possível do diabo será exatamente (5/2) * n onde n é o número de "jogos" jogados. Seu pior caso absoluto é contra si mesmo, onde sua pontuação será n, e seu melhor caso é contra um anjo, que será 4 * n

Afirma: opt_strat = diabo

isso é um torneio. Dar um tapinha nas costas do meu companheiro de cela é uma estratégia muito melhor do que a cooperação, porque ajuda mais o MY SCORE (+4). BÔNUS - ele é atingido (-1)! Se eu esticar meu pescoço para ele, ganho (+2) e solto (-1). Portanto, estatisticamente, a punhalada é recompensada.

Mas é ideal?

Não há razão para NUNCA (sob este sistema de pontuação) cooperar.

• Se você escolheu a hora errada para se calar, você perde.
• Se você rat, pelo menos você não perde nada.
• Se você rat e ele é burro, você ganha 2x mais do que se tivesse sido um bom idiota.

No sistema KOTH, a maximização dos retornos é essencial. Mesmo que você tenha dois bots que são perfeitamente sincronizados e cooperam, as pontuações individuais ainda serão aumentadas em 200 pontos pelo espírito esportivo. Um diabo, por outro lado, ganhará pelo menos 100 pontos, com um caso médio de 200 e um máximo de 400, e custará aos seus oponentes até 100 pontos cada! Então, praticamente, o diabo realmente marca um jogo médio de 300, chegando a 500.

Bottom line - o tempo dirá

Para mim, parece que a pontuação deve ser repensada para que o diabo não tome o dia. Aumentar a pontuação da cooperação para 3, todos podem fazer isso. É possível, no entanto, detectar demônios e impedi-los de marcar todos os seus 400, como mostram pavlov e despeito. Posso provar que qualquer um deles receberá pontos suficientes para que sua cooperação justifique sua fé? não. Tudo isso depende do campo final dos candidatos.

GL, HF!

E faça o seu pior para este post. Quero escrever meu artigo sobre isso quando tudo estiver dito e feito.

Histórico de versões

1. Adicionada uma variável de margem que altera a tolerância de Lisper para duchebaggery aleatoriamente.
2. Lisper atualizado para concorrer nas duas primeiras rodadas e sair com o pé direito com oponentes cooperativos
3. Utilizou um algoritmo genético para encontrar os valores mais robustos para o gerador de limiar aleatório com base em sua pontuação cumulativa máxima contra um conjunto padrão de oponentes. Atualização postada, incluindo eles.

VERSÃO OFICIAL DO LISPER

VERSÃO DE DESENVOLVIMENTO LISPER

Desconfiança (variante)

Este saiu primeiro em meus próprios testes anos atrás (naquela época eu estava no 11º ano e fiz uma pequena tese sobre exatamente isso, usando estratégias criadas por outros alunos também). Começa com a sequência tcc(e depois toca como Tit for Tat).

Desculpas pelo código horrível; se alguém puder fazer isso mais curto sem jogar exatamente, eu ficaria grato :-)

#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;
}

Míssil Anti-T42T

#!/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'

Faz razoavelmente bem contra o conjunto básico de guerreiros: mata Angel, levemente derrotado por Devil (mas mantém sua pontuação baixa), geralmente vence RAND com facilidade e apenas vence Tit por Tat. Faz mal quando joga contra si mesmo.

Convergência

Inicialmente agradável, depois joga aleatoriamente com um olho na história do oponente.

/* 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;
}

Tentei diminuir o peso da história, mas não a otimizei adequadamente.

Tubarão

#!/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'

Faz muito bem contra a lista de base.

Pavlov - Ganhe estadia, perca o interruptor

No primeiro turno, ele coopera e, em seguida, coopera se e somente se ambos os jogadores optaram pela mesma escolha na jogada anterior.

#!/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'

Honra entre ladrões

#!/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'

Observe que THIEVES_CANTé essencialmente um aperto de mão, embora só surja quando estiver jogando contra um cooperador. No entanto, evita o problema do parasita, verificando se há cruzamentos posteriores. Faz muito bem contra a lista de base.

"Probabimatic"

Começa por cooperar e, em seguida, escolhe a opção que oferece o maior valor esperado. Simples.

#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;
}

Costumava começar a cooperar, mas agora parece que desertar realmente funciona melhor. EDIT: Oh espera, na verdade não.

Vespa hiper-racional

Implementado em Java porque não tinha certeza de quão complexas as estruturas de dados terminariam. Se isso é um problema para alguém, acho que posso portá-lo para o bash sem muitos problemas, porque no final, ele realmente usa apenas matrizes associativas simples.

Nota : removi isso de um pacote alinhado com a versão mais recente do meu patch para o apontador para manipular Java. Se você deseja publicar uma solução Java que utiliza classes internas, precisará corrigir o 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());
    }

}

As alterações que fiz no apontador para executar isso são:

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

Obrigado a @rmckenzie por desistir da minha função de desafiador.

Soft_majo

Ah, bem, outra das estratégias padrão, apenas para completar a formação.

Este escolhe o movimento que o oponente mais fez; se igual, coopera.

#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');
    }
}

Otário aleatório

Este irá desertar se o oponente desertar com muita freqüência (limite), mas tentará aleatoriamente dar uma punhalada de vez em quando.

Funciona razoavelmente bem contra todos, exceto os players Java e Lisp (que eu não consigo executar, devido a Java nem Lisp na máquina de teste); na maioria das vezes, pelo menos.

#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;
}

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'

Ainda não calculamos o melhor valor bygones. Não espero que seja uma estratégia vencedora , mas estou interessado no desempenho de uma estratégia algo como o que eu acho que é "bom" na vida real. Uma revisão futura também pode incluir a verificação do número de deserções mútuas.

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'

Tem um resultado divertidamente assimétrico quando lançado contra si mesmo. Se apenas essa solução pudesse ser aplicada na vida real.

druida

#!/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'

Faz razoavelmente bem contra a lista de base.

Simplório

#!/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'

Está bem contra a lista de base.

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'

Faz mal contra o conjunto de base, mas muito bem contra seu alvo. Obviamente, não está escrito em Scheme.

Peitos para duas tatuagens

outro velho favorito

#!/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'