1P5: Iteriertes Gefangenendilemma

35

Diese Aufgabe ist Teil des First Periodic Premier Programming Puzzle Push und soll den neuen Herausforderungstyp- Vorschlag demonstrieren .

Die Aufgabe besteht darin, ein Programm zu schreiben, um das iterierte Gefangenendilemma besser zu spielen als andere Teilnehmer.

Schau, Vinny. Wir kennen Ihren Zellengenossen - wie heißt er? Ja, McWongski, der Nippo-Irisch-Ukrainische Gangster - hat etwas vor und Sie wissen, was es ist.

Wir versuchen hier nett zu sein, Vinnie. Ich gebe dir eine Chance.

Wenn du uns sagst, was er plant, werden wir sehen, dass du einen guten Auftrag bekommst.

Und wenn Sie nicht ...

Die Regeln des Spiels

  • Der Wettbewerb besteht aus einem vollständigen Round-Robin (alle möglichen Paarungen) von jeweils zwei Teilnehmern (einschließlich Selbstspielen).
  • Zwischen jedem Paar werden 100 Runden gespielt
  • In jeder Runde wird jeder Spieler gebeten, zu entscheiden, ob er mit dem anderen Spieler zusammenarbeitet oder ihn verrät, ohne die Absichten der anderen Spieler zu kennen, aber mit einer Erinnerung an die Ergebnisse früherer Runden, die gegen diesen Gegner gespielt wurden.
  • Punkte werden für jede Runde basierend auf der kombinierten Auswahl vergeben. Wenn beide Spieler zusammenarbeiten, erhalten sie jeweils 2 Punkte. Gegenseitiger Verrat bringt jeweils 1 Punkt. Im gemischten Fall erhält der betrügerische Spieler 4 Punkte und der Mitwirkende wird mit 1 bestraft.
  • Ein "offizielles" Spiel wird nicht früher als 10 Tage nach dem Posten mit allen Einsendungen durchgeführt, die ich zur Arbeit bringen kann, und zur Auswahl des "akzeptierten" Gewinners verwendet. Ich habe eine Mac OS 10.5-Box, daher sollten POSIX-Lösungen funktionieren, aber es gibt Linux-Systeme, die dies nicht tun. Ebenso habe ich keine Unterstützung für die Win32-API. Ich bin bereit, grundlegende Anstrengungen zu unternehmen, um Dinge zu installieren, aber es gibt eine Grenze. Die Grenzen meines Systems stellen in keiner Weise die Grenzen akzeptabler Antworten dar, sondern lediglich die, die in der "offiziellen" Übereinstimmung enthalten sein werden.

Die Programmierschnittstelle

  • Einträge sollten in Form von Programmen vorliegen, die über die Befehlszeile ausgeführt werden können. Die Entscheidung muss die (einzige!) Ausgabe des Programms auf der Standardausgabe treffen. Der Verlauf der vorherigen Runden mit diesem Gegner wird als Befehlszeilenargument dargestellt.
  • Die Ausgabe ist entweder "c" (für Clam Up ) oder "t" (für Tell All ).
  • Der Verlauf ist eine einzelne Zeichenfolge, die frühere Runden darstellt, wobei die letzten Runden am frühesten in der Zeichenfolge erscheinen. Die Charaktere sind
    • "K" (für gehalten den Glauben , der gegenseitige Zusammenarbeit bedeutet)
    • "R" (für Ratte b @ st @ rd hat mich ausverkauft! )
    • "S" (für " Trottel", was bedeutet, dass Sie von einem Verrat profitiert haben)
    • "E" (für alle, die auf gegenseitigen Verrat achten)

Die Klammer

Vier Spieler werden vom Autor zur Verfügung gestellt

  • Engel - kooperiert immer
  • Teufel - redet immer
  • TitForTat - kooperiert in der ersten Runde immer so, wie er es in der letzten Runde getan hat
  • Zufällig - 50/50

zu denen ich alle Einträge hinzufüge, die ich ausführen kann.

