In dieser Herausforderung spielst du das Dilemma des lauten iterierten Gefangenen.

Das Gefangenendilemma ist ein Szenario in der Spieltheorie, in dem es zwei Spieler gibt, die jeweils zwei Optionen haben: Kooperation oder Defekt. Jeder Spieler macht es besser für sich, wenn er defekt ist, als wenn er kooperiert, aber beide Spieler würden das Ergebnis, bei dem beide Spieler kooperieren, dem vorziehen, bei dem beide Spieler defekt sind.

Das iterierte Gefangenendilemma ist dasselbe Spiel, außer dass Sie wiederholt gegen denselben Gegner spielen und wissen, was Ihr Gegner in der Vergangenheit gespielt hat. Ihr Ziel ist es immer, die höchste Punktzahl für sich selbst zu erzielen, unabhängig davon, wie Ihr Gegner vorgeht.

Das laute Dilemma der iterierten Gefangenen bringt ein wenig Lärm in die Kommunikation. Wenn du weißt, was dein Gegner in der Vergangenheit gespielt hat, werden Geräusche eingeführt. Sie werden auch wissen, welche Bewegungen Sie in der Vergangenheit gemacht haben. Die Geräuschrate ist während einer Runde gegen denselben Gegner konstant, aber zwischen verschiedenen Runden unterschiedlich.

Herausforderung

In dieser Herausforderung werden Sie ein Python 3-Programm schreiben, um das Dilemma eines lauten iterierten Gefangenen zu spielen.

Ihr Programm erhält drei Eingaben:

• Deine eigenen Züge, ohne zufällige Flips.

• Die Züge deines Gegners mit zufälligen Flips.

• Eine Statusvariable, die in jeder Runde als leere Liste beginnt und die Sie bei Bedarf ändern können. Sie können dies ignorieren, wenn Sie es nicht verwenden möchten.

Ihr Programm sollte ausgegeben werden, 'c'um zusammenzuarbeiten oder 'd'zu defekten.

Hier ist zum Beispiel ein Programm, das kooperiert, wenn der Gegner in der Vergangenheit mindestens 60% der Zeit kooperiert hat, nachdem zufällige Flips angewendet wurden, und für die ersten 10 Flips:

def threshold(my_plays, their_flipped_plays, state):
    if len(their_flipped_plays) < 10:
        return 'c'
    opp_c_freq = their_flipped_plays.count('c')/len(their_flipped_plays)
    if opp_c_freq > 0.6:
        return 'c'
    else:
        return 'd'

Wenn Sie Python nicht kennen, schreiben Sie Ihren Beitrag in Pseudocode, und jemand (ich oder ein anderes Mitglied der Site) kann das entsprechende Python-Programm erstellen.

Gameplay

Der Turnierläufer ist hier zu finden: noisy-game . Laufen noisy-game.py, um das Turnier zu starten. Ich werde dieses Repository mit neuen Einreichungen auf dem Laufenden halten. Beispielprogramme finden Sie in basic.py.

Die Gesamtpunktzahl eines Programms ergibt sich aus der Gesamtpunktzahl von über 100 Spielen des Spiels.

Ein Spiel besteht aus Round-Robin-Matches jedes Spielers gegen jeden Spieler, einschließlich sich selbst. Ein Matchup besteht aus 100 Runden. Eine Runde besteht aus 300 Zügen, bei denen jeweils 'c'oder ausgegeben werden 'd'.

Ihre Einsendung wird gegen jede Einsendung, einschließlich Ihrer eigenen, ein Matchup spielen. Jedes Matchup besteht aus 100 Runden. Während jeder Runde wird eine Schlagwahrscheinlichkeit einheitlich zufällig aus gewählt [0, 0.5].

Jede Runde besteht aus 300 Zügen. Bei jedem Zug erhalten beide Programme alle vorherigen Spiele, die sie versucht haben, und alle vorherigen Spiele, die das andere Programm nach dem Anwenden von Flips gemacht hat, sowie eine Statusvariable, eine veränderbare Liste, die das Programm ändern kann, wenn es möchte. Die Programme geben ihre Züge aus.

Züge werden wie folgt gewertet: Wenn ein Programm a spielt 'c', erhält das gegnerische Programm 2 Punkte. Wenn ein Programm einen 'd'abspielt, erhält dieses Programm 1 Punkt.

Dann wird jeder Zug unabhängig mit einer Wahrscheinlichkeit gespiegelt, die gleich der Spiegelwahrscheinlichkeit ist, und zum Zeigen für den Gegner gespeichert.

