看完《黑暗骑士》后，我对囚徒困境的概念非常着迷。在某种情况下，必须有一种算法可以最大化自己的收益。

对于那些发现该外国人的人：http://en.wikipedia.org/wiki/Prisoner%27s_dilemma

非常非常有趣的东西。

编辑：问题是，对于囚徒困境，最有效的算法是什么？

解决方案

困境的全部是，最佳解决方案(两个囚犯都保持安静)很危险，因为部分问题不在掌控之中。因此，选择次优解决方案似乎可以最大程度地提高收益，但仍然不理想

当部分问题未知时，我看不到算法如何提供解决方案。

没错。这使我还记得这篇关于软件开发中囚徒困境的旧文章。

对于算法PD竞赛，请点击此处

这也是一个很好的

维基百科页面似乎给出了所有答案……针对一次囚犯的困境，针对每个囚犯(不是两个囚犯)的最佳解决方案是出卖。

对于反复犯人的困境，最好在第一次走动时保持沉默，然后再做其他犯人在最后走动时所做的事情。

因为我们无法明确地预测第二名囚犯的行为，所以没有。

各种各样的"解决方案"都对第二名囚犯的行为做出了基本的但非常严格的假设，但对于无约束的问题却无话可说(这就是使它如此令人信服的困境)。

鉴于我们不能依靠第二名囚犯的行为，我的两分钱归结为：我们是乐观主义者还是愤世嫉俗者？这两个囚犯是要团结在一起(在盗贼中间名声高涨)，还是他们会在第一个机会互相勾结以挽救自己的嗓子……？

好吧，据我所知，模式识别也是其中很大的一部分。寻找另一名囚犯的习惯，他多久保持安静和何时自觉。我们还必须交叉参考自己的选择，以确定我们为使他以某种方式做出反应所采取的措施。

我认为它比Wiki解释的要复杂一些。这不仅是囚犯在最后一刻所做的，而且在那之前一直延伸到无穷无尽。

此外，在反复进行的囚徒游戏中，最佳策略将根据进行中的其他策略而有所不同。

在对一个总是有缺陷的玩家进行的系列赛中，总是背叛是最好的策略。当与可能合作的玩家对战时，采取一种报复但偶尔原谅的策略可能是最好的。

我应该补充一点，这仅适用于长度未知的游戏。任何已知长度的游戏都与单局游戏相同。

试图为囚徒困境找到最佳解决方案就像为Ro-Sham-Bo(剪刀石头布)寻找解决方案。我们能做的最好的事情就是为对手建模并尝试利用模式。

在游戏理论和计算机科学的早期，约翰·冯·诺伊曼(John von Neumann)和兰德公司(Rand Corporation)花费了大量的头骨汗水，试图提出一种解决囚徒困境的最佳算法，但没有成功，iirc最终在数学上证明了没有最佳解决方案。

由于只有一种选择，并且在没有任何可变输入的情况下，算法或者是：

cooperate = true;

...或者...

cooperate = false

找到针对囚徒困境的策略，这是很多人都做过的事情，这更有趣。例如http://www.iterated-prisoners-dilemma.net/

即使那样，它也不是"可解决的"，因为另一个参与者是不可预测的。

我建议阅读Axelrod的《合作的演变》。这是针对被囚徒困境的竞争策略的计算机实验。当我最后一次听说时，针锋相对的策略首先出现了。它可能已更改。

囚徒困境的全部要点是，最佳策略是出卖另一名囚犯。 O(1)

对于一次性版本的游戏，最佳策略始终是缺陷，因为没有报复的机会。

对于迭代版本，它变得更加有趣，因为玩家可以响应对手的先前选择。

如果我们事先确切知道将要进行多少回合，那么逻辑上的"最佳"策略仍将始终存在缺陷。这是因为由于没有报复的机会，所以在最后一回合总是背叛是有意义的。当然，我们的理性对手会知道这一点，并且总是在最后一回合中失误。这使我们明智地在倒数第二个弯道上犯错，因为无论如何在最后弯道上没有合作的机会。按照这一逻辑得出其自然结论，我们应该在每一个步骤中都存在缺陷。

当回合总数未知时，事情会变得更加有趣。一个好的游戏策略应该尝试预测对手会做什么。我研究了使用进化算法和简单的机器学习以及对手建模方法来为我的硕士学位生成游戏策略。如果我们真的有兴趣，可以阅读我的论文。

根据尤瓦尔(Yuval)的建议，最好的起点可能是阿克塞尔罗德(Axelrod)的开创性著作。如果我们真的很感兴趣，可以进行20周年的后续活动，其中包括许多其他研究人员在IPD(迭代囚徒困境)方面的最新作品。

此外，我还彻底推荐了威廉·庞德斯通(William Poundstone)的《囚徒困境》，这是约翰·冯·诺伊曼(John von Neumann)的传记，也是博弈论的一部分。

数学上其他职位回答了这个问题，但实际上，可能还有其他选择。无论这些选择多么荒谬，它们都将带来更多的结果可能性，并可能导致个人获利的机会增加。例如，在蝙蝠侠案中，这将破坏情节，但他本来可以杀死小丑，从而破坏小丑对结果的其他影响。通过让小丑活下去，蝙蝠侠不知不觉地允许小丑获得他唯一的"胜利"。

当我们退后一步并考虑整个比赛时，游戏变得更加有趣。例如，几年前，来自英国的一支团队赢得了一项PD比赛，该团队提交了多项参赛作品。其中一个是"主人"，另一个是"奴隶"。它们都将通过执行特定的动作序列开始，这些动作序列将使主机和从机能够相互识别。一旦认识到，主机将有缺陷，而从机将在其余的迭代中进行协作。因此，主人赢得了比赛，但付出了奴隶的代价。

该策略具有经济意义，因为第一名获得了金钱奖励，但参赛费用很低。

更一般而言，在为TD锦标赛编写程序时，我们需要查看更大的图景：

• 奖项如何颁发？
• 你可以和其他参赛者合谋吗？
• 入境费用是多少？罚款？

否则，是的，主要策略是缺陷单发PD。正如其他人所提到的，阿克塞尔罗德(Axelrod)表明，在一系列比赛中针锋相对很强，但是在这些比赛中，没有人想到与其他选手共谋。