Die Gesamtpunktzahl ist die Gesamtpunktzahl gegenüber allen Gegnern (einschließlich einmaliger Selbstspiele und Verwendung der Durchschnittspunktzahl).

Teilnehmer

(Stand: 2. Mai 2011, 7:00 Uhr)

Der geheime Händedruck | Anti-T42T-Rakete | Misstrauen (Variante) | Anti-Handshake | Der kleine Lisper | Konvergenz | Hai | Probabimatic | Pawlow - Win Stay, Lose Switch | Ehre unter Dieben | Hilf Vampire | Druide | Kleiner Schemer | Vergangenheit | Meise für zwei Tats | Simpleton |

Torschütze

#! /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
  • Beschwerden über meine schreckliche Python sind willkommen, da ich mir sicher bin, dass dies in mehrfacher Hinsicht scheiße ist
  • Bugfixes willkommen

Torschützenkönig:

  • Drucke sortierte Spieler und Punktzahlen aus und erkläre einen Gewinner (4/29, Casey)
  • Optional können Sie mehrere Turniere ausführen ( ./score warriors/ num_tournaments)Standard = 1), Python-Quellen erkennen und kompilieren (4/29, Casey)
  • Behebung eines besonders dummen Fehlers, bei dem dem zweiten Spieler ein falscher Verlauf übergeben wurde. (4/30, dmckee; danke Josh)

Anfängliche Krieger

Beispielhaft und damit die Ergebnisse verifiziert werden können

Engel

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

oder

#!/bin/sh
echo c

oder

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

Teufel

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

Zufällig

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

Beachten Sie, dass der Schreiber den Krieger möglicherweise innerhalb einer Sekunde mehrmals erneut aufrufen kann. Daher müssen ernsthafte Anstrengungen unternommen werden, um die Zufälligkeit der Ergebnisse zu gewährleisten, wenn Zeit für die Aussaat des PRNG verwendet wird.

Wie du mir so ich dir

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

Der erste, der tatsächlich etwas mit der Geschichte macht.

Läuft der Torschütze nur auf die zur Verfügung gestellten Kriegererträge

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)

Dieser Teufel, er ist ein Handwerker, und nette Leute kommen anscheinend als Letzte rein.

Ergebnisse

des "offiziellen" Laufs

('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
dmckee
quelle
2
Wenn mein Zellengenosse Nippo-Irisch-Ukrainisch ist, warum sieht sein Name dann Hiberno-Chinesisch-Russisch aus?
Peter Taylor
2
@ Peter: LOL. Die Wahrheit? Nun, (1) die Abstammungen sind nicht klar, aber ich komme wahrscheinlich durch meine Mikrophonie über die Scotch-Irish; (2) Nachdem ich "Nippo" geschrieben hatte, probierte ich verschiedene Teile der Namen meiner Freunde aus dem Land der aufgehenden Sonne aus und mochte die Art und Weise, wie sie gescannt wurden, nicht. Also ging ich voran und verwendete einen chinesischen Nachnamen, der klang stattdessen gut, und (3) ich würde den Unterschied nicht kennen, wenn sie mich abwechselnd mit Reifen schlugen. Was unter den gegebenen Umständen wahrscheinlich erscheint.
DMCKEE
1
@Josh: Wäre es einfach, return (s1, L1+h1), (s2, L2+h1)zu return (s1, L1+h1), (s2, L2+h2)[Notiz L2+h2statt L2+h1am Ende] zu wechseln ? // Fehler beim Ausschneiden und Einfügen oder etwas ähnlich idiotisches. Meine Güte!
dmckee
2
Ich habe einige Zeit mit dem Testskript verbracht und freue mich, hier ein Update ankündigen zu können . Dieses Update fügt dem Testskript eine einfache Shell hinzu, die es dem Benutzer ermöglicht, diesen Bot gegen diesen Bot manuell auszuführen, Turniere mit eingeschränkten Feldern und einige andere coole Dinge auszuführen. Zögern Sie nicht, Vorschläge zu machen! Oh. Und ich schulde @josh für die Bot-gegen-Bot-Idee. Es ist wirklich nur eine schickere Implementierung seines "Trainer" -Skripts.
Ankunft
2
Interessant: Es gab 23 Wettbewerbsteilnehmer, von denen jeder 22 Runden bestritt. Wenn jeder "Angel" gespielt hätte, wäre jede Punktzahl 4400 gewesen, aber selbst die beste Punktzahl von 4167 passte nicht dazu. Wenn wir nur in einer perfekten Welt leben würden ... :)
Briguy37

