Noisy Iterated Prisoner's Dilemma

Question

In this challenge, you will play the noisy iterated prisoner's dilemma.

The Prisoner's dilemma is a scenario in game theory where there are two players, each with two options: cooperate, or defect. Each player does better for themself if they defect than if they cooperate, but both players would prefer the outcome where both players cooperate to the one where both players defect.

The iterated prisoner's dilemma is the same game, except you play against the same opponent repeatedly, and you know what your opponent has played in the past. Your objective is always to accumulate the highest score for yourself, regardless of how your opponent does.

The noisy iterated prisoner's dilemma introduces some noise into the communication. Your knowledge of what your opponent has played in the past will have some noise introduced. You will also know what moves you made in the past. The noise rate is constant over a round against the same opponent, but different between different rounds.

Challenge

In this challenge, you will write a Python 3 program to play the noisy iterated prisoner's dilemma.

Your program will receive three inputs:

• Your own moves, without random flips applied.

• Your opponent's moves, with random flips applied.

• A state variable, which starts as an empty list each round, and which you can modify if you want. You can ignore this if you don't want to use it.

Your program should output 'c' to cooperate or 'd' to defect.

For instance, here's a program that cooperates if the opponent has cooperated at least 60% of the time in the past, after random flips were applied, and for the first 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'

If you don't know Python, write your submission in pseudocode, and someone (me or another member of the site) can make the corresponding Python program.

Gameplay

The tournament runner can be found here: noisy-game. Run noisy-game.py to run the tournament. I'll keep that repository updated with new submissions. Example programs can be found in basic.py.

A program's overall score is the total of its score over 100 plays of the game.

A game consists of round-robin matchups of each player against each player, including itself. A matchup consists of 100 rounds. A round consists of 300 moves, each of which involves outputting 'c' or 'd'.

Your submission will play a matchup against every submission, including your own. Each matchup will consist of 100 rounds. During each round, a flip probability will be chosen uniformly randomly from [0, 0.5].

Each round will consist of 300 moves. On each move, both programs will receive all previous plays they have attempted, and all previous plays the other program has made, after flips are applied, and a state variable, which is a mutable list which the program can modify if it wants to. The programs will output their moves.

Moves are scored as follows: If a program plays a 'c', the opposing program gets 2 points. If a program plays a 'd', that program gets 1 point.

Then, each move is flipped independently with probability equal to the flip probability, and stored for showing to the opponent.

After all of the rounds have been played, we sum the number of points each player got in each matchup. Then, we use the following scoring system to calculate each player's score for the game. This scoring is performed after all of the matchups are complete.

Scoring

We will use evolutionary scoring. Each program starts with equal weight. Then, weights are updated as follows, for 100 iterations, using the point totals from the game:

Each program's new weight is proportional to the product of its previous weight and its average point total, weighted by the weights of its opponents.

100 such updates are applied, and the final weights are each program's score for that run of the game.

The overall scores will be the sum over 100 runs of the game.

The players will be all valid answers to this challenge, plus six basic programs to get us started.

Caveats

Do not modify the inputs. Do not attempt to affect the execution of any other program, except via cooperating or defecting. Do not make a sacrificial submission that attempts to recognize another submission and benefit that opponent at its own expense. Standard loopholes are banned.

EDIT: Submissions may not exactly duplicate any of the basic programs or any earlier submission.

If you have any questions, feel free to ask.

Current results

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

Results with only answers to this question and basic programs that ignore the opponent's play:

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

Winning

The competition will stay open indefinitely, as new submissions are posted. However, I will declare a winner (accept an answer) based on the results 1 month after this question was posted.

Answer 1

Tit-For-Whoops

Inspired by a strategy from 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'

Defects only if the other player has defected twice in a row, to prevent misunderstandings.

Answer 2

Change of Heart

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

Has a change of heart partway through. Does surprisingly well.

Answer 3

Strategy Stealer

Inspired by enough, change_of_heart, and tit-for-whoops. Should be a little more forgiving. I tried to tweak the numbers for best results but they didn't want to change much.

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'

Answer 4

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"

