Project1

标题: 只因世界如此 —— P1 囚徒困境锦标赛拾遗 [打印本页]
作者: LBQ    时间: 2018-1-15 02:45
标题: 只因世界如此 —— P1 囚徒困境锦标赛拾遗
本帖最后由 LBQ 于 2018-1-15 05:17 编辑

写在前面

其实我说真的，不是特别想来写这个，因为比赛反响有不是很好，投稿人也不是那么多。我也更不是研究这个的。

然后也许这个世界上，某个角落里，有专门研究这种基础博弈论的中文爱好者论坛。

这么一想，假如写篇文章说说游戏设计，也许还更好。不过也罢，无论是自己的问题，还是环境的制约。

于是我试图在我对这个有限的兴趣下，试图写下最有趣、最能给 P1 的人带来一定收获的文章。

囚徒困境

学过囚徒困境的可以跳过。

经典的囚徒困境，借用维基，是这样的：

警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人有罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择：

    若一人认罪并作证检控对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监10年。
    若二人都保持沉默（相关术语称互相“合作”），则二人同样判监半年。
    若二人都互相检举（互相“背叛”），则二人同样判监5年。

为了解释起来更清楚，借用知乎的语言：

一个犯罪团伙的两个成员(A和B)被拘捕了，他们完全被隔离开，互相之间绝对没有办法互通消息。警方目前缺乏证据，无法以他们所共犯的主要罪行来将他们定罪。但是警方手里有一些次要证据，可以较轻的罪名判他俩各一年。于是警方对他们分别同时提出了“浮士德”交易的条件（别管浮士德是什么，这不重要）：

1. 如果A和B都供述罪行，那么每人判两年。
2. 如果A供述，B不供述，那么A可释放，B要坐3年牢（反之亦然）
3. 如果A和B都不供述，那么他们每人要判一年。

我再解释的清楚一些。A和B对上面交易的3个条件各自都很清楚明了地知道。也就是说，他们知道警察手里的证据只够判每人一年的，如果没有这个交易，他俩也就是各坐一年牢完事。有了这个交易，他俩只要都不认罪，也还是只要坐一年。

另一个重要的假设条件：他俩都是所谓的“经济人”。也就是说，他们每个人做出的决策，都会以自己的利益最大化为目的。在这个“游戏”中，如果某犯的选择是不供述，那么我们把他的选择叫做“合作”（意指他试图采取跟另一名罪犯合作的策略，当然他必须指望对方也合作，才能获益）；如果某犯选择了供述，那么我们把他的这个选择称作“背叛”。


说到这里，我把关于这个交易该交代的都交代了。但是我多次发现，对于理科生，这些信息已经够了，但是文科生常常没看明白。鉴于电商多有文艺青年出身的掌柜，这里我再给一个文科生专用案情详述（理科生跳过吧）：

A和 B一起持枪抢银行，目前被拘捕关押，互相隔离。他们被抓的时候，随身搜出了没有登记过的点22口径手枪。但是除了非法持枪这个铁证之外，检方并没有确凿的证据来起诉他们抢银行的罪行。他们知道检方证据不足，所以他们现在只要一口咬定没抢银行，那就最多因非法持枪罪判一年。

对于警察来说，这也是个无奈的局面，谁让他们抓不到证据呢？ 可是这时有个年轻的检察官说：我有办法。这个聪明的检察官分别给A和B提供了相同的选择。他对他们分别说：
“你好哥们！我是地区检察官柯南。我现在经授权可以和你达成一个交易。交易的条件是这样的：你现在可以选择沉默，也可以选择把抢银行的事供出来。如果你供述了，而你的同伙保持沉默，那我可以放了你，但是你的同伙要判三年。反过来，如果你沉默，但是你同伙供述了，那同样，他就自由了，你要坐三年牢。如果你们两个人都供述认罪了，那你们各自要坐两年牢。但是如果你们俩都沉默，那我就只能以非法持枪罪起诉你们，每人判一年。你好好想想吧，明天早上之前写好你的选择，交给狱卒。”