Antworten:

11

Allmählich

Diese Strategie basiert auf einem Artikel von Beaufils, Delahaye und Mathieu . Mein C ist wirklich nicht das Beste. Wenn also jemand Vorschläge zur Verbesserung / Beschleunigung des Codes hat, lass es mich wissen!

[Bearbeiten] Bemerkenswert ist, dass Gradual als Strategie konzipiert wurde, die Tit für Tat übertrifft. Es hat insofern ähnliche Eigenschaften, als es bereit ist, mit einem defekten Gegner zusammenzuarbeiten und sich an ihm zu rächen. Im Gegensatz zu Tit for Tat, bei dem nur die letzte gespielte Runde gespeichert ist, merkt sich Gradual die vollständige Interaktion und zeigt an, wie oft sich der Gegner bisher geschlagen hat. Danach wird es jedoch wieder eine gegenseitige Zusammenarbeit geben.

Wie üblich hängt die Leistung der Strategie ein wenig von der Aufstellung anderer Strategien ab. Auch das Originalpapier war in einigen Details nicht wirklich klar.

#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;
}
Ventero
quelle
11

Der geheime Handschlag

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

Die Strategie besteht darin, die ersten 10 Runden für einen "geheimen" Handschlag zu opfern. Wenn ich mit mir selbst in einer Zelle bin, erkenne ich die Geschichte der ersten 10 Züge und setze für den Rest des Spiels meine Engelsmütze auf. Sobald ich erkenne, dass mein Zellengenosse nicht ich selbst ist, verwandle ich mich in einen Teufel, um übermäßig kooperative Zellengenossen auszunutzen.

Ob ich die ersten 10 Runden opfern kann, um den Teufel auszumerzen, hängt stark davon ab, wie viele Einträge es gibt. Um den Schaden so gering wie möglich zu halten, werden im Handshake nur 3 Kooperationen angezeigt.

Edit: TAGMATCH dynamic jetzt, um dumme Fehler wie das Ändern von nur einem zu vermeiden und TAG zu einem späteren Zeitpunkt dynamisieren zu können.

Bearbeiten 2: Das Tag wird nun beim ersten Durchlauf nach dem Zufallsprinzip generiert und in der durch angegebenen Datei gespeichert sys.argv[0]( .pycersetzt durch, .pysodass es zum Code, nicht zum Bytecode, zur Datei wechselt). Ich denke, dies ist die einzige Information, die alle meine Instanzen haben, die niemand sonst hat. Es scheint also die einzige Möglichkeit zu sein, Parasiten zu vermeiden.

Aaron Dufour
quelle
Aber woher weiß dein Doppelgänger, dass er sich zum Teufel machen soll?
Arrdem
1
(Ich fühle mich wie ein Papagei und sage die ganze Zeit "Tit for Tat" ...) Beachten Sie, dass T4T Ihre Strategie in einer Paarung mit T4T (kooperiert früher) und Devil (weniger Rattenergebnisse) übertrifft und mit Ihrer übereinstimmt Strategie. Natürlich zählt am Ende die Gesamtsumme, nicht die Paarungssumme. Wie Sie sagen, ist die Bevölkerung wichtig.
Josh Caswell
1
Oh nein, du bekommst ein zusätzliches S von Tit für Tat. Nett. Mir war nicht klar, TAGdass man rückwärts spielt. Aber solltest du TAGMATCHnicht KEEEKEEEKE sein? "".join({('c', 'c'):'K', ('t', 't'): 'E'}[moves] for moves in zip(TAG, TAG))
Josh Caswell
@ John Guter Punkt - Ich hatte ursprünglich ein anderes TAG und als ich es änderte, um die Zusammenarbeit zu minimieren, vergaß ich, TAGMATCH zu aktualisieren. @Arrdem Die Idee ist, dass, wenn ich gegen mich selbst spiele, das Beste für beide ist, die ganze Zeit zusammenzuarbeiten, um die Summe ihrer Punkte zu maximieren.
Aaron Dufour
1
Oh, verdammt noch mal. Also muss ich jetzt alle .pyDateien nach Ihrem Code durchsuchen und den TAG extrahieren. In C mache ich das allerdings nicht ...
Joey
6

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

