囚徒博弈的问题对看到本文的读者来说应该很熟悉了，在此就不多赘述。在现实中，囚徒困境显然存在多轮博弈的情况，并且往往更加常见。在 Effective Choice in the Prisoner’s Dilemma | Massachusetts Institute of Technology 这篇论文中对 15 种多轮囚徒博弈的策略进行了考察，完整的数据模拟还在进行中，但在复现论文实验结果的过程中，不妨先简要分析下 Nydegger 这个策略。
策略介绍
// 以下为论文原文。
Third Place with 485.5 points is a 23-line program by Rudy NYDEGGER of the Department of Psychology, Union College, Schenectady, New York. The program begins with tit for tat for the first three moves, except that if it was the only one to cooperate on the first move and the only one to defect on the second move, it defects on the third move. After the third move, its choice is determined from the 3 preceding outcomes in the following manner. Let A be the sum formed by counting the other’s defection as 2 points and one’s own as 1 point, and giving weights of 16, 4. and 1 to the preceding three moves in chronological order. The choice can be described as defecting only when A equals I, 6,7,17,22,23,26,29,30,31,33,38,39,45,49,54,55,58, or 61. Thus if all three preceding moves are mutual defection, A = 63 and the rule cooperates.
This rule was designed for use in laboratory experiments as a stooge which had a memory and appeared to be trustworthy, potentially cooperative, but not gullible (Nydegger. 1978).
第三名是纽约州斯克内克塔迪联合学院心理学系 Rudy NYDEGGER 的 23 行程序，得分 485.5 分。
程序开始前三步是针锋相对，但如果在第一步中只有它合作，在第二步中也只有它背叛，那么它在第三步就背叛。第三步之后，它的选择由前 3 个结果按以下方式决定。设 A 为将对方背叛算作 2 分，将自己背叛算作 1 分，按时间顺序对前三步分别赋予 16、4 和 1 的权重之和。仅当 A 等于 1、6、7、17、22、23、26、29、30、31、33、38、39、45、49、54、55、58 或 61 时，该选择才可描述为背叛。因此，如果前三步都是相互背叛，则 A = 63，规则合作。这条规则是为在实验室实验中使用而设计的，它记忆并且看起来值得信赖，可能合作，但不易受骗。
引入分析工具
前三步的针锋相对比较容易理解，基本就是 TitForTat 策略部分的短口径版本，这三步相对于完整的一轮模拟（200 回合）占比极少，就不再过多讨论这部分，而是更多关注在后面的部分上。后半部分的策略通过最近三轮的过程计算得到一个分数，然后检查这个分数是否在给定的列表中，如果是则这一轮选择背叛。
显然大家的注意力都不是那么足1，在这里还是将这个策略检查列表转写为可读性更高的版本，这里摘取了最中间的转换代码，完整代码可见于 nydegeer_explainer at master。
// 部分转换代码
func NewCase(no int) *Case {
if no < 0 || no >= MaxScore {
panic(fmt.Sprintf("wrong no of [%d]", no))
}
c := &Case{
No: no,
Rounds: [3]Match{},
}
for i := 0; i < 3; i++ {
k := no % 4
c.Rounds[2-i].OpponentAct = Act(k / 2)
c.Rounds[2-i].SelfAct = Act(k % 2)
no = no / 4
}
return c
}
这是工具输出的结果：actTable.log at master。
结果分析
策略分析
- 在最近三轮中，如果最后一轮双方都选择了合作，那么下一轮 Nydegger 策略一定会选择合作；
- 如果对方在最近三轮中，第一轮选择了合作，那么下一轮 Nydegger 策略也一定会选择合作；
- 在一些情况下，即使在过去三轮中，对方背叛的次数比自己还多，Nydegger 策略也愿意在下一轮中选择合作，例如 14、34、35、41、42、43、46、47、59 等；
- 在这样的场景下，Nydegger 有明显的劣势，例如当出现 score = 42 的场景下，自己一直选择合作，对方一直选择背叛，下一轮自己还会选择合作，如果对方一直选择背叛，那么会一直让对方拿到最高分。
- 因为前三轮是会 copy 对方上一轮的行动，所以如果对方在前三轮中选择合作，然后一直背叛，就会经历从 2 -> 10 -> 42 -> 42 -> … ，最终一直落在 42 情况，导致拿到极低的分数。
简要总结
在 Nydegger 策略中，我们可以看到有这么几个特点：
- 这是一个“善良”的策略，在所有的 64 种情况中，只有 19 种情况，会导致 Nydegger 策略在下一轮中选择背叛；
- 这个策略有少许“加倍奉还” & “抓着好人薅”的倾向，对应于 26、21&29 等情况；
- 这个策略有“悬崖勒马” & “主动示好” 的趋势，对应于 62、63 等情况。