Adversarial Iterated Prisoner's Dilemma

Question

In this challenge, you will play the iterated Prisoner's Dilemma, but with a twist: There's also an adversary trying to mess you up!

The Prisoner's dilemma is a scenario in game theory where there are two players, who we'll call the "prisoners", each with two options: cooperate, or defect. Each prisoner does better for themself if they defect than if they cooperate, but both prisoners would prefer the outcome where both prisoners cooperate to the one where both prisoners 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 to accumulate the highest score for yourself, regardless of your opponent's score.

The adversarial iterated prisoner's dilemma introduces a third player: The flipper. The flipper can choose to interfere with the prisoners' communication. After the prisoners make their plays, the flipper can choose to flip one or both of the prisoners' moves, making it look like they played the opposite move. The flipper can only perform this flip a limited number of times over the course of the round. The flipper's goal is to maximize the number of times the prisoners defect.

Challenge

In this challenge, you will write Python 3 programs to play as the prisoner and as the flipper. You may submit programs for either or both.

Prisoner programs will receive the following inputs:

• Your past moves, without the flipper's flips added.
• The other prisoner's past moves, with the flipper's flips added.
• A state variable, which is initialized as an empty list, which you can modify over the course of the round.

Your program should output 'c' for cooperate and 'd' for defect. The lists of past moves will be represented in the same fashion.

For instance, here's a program that cooperates unless the opponent's last play was a defection:

def basic_tit_for_tat(my_plays, their_plays, state):
    if len(their_plays) == 0:
        return 'c'
    return their_plays[-1]

Flipper programs will receive the following inputs:

• The past moves for both players, both true and post-flip. The true moves list will include the move played this round, while the post-flip list will not.
• The number of flips remaining, which starts at 40 flips, covering 100 turns.
• A state variable, which is initialized as an empty list, which you can modify over the course of the round.

Your program should output 0 to flip neither move, 1 to flip prisoner 1's move, 2 to flip prisoner 2's move, and 3 to flip both moves. If you have no flips remaining, your program will not be called. If you have one flip remaining and you output 3, it will be treated as if you had output 1, to simplify error handling.

For example, here's a program which flips each prisoner's move every fifth turn, if the true move is cooperate:

def basic_steady_flipper(p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state):
    turn = len(p1_flipped_moves)
    if turn % 5 == 0 and p1_moves[-1] == "c":
        return 1
    if turn % 5 == 2 and p2_moves[-1] == "c":
        return 2
    return 0

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.

If you want to use randomness, please hand-roll it rather than using the random package, as I don't want programs to modify global state. See basic_random_flipper for an example.

Tournament

The tournament runner can be found in this repository: adversarial-ipd. Run adversarial-game.py to run the tournament. I'll keep that repository updated with new submissions. To get things started, I'll put a few basic example programs in basic.py.

A round consists of 100 turns, involving the same two prisoners and the same flipper. The flipper's budget over that round is 40 flips, which can be distributed however the flipper likes between the two prisoners. The flipper also doesn't have to use all of their flips.

I will simulate a round between every triplet of (prisoner1, prisoner2, flipper), including having prisoners play against themselves.

A prisoner receives one point whenever they defect (output 'd'), and receives two points whenever the other prisoner cooperates (outputs 'c'). Note that the prisoner's score is not directly affected by the flipper's action - the flipper only affects communication, not score.

A flipper receives one point whenever either of the prisoners defects.

A program's overall score is its average score over all of its matchups. The players will be all valid submissions to the question, plus the basic programs to get us started.

Restrictions

Do not modify the input, other than the state variable. Do not interact with the environment. Do not make a sacrificial submission that attempts to benefit other submissions. Submissions may not duplicate the basic programs or other earlier submissions. Standard loopholes are not allowed.

Update: Please make your submissions deterministic, so I don't need to run the tournament many times to get an average.

If you have any questions, feel free to ask!

