Diese Aufgabe ist Teil des First Periodic Premier Programming Puzzle Push und soll den neuen König-der-Hügel- 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
quelle
return (s1, L1+h1), (s2, L2+h1)
zureturn (s1, L1+h1), (s2, L2+h2)
[NotizL2+h2
stattL2+h1
am Ende] zu wechseln ? // Fehler beim Ausschneiden und Einfügen oder etwas ähnlich idiotisches. Meine Güte!Antworten:
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.
quelle
Der geheime Handschlag
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]
(.pyc
ersetzt durch,.py
sodass 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.quelle
TAG
dass man rückwärts spielt. Aber solltest duTAGMATCH
nicht KEEEKEEEKE sein?"".join({('c', 'c'):'K', ('t', 't'): 'E'}[moves] for moves in zip(TAG, TAG))
.py
Dateien nach Ihrem Code durchsuchen und den TAG extrahieren. In C mache ich das allerdings nicht ...Der kleine Lisper
Der Teufel
Beachten Sie das folgende Format (Player1, Player2)
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.
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.
Und bitte mach dein Schlimmstes zu diesem Beitrag. Ich möchte meine Abschlussarbeit darüber schreiben, wenn alles gesagt und getan ist.
Versionsgeschichte
OFFIZIELLE VERSION VON LISPER
VERSION VON LISPER ENTWICKELN
quelle
fink install clisp
:: wiederholt auf die Finger tippen ::There is no reason to EVER (under this scoring system) co-operate
ist 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.(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.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 :-)
quelle
case 1: case2: printf(...); break;
. Und gcc möchte eine explizitestring.h
Verwendungserklärungstrlen
. Auf jeden Fall habe ich es am laufen.Popen(p+" "+h,stdout=subprocess.PIPE,shell=True)
wann machth = ''
. Ich vermuteargc=1
.Anti-T42T-Rakete
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.
quelle
Konvergenz
Zunächst nett, dann willkürlich mit Blick auf die Geschichte des Gegners.
Ich habe versucht, die Gewichtung des Verlaufs zu ändern, sie jedoch nicht richtig optimiert.
quelle
Hai
Kann sich gegen die Basis gut behaupten.
quelle
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.
quelle
hist[0]
(hist[-1]
ist immer der erste Zug der Runde)?Ehre unter Dieben
Beachten Sie, dass es sich im
THIEVES_CANT
Wesentlichen 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.quelle
"Probabimatic"
Beginnt mit der Zusammenarbeit und wählt dann die Option aus, die den höchsten erwarteten Wert ergibt. Einfach.
Früher kooperierten wir, aber jetzt scheint es, dass das Defektieren tatsächlich besser funktioniert. EDIT: Oh warte, das tut es eigentlich nicht.
quelle
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.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.
Die Änderungen, die ich am Schreiber vorgenommen habe, um dies auszuführen, sind:
Vielen Dank an @rmckenzie für das Einklappen meiner Herausfordererfunktion.
quelle
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)
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.
quelle
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.
quelle
Vergangenheit
Das beste Preis-Leistungs-Verhältnis haben wir noch
bygones
nicht 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.quelle
Hilf dem Vampir
Hat ein amüsant asymmetrisches Ergebnis, wenn er gegen sich selbst antritt. Wenn nur diese Lösung im wirklichen Leben angewendet werden könnte.
quelle
Druide
Geht einigermaßen gut gegen die Basisliste.
quelle
Einfaltspinsel
Geht in Ordnung gegen die Basisliste.
quelle
Kleiner Schemer
Geht schlecht gegen das Basisset, aber ziemlich gut gegen sein Ziel. Offensichtlich nicht in Schema geschrieben.
quelle
Tit für zwei Tats
ein weiterer alter Favorit
quelle
sys.exit(0)
? Oder lass es einfach zu Ende gehen. Bearbeiten: Auch der erste Aufruf Ihres Programms erfolgt ohne Historie, die einIndexError
Wenn verursachtargv[1]
.len(history)<2
Klausel weggelassen, da die letzte wie derelse
Teil aussieht .return
besonders!