Nachdem alle Runden gespielt wurden, addieren wir die Anzahl der Punkte, die jeder Spieler in jedem Matchup erhalten hat. Anschließend verwenden wir das folgende Bewertungssystem, um die Punktzahl jedes Spielers für das Spiel zu berechnen. Diese Wertung wird durchgeführt, nachdem alle Matchups abgeschlossen sind.

Wertung

Wir werden die Evolutionsbewertung verwenden. Jedes Programm beginnt mit gleichem Gewicht. Anschließend werden die Gewichte für 100 Iterationen unter Verwendung der Punktsummen aus dem Spiel wie folgt aktualisiert:

Das neue Gewicht jedes Programms ist proportional zum Produkt seines vorherigen Gewichts und seiner durchschnittlichen Punktzahl, gewichtet mit den Gewichten seiner Gegner.

100 solcher Aktualisierungen werden angewendet, und die endgültigen Gewichte sind die Punktzahlen der einzelnen Programme für diesen Lauf des Spiels.

Die Gesamtpunktzahl ergibt sich aus der Summe der über 100 Durchläufe des Spiels.

Die Spieler werden alle gültige Antworten auf diese Herausforderung sein, plus sechs Basisprogramme , um uns zum Start zu bringen.

Vorbehalte

Verändern Sie die Eingänge nicht. Versuchen Sie nicht, die Ausführung eines anderen Programms zu beeinträchtigen, außer durch Zusammenarbeit oder Fehler. Machen Sie keine Opfergabe, bei der versucht wird, eine andere Aufgabe zu erkennen, und nutzen Sie diesen Gegner auf eigene Kosten. Standardlücken sind verboten.

BEARBEITEN: Einreichungen dürfen keines der Basisprogramme oder frühere Einreichungen exakt duplizieren .

Wenn Sie Fragen haben, können Sie diese gerne stellen.

Aktuelle Ergebnisse

nicht_genug: 40.6311
stealer: 37.1416
enough: 14.4443
wait_for_50: 6.947
threshold: 0.406784
buckets: 0.202875
change_of_heart: 0.0996783
exploit_threshold: 0.0670485
kickback: 0.0313357
tit_for_stat: 0.0141368
decaying_memory: 0.00907645
tit_for_whoops: 0.00211803
slider: 0.00167053
trickster: 0.000654875
sounder: 0.000427348
tit_for_tat: 9.12471e-05
stubborn_stumbler: 6.92879e-05
tit_for_time: 2.82541e-05
jedi2sith: 2.0768e-05
cooperate: 1.86291e-05
everyThree: 1.04843e-05
somewhat_naive: 4.46701e-06
just_noise: 1.41564e-06
growing_distrust: 5.32521e-08
goldfish: 4.28982e-09
vengeful: 2.74267e-09
defect: 3.71295e-10
alternate: 2.09372e-20
random_player: 6.74361e-21

Ergebnisse mit nur Antworten auf diese Frage und Basisprogrammen, die das Spiel des Gegners ignorieren:

nicht_genug: 39.3907
stealer: 33.7864
enough: 20.9032
wait_for_50: 5.60007
buckets: 0.174457
kickback: 0.0686975
change_of_heart: 0.027396
tit_for_stat: 0.024522
decaying_memory: 0.0193272
tit_for_whoops: 0.00284842
slider: 0.00153227
sounder: 0.000472289
trickster: 0.000297515
stubborn_stumbler: 3.76073e-05
cooperate: 3.46865e-05
tit_for_time: 2.42263e-05
everyThree: 2.06095e-05
jedi2sith: 1.62591e-05
somewhat_naive: 4.20785e-06
just_noise: 1.18372e-06
growing_distrust: 6.17619e-08
vengeful: 3.61213e-09
goldfish: 3.5746e-09
defect: 4.92581e-10
alternate: 6.96497e-20
random_player: 1.49879e-20

Gewinnen

Der Wettbewerb bleibt auf unbestimmte Zeit geöffnet, da neue Beiträge veröffentlicht werden. Ich erkläre jedoch einen Monat nach dem Absenden dieser Frage einen Gewinner (akzeptiere eine Antwort) auf der Grundlage der Ergebnisse.

Genug ist nicht genug

(könnte auch enough2oder genannt werden stealback)

def nicht_genug(m,t,s):
    if not s:
        s.append("c")
        return "c"
    if s[0]=="t":
        return "d"
    if m[-42:].count("d")>10 or len(t)+t.count("d")>300:
        s[0]="t"
        return "d"
    if t[-1]=="d":
        if s[0]=="d":
            s[0]="c"
            return "d"
        else:
            s[0]="d"
            return "c"
    else:
        if t[-3:].count("d")==0:
            s[0]="c"
        return "c"