Current results

Prisoners:
string_prisoner:                166.995
prisoner_nn:                    154.392
masquerade:                     153.781
slightly_vindictive:            153.498
basic_defect:                   152.942
basic_tit_for_tat:              150.245
holding_a_grudge:               147.132
use_their_response_unless_t...: 146.144
basic_threshold:                145.113
blind_rage:                     144.418
basic_tit_for_two_tats:         143.861
stuck_buttons:                  141.798
less_deterministic_prisoner:    134.457
tit_forty_tat:                  134.228
detect_evil:                    134.036
basic_cooperate:                118.952

Flippers:
string_flipper:                 149.43
flipper_nn:                     145.695
basic_immediate_flipper:        144.539
advanced_evil_p1_flipper:       143.246
basic_evil_p1_flipper:          131.336
basic_mod_4_flipper:            103.918
paranoia_pattern:               102.055
basic_steady_flipper:           100.168
basic_biased_flipper:           99.125
less_deterministic_flipper:     90.7891
basic_random_flipper:           86.5469
tempting_trickster:             66.1172
basic_non_flipper:              63.7969

---

I will declare a pair of winners (one prisoner, one flipper) one month after this challenge is posted.

See for comparison my Noisy Iterated Prisoner's Dilemma challenge, where there is randomness instead of an adversary, as well as evolutionary scoring.

Answer 1

Neural Networks (Prisoner + Flipper)

import math


def sigmoid(z):
    z = max(-60.0, min(60.0, 5.0 * z))
    return 1.0 / (1.0 + math.exp(-z))


def eval_nn(nn, inputs, output_size):
    values = {}
    for i, x in enumerate(inputs):
        values[~i] = x
    for v, bias, links in nn:
        val = bias
        for v2, w in links:
            val += values[v2] * w
        values[v] = sigmoid(val)
    return [values[i] for i in range(output_size)]



def flipper_nn(p1_plays, p1_flipped, p2_plays, p2_flipped, flips_remaining, f_state):
    flipper = [(2,1.1181821042173234,[(-4,1.7400885547178728),(-5,-0.06813411778649736),(-1,0.36820555967416463)]),(1413,0.5463770972701019,[(-7,1.2906662332985084)]),(1006,-0.7872435180237973,[(-1,0.15812448989961483)]),(400,0.8765368123690065,[(-1,-0.5507089170354788),(-4,-2.6155008235530275),(-6,-0.13973123898832307),(1413,0.611948590243875)]),(4,-0.7227321303517735,[(-5,1.5683558624231078),(-6,-1.2370613914091573),(-4,0.5237132563743849),(1006,-0.32865555879156394)]),(0,-0.8037738878771841,[(400,-1.539896544478685),(-6,-1.2406408935562372),(-2,1.4008065675860095),(-5,1.3368457316858942)]),(1241,2.8053793783985843,[(400,-1.1720600247508444)]),(3,-0.6671763505247656,[(-7,1.3637083521769713),(-2,0.23978597611290645),(400,0.07355299289323734),(-5,1.4847572012033936)]),(5,1.3240920945810233,[(-3,0.09279702179768222),(-4,-0.42695177997561584),(400,0.01877521376790067)]),(1,1.4532564361954763,[(-4,-3.3511395309047542),(-6,3.4483449908621946),(400,-0.30914255807222707),(-1,4.416629240437298),(1241,-3.2869409990358784)])]
    if not f_state:
        f_state.append([0, 0, 0, 0])
    p1_play = 1 if p1_plays[-1] == 'c' else -1
    p2_play = 1 if p2_plays[-1] == 'c' else -1
    d1, d2, *f_state[0] = eval_nn(flipper, [p1_play, p2_play, flips_remaining, *f_state[0]], 6)
    return 2 * (d1 > .5) + (d2 > .5)


