W tym wyzwaniu zmierzysz się z hałaśliwym, powtarzającym się dylematem więźnia.

W dylemat więźnia jest scenariusz, w teorii gier, gdzie istnieją dwa graczy, każdy z dwóch opcji: współpracuje lub wada. Każdy gracz radzi sobie lepiej, jeśli ma wadę, niż gdyby współpracował, ale obaj gracze wolą wynik, w którym obaj gracze współpracują, niż ten, w którym obaj grają.

Dylemat iterowanego więźnia to ta sama gra, tyle że wielokrotnie grasz przeciwko temu samemu przeciwnikowi i wiesz, w co grał Twój przeciwnik w przeszłości. Twoim celem jest zawsze zdobycie jak najwyższego wyniku, niezależnie od tego, jak robi to twój przeciwnik.

Hałaśliwy iterowany dylemat więźnia wprowadza pewne zakłócenia w komunikacji. Twoja wiedza o tym, w co grał Twój przeciwnik w przeszłości, wprowadzi trochę hałasu. Dowiesz się również, jakie ruchy wykonałeś w przeszłości. Poziom hałasu jest stały w trakcie rundy przeciwko temu samemu przeciwnikowi, ale różny dla różnych rund.

Wyzwanie

W tym wyzwaniu napiszesz program w języku Python 3, który rozwiąże dylemat hałaśliwego iterowanego więźnia.

Twój program otrzyma trzy dane wejściowe:

• Twoje własne ruchy, bez losowych rzutów.

• Ruchy przeciwnika, z zastosowaniem losowych rzutów.

• Zmienna stanu, która zaczyna się jako pusta lista w każdej rundzie i którą możesz zmodyfikować, jeśli chcesz. Możesz to zignorować, jeśli nie chcesz go używać.

Twój program powinien wysyłać dane 'c'do współpracy lub 'd'do defektu.

Na przykład, oto program, który współpracuje, jeśli przeciwnik współpracował przez co najmniej 60% czasu w przeszłości, po zastosowaniu losowych rzutów i dla pierwszych 10 rzutów:

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'

Jeśli nie znasz języka Python, napisz swoje zgłoszenie w pseudokodzie, a ktoś (ja lub inny członek witryny) może utworzyć odpowiedni program w języku Python.

Rozgrywka

Turniej można znaleźć tutaj: noisy-game . Uruchom, noisy-game.pyaby uruchomić turniej. Będę aktualizować to repozytorium o nowe zgłoszenia. Przykładowe programy można znaleźć w basic.py.

Ogólny wynik programu to suma jego wyników w ponad 100 grach.

Gra składa się z pojedynczych rund każdego gracza przeciwko każdemu graczowi, w tym sobie. Pojedynek składa się ze 100 rund. Runda składa się z 300 ruchów, z których każdy wymaga wykonania 'c'lub 'd'.

Twoje zgłoszenie spowoduje rozegranie pojedynku z każdym zgłoszeniem, w tym własnym. Każdy pojedynek będzie się składał ze 100 rund. Podczas każdej rundy prawdopodobieństwo odwrócenia będzie losowo wybierane równomiernie [0, 0.5].

Każda runda będzie się składać z 300 ruchów. Przy każdym ruchu oba programy otrzymają wszystkie poprzednie odtworzenia, które próbowały, i wszystkie poprzednie odtworzenia, które wykonał drugi program, po zastosowaniu odwrotności, oraz zmienną stanu, która jest zmienną listą, którą program może modyfikować, jeśli chce. Programy wygenerują swoje ruchy.

Ruchy są punktowane w następujący sposób: Jeśli program zagra 'c', program przeciwny otrzymuje 2 punkty. Jeśli jakiś program gra 'd', ten program otrzymuje 1 punkt.

Następnie każdy ruch jest odwracany niezależnie z prawdopodobieństwem równym prawdopodobieństwu przewrócenia i zapisywany do pokazania przeciwnikowi.

