Шумная итеративная дилемма заключенного

34

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

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

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

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

Вызов

В этом задании вы напишите программу на 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 месяц после опубликования этого вопроса.

isaacg
источник
Как tit_for_whoops игнорирует игру противника?
LyricLy
@LyricLy Я предполагаю, что категория относится к основным программам, предоставляемым Исааком, которые игнорируют своих противников.
FryAmTheEggman
1
Правильно ли я понимаю, что вы можете использовать переменную состояния для записи всех ваших ходов по мере их отправки, и, следовательно, знать как свои истинные ходы, так и перевернутые ходы и оценивать вероятность переворачивания?
xnor
1
@xnor Тебе всегда рассказывают твои настоящие поступки. Только движения противника могут быть перевернуты.
1
@isaacg Я exploit_threshold()несколько раз пытался скопировать как exploit_threshold1()и т. д. и добавил их в playersсписок. Почему я получаю совершенно разные результаты для идентичных стратегий?
августа

Ответы:

4

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делает, и, действительно, кажется, что мы должны простить и забыть (ну, почти ...) более ранние одиночные таты. И много игроков дефект в последних раундах. Я до сих пор предпочитаю быть милым, когда все было хорошо, но планка устойчивости бота продолжает снижаться.

Кристиан Сиверс
источник
10

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

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

LyricLy
источник
Спасибо за заявку! Имейте в виду, что поскольку вероятность переворачивания составляет в среднем 1/4, каждые 16 ходов будет происходить двойной переворот.
Исаак
Я добавил переменную состояния, которую вы можете игнорировать, если не хотите ее использовать.
Исаак
9

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

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

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

qwewqa
источник
Поздравляем с занятием первого / второго места. Я впечатлен и удивлен, что противник, игнорирующий стратегию, делает это хорошо.
Исаак
9

Стратегия 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'
adebunk
источник
добро пожаловать в PPCG!
Джузеппе
Поздравляем с лидерством!
Исаак
8

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

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

синий
источник
Хорошая подача! В настоящее время вы находитесь на 1-м месте без основных программ, ориентированных на оппонента.
Исаак
7

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

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'

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


источник
Да, к сожалению, нет состояния, но я хотел, чтобы представления были единообразными, так что это лучшее, что я мог придумать. У вас есть идеи, как добавить состояние?
Исаак
Просто есть stateаргумент, что по умолчанию это список? Списки изменчивы, поэтому состояние можно легко изменить.
LyricLy
Как же так? Я не понимаю, как это могло быть.
LyricLy
@ Мнемоник Я думаю, я знаю, как это реализовать. Я поверну это.
Исаак
Я добавил переменную состояния, которая по сути является пустым списком и которую вы можете изменить.
Исаак
7

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'

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

Лео
источник
6

ползунок

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» или от него.

миль
источник
Я сделал функционально эквивалентную переписку этого, чтобы использовать переменную состояния, потому что она работала довольно медленно. Вам не нужно ничего менять, однако.
Исаак
6

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

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: Удалено условие и добавлена ​​функция распределения

JMigst
источник
Контракты на написание первой программы, чтобы взять на себя инициативу!
Исаак
6

Noise Bot

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

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

Крис
источник
6

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

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итого.

Кристиан Сиверс
источник
Поздравляем с лидерством!
Исаак
6

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

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

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

Крис
источник
6

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

Только последние 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'

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

Гектор-Waartgard
источник
Добро пожаловать на сайт! К сожалению, ваш код не работает в настоящее время. У вас есть элиф после другого. Не могли бы вы это исправить? Спасибо
Исаак
Я предполагаю, что все, начиная с элифа, должно быть еще раз отступено?
Исаак
Правильно, я сделаю отступ.
Гектор-Ваартгард
@isaacg Я обновил свой ответ новым кодом. У меня недостаточно репутации, чтобы рассказать вам об этом в комментариях. Я не уверен, что правильно использую переменную состояния, я предполагаю, что это пустой список, который я могу добавить, что захочу, исправить?
Гектор-Ваартгард
2
Это не сработает. После каждого хода решается, будет ли текущий ход перевернут или нет (независимо для двух игроков). Это решение затем фиксируется. Вы всегда увидите один и тот же первый ход, который может быть перевернут или нет, но он не изменится.
Кристиан Сиверс
5

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

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'

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

qwewqa
источник
5

взятка

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"

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

Кристиан Сиверс
источник
Поздравляем с лидерством в версии, в которой удалены адаптивные базовые заклинания.
Исаак
Спасибо. Я думаю, это удивительно, насколько разные результаты!
Кристиан Сиверс
4

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

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

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

Крис
источник
4

Эхолот:

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

в основном, если все 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]
Разрушаемый Лимон
источник
3

чередовать

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 раундах.

Крис
источник
3

Ждать 50

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

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

MegaTom
источник
Я исправил ваш питон, сохраняя ваши намерения.
Исаак
Поздравляем с переходом на 3 место.
Исаак
2

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 ходов, это был шум, а не то, что вы злые!

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

JeroendeK
источник
2

Каждые три

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 последних раундов.

MegaTom
источник
2

Ковши

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 дефектов.

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

brian_t
источник
Если вы хотите что-то протестировать локально, вы можете клонировать репозиторий и запустить noisy-game.py. Это займет некоторое время, поэтому вы можете удалить некоторых противников playersдля быстрой итерации.
Исаак
Спасибо, Исаак - мне придется поиграть с ним и немного поработать.
brian_t
1

Тит-For-Stat

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

def tit_for_stat(m, t, s):
  if t.count('d') * 2 > len(m):
    return 'd'
  else:
    return 'c'
RamenChef
источник