Der Teufel

Beachten Sie das folgende Format (Player1, Player2)

  • (C, T) - P2 erhält VIER PUNKTE für seinen Verrat, während P1 EINEN VERLIERT
  • (T, T) - P2 UND P1 GEWINNEN 1

Unter der Annahme, dass P2 der Teufel ist, kann der Teufel niemals Punkte verlieren, und das Schlimmste, was er tun kann, ist, nur einen Punkt zu gewinnen. Gegen einen rein zufälligen Gegner wird der schlechteste Punktestand des Teufels genau (5/2) * n sein, wobei n die Anzahl der gespielten "Spiele" ist. Sein absoluter Worst-Case ist gegen sich selbst, wo sein Score n sein wird, und sein Best-Case gegen einen Engel, der 4 * n sein wird

Behaupten Sie: optimal_strat = devil

Das ist ein Turnier. Das Zurückstechen meines Zellenkameraden ist eine viel bessere Strategie als die Zusammenarbeit, da es MEINEM PUNKT mehr hilft (+4). BONUS - er wird zugeschlagen (-1)! Wenn ich ihm den Hals raushole, gewinne ich (+2) und verliere (-1). Dafür wird statistisch gesehen Backstabbing belohnt.

Aber ist es optimal?

Es gibt keinen Grund, mit EVER (im Rahmen dieses Bewertungssystems) zusammenzuarbeiten.

  • Wenn Sie den falschen Zeitpunkt gewählt haben, verlieren Sie.
  • Wenn Sie eine Ratte sind, verlieren Sie zumindest nichts.
  • Wenn Sie eine Ratte und er ist dumm, gewinnen Sie 2x mehr als wenn Sie ein guter Pall gewesen wären.

Im KOTH-System ist die Maximierung der Rendite von wesentlicher Bedeutung. Selbst wenn Sie zwei Bots haben, die perfekt synchronisiert sind und zusammenarbeiten, werden ihre individuellen Punktzahlen für ihre Sportlichkeit nur um 200 Punkte erhöht. Ein Teufel hingegen erhält mindestens 100 Punkte, im Durchschnitt 200 und maximal 400, und kostet seine Gegner jeweils bis zu 100 Punkte! Praktisch gesehen erzielt der Teufel ein durchschnittliches Spiel von 300 Punkten, das auf 500 Punkte ansteigt.

Fazit: Die Zeit wird es zeigen

Für mich sieht es so aus, als müsste die Wertung neu bewertet werden, damit der Teufel nicht den Tag übersteht. Erhöhen Sie die Kooperationspunktzahl auf 3, um dies zu erreichen. Es ist jedoch möglich, Teufel zu entdecken und sie daran zu hindern, ihre vollen 400 zu erreichen, wie Pawlow und Trotz zeigen. Kann ich beweisen, dass einer von beiden genug Punkte für die Zusammenarbeit aufgreift, um seinen Glauben zu rechtfertigen? Nein. All dies hängt vom endgültigen Teilnehmerfeld ab.

VIEL GLÜCK UND VIEL SPASS!

Und bitte mach dein Schlimmstes zu diesem Beitrag. Ich möchte meine Abschlussarbeit darüber schreiben, wenn alles gesagt und getan ist.

Versionsgeschichte

  1. Es wurde eine Randvariable hinzugefügt, die die Toleranz von Lisper für Duchebaggery zufällig ändert.
  2. Aktualisierte Lisper-to-Clam für die ersten beiden Runden, um mit kooperativen Gegnern auf dem rechten Fuß auszusteigen
  3. Verwendete einen genetischen Algorithmus, um die robustesten Werte für den Zufallsschwellenwertgenerator basierend auf ihrer maximalen kumulativen Punktzahl gegenüber einer Standardmenge von Gegnern zu finden. Gepostet Update einschließlich ihnen.

