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