To zadanie jest częścią First Periodic Premier Programming Puzzle Push i ma na celu demonstrację nowej propozycji typu wyzwanie króla wzgórza .

Zadanie polega na napisaniu programu, który lepiej rozwiąże dylemat więźnia niż inni uczestnicy.

Spójrz, Vinny. Znamy twojego kolegę z celi - jak on się nazywa? Tak, McWongski, Nippo-irlandzko-ukraiński gangster - coś knuje i wiesz, co to jest.

Próbujemy być tutaj mili, Vinnie. Daje ci szansę.

Jeśli powiesz nam, co planuje, zobaczymy, że dostałeś dobre zadanie.

A jeśli nie ...

Zasady gry

• Konkurs składa się z pełnego rundy (wszystkie możliwe parowania) dwóch zawodników jednocześnie (w tym gry własnej).
• Rozgrywa się 100 rund między każdą parą
• W każdej rundzie każdy gracz jest proszony o wybór pomiędzy współpracą z innym graczem lub zdradzeniem go, bez znajomości intencji innych graczy w tej sprawie, ale z pamięcią wyników poprzednich rund rozgrywanych z tym przeciwnikiem.
• Punkty są przyznawane za każdą rundę na podstawie połączonego wyboru. Jeśli obaj gracze współpracują, każdy otrzymuje 2 punkty. Wzajemna zdrada daje po 1 punkcie. W przypadku mieszanym zdradzający gracz otrzymuje 4 punkty, a kooperator zostaje ukarany 1.
• „Oficjalny” mecz zostanie rozegrany nie wcześniej niż 10 dni po opublikowaniu wszystkich zgłoszeń, które mogę zabrać do pracy i zostaną użyte do wybrania „zaakceptowanego” zwycięzcy. Mam system Mac OS 10.5, więc rozwiązania POSIX powinny działać, ale istnieją linuksizmy, które nie działają. Podobnie nie mam wsparcia dla interfejsu API win32. Chcę podjąć podstawowy wysiłek, aby zainstalować rzeczy, ale jest pewien limit. Granice mojego systemu w żaden sposób nie reprezentują granic akceptowalnych odpowiedzi, po prostu te, które zostaną uwzględnione w „oficjalnym” meczu.

Interfejs programisty

• Wpisy powinny mieć postać programów, które można uruchamiać z wiersza poleceń; decyzja musi być (jedynym!) wyjściem programu na standardowe wyjście. Historia poprzednich rund z tym przeciwnikiem zostanie przedstawiona jako argument wiersza poleceń.
• Wyjście to „c” (dla clam up ) lub „t” (dla Tell all ).
• Historia jest pojedynczym ciągiem znaków reprezentujących poprzednie rundy, przy czym najnowsze rundy pojawiają się najwcześniej w ciągu. Postacie są
  • „K” (dla zachowania wiary oznacza wzajemną współpracę)
  • „R” (dla szczura b @ st @ rd mnie wyprzedał! )
  • „S” (dla frajera! Co oznacza, że ​​skorzystałeś ze zdrady)
  • „E” (bo wszyscy szukają numer jeden na wzajemnej zdradzie)

Wspornik

Autor zapewni czterech graczy

• Anioł - zawsze współpracuje
• Diabeł - zawsze mówi
• TitForTat - Współpracuje w pierwszej rundzie, a następnie zawsze robi to, co zrobił w ostatniej rundzie
• Losowo - 50/50

do którego dodam wszystkie wpisy, które mogę uruchomić.

Całkowity wynik będzie sumą punktów przeciwko wszystkim przeciwnikom (w tym samobójstwom tylko raz i przy użyciu średniego wyniku).

Uczestnicy

(aktualny od 2 maja 2011 r. 7:00)

Tajny uścisk dłoni | Pocisk anty-T42T | Nieufność (wariant) | Anti-Handshake | Mały Lisper | Konwergencja | Rekin | Probabimatic | Pavlov - Win Stay, Lose Switch | Honor Wśród Złodziei | Pomóż wampirowi | Druid | Mały Schemer | Bygones | Tit for Two Tats | Simpleton |