Ich erfuhr, dass die ursprüngliche Meise für zwei Tattoos auf zwei aufeinanderfolgende Tattoos gewartet tit_for_whoopshat, und in der Tat scheint es, dass wir frühere einzelne Tattoos vergeben und vergessen sollten ( na ja, fast ...). Und viele Spieler haben in den letzten Runden Fehler gemacht. Ich bin immer noch lieber nett, wenn bisher alles in Ordnung war, aber die Toleranzgrenze des Bots wird immer niedriger.

Tit-For-Whoops

Inspiriert von einer Strategie von ncase.me/trust

def tit_for_whoops(m, t, s):
    if len(t) < 2:
        return 'c'
    else:
        return 'd' if all([x == 'd' for x in t[-2:]]) else 'c'

Fehler nur, wenn der andere Spieler zweimal hintereinander fehlerhaft war, um Missverständnisse zu vermeiden.

Sinneswandel

def change_of_heart(m, t, s):
    return 'c' if len(t) < 180 else 'd'

Hat eine Veränderung des Herzens auf halbem Weg durch. Macht sich überraschend gut.

Strategie-Stealer

Inspiriert von genug, change_of_heart und tit-for-whoops. Sollte etwas verzeihender sein. Ich habe versucht, die Zahlen zu optimieren, um die besten Ergebnisse zu erzielen, aber sie wollten nicht viel ändern.

def stealer(mine, theirs, state):
    if len(mine) == 0:
        state.append('c')
        return 'c'
    elif len(mine) > 250:
        return "d"
    elif state[0] == 't':
        return 'd'
    elif mine[-40:].count('d') > 10:
        state[0] = 't'
        return 'd'
    elif theirs[-1] == 'd':
        if state[0] == 'd':
            state[0] = 'c'
            return 'd'
        else:
            state[0] = 'd'
            return 'c'
    elif all([x == 'c' for x in theirs[-3:]]):
        state[0] = 'c'
        return 'c'
    else:
        return 'c'

Tit-For-Time

def tit_for_time(mine, theirs, state):
    theirs = theirs[-30:]
    no_rounds = len(theirs)
    return "c" if no_rounds < 5 or random.random() > theirs.count("d") / no_rounds else "d"

Wenn du die meiste Zeit damit verbracht hast, mich zu verletzen, werde ich dich nur zurück verletzen. Wahrscheinlich.

Wachsendes Misstrauen

import random

def growing_distrust(mine, theirs, state):
    # Start with trust.
    if len(mine) == 0:
        state.append(dict(betrayals=0, trust=True))
        return 'c'

    state_info = state[0]

    # If we're trusting and we get betrayed, trust less.
    if state_info['trust'] and theirs[-1] == 'd':
        state_info['trust'] = False
        state_info['betrayals'] += 1

    # Forgive, but don't forget.
    if random.random() < 0.5 ** state_info['betrayals']:
        state_info['trust'] = True

    return 'c' if state_info['trust'] else 'd'

Je mehr der Gegner mich verrät, desto weniger kann ich darauf vertrauen, dass es nur Lärm war.

Jedi2Sith

Beginnt alles schön und selbstlos, aber mit der Zeit nimmt der Einfluss der dunklen Seite stetig zu, bis der Punkt ohne Wiederkehr. Diesen Einfluss kann man nicht aufhalten, aber all die schlechten Dinge, die passieren, tragen einfach zur Macht der dunklen Seite bei ...

def jedi2sith(me, them, the_force):
  time=len(them)
  bad_things=them.count('d')
  dark_side=(time+bad_things)/300
  if dark_side>random.random():
    return 'd'
  else:
    return 'c'

Probieren Sie es online!

Schieberegler

def slider(m, t, s):
    z = [[2, 1], [0, 1], [2, 3], [2, 1]]
    x = 0
    for y in t:
      x = z[x][y == 'c']
    return 'c' if x < 2 else 'd'

Beginnt mit 'c' und gleitet nach und nach von 'd' weg.

Hartnäckiger Stolper