好，我们来看一下他们的选择思路。假设你是A，你现在不知道B会怎么选，所以你必须考虑B做出每一种选择可能给你带来的后果。
假如B选择了沉默，那么你现在做哪个选择更划算呢？如果你沉默，那你坐一年牢；如果你供述，那么你可以不坐牢。所以如果B沉默的话，你应该选供述更划算。
假如B选择了供述，那你的两种选择分别会带来什么样的后果呢？ 如果你沉默，那你要坐3年牢；如果你供述，那你要被关2年。2年 v.s. 3年，那还是选供述更划算。
于是，无论B做哪个选择，你都应该选择供述更划算。于是，“供述”便是A唯一合理的理性的，利益最大化，损失最小化的选择。
同样的道理，B也会选择供述。这样一来，第二天早上我们这位聪明的检察官将会毫无悬念地得到两份认罪供述。
这个毫无悬念的结局就是经典囚徒困境的唯一答案（囚徒困境有其他条件变化而产生的变体，答案也随之会变化）。两个囚犯被这个游戏逼入了一个悲惨的困境，明明有一个“你好我也好”的可能，但是偏偏结果却必然是“你不怎样我也不怎么样”。而这个必然的结局就是著名的“纳什均衡点”。



作者：Roland Xu
链接：https://www.zhihu.com/question/19955241/answer/20092360
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

囚徒困境，多回合版本

现在我们从故事跳到理论，或者说，我们假设，我们故事的主人公 A 和 B 每周都会被抓起来，并且刑期改为罚款之类的，毕竟是理论游戏，不要在意细节，然后这样被抓了连续 100 次，也就说进行了 100 次上面的囚徒困境，并且当然，A 和 B 都记得之前对方是怎么决策的。

我们继续假设 A 和 B 的目标是使自己的刑期最小，而不是坑害对方。现在的主要区别是“A 或者 B 会为自己之前的行为付出代价”。

我个人的解释如下。

我们假设 A 和 B 被再次逮捕，这次 A 和 B 还是不互相相信，再度互相背叛。然后再度被逮捕，再度互相背叛，再度互相逮捕，直到有次，A 试图做了一次短期内不理性的决策“合作”。那么那次 B 就会被无罪释放，A 会受到最严重的惩罚。

那么 B 接下来，之后的回合会怎么做？

B 当然也可以继续无脑背叛 A，假设 A 下次还选择了合作，那么 B 诚然“赢了”，但是 A 也许也不再相信 B，之后他们继续永远背叛了下去。

假如 B 选择下回合合作的话，那么 A 也许与 B 之间建立了信任，那么 A 和 B 就会这样一直合作下去。

一直合作，比起一直背叛，最后两个人的刑期都会减少。这也可以说是理性的胜利。

值得注意的是，对于我们的 A，B 而言，他们目标不是“赢过对方”，对 A 来讲，假如他被判刑 2 年，是永远比他被判刑 3 年好的，无论 B 被怎么判，只要他自己被判的刑少就最好。

我们这次的游戏

我们假设这样，我们活在一个反乌托邦的未来社会，因为某种原因教育变得十分重要，所以学生会（就是各种学生啊）统治所有人，这里面，所有人因为个人力量的限制，都选择与另外一个人短期组队生存，一起对抗学生会，然后邪恶的学生会经常会逮捕这“一队人”。我们假设邪恶的学生会因为某种原因对每次逮捕的两个人实施囚徒困境策略，然后也只做短期的惩罚。

然后我也知道这个故事漏洞百出，但是，毕竟是纯理论游戏，各位就别太乱想。

然后我们假设这些学生会对抗军非常混乱，之间是没有多少交流的，也就说人与人，即使是短期的合作，也不能信任对方。

那么假设你是一个其中一个人，你和 B 组队了，你和 B 一起对抗学生会，然后你也知道，和学生会对抗的人，平均会被逮捕 100 次到 200 次，然后你某天睡觉前，突然想到，你之前执行的策略是“一直背叛”，无论对方中间是否显示出合作的意图。但是，你突然想起来我之前说的，中间合作反而惩罚更少，你开始思考自己的决策，并且最后思考出来了一个策略：

我一开始先显示出合作的倾向，第一回合先合作，之后的回合，如果对方背叛我一次（也就说第一回合不算），我就永远背叛

然后你执行这个策略，换了好几次搭档，发现比之前的“一直背叛”有效得多。

那好，假设你“退休”了，你的徒弟问你，应该采取什么策略，你会怎么回答？


我们这次的游戏：实际模拟版本

我们为了计算机模拟，以及数据分析方便，在此试图精准描述我们的游戏：

