题

看完“黑暗骑士”之后，我对“囚徒困境”的概念变得十分着迷。 必须是一种算法，可以在给定情况的情况下最大化自己的收益。

对于那些发现这种外国人的人： http://en.wikipedia.org/wiki/囚犯％27s_dilemma

非常非常有趣的东西。

编辑：问题是， 是什么，如果有的话，是囚徒困境中最有效的算法？

有帮助吗？

解决方案

由于只有一个选择，并且在没有任何可变输入的情况下，您的算法要么是：

cooperate = true;

...或... 

cooperate = false

找到迭代囚徒困境的策略更有意思，这是许多人所做的事情。例如 http://www.iterated-prisoners-dilemma.net/

即便如此，它也不是“可以解决的”，因为另一个玩家是不可预测的。

其他提示

维基百科页面似乎给出了所有答案......对于一次性囚犯的困境，每个囚犯（不是两个囚犯）的最佳解决方案就是背叛。

对于重复囚犯的困境，最好在第一时间保持沉默，然后在那之后做其他囚犯在最后一次做的事情。

困境的全部意义在于最佳解决方案（两个囚犯都保持安静）是危险的，因为部分问题不在您的手中。因此，选择次优解决方案似乎可以最大化您的收益，但它仍然不是最理想的

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

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

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

迭代版本会变得更有趣，因为玩家可以回应对手以前的选择。

如果我们事先知道将会有多少回合，那么逻辑上的“最佳”回合策略仍然是永远的缺陷。这是因为在最后一回合缺陷总是有意义的，因为没有报复的可能性。当然，我们理性的对手会知道这一点，并且在最后一回合也总是有缺陷。因为在最后一回合没有合作的机会，所以我们在倒数第二轮就有缺陷是明智的。按照这个逻辑得出它的自然结论，我们应该在每个转折点都有缺陷。

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

根据Yuval的建议，最好的起点可能是 Axelrod的开创性着作。如果你真的，真的对这些东西感兴趣，那就有一个 20周年纪念活动，包括其他研究人员最近关于IPD（迭代囚徒困境）的工作。

另外，我彻底推荐了William Poundstone的囚徒困境，是约翰冯诺依曼的部分传记和博弈论的部分介绍。

嗯，据我所知，模式识别也是其中很重要的一部分。寻找另一个囚犯的习惯 - 他多久经常保持安静，何时蹲下。你还必须交叉引用你自己的选择，以确定你做了什么让他以某种方式作出反应。

我认为它比维基解释的要复杂一点。它不仅仅是囚犯在最后一次行动中所做的事情，而且在所有事情发生之前都延伸到了无限。

没有，因为你不能断然预测第二个囚犯的行为。

有各种各样的“解决方案”。对第二个囚犯的行为做出潜在但非常严格的假设，但他们对无约束的问题几乎没有什么可说的（这就是使其成为一个引人注目的困境的原因）。

我的两分钱，因为你不能依赖第二个囚犯的行为是因为它归结为：你是乐观主义者还是愤世嫉俗者？这两个囚犯是否会团结在一起（小偷之间的荣誉），还是他们会在第一次拯救自己的喉咙时互相争吵......？

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

在针对总是缺陷总是叛逃的玩家的系列赛中是最好的策略。当与可能合作的玩家对战时，一种报复的策略，但偶尔会被宽恕，这可能是最好的。

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

试图找到囚徒困境的最佳解决方案就像试图为Ro-Sham-Bo（石头剪刀）找到一个解决方案。你能做的最好的事情就是塑造你的对手并尝试利用模式。

在游戏理论和计算机科学的早期，John von Neumann和兰德公司花费了大量的头骨汗水试图找出一个解决囚徒困境的最佳算法而没有成功，并且最终在数学上证明了没有最佳解决方案。

啊，是的。这让我记得这篇关于软件开发中的囚徒困境的旧文章

对于算法PD比赛，请参阅此处

这个也很好

囚徒困境的全部意义在于，你的最佳策略是背叛另一名囚犯。 O（1）

在数学上，其他帖子回答了这个问题，但实际上，可能还有其他选择。无论这些选择多么荒谬，它们都会带来额外的结果可能性，并且可能会增加个人收益的机会。例如，在蝙蝠侠的情况下，它会破坏情节，但他可能刚刚杀死了小丑 - 从而破坏了小丑对结果的任何额外影响。通过让小丑活着，蝙蝠侠在不知不觉中让小丑成为唯一的“胜利”。他需要。

当您退后一步并考虑整个锦标赛时，游戏会变得更加有趣。例如，几年前，来自英国的提交多个参赛作品的团队赢得了PD比赛。其中一个是“主人”。另一个是“奴隶”。它们都将通过播放特定的动作序列开始，这些动作将允许主人和奴隶相互认识。一旦被识别，主设备就会出现故障，并且从设备将在剩余的迭代中进行协作。因此，大师赢得了比赛，但牺牲了奴隶。

该战略具有经济意义，因为首先获得了奖金，但进入成本却很低。

更一般地说，在为TD锦标赛编写程序时，您需要查看更大的图片：

  1. 如何颁发奖品？
  2. 你可以和其他参赛者合谋吗？
  3. 入境费用是多少？处罚？

    4. 否则，是的，主导策略是在一次性PD中出现缺陷。正如其他人所提到的，阿克塞尔罗德在一系列比赛中表现出针锋相对的强势，但在这些比赛中，没有人想过与其他参赛者合谋。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top