OFFIZIELLE VERSION VON LISPER

VERSION VON LISPER ENTWICKELN

arrdem
quelle
Die Wertung variiert in verschiedenen Spielvarianten. Ich habe versucht , die Anreize für die Zusammenarbeit zu erhöhen, und ich bin damit einverstanden, dass dies Auswirkungen auf die gewählten Strategien haben wird. Die gute Nachricht: Sie können sich den Torschützen schnappen, Ihre eigenen Regeln festlegen und ihn ausprobieren. Grundsätzlich könnte man sogar ein Kopfgeld anbieten.
dmckee
fink install clisp :: wiederholt auf die Finger tippen ::
dmckee
1
@josh - danke für den Link. Ich habe einige andere Wikipedia-Seiten zu diesem Dilemma gelesen, aber diesen Abschnitt habe ich verpasst. Ein Regelfehler, den ich gerade bemerkt habe, es gibt keine Regeln für Einträge, die das Dateisystem verwenden. Dies schafft das Potenzial für eine viel effizientere Zusammenarbeit im Sinne des Handshakes.
arrdem
3
There is no reason to EVER (under this scoring system) co-operateist nur zur Hälfte richtig. Wenn du weißt, dass dein Gegner die Geschichte nicht berücksichtigt (Engel, Teufel, Zufall), solltest du immer einen Fehler machen. Wenn Ihr Gegner den Verlauf berücksichtigt und Sie synchronisieren können, können Sie es besser machen. Ich habe ein paar Ideen, bei denen es darum geht, festzustellen, ob der Gegner rational oder superrational ist.
Peter Taylor
1
Erhalten Sie mit der neuesten Version nicht zu einem Drittel der Zeit Fehler durch Nullteilung? Wann immer (random 20)2, 5 oder 8 ergibt, (/ (+1 rand-num) 10)ist 0,3, 0,6, 0,9 und der Rest der Division mit 0,3 ist 0; so (floor *dbag* *margin*)stirbt.
Josh Caswell
5

Misstrauen (Variante)

Dieser kam vor Jahren als erster in meinen eigenen Tests heraus (damals war ich in der 11. Klasse und habe eine winzige Diplomarbeit zu genau diesem Thema angefertigt, wobei ich Strategien verwendete, die auch von anderen Studenten entwickelt wurden). Es beginnt mit der Sequenz tcc(und spielt danach wie Tit für Tat).

Entschuldigung für den schrecklichen Code; Wenn jemand das kürzer machen kann, während er nicht gerade Golf spielt, wäre ich dankbar :-)

#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;
}
Joey
quelle
Keine Notwendigkeit für doppelten Code auf Länge 1 und 2. Verwenden Sie fallen durch: case 1: case2: printf(...); break;. Und gcc möchte eine explizite string.hVerwendungserklärung strlen. Auf jeden Fall habe ich es am laufen.
DMCKEE
Ah, das stimmt. Ich war mir nicht sicher, wie ich die allererste Runde erkennen sollte, ob es ein leeres erstes Argument (Geschichte) gibt oder nur keines.
Joey
Ich bin mir nicht sicher. Es ist das, was Python mit Popen(p+" "+h,stdout=subprocess.PIPE,shell=True)wann macht h = ''. Ich vermute argc=1.
DMCKEE
1
Diese anfängliche Sequenz ist eine gute Idee und zielt genau auf Tit ab, um Tats Schwäche zu finden. Du bekommst einen winzigen Vorsprung und spielst danach seinen Weg.
Josh Caswell
1
@Josh, wo ist die winzige Spur? Gegen T4T beginnt dies mit SRK und setzt sich dann mit K fort. Aber SR ist jedem Spieler 3 Punkte wert.
Peter Taylor
5

Anti-T42T-Rakete

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