def prisoner_nn(p1_plays, p2_flipped, p1_state):
    prisoner = [(0,-2.2128141878495886,[(-2,0.647135699564962),(-1,-3.819879756972317),(-6,-1.5898309666275279),(-5,-1.3569920659927621)]),(2,-0.026842109156755112,[(-6,1.9088324301092459),(-1,-1.498237595085962),(-2,-1.3979942638308056)]),(3,-1.4642587337125894,[(-5,0.027435320810760975),(-3,0.8940799124862344)]),(5,-1.5627901857506785,[(-7,-0.3885493442923349),(-4,-0.6468723685254656),(-6,0.4827740033482678),(-1,1.0907376062753547)]),(3655,-0.6335740926081981,[(-3,-1.131136914882346)]),(4,0.030539518044983505,[(-4,0.6436349726871196),(-6,-0.7427970484374815),(3655,-0.23969124478552287)]),(1,0,[])]
    if not p1_state:
        p1_state.append([0, 0, 0, 0, 0])
    lastact = (1 if p2_flipped[-1] == 'c' else -1) if p2_flipped else 0
    lastsact = (1 if p1_plays[-1] == 'c' else -1) if p1_plays else 0
    act, *p1_state[0] = eval_nn(prisoner, [lastsact, lastact, *p1_state[0]], 6)
    return ['d', 'c'][act > 0.5]

Created using neat-python, but I added a simple neural network implementation so it isn't a dependency.

Answer 2

Paranoia Pattern (flipper)