Po rozegraniu wszystkich rund sumujemy liczbę punktów, jaką każdy gracz otrzymał w każdym pojedynku. Następnie wykorzystujemy następujący system punktacji do obliczenia wyniku każdego gracza w grze. Ta punktacja jest przeprowadzana po zakończeniu wszystkich pojedynków.

Punktacja

Wykorzystamy ewolucyjną punktację. Każdy program zaczyna się od równej wagi. Następnie wagi są aktualizowane w następujący sposób, dla 100 iteracji, z wykorzystaniem sum punktowych z gry:

Nowa waga każdego programu jest proporcjonalna do iloczynu jego poprzedniej wagi i jego średniej sumy punktów, ważonej wagami przeciwników.

Zastosowano 100 takich aktualizacji, a ostateczne wagi są wynikiem każdego programu dla tego przebiegu gry.

Ogólne wyniki będą sumą ponad 100 przebiegów gry.

Gracze otrzymają wszystkie prawidłowe odpowiedzi na to wyzwanie oraz sześć podstawowych programów, które pomogą nam zacząć.

Ostrzeżenia

Nie modyfikuj wejść. Nie próbuj wpływać na wykonanie jakiegokolwiek innego programu, z wyjątkiem współpracy lub uszkodzenia. Nie składaj ofiarnego poddania się, które usiłuje rozpoznać kolejne poddanie się i przynieść korzyści przeciwnikowi na własny koszt. Standardowe luki są zabronione.

EDYCJA: Zgłoszenia nie mogą dokładnie powielać żadnego z podstawowych programów ani żadnego wcześniejszego zgłoszenia.

Jeśli masz jakieś pytania, możesz je zadać.

Aktualne wyniki

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

Wyniki zawierające tylko odpowiedzi na to pytanie i podstawowe programy, które ignorują grę przeciwnika:

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

Zwycięski

Konkurs będzie otwarty przez czas nieokreślony, ponieważ publikowane będą nowe zgłoszenia. Ogłaszam jednak zwycięzcę (akceptuję odpowiedź) na podstawie wyników 1 miesiąc po opublikowaniu tego pytania.

Genug ist nicht genug

