English 中文(简体)
囚犯困境算法
原标题:
  • 时间:2008-09-24 12:11:36
  •  标签:

看完《黑暗骑士》后,我被“囚犯困境”的概念迷住了。必须有一种算法,在给定的情况下使自己的增益最大化。

对于那些觉得这是外国的人:http://en.wikipedia.org/wiki/Prisoner%27s_dilemma

非常非常有趣的东西。

编辑:问题是,如果有的话,什么是解决囚犯困境的最有效算法?

最佳回答

由于只有一个选择,并且在没有任何可变输入的情况下,您的算法将是:

cooperate = true;

cooperate = false

更有趣的是,找到一个解决反复囚犯困境的策略,这是许多人都做过的事情。例如http://www.iterated-prisoners-dilemma.info/

即便如此,这也是无法解决的,因为其他玩家是不可预测的。

问题回答

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

对于反复出现的囚犯困境,最好在第一次尝试时保持沉默,然后再做其他囚犯在最后一次尝试时做的任何事情。

困境的全部意义在于,最佳解决方案(两名囚犯都保持沉默)是危险的,因为部分问题不在你的掌控范围内。因此,选择次优解决方案似乎可以最大限度地提高收益,但它仍然是次优的

当问题的一部分是未知的时,我看不出算法如何提供解决方案。

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

对于一次性版本的游戏,最好的策略总是叛逃,因为没有报复的机会。

迭代版本变得更有趣,因为玩家可以对对手之前的选择做出反应。

如果我们事先确切知道会有多少轮,那么合乎逻辑的“最佳”策略仍然是始终缺陷。这是因为在最后一个转弯时叛逃总是有意义的,因为没有报复的机会。当然,我们理性的对手会知道这一点,而且总是在最后一个回合出现失误。这使得我们在倒数第二个转弯时叛逃是明智的,因为无论如何在最后一个转弯时都没有合作的机会。按照这个逻辑得出自然的结论,我们应该在每一个转折点上都有所缺陷。

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

根据尤瓦尔的建议,最好的起点可能是Axelrod的开创性书籍。如果你真的、真的对这些东西感兴趣,有一个20周年随访,其中包括其他研究人员关于IPD(迭代囚犯困境)的许多最新研究。

此外,我还彻底推荐了William Poundstone的《囚犯的困境》,这本书一部分是约翰·冯·诺依曼的传记,一部分是博弈论导论。

好吧,据我所知,模式识别也是其中的一个重要部分。发现另一个囚犯的习惯——他多久保持沉默一次,什么时候吸毒。你还必须将其与你自己的选择相互参照,以确定你做了什么让他做出某种反应。

我认为这比维基解释的要复杂一些。这不仅仅是囚犯在最后一次行动中所做的,而是在那之前的所有行动中,一直延伸到无限。

没有,因为你无法明确预测第二个囚犯的行为。

有各种各样的“解决方案”对第二名囚犯的行为做出了潜在但非常严格的假设,但对不受约束的问题却没有什么可说的(这就是为什么它会成为如此令人信服的困境)。

我的两分钱,考虑到你不能依赖第二个囚犯的行为,归根结底是:你是乐观主义者,还是愤世嫉俗者?这两个囚犯是要粘在一起(小偷中的荣誉),还是要一有机会就互相告发以保住自己的喉咙。。。?

此外,在迭代囚犯游戏中,最佳策略将根据游戏中的其他策略而变化。

在与一个总是有缺陷的球员的系列赛中,叛逃是最好的策略。当与可能合作的球员比赛时,最好的策略是报复,但偶尔会原谅。

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

试图为囚犯的困境找到一个最佳解决方案就像试图为Ro Sham Bo(石头剪刀)找到一个。你能做的最好的事情就是模仿你的对手,并尝试利用模式。

在博弈论和计算机科学的早期,约翰·冯·诺依曼和兰德公司花费了大量的精力,试图找到一个解决囚犯困境的最佳算法,但没有成功,最终在数学上证明了没有最佳解决方案。

啊,是的。这让我想起了这篇关于软件开发中的囚徒困境

对于算法PD竞争,请查看此处

这个也不错

囚犯困境的全部意义在于,你的最佳策略是背叛另一个囚犯。O(1)

从数学上讲,其他帖子回答了这个问题,但实际上,可能还有其他选择。无论这些选择多么荒谬,它们都会带来额外的结果可能性,并可能增加个人收益的机会。例如,在蝙蝠侠的案例中,这会破坏剧情,但他本可以杀死小丑——从而破坏小丑对结局的任何额外影响。通过让小丑活下来,蝙蝠侠无意中让小丑获得了他所需要的唯一“胜利”。

当你退一步考虑整个比赛时,比赛会变得更加有趣。例如,几年前,一支来自英国的球队赢得了一场PD锦标赛,该球队提交了多个参赛作品。他们中的一个是“主人”,另一个则是“奴隶”。他们都会从播放一系列特定的动作开始,这将允许主人和奴隶相互识别。一旦被识别,主设备将出现故障,而从设备将在剩余的迭代中进行协作。因此,主人赢得了比赛,但代价是奴隶。

这一策略在经济上是有意义的,因为第一名有货币奖励,但进入成本很低。

更普遍地说,在为TD锦标赛编写程序时,您需要着眼于大局:

  1. how are the prizes awarded?
  2. can you conspire with other contestants?
  3. what are the costs of entry? penalties?

否则,是的,主要策略是在一杆PD中叛逃。正如其他人所提到的,阿克塞尔罗德在一系列比赛中表明,针锋相对是强有力的,但在这些比赛中,没有人想过与其他参赛者合谋。





相关问题