Geht einigermaßen gut mit der Basisgruppe der Krieger um: Tötet Angel, der von Devil leicht geschlagen wurde (aber seine Punktzahl niedrig hält), schlägt RAND im Allgemeinen handlich und schlägt Tit für Tat nur knapp. Tut schlecht, wenn man gegen sich selbst spielt.

Josh Caswell
quelle
Ich habe eine Bearbeitung eingereicht, mit der diese tatsächlich funktioniert :) Sie muss genehmigt werden.
Casey
@Casey: Guter Herr, ich mache so viele dumme Fehler in meiner Begeisterung für dieses Problem! Danke, aber warum hast du den Sh-Bang beseitigt?
Josh Caswell
Das war ein Unfall. Ich werde es wieder hinzufügen.
Casey
@Casey: kein Problem. Ich werde es tun. Müssen sowieso eine Doc-Zeichenfolge hinzufügen.
Josh Caswell
4

Konvergenz

Zunächst nett, dann willkürlich mit Blick auf die Geschichte des Gegners.

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

Ich habe versucht, die Gewichtung des Verlaufs zu ändern, sie jedoch nicht richtig optimiert.

dmckee
quelle
4

Hai

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

Kann sich gegen die Basis gut behaupten.

Josh Caswell
quelle
... die Muschel ergreifen?
Arrdem
:) Ergreife die Narren.
Josh Caswell
+1 für den gleichbleibenden 2. Platz im aktuellen Feld.
Ankunft
3

Pavlov - Gewinnen Sie Aufenthalt, verlieren Sie Schalter

In der ersten Runde kooperiert es, und dann kooperiert es genau dann, wenn beide Spieler im vorherigen Zug die gleiche Wahl getroffen haben.

#!/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'
Casey
quelle
Sollte das nicht genutzt werden hist[0]( hist[-1]ist immer der erste Zug der Runde)?
Josh Caswell
Oh wow, du hast recht. Ich nahm an, dass die Eingabezeichenfolge die letzten Runden am Ende der Zeichenfolge und nicht am Anfang hatte. Fest.
Casey
3

Ehre unter Dieben

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

Beachten Sie, dass es sich im THIEVES_CANTWesentlichen um einen Handschlag handelt, der jedoch nur beim Spiel gegen einen Mitspieler auftritt. Es vermeidet jedoch das Parasitenproblem, indem es auf spätere Kreuze überprüft. Kann sich gegen die Basis gut behaupten.

Josh Caswell
quelle
+1 für den ersten Strat, der Lisper zuverlässig auslöst. Durchschnittliche Gewinnspanne - 300 Punkte.
Arrdem
Scheint der Stärkste in einem Turnierlauf des aktuellen Feldes zu sein.
Peter Taylor
Eigentlich nein, Druide ist jetzt, wo ich den Fehler im Torschützen behoben habe.
Peter Taylor
@rmckenzie, @Peter: Meine Güte, wirklich? Ich wollte nur Persönlichkeit.
Josh Caswell
@josh - nicht mehr .... auf dem neuen Scoring-Code @ Caseys Scoring-Code Lisper ist wieder an der Spitze, gefolgt von Shark.
Arrdem
3

"Probabimatic"

Beginnt mit der Zusammenarbeit und wählt dann die Option aus, die den höchsten erwarteten Wert ergibt. Einfach.

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

Früher kooperierten wir, aber jetzt scheint es, dass das Defektieren tatsächlich besser funktioniert. EDIT: Oh warte, das tut es eigentlich nicht.

