# Best Iterated Prisoner's Dilemma Move

## Introduction

In the prisoner's dilemma, two partners in crime are being interrogated, and have the choice to either betray their partner or stay silent.

• If both prisoners betray each other, they both get 2 years in prison.
• If neither betrays (both stay silent), they both get 1 year in prison.
• If only one betrays and the other stays silent, then the betrayer gets no prison time, but the other gets 3 years in prison.

In the iterated version of the dilemma, this situation is repeated multiple times, so the prisoners can make decisions based on the outcomes of previous situations.

## Challenge

Imagine that you are a player participating in this dilemma against an opponent.

Your opponent is described by a function $$\f: M \mapsto m\$$, where $$\m = \{s,b\}\$$ is the set of "moves" player can make (stay silent or betray) and $$\M = [(m_{1o}, m_{1p}), (m_{2o}, m_{2p}), \ldots]\$$ is a list of all the previous moves that your opponent and you made. In other words, given all the moves made in the game so far, the function outputs a new move. (Note that this is deterministic; also, the opponent's move can depend on its own previous moves as well as the player's.)

Your code should take as input the opponent's function $$\f\$$ and some number $$\n\$$ and return the maximum reward which the optimal player can receive within $$\n\$$ iterations (i.e. the minimum number of years that the optimal player will stay in jail). You can output this as either a positive or negative integer.

