В этом задании вы сыграете дилемму зашумленного итератора.

В Дилемма Заключенного это сценарий в теории игр , где есть два игрока, каждый с двумя вариантами: сотрудничать или дефект. Каждый игрок делает лучше для себя, если он уходит, чем если бы он сотрудничал, но оба игрока предпочли бы результат, в котором оба игрока сотрудничали, чем тот, где оба игрока дефектовали.

Дилемма повторного заключенного - та же самая игра, за исключением того, что вы неоднократно играете с одним и тем же противником, и вы знаете, что играл ваш противник в прошлом. Ваша цель всегда состоит в том, чтобы набрать для себя наибольшее количество очков, независимо от того, как это делает ваш противник.

Шумная повторяющаяся дилемма заключенного вносит некоторый шум в общение. В ваших знаниях о том, что ваш оппонент играл в прошлом, появится немного шума. Вы также будете знать, какие движения вы сделали в прошлом. Уровень шума постоянен в течение раунда против одного и того же противника, но отличается в разных раундах.

Вызов

В этом задании вы напишите программу на Python 3, которая сыграет дилемму зашумленного итератора.

Ваша программа получит три входа:

• Ваши собственные ходы, без применения случайных сальто.

• Ходы вашего оппонента с применением случайных сальто.

• Переменная состояния, которая начинается как пустой список каждый раунд, и которую вы можете изменить, если хотите. Вы можете игнорировать это, если не хотите его использовать.

Ваша программа должна выводить данные 'c'для взаимодействия или 'd'дефекта.

Например, вот программа, которая взаимодействует, если противник сотрудничал, по крайней мере, 60% времени в прошлом, после применения случайных бросков и для первых 10 бросков:

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'

Если вы не знаете Python, напишите свое представление в псевдокоде, и кто-то (я или другой участник сайта) может создать соответствующую программу Python.

Игровой процесс

Бегун турнира можно найти здесь: шумная игра . Беги, noisy-game.pyчтобы запустить турнир. Я буду держать этот репозиторий обновленным с новыми представлениями. Примеры программ можно найти в basic.py.

Общий балл программы - это сумма баллов за 100 игр в игре.

Игра состоит из круговых матчей каждого игрока против каждого игрока, включая его самого. Матч состоит из 100 раундов. Раунд состоит из 300 ходов, каждый из которых включает в себя вывод 'c'или'd' .

Ваша заявка будет играть матч против каждой подачи, включая вашу собственную. Каждый матч будет состоять из 100 раундов. Во время каждого раунда вероятность переворота будет выбираться равномерно случайным образом [0, 0.5].

Каждый раунд будет состоять из 300 ходов. На каждом ходу обе программы будут получать все предыдущие попытки воспроизведения, которые они предприняли, и все предыдущие воспроизведения, сделанные другой программой, после применения переворотов, и переменную состояния, которая является изменяемым списком, который программа может изменить, если она хочет. Программы выведут свои ходы.

Ход оценивается следующим образом: если программа играет 'c', противоборствующая программа получает 2 балла. Если программа играет 'd', эта программа получает 1 балл.

Затем каждый ход переворачивается независимо с вероятностью, равной вероятности переворачивания, и сохраняется для показа противнику.

После того, как все раунды были сыграны, мы суммируем количество очков, которое каждый игрок получил в каждом матче. Затем мы используем следующую систему подсчета очков для подсчета очков каждого игрока в игре. Эта оценка выполняется после завершения всех матчей.

счет

Мы будем использовать эволюционную оценку. Каждая программа начинается с одинакового веса. Затем веса обновляются следующим образом для 100 итераций с использованием итоговых очков в игре:

Новый вес каждой программы пропорционален произведению ее предыдущего веса и его среднего общего балла, взвешенного по весам ее противников.

Применяется 100 таких обновлений, и итоговые веса являются баллами каждой программы за этот запуск игры.

Общая сумма очков будет суммой за 100 прогонов игры.

Все игроки получат правильные ответы на этот вызов, а также шесть основных программ, которые помогут нам начать.

Предостережения

Не модифицируйте входы. Не пытайтесь повлиять на выполнение любой другой программы, кроме как через сотрудничество или дефекты. Не делайте жертвенного представления, которое пытается распознать другое представление и принесет пользу этому противнику за свой счет. Стандартные лазейки запрещены.

РЕДАКТИРОВАТЬ: Представления не могут точно дублировать какие-либо из основных программ или любой более ранней подачи.

Если у вас есть вопросы, не стесняйтесь спросить.

Текущие результаты

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

Результаты только с ответами на этот вопрос и основные программы, которые игнорируют игру противника:

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

выигрыш

Конкурс будет оставаться открытым в течение неопределенного времени, так как новые материалы публикуются. Тем не менее, я объявлю победителя (приму ответ) по результатам 1 месяц после опубликования этого вопроса.

Genug ist nicht genug

