35
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How does tit_for_whoops ignore the opponent's play? \$\endgroup\$ – LyricLy May 5 '18 at 1:07
  • \$\begingroup\$ @LyricLy I assume the category refers to the basic programs provided by Isaac which ignore their opponents. \$\endgroup\$ – FryAmTheEggman May 5 '18 at 1:11
  • 1
    \$\begingroup\$ Do I understand right that you can use the state variable to record all your moves as you submit them, and therefore know both your true moves and flipped moves, and estimate the flip probability? \$\endgroup\$ – xnor May 5 '18 at 16:52
  • 1
    \$\begingroup\$ @xnor You always get told your true moves. It's only the opponents moves that may get flipped. \$\endgroup\$ – Mnemonic May 5 '18 at 16:56
  • 1
    \$\begingroup\$ @isaacg I tried copying exploit_threshold() several times as exploit_threshold1(), etc and added them to the players list. Why do I get vastly different results for identical strategies? \$\endgroup\$ – ngn May 5 '18 at 18:35

23 Answers 23

4
\$\begingroup\$

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.

\$\endgroup\$
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your submission! Keep in mind that since the flip probability averages 1/4, there's going to be a double-flip once every 16 moves or so. \$\endgroup\$ – isaacg May 5 '18 at 0:41
  • \$\begingroup\$ I added a state variable, which you can ignore if you don't want to use it. \$\endgroup\$ – isaacg May 5 '18 at 1:23
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Congratulations on taking the lead/second place. I'm impressed and surprised that an opponent ignoring strategy does so well. \$\endgroup\$ – isaacg May 7 '18 at 4:32
9
\$\begingroup\$

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'
\$\endgroup\$
  • \$\begingroup\$ welcome to PPCG! \$\endgroup\$ – Giuseppe May 8 '18 at 22:35
  • \$\begingroup\$ Congratulations on taking the lead! \$\endgroup\$ – isaacg May 9 '18 at 1:36
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice submission! You're currently in 1st place without the opponent-aware basic programs. \$\endgroup\$ – isaacg May 5 '18 at 22:14
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yeah, the no state thing is unfortunate, but I wanted the submissions to be uniform, so this is the best I could think of. Do you have any idea for how to add a state? \$\endgroup\$ – isaacg May 5 '18 at 1:11
  • \$\begingroup\$ Just have a state argument that by default is a list? Lists are mutable, so the state would be modifiable easily. \$\endgroup\$ – LyricLy May 5 '18 at 1:13
  • \$\begingroup\$ How so? I don't see how that could be. \$\endgroup\$ – LyricLy May 5 '18 at 1:16
  • \$\begingroup\$ @Mnemonic I think I know how to implement this. I'll give it a whirl. \$\endgroup\$ – isaacg May 5 '18 at 1:17
  • \$\begingroup\$ I added a state variable, which is intially an empty list, and which you can modify. \$\endgroup\$ – isaacg May 5 '18 at 1:22
7
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I did a functionally equivalent rewrite of this to use the state variable, because it was running pretty slowly. You don't need to change anything, however. \$\endgroup\$ – isaacg May 7 '18 at 7:56
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Contratulations on writing the first program to take the lead! \$\endgroup\$ – isaacg May 5 '18 at 7:11
6
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Congratuations on taking the lead! \$\endgroup\$ – isaacg May 7 '18 at 17:43
6
\$\begingroup\$

Goldfish Bot

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

A goldfish never forgives, but it quickly forgets.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Welcome to the site! Unfortunately, your code doesn't work currently. You have an elif after an else. Could you fix it? Thanks \$\endgroup\$ – isaacg May 7 '18 at 18:02
  • \$\begingroup\$ I'm guessing everything from the elif onward should be indented once more? \$\endgroup\$ – isaacg May 7 '18 at 18:05
  • \$\begingroup\$ Correct, I'll indent. \$\endgroup\$ – Hektor-Waartgard May 7 '18 at 18:06
  • \$\begingroup\$ @isaacg I have updated my answer with a new code. I do not have reputation enough to tell it to you in the question-comments. I am not certain that I am using the state variable correctly, I assume it is an empty list which I can append whatever I want to, correct? \$\endgroup\$ – Hektor-Waartgard May 9 '18 at 13:34
  • 2
    \$\begingroup\$ That won't work. After each turn, it is decided whether the current move is flipped or not (independently for the two players). That decission is then fixed. You will always see the same first move which may be flipped or not, but it won't change. \$\endgroup\$ – Christian Sievers May 9 '18 at 13:36
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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...

\$\endgroup\$
  • \$\begingroup\$ Congratulations on taking the lead in the version where adaptive basic spells are removed. \$\endgroup\$ – isaacg May 6 '18 at 20:33
  • \$\begingroup\$ Thanks. I think it's amazing how different the two results are! \$\endgroup\$ – Christian Sievers May 6 '18 at 20:50
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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]
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I fixed your python while preserving your intent. \$\endgroup\$ – isaacg May 15 '18 at 6:47
  • \$\begingroup\$ Congratulations on moving into 3rd place. \$\endgroup\$ – isaacg May 15 '18 at 7:04
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ If you want to test things locally, you can clone the repository, and run noisy-game.py. It takes a while, so you might want to remove some of the opponents in players for quick iterations. \$\endgroup\$ – isaacg May 11 '18 at 23:08
  • \$\begingroup\$ Thanks Isaac - I'll have to play with it and do some tinkering. \$\endgroup\$ – brian_t May 14 '18 at 23:32
1
\$\begingroup\$

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'
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.