我们定义一个“回合”为一次囚徒困境的双方的决策。

我们定义一个“决策”或者“策略”为一个基于对方之前所有回合的行动，以及自己之前所有回合的行动，以及当前回合数，得出要不“合作”要不“背叛”的一个清晰逻辑。

我们定义“一局游戏”是随机的，100 回合，或者 200 回合（200 回合情况下最后得分减半），决策在游戏一开始不知道是 100 还是 200。游戏之间所有的决策的记忆会被清除。

我们按照分值量化判刑，分值越高，判刑越少。


所有策略的目标是最大化自己分值。

有两个赛制：

单循环赛

所有提交上来的策略都会互相跟对方比一遍，然后最后累计分数高的获胜。

生存模拟

所有策略定义为“种族”。



一上场所有种族都会被复制出 100 个个体。

循环开始：

这些个体，被两两互配，进行一局游戏，然后每个个体这样都会有计分。

最后种族的得分，是这个种族所有个体的得分的累计。

然后重新调整所有种族之间的个体比例，比例等同于这轮的种族的得分之间的比例。

如此循环 N 轮。


我们做 1000 轮循环，取第 100 轮结束时候结果，按照个体存活数量做排名，存活的越多越好。

剩下的 1000 轮循环的过程当参考。



参赛策略


主办方提交了三个策略。

【好人】永远合作
【坏人】永远背叛
【基础以牙还牙】第一回合背叛，之后重复对方上回合的决策。

剩下为 12 个“玩家”策略，因为之后公布排名的时候还会再复制一遍，已经折叠。

玩家策略


接下来是所有对局的展示，我先来给个图例：



以“余烬之中”vs“贝叶斯学派”为例。

一上场是对局名称，之后最底下有最后得出的分值（以及对应的换算的判刑年数）。

中间实际上有两个图，左边的线图，和右边的“决策图”。

图都是最上面为第一回合，最下面是最后一回合。

线图代表双方的得分变化，左边是正方向，红色代表 Player 2（vs 后面的人），黑色是 Player 1。

比如黑线在红线左边的时候，就代表余烬之中当时得分比贝叶斯学派高（等价于：余烬之中背叛了贝叶斯学派的合作）。

右边的决策图，代表了双方做的决策。

如果一个人的方向（左边为 P1，右边为 P2）有紫色，代表那一回合他背叛了对方的合作。

如果是亮绿色，代表两个人都选择了合作，如果是最宽的深蓝色，那么代表双方在互相背叛。

横向排在一起的对局代表同一时间举行的。比如说上图的所有对局是当时进行的“第一轮”。

之后往下会是第二轮第三轮。

下附上最后所有循环赛对局。



最终比分统计如下：

白色药草
4963
鑫晴
4878
琪露诺
4645
kise tsu
4598
复读机
4558
好人
4356
悪い魔
4348
凰之矢
4263
贝叶斯学派
3779
基础以牙还牙
3680
余烬之中
2982
坏人
2969
taroxd 萌新（编辑注：不是taroxd）
2846
鶸
2711
静寂之夜
2422


白色药草获胜。

之后是生存模拟的图：







100 轮的人口统计：

好人(coop)
243.12
复读机(repeater)
240.9
琪露诺(cirno)
238.78
鑫晴(mood)
236.69
kise tsu(kise)
216.34
凰之矢(arr)
204.68
悪い魔(ma)
181.2
白色药草(ming)
129
贝叶斯学派(bayes)
0
基础以牙还牙(tt)
0
余烬之中(esphas)
0
坏人(defect)
0
taroxd 萌新(taroxd)
0
鶸(weak_bird)
0
静寂之夜(ya)
0


因为好人是主办方提交的，所以复读机胜利。

策略注解

“鶸”:
随机（50%）从背叛和合作中选一个。

随机选择，给整个游戏增加混乱度用的，这种无法预测的策略在生存模拟中，导致一些后期比较成功的策略前期受挫。

克制了琪露诺。

“贝叶斯学派”
策略：若对方的历史记录选择合作较多，则选择合作；否则（若相等或对方选择背叛更多）选择背叛。

特点是第一回合会背叛，所以有些对抗策略看到这番景象也选择了背叛。于是有的时候就一直背叛了下去。

实际操作中也许是因为第一回合背叛而不被对手信任。

