最佳迭代囚徒困境移动
Introduction
在囚犯的困境中，两个犯罪伙伴正在接受审讯，他们可以选择要么背叛他们的伴侣，要么保持沉默。
- 如果两名囚犯都背叛了对方，他们都会被判两年徒刑。
- 如果两个人都不背叛(都保持沉默)，他们都会被判一年监禁。
- 如果只有一个背叛而另一个保持沉默，那么背叛者就没有被监禁的时间，而另一个则被判3年监禁。
在这种困境的迭代版本中，这种情况会重复多次，因此囚犯可以根据先前情况的结果做出决定。
挑战
想象一下，你是一个面对对手的进退两难的球员。
你的对手被一个函数f: M \mapsto m描述，其中m = \{s,b\}是玩家可以做的一组“移动”(保持沉默或背叛)，M = [(m_{1o}, m_{1p}), (m_{2o}, m_{2p}), \ldots]是你和你的对手之前所有动作的列表。换句话说，考虑到到目前为止在游戏中所做的所有动作，这个函数会输出一个新的动作。(请注意，这是确定性的；而且，对手的移动可以取决于自己以前的移动以及玩家的移动。)
您的代码应该以对手的函数f和某些数字n作为输入，并返回最优玩家在n迭代中可以获得的最大奖励(即最优玩家将被关押的最小年限)。您可以将其输出为正整数或负整数。
您可以使用任意两个不同的符号来表示这两个动作，并且函数的输入格式是灵活的(例如，它还可以为对手和玩家以前的动作接受两个不同的列表)。
标准漏洞是被禁止的。因为这是密码-高尔夫，最短的代码就赢了。
示例
(所有代码示例都在JavaScript中；我将使用0表示“保持沉默”，使用1表示“叛变”移动。)
如果你的对手总是保持沉默，即他们是由函数定义的。
opponentFunc = (opponentMoves, playerMoves) => 0那么总是背叛是你的最大利益，所以
playerFunc(opponentFunc, 1) //=> [1], reward=0
playerFunc(opponentFunc, 3) //=> [1,1,1], reward=0假设你的对手使用“以牙还牙”的策略:在第一步保持沉默，然后做玩家在前一步所做的任何事情。换句话说，它们由函数定义。
opponentFunc = (opponentMoves, playerMoves) => (playerMoves.length==0) ? 0 : playerMoves[playerMoves.length-1]在这种情况下，最好的行动是保持沉默，直到最后一轮，在那里你背叛；
playerFunc(opponentFunc, 1) //=> [1], reward = 0
playerFunc(opponentFunc, 3) //=> [0,0,1], reward = -2下面是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
```回答 2
Code Golf用户
发布于 2023-01-26 18:32:56
Code Golf用户
发布于 2023-01-27 17:02:46
Python，68字节
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])对手函数使用与@Arnauld的答复相同的交错移动格式，输出一个正数。我使用吡虫啉找到一个简洁的表达式来确定奖励。
https://codegolf.stackexchange.com/questions/257097
复制相似问题
腾讯云开发者
