Best Iterated Prisoner's Dilemma Move

Question

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 code-golf, 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
```

Answer 1

Haskell,  96  89 bytes

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

Answer 2

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
      ) +           //       add not(p)
      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

Answer 3

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!

Answer 4

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}
     ]
    ]
   ];

Answer 5

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.