(można również nazwać enough2lub 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"

Dowiedziałem się, że oryginalne sikory na dwa taty tak samo czekały na dwa kolejne taty tit_for_whoops, i wydaje się, że powinniśmy wybaczyć i zapomnieć (no prawie ...) wcześniejsze pojedyncze taty. I wielu graczy ucieka w ostatnich rundach. Nadal wolę być miły, gdy do tej pory wszystko było w porządku, ale pasek tolerancji bota wciąż spada.

Tit-For-Whoops

Inspirowany strategią z 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'

Wady tylko wtedy, gdy drugi gracz pokonał dwa razy z rzędu, aby uniknąć nieporozumień.

Zmiana zdania

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

W międzyczasie zmienia się serce. Zaskakująco dobrze.

Stealer strategiczny

Zainspirowany wystarczającą ilością, change_of_heart i tit-for-whoops. Powinien być trochę bardziej wyrozumiały. Próbowałem podkręcić liczby, aby uzyskać najlepsze wyniki, ale nie chcieli wiele zmienić.

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"

Jeśli spędzasz większość czasu raniąc mnie, po prostu cię zranię. Prawdopodobnie.

Rosnąca nieufność

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'

Im bardziej przeciwnik mnie zdradza, tym mniej mogę ufać, że to tylko hałas.

Jedi2Sith

Zaczyna wszystko ładnie i bezinteresownie, ale z czasem wpływ ciemnej strony staje się coraz silniejszy, aż do momentu bez powrotu. Nie można powstrzymać tego wpływu, ale wszystkie złe rzeczy, które widzi, tylko przyczyniają się do potęgi ciemnej strony ...

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'

Wypróbuj online!

Suwak

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'

Zaczyna się od „c” i stopniowo przesuwa się w kierunku lub od „d”.

Uparty Stumbler

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'

Oparte na strategii progu wykorzystywania, tylko spójne gry śledzone w celu przełączania między defektami a przeważnie współpracą

AKTUALIZACJA: Śledzi zarówno dwie kolejne, jak i trzy kolejne gry, karając tylko w trudniejszych warunkach i dodając losowy wybór, gdy nie ma pewności

AKTUALIZACJA 2: Usunięto warunek i dodano funkcję dystrybucji

Hałas Bot

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

Jestem zdecydowanie współpracującym botem. To tylko hałas.

Wystarczy, wystarczy

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"

Zaczyna się jako tit dla dwóch tatów, w których dwa taty nie muszą być kolejne (w przeciwieństwie do tit_for_whoops). Jeśli gra dzbyt często, gra się dsuma.

Goldfish Bot

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

Złota rybka nigdy nie wybacza, ale szybko zapomina.

trickster (ponownie przywrócony)

Uwzględnia się tylko 10 ostatnich zagrań, ale dzieli się na dwa bloki po pięć, które są uśredniane dla każdego sklasyfikowanego jako dobry lub zły.

Jeśli przeciwnik gra średnio „fajnie”, trickster gra coraz mniej ładnie. Jeśli wyniki są niejednoznaczne, trickster gra fajnie, aby zwabić przeciwnika w bezpieczne miejsce. Jeśli wydaje się, że przeciwnik gra „źle”, trickster wykonuje odwet.

Chodzi o to, aby od czasu do czasu zbierać punkty od naiwnych graczy, jednocześnie wcześnie łapiąc podstępnych.

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'

Oświadczenie: Nigdy wcześniej nie pisałem tutaj, jeśli robię coś źle> proszę powiedz mi, a poprawię.

Rozkładająca się pamięć

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'

Więcej waży najnowszą historię. Powoli zapomina się o przeszłości.

Odrzut

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"

Niektóre niejasne pomysły ...

Naprawdę nie odbiera całej „szumowej” rzeczy

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

Nigdy nie wybacza zdrajcy.

sonda ultradźwiękowa:

edycja: dodano odwet w prawdopodobnie cichych scenariuszach

Zasadniczo, jeśli wszystkie 4 pierwsze ruchy są ze sobą zgodne, oznacza to, że powinniśmy oczekiwać mniejszego hałasu niż zwykle. co jakiś czas co nieco defektuje, aby zrekompensować sobie mniej punktów, które uzyskalibyśmy od braku defektów i aby można było za to winić hałas. my również podejmiemy działania odwetowe, jeśli będą one wady przeciwko nam

jeśli nasz przeciwnik ma dużo defektów w tych turach (2 lub więcej), po prostu odpuszczamy. gdyby był to tylko hałas, hałas i tak wpłynąłby na nasze ruchy.

w przeciwnym razie, jeśli tylko 1 ruch byłby wadliwy, wykonujemy proste sikanie dla tat przez resztę gry.

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]

Alternatywny

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'

Wybiera losowo w pierwszej rundzie, a następnie zmienia się. Zawsze defekty w ostatnich 10 rundach.

Poczekaj na 50

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

Po 50 defektach pozwól im je mieć!

Somehwat naiwny

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'

Zakładam tylko, że jeśli w ostatnich n zakrętach zmniejszyłeś prawdopodobieństwo przewrócenia (z grubsza) , był to hałas, a nie to, że jesteś podły!

Nie znalazłem najlepszego n , może przyjrzeć się temu dalej.

Co trzy

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"

Niezależnie od wad co trzy obroty. Uszkadza również ostatnie 50 tur. Wada także, jeśli jego przeciwnik pokonał 4 z 5 ostatnich rund.

Wiadra

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'

Miło jest zacząć. Patrzy na ich ostatnie 20, jeśli <25% d, zwraca c,> 75% d, zwraca d, a pomiędzy wybiera losowo wzdłuż funkcji prawdopodobieństwa liniowego. Ostatnie 50, wady. Miałem to co najmniej 10, ale widziałem wiele ostatnich 50 wad.

Po raz pierwszy tutaj, więc daj mi znać, czy coś trzeba naprawić (lub jak mogę to przetestować).

Tit-For-Stat

Wady, jeśli przeciwnik wykonał więcej niż połowę czasu.

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