Lowjacker
quelle
1
Noch ein Statistiker! Mal sehen, wie sich das gegen die anderen Rechner verhält !
Josh Caswell
Übrigens, wenn Sie zu wechseln for (char c = *str;, char c; for (c = *str;wird gcc dies kompilieren, ohne sich zu beschweren, dass es in den C99-Modus versetzt werden muss.
Peter Taylor
3

Hyperrationale Wespe

In Java implementiert, weil ich nicht sicher war, wie komplex die Datenstrukturen werden. Wenn dies ein Problem für jemanden ist, dann denke ich, dass ich es portieren kann, um ohne zu viele Probleme zu schlagen, weil es am Ende nur wirklich einfache assoziative Arrays verwendet.

Hinweis : Ich habe dies aus einem Paket entfernt, das der neuesten Version meines Patches für den Scorer entspricht, um mit Java umgehen zu können. Wenn Sie eine Java-Lösung veröffentlichen möchten, die innere Klassen verwendet, müssen Sie den Patch patchen.

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

}

Die Änderungen, die ich am Schreiber vorgenommen habe, um dies auszuführen, sind:

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

Vielen Dank an @rmckenzie für das Einklappen meiner Herausfordererfunktion.

Peter Taylor
quelle
Nur eine Frage des Stils ... sollte die .java-Datei als "Quelle" betrachtet und in das ./src-Verzeichnis verschoben und die letzte .class im ./warriors-Ordner mit demselben Index abgelegt werden, der für .c-Dateien verwendet wird, oder wird java interpretiert und als solches bleiben .java und .class zusammen? Schöne Änderungen am Torschützen auf jeden Fall ... werden sie in der Repo-Statistik haben.
Arrdem
@rmckenzie, guter Punkt: ja, technisch ist es kompiliert. Der Grund, warum ich die Quelldatei im Kriegerverzeichnis hatte, ist, dass die Python-Dateien auch dort sind - und sie sind kompiliert. Wenn Sie möchten, kann ich überprüfen, welche Änderungen erforderlich sind, um es von ./src nach ./warriors zu kompilieren. Es sind jedoch einige Compiler-Argumente erforderlich, da Java standardmäßig davon ausgeht, dass die Verzeichnisstruktur das Paket (Namespace) widerspiegelt.
Peter Taylor
@ Peter, ich habe mich nur gefragt ... die Krieger sind in ./warriors zu finden, weil sie * nix 777 sind oder auf andere Weise ausführbar sind. Die Python- und Lisp-Skripte werden NUR für die Leistung kompiliert, können jedoch in ihrem natürlichen (Quell-) Zustand ausgeführt werden. ZU MEINEM WISSEN ALS NICHT-JAVA-PERSON haben .java-Dateien diese Berechtigungen nicht und werden daher nicht angezeigt. Dafür gibt es den Hack ... weil das Kompilieren ein separater Schritt ist. Also ja. Ich würde es sehr begrüßen, wenn Sie diese Änderung vornehmen würden. REPO LINK
arrdem
Mit Ihrem Code und einer chmod 777'd-Wespe warf die JVM diese Schönheit. 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)
Arrdem
@rmckenzie, das ist komisch. Wie auch immer, ich denke, ich werde in Kürze einen Patch für dich haben. Ich musste den Ladecode hacken, da Klassendateien nicht ausführbar sind. Und wenn andere Java-Einträge innere Klassen verwenden, wird es kaputt gehen.
Peter Taylor
3

Soft_majo

Na ja, eine andere der Standardstrategien, nur um die Aufstellung zu vervollständigen.

Dieser wählt den Zug aus, den der Gegner am meisten gemacht hat. wenn es gleich ist, kooperiert es.

#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');
    }
}
Joey
quelle
Ihr Code ist soft_majo, aber Ihre Beschreibung ist hard_majo.
Peter Taylor
Peter: Eek, sorry; Fest.
Joey
3

Zufälliger Trottel

Dieser wird defekt sein, wenn der Gegner zu oft defekt ist (Schwelle), aber gelegentlich willkürlich versuchen, zurückzustechen.

Ziemlich gut gegen alle außer den Java- und Lisp-Playern (die ich nicht ausführen kann, da weder Java noch Lisp auf der Testmaschine vorhanden sind). zumindest die meiste Zeit.