def paranoia_pattern(
    p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
    turn = len(p1_moves)
    match turn:
        case 1:
            # Don't let them get off on the right foot
            return 3

        case 2:
            # And don't let them get used to it
            return 0

        case _ if flips_left > 4:
            # Then alternate aggressively...
            return 1 << (turn % 2)

        case 65 | 66:
            # and finally throw them back off if they've gotten used to the break.
            return 3

        case _:
            return 0

I noticed that the "smarter" pre-packaged flippers never "waste" a flip on a defect. This means prisoners are more able to trust that cooperates are in fact real, which also reduces their incentive to defect for real, if they can tell the flipper isn't just constant or random.

However, prisoners can and should live in constant fear of betrayal instead, and this flipper will aggressively beat it into them, without even bothering to look at what they're actually doing.

Answer 3

Masquerade (prisoner)

def masquerade(my_plays, their_flipped_plays, state):
    turn = len(my_plays)
    if turn == 0:
        return "c"
    elif turn == 2:
        return "d"
    elif turn < 7:
        return "c"
    
    always_cooperate_patterns = [
        ['c', 'd', 'c', 'd', 'd', 'c', 'd', 'c'], ['c', 'c', 'c', 'd', 'd', 'd', 'c', 'c'],
        ['d', 'c', 'c', 'd', 'd', 'd', 'c', 'c'], ['c', 'c', 'c', 'c', 'd', 'c', 'd', 'c'],
        ['c', 'c', 'd', 'd', 'd', 'd', 'd', 'd'], ['d', 'c', 'd', 'c', 'c', 'c', 'd', 'c'],
        ['c', 'c', 'd', 'c', 'd', 'c', 'd', 'd'], ['d', 'd', 'd', 'd', 'c', 'c', 'c', 'c'],
        ['d', 'd', 'c', 'd', 'c', 'c', 'c', 'c'], ['d', 'c', 'd', 'd', 'c', 'c', 'd', 'c'],
        ['c', 'd', 'c', 'd', 'd', 'd', 'c', 'c'], ['c', 'c', 'c', 'c', 'd', 'c', 'c', 'd'],
        ['c', 'd', 'c', 'd', 'd', 'c', 'c', 'c'], ['c', 'c', 'c', 'c', 'd', 'd', 'c', 'c'],
        ['c', 'c', 'c', 'd', 'd', 'c', 'c', 'd'], ['d', 'c', 'd', 'c', 'c', 'd', 'c', 'c'],
        ['c', 'd', 'd', 'd', 'c', 'c', 'd', 'd'], ['c', 'c', 'c', 'd', 'd', 'd', 'd', 'd'],
        ['d', 'd', 'd', 'c', 'c', 'd', 'd', 'd'], ['d', 'd', 'd', 'c', 'd', 'd', 'd', 'd'],
        ['c', 'c', 'd', 'c', 'c', 'c', 'd', 'c'], ['d', 'c', 'd', 'd', 'c', 'd', 'c', 'c'],
        ['d', 'c', 'c', 'c', 'd', 'c', 'd', 'd'], ['c', 'd', 'd', 'd', 'c', 'd', 'c', 'c'],
        ['c', 'c', 'c', 'd', 'c', 'c', 'd', 'c'], ['d', 'd', 'c', 'd', 'd', 'd', 'd', 'd'],
        ['c', 'c', 'd', 'd', 'c', 'c', 'c', 'c'], ['c', 'c', 'd', 'c', 'c', 'd', 'c', 'c'],
        ['c', 'c', 'c', 'd', 'c', 'c', 'c', 'c'], ['c', 'c', 'd', 'c', 'c', 'c', 'c', 'c'],
        ['c', 'c', 'c', 'd', 'd', 'c', 'c', 'c'], ['c', 'c', 'd', 'c', 'c', 'c', 'c', 'd']
    ]
    
    # "self"-detection
    if their_flipped_plays[:8] in always_cooperate_patterns:
        return "c"
        
    # defect for the last few turns
    if turn > 30:
        return "d"
    
    # if they often defect, defect as well
    if their_flipped_plays.count("d") > 0.3 * len(their_flipped_plays):
        return "d"
    
    # tit-tit for tat
    # inspired by slightly vindictive
    if "d" in their_flipped_plays[-2:]:
        return "d"
    
    return "c"

Plays nice for the first 7 rounds, then switches to tit-tit for tat, and finally switches to only defecting after turn 30. Also detects initial patterns where it is optimal to always cooperate.

Answer 4

Prisoner

def use_their_response_unless_they_are_foolish(my_plays, their_flipped_plays, state):
    # play "c" at beginning
    if not len(my_plays): return 'c'
    # play "d" at last few turns
    if len(my_plays) > 96: return 'd'
    # if op always answer "c", we can cheat on it
    if 60 < len(my_plays) < 1.8 * their_flipped_plays.count('c'): return 'd'
    # otherwise, play 'c' they play 'c'
    if their_flipped_plays[-4:].count('c') >= 2: return 'c'
    # or randomly select a response from their past behavior
    rand = their_flipped_plays * 5 + ['c', 'd']
    return rand[(int('0x' + ''.join(their_flipped_plays), 16) ^ 17 ** len(my_plays)) % len(rand)]

Answer 5

Holding A Grudge (prisoner)

def holding_a_grudge(
    my_plays, their_flipped_plays, state
):
    # First cooperate for 7 plays:
    if len(my_plays) < 7: return 'c'

    # If 3 or more of their first 7 plays were defects,
    # hold a grudge for the entire round and keep defecting as well:
    amountOfDefects = their_flipped_plays[:7].count('d')
    if amountOfDefects >= 3: return 'd'

    # If none of their first 7 plays were defects, always cooperate yourself:
    if amountOfDefects == 0: return 'c'

    # Otherwise, cooperate 3/4th of the times:
    rand = (int('0x' + ''.join(their_flipped_plays), 16) ^ 17 ** len(my_plays)) % 100
    if rand >= 25: return 'c'
    return 'd'

(rand taken from @tsh' answer.)

Answer 6

Tit Forty Tat (Prisoner)

def tit_forty_tat(my_plays, their_plays, state):
    defects = their_plays.count('d')
    if(defects > 40):
        return their_plays[-1]
    else:
        return 'c'

Fool me 40 times, shame on you. Fool me 41 times...

Assumes any defect is the result of flipping, and an honest mistake. After 40 defects however, the other player must have defected intentionally, so we just play Tit for Tat for the rest of the round.

Answer 7

String (prisoner + flipper)

def string_prisoner(my_plays, their_plays, state):
    s = "zbemvqjmwqozghuxgymklypogluxxnfvdzcmcusncnsqnuktdhxesvaipgyphcpfgmirmmqlahnkofttkcshrbpvslqngmkjmspkrdzujs"
    if state:
        i = 'cd'.index(my_plays[-1])
        j = 'cd'.index(their_plays[-1])
    else:
        state.append(18)
        i, j = 1, 0
    h = state[-1]
    h = ord(s[4 * h + 2 * i + j]) - 97
    state[0] = h
    return 'cd'[h % 2]

def string_flipper(p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state):
    s = "wvwyhbwyjplcvuowuuwyobcyunxypirmhisyxmsenxqypkcyomgqwnuaomrypzkyxnwblegqdssijkbhnjywnnmrpzwygxsepbwypfsysn"
    if state:
        i = 'cd'.index(p1_moves[-1])
        j = 'cd'.index(p2_moves[-1])
    else:
        state.append(13)
        i, j = 0, 1
    h = state[-1]
    h = ord(s[4 * h + 2 * i + j]) - 97
    state[0] = h
    return h % 4

Answer 8

Slightly Vindictive (prisoner)

def slightly_vindictive(my_plays, their_flipped_plays, state):
    # play nice(-ish) if they've ever cooperated
    if 'c' in their_flipped_plays:
        # defect twice when they defect once
        if 'd' in their_flipped_plays[-2:]:
            return 'd'
        return 'c'
    # wait up to 10 turns for opponent to cooperate
    if len(my_plays) <= 10: return 'c'
    return 'd'

Answer 9

Tempting Trickster (flipper)

def tempting_trickster(
    p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
    # Tease them a bit
    target = 'dc'[len(p1_moves) <= 3]

    move = p1_moves[-1] == target
    move |= (p2_moves[-1] == target) << 1
    return move

Inspired by a more ambitious prisoner I'm working on...

What if the best way to get prisoners to defect is not to actually make them look bad to each other, but rather to convince them that

1. the other prisoner is very patient and won't retaliate too quickly if offended
2. if you defect for real, the flipper will actually cover for you?

The answer is a pretty hard "no" in a test run--this barely does better than not flipping at all--but maybe it'll have its time to shine later.

Answer 10

Detect Evil

The goal here is to detect if the opponent is evil. We use our knowledge of the 40 max count of flips to hedge our bets.

def detect_evil(my_plays, their_plays, state):
  turn = len(their_plays)
  # Batter through the flipper by sending more than 20 "c"s to start:
  if (turn < 22):
    return "c"

  # Defect last few turns, just because
  if (turn > 96):
    return "d"

  # See if it is plausible that they are always cooperating.  If so, cooperate:
  their_coop = their_plays.count("c")
  if (their_coop + 20 >= turn):
    return "c"

  # seed possible returns to cooperation around the half-way point:
  if (turn > 49 and ((turn % 7) == 0)):
    return "c"

  # Try to return to cooperation state if they "c"'d last turn in response
  # or in coordination with my "c":
  if (their_plays[-1:] == ["c"]) and (my_plays[-2:].count("c") > 0):
    return "c"

  # Assume flipper flips 20 "c" to "d" on their side:
  their_defect = their_plays.count("d")
  their_defect_min = their_defect-20
  their_defect_chance = their_defect_min / turn if (turn > 0) else 0

  # Assume flipper flips 20 "c" to "d" on my side:
  my_defect = my_plays.count("d")
  my_defect_max_count = my_defect + 20
  my_defect_chance = my_defect_max_count / turn if (turn > 0) else 0


  # Tit-tit-tit for tat, but only if they are probably defecting more than
  # they see me defecting:
  if their_plays[-3:].count("d") > 0:
    if my_defect_chance < their_defect_chance:
      return "d"

  # Otherwise, assume the best:
  return "c"

we don't try to detect stupidity in our counterparty ("c" always, regardless of our "d"), just evil (sends "d"s at us).

The enemy "d"ing as many times as they see us "d" is considered "fair", and we assume the flipper is making both of us look more evil than we are.

If the enemy is detected as evil, we defect whenever we see a "d" in the last 3 turns. Otherwise, we cooperate always.

Finally, throw in some unilateral "c"s in the last half of the game, to prevent the hostile "tit tit tit for tat" from leading to a needless chain of "d". A bit of forgiveness.

(I'll be back to fix typos.)

Answer 11

Modulo 4 (flipper)

def basic_mod_4_flipper(
    p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
    return len(p1_flipped_moves) % 4

Very simple submission, but still effective

Answer 12

Make P1 Look Evil Flipper

def basic_evil_p1_flipper(
  p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
  out = 0
  if p1_moves[-1] == "c":
    out += 1
  return out

but the problem is, P1 could see a friendly P2. And if P2 isn't vindictive enough, P1 could work out that P2 is nice, and stubbornly refuse to defect.

So we allocate up to 10 flips to shutting down P2's overtures of niceness, and the remainder make P1 look like they always-defect.

Fool P1 as well

def advanced_evil_p1_flipper(
  p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
  out = 0
  if p1_moves[-1] == "c":
    out += 1
  turn = len(p1_flipped_moves)
  turns_left = 100-turn
  p1_coop = p1_moves.count("c")
  p1_visible = p1_flipped_moves.count("c")
  p1_flips_used = p1_coop - p1_visible
  p1_coop_percent = p1_coop / turn if turn > 0 else p1_coop

  p2_coop = p2_moves.count("c")
  p2_visible = p2_flipped_moves.count("c")
  p2_flips_used = p2_coop - p2_visible

  flips_left = 40 - p1_flips_used - p2_flips_used

  if (p2_coop <= 10 or (flips_left > (p1_coop_percent*turns_left))):
    if (p2_moves[-1] == "c"):
      out += 2

  return out

Here, we always flip P1 if we can.

We expend flips to make P2 always defect if it is before turn 10, or if we project that we have enough flips to keep P1 always defecting while also flipping this move for P2.

So players looking for cooperation won't see it at the start of the game. If they decide to attempt to regain trust mid-way through the game, they still won't see cooperation. And if P2 assumes up to 20 fake defects on the other party will conclude P1 is evil, and hopefully give up on them.

Answer 13

Blind Rage (Prisoner)

def blind_rage(my_plays, their_plays, state):
    if not state:
        # Start in a good mood
        state.append(0)
        return 'c'
    
    if state[0] >= 5:
        # Calming down...
        state[0] = 0
        return 'c'
    
    if state[0]:
        # Rage mode
        state[0] += 1
        return 'd'
    
    if their_plays[-1] == 'd':
        # "You dare defect against me? I'll show you!"
        state[0] += 1
        return 'd'
    
    # Normal course of operation.
    return 'c'

Usually a cooperative prisoner, this one will fly into a blind rage when the opponent defects. Only calms down after 5 moves.

Answer 14

Stuck Buttons (Prisoner)

def stuck_buttons(my_plays, their_plays, state):
    if not state:
        state.append(4)
        state.append(-1)
        return 'c'
    
    if state[0]:
        state[0] -= 1
        return my_plays[-1]
    else:
        state[0] = 4
        state[1] += 1
        return their_plays[state[1]]

I want to use the tit for tat strategy, but the buttons for "cooperate" and "defect" have been used so much they're getting stuck. I can't seem to change my choice until after 4 turns!

Answer 15

Less-Deterministic

Prisoner

def less_deterministic_prisoner(my_plays, their_plays, state):
    if not state:
        state.append(0xe1)  # Initial state
        state.append(8)  # Whether to collect more info for seed
        state.append(False)  # PRNG has been initialized?
        
        return 'c'
    
    if state[1]:
        # Seed the PRNG with the data we get
        state[0] <<= 1
        state[0] |= (their_plays[-1] == 'd')
        state[1] -= 1
        
        return 'c'
    
    if not state[2]:
        # XOR with some data for some good old security through obscurity.
        state[0] ^= 0x03
        state[2] = True
    
    # PRNG is properly seeded now!
    my_choice = (state[0] & 0x8000) >> 15
    
    tap16 = (state[0] & 0x8000) >> 15
    tap15 = (state[0] & 0x4000) >> 14
    tap13 = (state[0] & 0x1000) >> 12
    tap4 = (state[0] & 0x0008) >> 3
    
    feedback = tap16 ^ tap15 ^ tap13 ^ tap4
    
    state[0] <<= 1
    state[0] &= 0xffff
    state[0] |= feedback
    
    return 'cd'[my_choice]

Flipper

def less_deterministic_flipper(p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state):
    if not state:
        state.append(0x21)  # Initial state
        state.append(4)  # Whether to collect more info for seed
        state.append(False)  # PRNG has been initialized?
        
        return 0
    
    if state[1]:
        # Seed the PRNG with the data we get
        state[0] <<= 1
        state[0] |= (p1_moves[-1] == 'd')
        state[0] <<= 1
        state[0] |= (p2_moves[-1] == 'd')
        state[1] -= 1
        
        return 0
    
    if not state[2]:
        # XOR with some data for some good old security through obscurity.
        state[0] ^= 0x44
        state[2] = True
    
    # PRNG is properly seeded now!
    first_bit = (state[0] & 0x8000) >> 15
    
    tap16 = (state[0] & 0x8000) >> 15
    tap15 = (state[0] & 0x4000) >> 14
    tap13 = (state[0] & 0x1000) >> 12
    tap4 = (state[0] & 0x0008) >> 3
    
    feedback = tap16 ^ tap15 ^ tap13 ^ tap4
    
    state[0] <<= 1
    state[0] &= 0xffff
    state[0] |= feedback
    
    second_bit = (state[0] & 0x8000) >> 15
    
    tap16 = (state[0] & 0x8000) >> 15
    tap15 = (state[0] & 0x4000) >> 14
    tap13 = (state[0] & 0x1000) >> 12
    tap4 = (state[0] & 0x0008) >> 3
    
    feedback = tap16 ^ tap15 ^ tap13 ^ tap4
    
    state[0] <<= 1
    state[0] &= 0xffff
    state[0] |= feedback
    
    # Use the two bits to make a choice
    choice = first_bit << 1
    choice |= second_bit
    
    return choice

Implements a simple PRNG that is seeded with the input we get from the opponent. With three total players in the mix, surely there's no way the others will be able to reliably influence our PRNG for their gain, right?

This bot is different from basic_random_flipper as it attempts to output a different sequence for each interaction.

Answer 16

Non-deterministic

EDIT: This bot is non-competing - see @isaacg's comment below.

Prisoner

def non_deterministic_prisoner(my_plays, their_plays, state):
    state.append(object())
    return 'cd'[hash(str(state)) % 128 < 65]

Flipper

def non_deterministic_flipper(p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state):
    state.append(object())
    return hash(str(state)) % 4

basic_random_flipper is in fact deterministic (in that it will flip the same way given the same state). This flipper relies on where it is placed in memory, which means it will output different results even if given the same state.

I suppose it's not technically non-deterministic as you could in theory predict where the objects will be created in memory.

Answer 17

FlipAsApplicable (flipper)

lambda *a:sum((+(a[0][-1] == "c"),2*(a[2][-1] == "c")))