def stubborn_stumbler(m, t, s):
    if not t:
        s.append(dict(last_2=[], last_3=[]))
    if len(t) < 5:
        return 'c'
    else:
        # Records history to state depending if the last two and three
        # plays were equal
        s = s[0]
        if t[-2:].count(t[-1]) == 2:
            s['last_2'].append(t[-1])
        if t[-3:].count(t[-1]) == 3:
            s['last_3'].append(t[-1])
    c_freq = t.count('c')/len(t)
    # Checks if you've consistently defected against me
    opp_def_3 = s['last_3'].count('d') > s['last_3'].count('c')
    opp_def_2 = s['last_2'].count('d') > s['last_2'].count('c')
    # dist func from 0 to 1
    dist = lambda x: 1/(1+math.exp(-5*(x-0.5)))
    # You've wronged me too much
    if opp_def_3 and opp_def_2:
        return 'd'
    # Otherwise, if you're consistently co-operating, co-operate more
    # the less naive you are
    else:
        return 'c' if random.random() > dist(c_freq) - 0.5 else 'd'

Basierend auf Ihrer Exploit-Threshold-Strategie wurde nur bei konsistenten Spielen der Wechsel zwischen fehlerhaft und meistens kooperativ verfolgt

UPDATE: Verfolgt sowohl zwei als auch drei aufeinanderfolgende Spiele, bestraft nur unter härteren Bedingungen und fügt eine zufällige Auswahl hinzu, wenn Sie nicht sicher sind

UPDATE 2: Zustand entfernt und Verteilungsfunktion hinzugefügt

Noise Bot

def just_noise(m,t,s):
    return 'c' if random.random() > .2 else 'd'

Ich bin auf jeden Fall Bot zusammenarbeiten. Das ist nur Lärm.

Genug ist genug

def enough(m,t,s):
    if not s:
        s.append("c")
        return "c"
    if s[0]=="t":
        return "d"
    if m[-42:].count("d")>10:
        s[0]="t"
        return "d"
    if t[-1]=="d":
        if s[0]=="d":
            s[0]="c"
            return "d"
        else:
            s[0]="d"
            return "c"
    else:
        return "c"

Beginnt als Meise für zwei Tats, wobei die beiden Tats nicht aufeinander folgen müssen (im Gegensatz zu tit_for_whoops). Wenn es dzu oft spielen muss, geht es d-total.

Goldfisch-Bot

def goldfish(m,t,s):
    return 'd' if 'd' in t[-3:] else 'c'

Ein Goldfisch vergibt nie, vergisst aber schnell.

Trickster (wieder eingestellt)

Es werden nur die letzten 10 Spiele berücksichtigt, die jedoch in zwei Fünferblöcke unterteilt sind, deren Durchschnitt jeweils als gut oder schlecht eingestuft wird.

Wenn der Gegner im Durchschnitt "nett" spielt, spielt der Trickster immer weniger nett. Wenn die Ergebnisse nicht eindeutig sind, spielt der Betrüger nett, um den Gegner in Sicherheit zu bringen. Wenn der Gegner "schlecht" zu spielen scheint, revanchiert sich der Trickster.

Die Idee ist, ab und zu Punkte von naiven Spielern zu sammeln und frühzeitig betrügerische Spieler zu fangen.

import random
def trickster(player,opponent,state):
    pBad = 0.75
    pNice = 0.8
    pReallyBad =0.1
    decay = 0.98
    r = random.random()

    if len(player)<20: #start off nice
        return 'c' 
    else: #now the trickery begins
        last5 = opponent[-5:].count('c')/5.0 > 0.5
        last5old = opponent[-10:-5].count('c')/5.0  > 0.5
        if last5 and last5old: #she is naive, punish her
            pBad = pBad*decay #Increase punishment
            if r<pBad:
                return 'c'
            else:
                return 'd'
        elif last5 ^ last5old: #she is changing her mind, be nice!
            if r<pNice:
                return 'c'
            else:
                return 'd'
        else: #she's ratting you out, retaliate
            pReallyBad = pReallyBad*decay #Retaliate harder
            if r<pReallyBad:
                return 'c'
            else:
                return 'd'

Haftungsausschluss: Ich habe noch nie hier gepostet. Wenn ich etwas falsch mache, sage es mir bitte und ich werde es korrigieren.

Verfallendes Gedächtnis

def decaying_memory(me, them, state):
    m = 0.95
    lt = len(them)

    if not lt:
        state.append(0.0)
        return 'c'

    # If it's the last round, there is no reason not to defect
    if lt >= 299: return 'd'

    state[0] = state[0] * m + (1.0 if them[-1] == 'c' else -1.0)

    # Use a gaussian distribution to reduce variance when opponent is more consistent
    return 'c' if lt < 5 or random.gauss(0, 0.4) < state[0] / ((1-m**lt)/(1-m)) else 'd'

Wiegt die jüngste Geschichte mehr. Vergisst langsam die Vergangenheit.