Markier

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

• Skargi dotyczące mojego okropnego pytona są mile widziane, ponieważ jestem pewien, że jest to do bani więcej niż jeden sposób
• Mile widziane poprawki błędów

Dziennik zmian strzelców:

• Wydrukuj posortowanych graczy i wyniki oraz ogłosić zwycięzcę (4/29, Casey)
• Opcjonalnie uruchom wiele turniejów ( ./score warriors/ num_tournaments)) domyślnie = 1, wykryj i skompiluj źródła python (4/29, Casey)
• Napraw szczególnie głupi błąd, w którym drugiemu graczowi podawano nieprawidłową historię. (4/30, dmckee; dzięki Josh)

Początkowi wojownicy

Przykładowo, aby wyniki mogły zostać zweryfikowane

Anioł

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

lub

#!/bin/sh
echo c

lub

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

Diabeł

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

Losowy

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

Należy pamiętać, że sekretarz może wielokrotnie przywoływać wojownika w ciągu jednej sekundy, dlatego należy podjąć poważny wysiłek, aby zapewnić losowość wyników, jeśli czas zostanie wykorzystany do zainicjowania 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;
}

Pierwszy, który faktycznie ma coś wspólnego z historią.

Uruchamianie sekretarza tylko na podanych wojownikach daje

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)

Ten diabeł jest rzemieślnikiem, a sympatyczni faceci najwyraźniej wchodzą ostatni.

Wyniki

„oficjalnego” biegu

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

Stopniowy

Strategia ta oparta jest na dokumencie Beaufils, Delahaye i Mathieu . Moje C naprawdę nie jest najlepsze, więc jeśli ktoś ma jakieś sugestie dotyczące ulepszenia / przyspieszenia kodu, daj mi znać!

[Edytuj] Warto zauważyć, że Gradual został zaprojektowany jako strategia, która przewyższa Tit dla Tat. Ma podobne właściwości, ponieważ jest skłonny do współpracy i odwetu przeciwko wadliwemu przeciwnikowi. W przeciwieństwie do Tit for Tat, który ma tylko pamięć ostatniej rozegranej rundy, Gradual zapamięta całkowitą interakcję i zmieni liczbę przypadków, w których przeciwnik do tej pory pokonał. Później jednak znów zaoferuje wzajemną współpracę.

Jak zwykle wydajność strategii zależy nieco od składu innych strategii. Również oryginalny papier nie był tak naprawdę jasny w niektórych szczegółach.

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

Tajny uścisk dłoni

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

Strategia polega na poświęceniu pierwszych 10 rund w celu wykonania „tajnego” uścisku dłoni. Jeśli jestem w komórce, rozpoznaję historię pierwszych 10 ruchów i zakładam czapkę Anioła na resztę gry. Gdy tylko uznaję, że mój kolega z celi nie jest sobą, przekształcam się w diabła, próbując wykorzystać zbyt kooperatywnych towarzyszy.

To, czy poświęcenie pierwszych 10 rund pozwoli mi wyrównać samego Diabła, zależy w dużej mierze od liczby wpisów. Aby zminimalizować uszkodzenia, tylko 3 współpracowników pojawiają się w uścisku dłoni.

Edycja: TAGMATCH dynamiczny teraz, aby zapobiec głupim błędom, takim jak zmiana tylko jednego z nich, dzięki czemu mogę w pewnym momencie w przyszłości włączyć TAG dynamiczny.

Edycja 2: Teraz losowo generuje znacznik przy pierwszym uruchomieniu i zapisuje go w pliku określonym przez sys.argv[0]( .pyczastąpiony przez, .pywięc przechodzi do kodu, a nie kodu bajtowego, pliku). Myślę, że to jedyna informacja, którą mają wszystkie moje instancje, której nie ma nikt inny, więc wydaje się, że to jedyna opcja unikania pasożytów.

Mały 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
    )
)

Diabeł

Rozważ następujące formatowanie (Player1, Player2)