#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;
}
Joey
quelle
Gegen HyperrationalWasp wird es im Allgemeinen ungefähr so ​​sein wie gegen den Teufel. Es fängt einfach an, die ganze Zeit zusammenzuarbeiten, also gehe ich davon aus, dass es der Engel ist und greife an. Wenn es dann die Schwelle erreicht, wechselt man in den Teufelsmodus und ich wechsle in den t4t. Wenn es in den ersten 6 Zügen zufällig zurücksticht, wechsle ich zu t4t, bevor Sie zu Devil wechseln, aber die Chancen dafür sind nicht hoch.
Peter Taylor
1
Peter: Nun, ich teste die Strategien selten direkt gegeneinander, da das gesamte Feld einen erheblichen Einfluss auf die Strategieperformance hat. Momentan kämpft es meistens mit Allmählichen und Druiden um den ersten Platz in meinen Tests.
Joey
Allmählich und Druide erzielen beide ungefähr 200 Punkte gegen Wespe; Zufälliger Trottel erzielt ungefähr 83 Punkte.
Peter Taylor
2

Vergangenheit

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

Das beste Preis-Leistungs-Verhältnis haben wir noch bygonesnicht herausgefunden. Ich erwarte nicht, dass dies eine gewinnbringende Strategie ist, aber ich bin an der Leistung einer Strategie interessiert, die meiner Meinung nach im wirklichen Leben "gut" ist. Eine zukünftige Überarbeitung kann auch die Überprüfung der Anzahl der gegenseitigen Defekte beinhalten.

Josh Caswell
quelle
2

Hilf dem Vampir

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

Hat ein amüsant asymmetrisches Ergebnis, wenn er gegen sich selbst antritt. Wenn nur diese Lösung im wirklichen Leben angewendet werden könnte.

Josh Caswell
quelle
2

Druide

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

Geht einigermaßen gut gegen die Basisliste.

Josh Caswell
quelle
2

Einfaltspinsel

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

Geht in Ordnung gegen die Basisliste.

Josh Caswell
quelle
2

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

Geht schlecht gegen das Basisset, aber ziemlich gut gegen sein Ziel. Offensichtlich nicht in Schema geschrieben.

Josh Caswell
quelle
Warum spüre ich eine Herausforderung?
Arrdem
Besiegt diesen Mistkerl ... hat die Schwelle in Lisper zufällig festgelegt.
Arrdem
@rmckenzie: Aber wie hat sich das auf dein Spiel gegen den Rest des Feldes ausgewirkt? Wenn genügend Kooperationspartner zusammenarbeiten, werden sich paranoide oder neidische Strategien verschlechtern. Sie haben auch noch eine feste Obergrenze, die ausgenutzt werden kann.
Josh Caswell
Wenn Sie den aktuellen Text lesen, ist er eher defensiv als neidisch. Es versucht, Gegner zu erkennen, die statistisch tückische Strategien wie diese verfolgen, und gibt erst dann das Feuer zurück. Die CC-Eröffnung ist so konzipiert, dass sie mit Dieben auf dem richtigen Fuß aussteigt, und hat den zusätzlichen Vorteil, dass die meisten kooperativen Strats davon überzeugt werden, mitzuspielen.
1.
@rmckenzie: Sehr gut! Ich werde es versuchen.
Josh Caswell
1

Tit für zwei Tats

ein weiterer alter Favorit

#!/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'
Josh Caswell
quelle
Sie können eine Rückgabe nur dann durchführen, wenn Sie sich in einer Funktion befinden. Vielleicht benutzen sys.exit(0)? Oder lass es einfach zu Ende gehen. Bearbeiten: Auch der erste Aufruf Ihres Programms erfolgt ohne Historie, die ein IndexErrorWenn verursacht argv[1].
Casey
Möglicherweise haben Sie die len(history)<2Klausel weggelassen, da die letzte wie der elseTeil aussieht .
dmckee
@Casey @dmckee Vielen Dank für die Fehlerbehebungen. "Duh" auf mich für returnbesonders!
Josh Caswell
@dmckee: Dies begann als Teil eines komplizierteren Dings, und dann wurde mir klar, dass ich Tit for Two Tats neu geschrieben hatte und mich dazu entschlossen hatte, daran teilzunehmen. Benutzerfehler beim Kopieren und Einfügen.
Josh Caswell
@Josh: Ich habe deinen Bygones-Eintrag kurz gesehen, hast du ihn gelöscht? Es sah interessiert aus.
Casey