Rückschlag

def kickback(m, t, s):
  if len(m) < 10:
    return "c"
  td = t.count("d")
  md = m.count("d")
  f = td/(len(t)+1)
  if f < 0.3:
    return "d" if td > md and random.random() < 0.1 else "c"
  return "c" if random.random() > f+2*f*f else "d"

Einige vage Ideen ...

Bekommt nicht wirklich die ganze "Noise" Sache

def vengeful(m,t,s):
    return 'd' if 'd' in t else 'c'

Vergibt niemals einen Verräter.

Schallgeber:

edit: Vergeltung in wahrscheinlich geräuscharmen Szenarien hinzugefügt

Im Grunde genommen bedeutet dies, dass wir weniger Lärm als gewöhnlich erwarten sollten, wenn alle 4 ersten Züge zusammenarbeiten. hin und wieder ein bisschen defekt, um die weniger Punkte auszugleichen, die wir durch nie defektes Material bekommen würden, und um es auf Lärm zurückführen zu können. wir rächen uns auch, wenn sie gegen uns defekt sind

Wenn unser Gegner in diesen Spielzügen (2 oder mehr) viele Defekte ausführt, gehen wir einfach auf sie zurück. Wenn es nur Lärm wäre, würde der Lärm unsere Bewegungen sowieso beeinträchtigen.

andernfalls, wenn nur 1 Zug fehlerhaft war, machen wir für den Rest des Spiels nur eine einfache Meise.

def sounder(my, their, state):
    if len(my)<4:
        if their.count("d")>1:
            return "d"
        return "c"
    elif len(my) == 4:
        if all(i == "c" for i in their):
            state.append(0)
            return "d"
        elif their.count("c") == 3:
            state.append(1)
            return "c"
        else:
            state.append(2)
    if state[0] == 2:
        return "d"
    if state[0] == 0:
        if not "d" in my[-4:]:
            return "d"
        return their[-1]
    else:
        return their[-1]

Wechseln

def alternate(m, t, s):
    if(len(m)==0):
        return 'c' if random.random()>.5 else 'd'
    elif(len(m)>290):
        return 'd'
    else:
        return 'd' if m[-1]=='c' else 'c'

Picks zufällig in der ersten Runde, dann wechselt. Immer Mängel in den letzten 10 Runden.

Warte auf 50

def wait_for_50(m, t, s):
  return 'c' if t.count('d') < 50 else 'd'

Nach 50 Fehlern, lass es sie haben!

Irgendwie naiv

def somewhat_naive(m, t, s):
    p_flip = 0.25
    n = 10
    if len(t) < n:
        return 'c' if random.random() > p_flip else 'd'
    d_freq = t[-n:].count('d')/n
    return 'c' if d_freq < p_flip else 'd'

Ich gehe einfach davon aus, dass wenn Sie in den letzten n Runden weniger als die Flip-Wahrscheinlichkeit (ungefähr) verloren haben , es ein Rauschen war und nicht, dass Sie gemein sind!

Habe nicht herausgefunden, was das beste n ist , könnte das genauer untersuchen.

Alle drei

def everyThree(me,him,s):
    if len(me) % 3 == 2:
        return "d"
    if len(me) > 250:
        return "d"
    if him[-5:].count("d")>3:
        return "d"
    else:
        return "c"

Defekte alle drei Umdrehungen unabhängig. Defekte auch die letzten 50 Umdrehungen. Auch defekt, wenn sein Gegner 4 von 5 der letzten Runden defekt ist.

Eimer

def buckets(m, t, s):
    if len(m) <= 5:
        return 'c'
    if len(m) >= 250:
        return 'd'
    d_pct = t[-20:].count('d')/len(t[-20:])
    if random.random() > (2 * d_pct - 0.5):
        return 'c'
    else:
        return 'd'

Spielt sich schön anzufangen. Betrachtet die letzten 20, wenn <25% d c zurückgibt,> 75% d, d zurückgibt und dazwischen zufällig entlang einer linearen Wahrscheinlichkeitsfunktion wählt. Letzte 50, Mängel. Hatte dies zuletzt 10 aber sah viele der letzten 50 Mängel.

Lassen Sie mich hier zum ersten Mal wissen, ob etwas repariert werden muss (oder wie ich dies testen kann).

Tit-For-Stat

Mängel, wenn der Gegner mehr als die Hälfte der Zeit gescheitert ist.

def tit_for_stat(m, t, s):
  if t.count('d') * 2 > len(m):
    return 'd'
  else:
    return 'c'