“复读机”
第一轮合作，以后选择对方上一回合的选择

这个是之前其他人的比赛中的最优选择，比较有趣的是在生存模拟中输给了好人，并且在循坏赛中也没有胜出。

我们这次的其他一些参赛策略真的比较奇怪，导致复读机没有直接胜利。

“琪露诺”
默认合作，如果对方在过去5回合内使用的背叛次数较多，就使用背叛

与随机算法对抗的时候弱，但是除此之外貌似结果很好。

“余烬之中”
rand() < 0.45 背叛，否则合作

比较有趣的是最终结果比“鶸”好。

“鑫晴”
1. 第一回合选择合作，之后一直选择合作。

2. 如果期间对方选择背叛，第一次被背叛依然选择合作，第二次被背叛则永远选择背叛。

这次有些参赛策略第一回合会背叛，但是之后假如合作的话是会选择合作的，鑫晴的这个策略能够让第一回合背叛的人之后合作。

“白色药草”
永远合作，如果对方累计背叛两次，则接下来永远背叛，第100轮必然背叛。

白色药草的策略跟鑫晴的几乎一样，但是加了第一百回合永远背叛，导致最后比鑫晴分高。

“taroxd 萌新”

全部背叛

因为这次很多策略喜欢合作，所以全部背叛最后判刑很高。


“木瀬津”

前五回合合作，后面每五回合执行对方前五回合执行得最多的。

类似于琪露诺的，不知道后面的“每五回合”是不是导致更加迟钝了一些。

“恶い魔”，
永远合作，如果无人背叛就永远合作，如果背叛一次就一直背叛，直到对方连续选了三次合作，就重新合作，如果再次背叛，永远不合作

特殊的是，有些策略会第一回合背叛，之后有可能合作，所以这个有可能会和对手一直背叛。

“静寂之夜”
如果第10回合有人背叛 那我从11回合开始就每隔一回合背叛，每隔2回合合作，如果第10无人背叛，那我则每隔1回合合作，每隔2回合背叛。
前十回合都随机 0.5 背叛。上法没有定义的回合，如果对方第十回合背叛过，0.75 几率背叛，否则 0.25 几率背叛

比较特殊的策略，跟其他随机性比较强的策略一样得分不好。

“凰之矢”
我的策略是：第一回合合作，之后如果对方曾背叛过，之后全部为背叛，否则合作，第200回合背叛。

有的游戏进行不到第 200 回合，并且对对方一次的背叛没有容忍。

主办方三策略。

【好人】永远合作 - 因为这次比赛喜欢合作的偏多
【坏人】永远背叛
【基础以牙还牙】第一回合背叛，之后重复对方上回合的决策 - 因为第一回合背叛，有的时候跟别人一起背叛到死

我们这次有比较多的改邪归正策略（第一回合背叛，之后看情况会合作）和善良策略（喜欢合作），而邪恶策略（喜欢背叛）也许太简单了些。

所以，也许在另一个世界，各位的特殊决策会更强吧。


模拟用源码（MIT 协议）

作者: 不死鸟之翼    时间: 2018-1-15 02:56
看了各位的策略 很有趣 有种AI猜拳的感觉
作者: ⑨姐姐    时间: 2018-1-15 08:42
最后一回合背叛的策略让人想到一些老人不守公德、为所欲为……
作者: zmj945    时间: 2018-1-15 10:16
作为理性的文科生前面的3个概率都看懂了。
后面的分析和运算真是非常知乎不得不说很强大啊。

已经脑补了平行世界的故事，还可以加上监狱游戏（心理学的那个著名案例）。
挖掘人性，呼唤真情23333
其实已经可以做游戏了。（掩面）
作者: 鑫晴    时间: 2018-1-15 11:11
这故事告诉我们，不要和坏叔叔们玩
作者: soulsaga    时间: 2018-1-15 14:16
我觉得应该禁止太随机性的策略..这样不好玩..
作者: 天使喝可乐    时间: 2018-1-15 19:22
虽然没看懂，但我好像获胜了
作者: 不死鸟之翼    时间: 2018-1-16 00:29
soulsaga 发表于 2018-1-15 14:16
我觉得应该禁止太随机性的策略..这样不好玩..

概率值也是策略的一部分）逃
作者: soulsaga    时间: 2018-1-16 12:27
不以胜利为目的的策略还是禁止算了吧..



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1