• (C, T) - P2 zyskuje CZTERY PUNKTY za swoją zdradę, a P1 LOSUJE JEDEN
• (T, T) - ZYSK P2 I P1 1

Zakładając, że P2 jest diabłem, nie ma sposobu, aby diabeł kiedykolwiek stracił punkty, w rzeczywistości najgorsze, co może zrobić, to zdobyć tylko jeden punkt. Wobec czysto losowego przeciwnika najgorszym możliwym wynikiem diabła będzie dokładnie (5/2) * n, gdzie n jest liczbą rozegranych „gier”. Jego najgorszy przypadek jest przeciwko samemu sobie, gdzie jego wynik będzie równy n, a jego najlepszy przypadek będzie przeciwko aniołowi, który będzie równy 4 * n

Twierdz: optymalny_strat = diabeł

to jest turniej. Dźgnięcie w plecy mojego kolegi z komórki jest znacznie lepszą strategią niż współpraca, ponieważ pomaga MOJEMU WYNIKU więcej (+4). BONUS - zostaje uderzony (-1)! Jeśli wystawię mu szyję, mogę zyskać (+2) i stracić (-1). Dlatego statystycznie dźgnięcie w plecy jest nagradzane.

Ale czy to jest optymalne?

Nie ma powodu, aby NIGDY (w ramach tego systemu punktacji) współpracować.

• Jeśli wybrałeś niewłaściwy czas na milczenie, przegrywasz.
• Jeśli szczurujesz, przynajmniej nic nie tracisz.
• Jeśli szczurujesz, a on jest głupi, zyskujesz 2x więcej niż gdybyś był dobrym kumplem.

W systemie KOTH maksymalizacja zwrotów jest niezbędna. Nawet jeśli masz dwa boty, które są doskonale zsynchronizowane i współpracują, wyniki ich poszczególnych osób nadal będą zwiększone tylko o 200 punktów za ich sportowe umiejętności. Z drugiej strony, diabeł zdobędzie co najmniej 100 punktów, przy średnim przypadku 200 i maksymalnie 400, i kosztuje przeciwników do 100 punktów każdy! Tak więc praktycznie diabeł naprawdę osiąga średnią liczbę gier wynoszącą 300, zwiększając do 500.

Konkluzja - czas pokaże

Dla mnie wygląda na to, że punktacja powinna zostać ponownie rozważona, aby diabeł nie wykorzystał dnia. Zwiększenie wyniku współpracy do 3 wszystko może to zrobić. Można jednak wykryć diabły i uniemożliwić im zdobycie pełnych 400 punktów, jak pokazują pavlov i złośliwość. Czy mogę udowodnić, że któryś z nich zbierze wystarczającą liczbę punktów, aby uzasadnić swoją wiarę? Nie. Wszystko to zależy od ostatecznego pola rywali.

GL, HF!

I proszę zrób najgorsze z tego postu. Chcę napisać o tym mój starszy artykuł, kiedy wszystko zostanie powiedziane i zrobione.

Historia wersji

1. Dodano zmienną marginesu, która losowo zmienia tolerancję Lispera na duchebaggery.
2. Zaktualizowano Lisper, aby milczał przez pierwsze dwie rundy, aby wysiąść na właściwej stopie z kooperatywnymi przeciwnikami
3. Wykorzystano algorytm genetyczny, aby znaleźć najsolidniejsze wartości generatora progów losowych na podstawie ich maksymalnego skumulowanego wyniku względem standardowego zestawu przeciwników. Wysłano aktualizację, w tym je.

OFICJALNA WERSJA LISPER

ROZWÓJ WERSJI LISPER

Nieufność (wariant)

Ten wyszedł pierwszy raz w moich testach lata temu (wtedy byłem w 11 klasie i napisałem drobną tezę na ten temat, stosując strategie opracowane również przez innych uczniów). Zaczyna się od sekwencjitcc (i potem gra jak Tit dla Tat.

Przepraszamy za ten okropny kod; jeśli ktoś może to skrócić, choć nie do końca gra w golfa, byłbym wdzięczny :-)

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