You can use any two distinct symbols to represent the two moves, and the input format for the function is flexible (e.g. it could also take in two different lists for the opponents and player's previous moves.)

Standard loopholes are forbidden. Since this is , the shortest code wins.

## Examples

(All the code examples will be in JavaScript; I will use 0 for the "stay silent" move and 1 for the "betray" move.)

If your opponent always stays silent, i.e. they are defined by the function

opponentFunc = (opponentMoves, playerMoves) => 0


Then it is in your best interest to always betray, so

playerFunc(opponentFunc, 1) //=> [1], reward=0
playerFunc(opponentFunc, 3) //=> [1,1,1], reward=0


Suppose your opponent employs the "tit for tat" strategy: stay silent on the first move, then does whatever the player did on the previous move. In other words, they are defined by the function

opponentFunc = (opponentMoves, playerMoves) => (playerMoves.length==0) ? 0 : playerMoves[playerMoves.length-1]


In that case the best actions to take are to stay silent until the final turn, where you betray; i.e.

playerFunc(opponentFunc, 1) //=> [1], reward = 0
playerFunc(opponentFunc, 3) //=> [0,0,1], reward = -2


Here is a recursive reference implementation in JavaScript:

reward = (opponentMove, playerMove) => [[-1,0],[-3,-2]][opponentMove][playerMove]
playerReward = (oppFunc, n, oppMoves=[], plaMoves=[], oppNextMove = oppFunc(oppMoves,plaMoves)) =>
(n==0) ? 0 : Math.max(
reward(oppNextMove,0)+playerReward(oppFunc, n-1, oppMoves+[oppNextMove], plaMoves+[0]),
reward(oppNextMove,1)+playerReward(oppFunc, n-1, oppMoves+[oppNextMove], plaMoves+[1])
)

//Testing
opponentFunc = (opponentMoves, playerMoves) => (playerMoves.length==0) ? 0 : playerMoves[playerMoves.length-1]
console.log(reward(opponentFunc, 5)) //=> -4
$$$$

• @Arnauld Yes,because of the definition of a function. Jan 26 at 14:37
• @Arnauld Fixed. Jan 26 at 18:20
• IIRC if the total number of iterations is known in advance (which is the setting you are talking about) then the game theoretic winning strategy is still to just play 'betray' every single time (proven by induction starting at the last game). Only if the number of iterations is unknown more complex strategies arise. Jan 27 at 12:53
• @quarague The unique subgame perfect Nash equilibrium is that both players choose 'betray' every time, but that doesn't mean it is the best response to every possible strategy your opponent might have. The "tit for tat" strategy described in the challenge is an example where choosing 'betray' every time is not the best response. Jan 27 at 14:07
• I'm impressed by JavaScript's ability to understand my obviously incorrect code, haha Jan 28 at 16:01

a#b=3-b-2*a
(f%l)0=0
(f%l)t=min(f l#0+(f%((f l,0):l))(t-1))((f l#1+(f%((f l,1):l))(t-1)))


Attempt This Online!

-1 byte by Kevin Cruijssen

• Welcome to Code Golf! Just to let you know, you can click the blue button in the top right of Attempt This Online to automatically generate a CGCC submission for you (yours looks like it was written manually). Jan 26 at 23:15
• I don't know Haskell, but I'm pretty sure you can save a byte by removing the space at ,0. Jan 27 at 7:38

# JavaScript (ES6),  96 92  90 bytes

Expects (opponentFunc)(n), where opponentFunc takes a flat array of moves $$\[m_{1o},m_{1p},m_{2o},m_{2p},\dots]\$$ with $$\0\$$ for silent and $$\1\$$ for betray. Returns a positive integer.

F=>m=g=(n,i)=>i>>n?m:g(n,-~i,(h=M=>s=n--&&!(p=i>>n&1)+h([...M,M=F(M),p])+M*2)([])>m?0:m=s)


Try it online!

### Encoding

Using $$\0\$$ for silent and $$\1\$$ for betray, the outcome is defined by the following table:

p (player) o (opponent) years in prison (for the player)
0 0 1
0 1 3
1 0 0
1 1 2

which is $$\o\times2+(1-p)\$$, or o * 2 + !p as JS code.

### Commented

F =>                // F = opponent function
m =                 // m = maximum outcome, initially non-numeric
g = (n, i) =>       // g is the outer recursive function,
// trying all possible move sequences
i >> n ?            // if i has reached the upper bound 2**n:
m                 //   stop and return m
:                   // else:
g(                //   do a recursive call:
n,              //     pass n unchanged
-~i,            //     increment i
( h = M =>      //     h is the inner recursive function,
//     testing a specific move sequence
s =           //     save the final score in s
n-- &&        //     if n is not 0 (decrement afterwards):
!(p =         //       compute the player's move p,
i >> n & 1  //       which is the n-th bit of i
h(            //       add the result of a recursive call:
[ ...M,     //         update M[]
M = F(M), //         by adding the opponent's move
//         (reuse M to store it)
p         //         and the player's move
]           //
) +           //       end of recursive call
M * 2         //       add twice the opponent's move
)([])           //     initial call to h with M[] = []
> m ? 0 : m = s //     update m to min(m, s)
)                 //   end of recursive call

• @DominicvanEssen I think you should have moves.length<6 instead of moves.length<=6 in your opponent's function. Jan 28 at 12:56
• yes, I realised that as you were replying. Sorry for my terrible attempt at cobbling-together Javascript! The .length value is rather counter-intuitive to me... Jan 28 at 12:58

# Python, 148 bytes

lambda g,n:max(product((0,1),repeat=n),key=lambda i:sum([1,3,0,2][k*2+l]for k,l in zip(i,[g(i[:j])for j in range(len(i))])))
from itertools import *


Attempt This Online!

• Don't we have to output the 'reward' as an integer rather than the sequence of moves? Jan 26 at 21:21
• Also note that the opponent's next move can also depend on the previous moves by the opponent, not just the player's moves. Jan 27 at 16:47
• The opponent would already know their own moves though Jan 27 at 17:00
• you can remove the space after import for -1 byte
– c--
Jan 27 at 20:10

# Wolfram Language (Mathematica), 86 bytes

If[#2==0,0,Min@Table[2 #1[#3]-i+1+#0[#1,#2-1,Append[#3,{i,#1[#3]}]],{i,0,1}]]&[##,{}]&


Try it online!

Full version:

ClearAll;

reward[moves_List] := 2 moves[[2]] - moves[[1]] + 1;

(*Tit-For-Tat*)
oppFuncTFT[moves_List] := If[moves == {}, 0,
moves[[-1, 1]]];

(*Win-Stay,Lose-Switch*)
oppFuncWSLS[moves_List] := If[moves == {}, 0,
With[{prev = moves[[-1]], switch = Abs[# - 1] &},
If[reward[Reverse@prev] >= reward[prev], prev[[2]],
switch[prev[[2]]]]
]
];

totalPlayerReward[oppFunc_Symbol, n_Integer, moves_List: {}] :=
With[{oppNextMove = oppFunc[moves]},
If[n == 0, 0,
Min[
reward[{#, oppNextMove}] +
totalPlayerReward[oppFunc, n - 1,
Append[moves, {#, oppNextMove}]]
& /@ {0, 1}
]
]
];


# Python, 68 bytes

f=lambda o,n,*M:n and min(3**o(M)-p+f(o,n-1,*M,o(M),p)for p in[0,1])
`

Attempt This Online!

The opponent function uses the same interleaved moves format as @Arnauld's answer, outputs a positive number. I used pysearch to find a compact expression for determining the reward.