If you've been spending most of the time hurting me, I'll just hurt you back. Probably.

Answer 5

Growing Distrust

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'

The more the opponent betrays me, the less I can trust it was just noise.

Answer 6

Jedi2Sith

Starts off all nice and selfless, but with time the influence of the dark side grows steadily stronger, until the point of no return. There's no stopping this influence, but all the bad things it sees happening just contribute to the power of the dark side...

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'

Try it online!

Answer 7

Genug ist nicht genug

(could also be called enough2 or 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"

I learned that the original tit for two tats did wait for two consecutive tats like tit_for_whoops does, and indeed it seems we should forgive and forget (well, almost...) earlier single tats. And a lot of players defect in the last rounds. I still prefer to be nice when everything has been fine so far, but the bot's tolerance bar keeps getting lower.

Answer 8

Slider

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'

Starts off with 'c', and gradually slides towards or away from 'd'.

Answer 9

Stubborn 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'

Based off of your exploit threshold strategy with only consistent plays kept track for switching between defect and mostly co-operate

UPDATE: Keeps track of both two consecutive and three consecutive plays, punishing only under harsher conditions and adding a random choice when not sure

UPDATE 2: Removed condition and added distribution function

Answer 10

Noise Bot

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

I'm definitely cooperate bot. That's just noise.

Answer 11

Enough is Enough

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"

Starts as tit for two tats where the two tats don't have to be consecutive (unlike tit_for_whoops). If it has to play d too often it goes d-total.

Answer 12

Goldfish Bot

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

A goldfish never forgives, but it quickly forgets.

Answer 13

trickster (reinstated again)

Only the last 10 plays are accounted for, but divided into two blocks of five, which are averaged with each classified as good or bad.

If the opponent plays on average "nice", the trickster plays less and less nice. If the results are ambiguous the trickster plays nice to lure the opponent into safety. If the opponent appears to be playing "bad" the trickster retaliates.

The idea is to gather points now and then from naïve players, while catching deceitful ones early.

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'

Disclaimer: I have never posted here before, if I am doing something wrong >please tell me and I'll correct.

Answer 14

Decaying Memory

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'

Weighs recent history more. Slowly forgets the past.

Answer 15

Kickback

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"

Some vague ideas...

Answer 16

Doesn't Really Get The Whole "Noise" Thing

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

Never forgives a traitor.

Answer 17

sounder:

edit: added retaliation in probably low noise scenarios

basically, if all 4 first moves are cooperate, that means we should expect less noise than usual. defect a little bit every so often to make up for the less points we would get from never defecting, and have it be able to be blamed on noise. we also retaliate if they defect against us

if our opponent does a lot of defecting in those turns (2 or more) we just defect back at them. if it was just noise, the noise would affect our moves anyway.

otherwise, if only 1 move was defect, we just do simple tit for tat the rest of the game.

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]

Answer 18

Alternate

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 randomly in the first round, then alternates. Always defects in the last 10 rounds.

Answer 19

Wait for 50

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

After 50 defects, let 'em have it!

Answer 20

Somehwat naive

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'

I'll just assume that if you've defected less than the flip probability (roughly) in the last n turns, it was noise and not that you're mean!

Haven't figures out the best n, might look further into that.

Answer 21

Every Three

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"

Defects every three turns regardless. Also defects the last 50 turns. Also defects if his opponent defected 4 out of 5 of the last rounds.

Answer 22

Buckets

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'

Plays nice to begin. Looks at their last 20, if < 25% d, returns c, > 75% d, returns d, and in between chooses randomly along a linear probability function. Last 50, defects. Had this at last 10 but saw lots of last 50 defects.

First time here so let me know if something needs to be fixed (or how I can test this).

Answer 23

Tit-for-Tat (pseudocode)

I'm surprised no one has put a basic tit-for-tat

Also, is the challenge considered over because not a lot of people have posted, and is it against the stack exchanges rules to post on an old thread?

    def tit_for_tat (my-moves, op-moves) {
      if (op-moves[last] == 'D')
        return D
      else
        return C
    }

Answer 24

Tit-For-Stat

Defects if the opponent has defected more than half the time.

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