(также можно назвать enough2или 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"

Я узнал, что оригинальная синица для двух татов действительно ждала двух последовательных татов, как это tit_for_whoopsделает, и, действительно, кажется, что мы должны простить и забыть (ну, почти ...) более ранние одиночные таты. И много игроков дефект в последних раундах. Я до сих пор предпочитаю быть милым, когда все было хорошо, но планка устойчивости бота продолжает снижаться.

Тит-For-упс

Вдохновлен стратегией от 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'

Дефекты только в том случае, если другой игрок сбежал дважды подряд, чтобы избежать недоразумений.

Изменение сердца

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

Изменения в сердце на полпути. Удивительно хорошо.

Стратегия Stealer

Вдохновленный достаточно, change_of_heart и tit-for-whoops. Должно быть немного больше, чтобы прощать. Я пытался настроить цифры для достижения наилучших результатов, но они не хотели сильно меняться.

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'

Тит-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"

Если ты проводил большую часть времени, причиняя мне боль, я просто сделаю тебе больно. Вероятно.

Растущее недоверие

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'

Чем больше оппонент меня предает, тем меньше я могу верить, что это был просто шум.

Jedi2Sith

Начинается все хорошее и самоотверженное, но со временем влияние темной стороны неуклонно усиливается, вплоть до точки невозврата. Это влияние не остановить, но все плохие вещи, которые он видит, просто способствуют силе темной стороны ...

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'

Попробуйте онлайн!

ползунок

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'

Начинается с «c» и постепенно скользит к «d» или от него.

Упрямый Спотыкатель

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'

Исходя из вашей стратегии порога эксплойта с единой последовательной игрой, отслеживается переключение между дефектом и в основном сотрудничество

ОБНОВЛЕНИЕ: отслеживает как два последовательных, так и три последовательных воспроизведения, наказывая только в более жестких условиях и добавляя случайный выбор, если не уверен

ОБНОВЛЕНИЕ 2: Удалено условие и добавлена ​​функция распределения

Noise Bot

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

Я определенно сотрудничаю с ботом. Это просто шум.

Хватит значит хватит

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"

Начинается как синица для двух татов, где эти два тита не должны быть последовательными (в отличие от tit_for_whoops). Если это должно играть dслишком часто, это идет - dитого.

Золотая рыбка Бот

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

Золотая рыбка никогда не прощает, но она быстро забывает.

обманщик (восстановлен снова)

Только последние 10 игр учитываются, но делятся на два блока по пять, которые усредняются, причем каждый классифицируется как хороший или плохой.

Если оппонент играет в среднем «приятно», то обманщик играет все реже и хуже. Если результаты неоднозначны, обманщик играет хорошо, чтобы заманить противника в безопасное место. Если противник, кажется, играет «плохо», обманщик отвечает.

Идея состоит в том, чтобы время от времени набирать очки у наивных игроков, а рано ловить лживых.

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'

Отказ от ответственности: я никогда не писал здесь раньше, если я делаю что-то не так>, пожалуйста, сообщите мне, и я исправлю.

Разлагающаяся память

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'

Весит новейшая история больше. Медленно забывает прошлое.

взятка

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"

Некоторые смутные идеи ...

Действительно не получает всю "шум" вещь

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

Никогда не прощает предателя.

Эхолот:

редактировать: добавлен ответный удар в сценариях с низким уровнем шума

в основном, если все 4 первых хода согласованы, это означает, что мы должны ожидать меньше шума, чем обычно. порой делайте небольшие дефекты, чтобы компенсировать меньшее количество баллов, которые мы получили бы, если бы никогда не отказывались, и чтобы его можно было обвинить в шуме. мы также ответим, если они перестанут действовать против нас

если наш противник делает много дефектов в те ходы (2 или более), мы просто возвращаемся к ним. если бы это был просто шум, шум все равно бы повлиял на наши движения.

в противном случае, если бы только 1 ход был дефектным, мы просто делали простое остроумие до конца игры.

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]

чередовать

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'

Выбирает случайным образом в первом раунде, затем чередуется. Всегда дефекты в последних 10 раундах.

Ждать 50

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

После 50 дефектов, пусть это будет!

Somehwat наивный

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'

Я просто предполагаю, что если вы сбежали меньше, чем вероятность (примерно) в последние n ходов, это был шум, а не то, что вы злые!

Не могу понять, лучший русский , может посмотреть дальше.

Каждые три

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"

Дефекты каждые три оборота независимо. Также дефекты последних 50 витков. Также дефекты, если его противник сбил 4 из 5 последних раундов.

Ковши

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'

Играет приятно для начала. Просматривает их последние 20, если <25% d, возвращает c,> 75% d, возвращает d, и между ними выбирается случайным образом по линейной вероятностной функции. Последние 50, дефекты. Было это в прошлом 10, но видел много последних 50 дефектов.

Впервые здесь, так что дайте мне знать, если что-то нужно исправить (или как я могу это проверить).

Тит-For-Stat

Дефекты, если противник сбежал более половины времени.

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