Pocisk anty-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'

Radzi sobie dość dobrze w stosunku do podstawowego zestawu wojowników: zabija Anioła, lekko pobitego przez Diabła (ale utrzymuje niski wynik), generalnie pokonuje RAND ręcznie, a po prostu ledwo pokonuje Tit dla Tat. Radzi sobie źle, gdy gra przeciwko sobie.

Konwergencja

Początkowo fajnie, potem gra losowo, mając oko na historię przeciwnika.

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

Próbowałem wyważyć wagę historii, ale nie odpowiednio ją zoptymalizowałem.

Rekin

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

Radzi sobie całkiem dobrze w stosunku do podstawowego składu.

Pavlov - Win Stay, Lose Switch

W pierwszej turze współpracuje, a następnie współpracuje wtedy i tylko wtedy, gdy obaj gracze wybrali ten sam wybór w poprzednim ruchu.

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

Honor wśród złodziei

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

Pamiętaj, że THIEVES_CANTjest to w zasadzie uścisk dłoni, choć pojawi się tylko podczas gry przeciwko kooperatorowi. Jednak pozwala uniknąć problemu pasożyta, sprawdzając, czy nie ma późniejszych krzyżówek. Radzi sobie całkiem dobrze w stosunku do podstawowego składu.

„Probabimatic”

Zaczyna od współpracy, a następnie wybiera dowolną opcję, która daje najwyższą oczekiwaną wartość. Prosty.

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

Kiedyś zaczynało się od współpracy, ale teraz wydaje się, że defektowanie faktycznie działa lepiej. EDYCJA: Och, czekaj, tak naprawdę nie.

Hyperrational Wasp

Zaimplementowano w Javie, ponieważ nie byłem pewien, jak skomplikowane będą struktury danych. Jeśli jest to dla kogoś problem, to myślę, że mogę go przesłać, aby uderzyć bez zbyt wielu problemów, ponieważ w końcu tak naprawdę używa tylko prostych tablic asocjacyjnych.

Uwaga : Usunąłem to z pakietu zgodnie z najnowszą wersją mojej poprawki do systemu oceniającego do obsługi Javy. Jeśli chcesz opublikować rozwiązanie Java, które korzysta z wewnętrznych klas, musisz załatać łatkę.

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());
    }

}

Zmiany, które wprowadziłem w sekrecie, aby to uruchomić, to:

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

Dzięki @rmckenzie za złożenie mojej funkcji pretendenta.

Soft_majo

Ach, kolejna standardowa strategia, tylko po to, by ukończyć skład.

Ten wybiera ruch, który przeciwnik wykonał najwięcej; jeśli równa, to współpracuje.

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

Losowy frajer

Ten zada się, jeśli przeciwnik zbyt często defekuje (próg), ale od czasu do czasu spróbuje dźgnąć w plecy.

Nieźle sobie radzi ze wszystkimi oprócz graczy Java i Lisp (których nie mogę uruchomić, ponieważ ani Java, ani Lisp nie są uruchomione na maszynie testowej); przynajmniej przez większość czasu.

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

Jak bygonesdotąd nie wypracowałem najlepszej wartości . Nie spodziewam się, że będzie to zwycięska strategia, ale interesuje mnie wykonanie strategii podobnej do tego, co uważam za „dobre” w prawdziwym życiu. Przyszła zmiana może również obejmować sprawdzenie liczby wzajemnych usterek.

Pomóż wampirowi

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

W porównaniu z sobą ma zabawnie asymetryczny wynik. Gdyby tylko to rozwiązanie można było zastosować w prawdziwym życiu.

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'

Radzi sobie dobrze w stosunku do podstawowego składu.

Prostak

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

Nie przeszkadza w stosunku do podstawowego składu.

Mały 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'

Słabo sprawdza się w stosunku do zestawu podstawowego, ale całkiem dobrze w stosunku do celu. Oczywiście nie napisane w schemacie.

Sikora na dwa taty

inny stary faworyt

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