杀人的理论分析

zhiqiang十一月 10, 2007 自然科学

“杀人”，英文名为"Mafia Game"，广泛流传于国内外。上个星期我们在玩的时候被Elchanan Mossel发现，然后他给了一个talk，内容就是杀人的理论分析。

他的论文在这里：Mafia : A Theoretical Study Of Players and Coalitions in a Partial Information Environment。

不过很可惜的是，国外和国内的游戏规则差别太大，比如他们玩游戏的时候每个人死了之后身份便会公开，这样便使得游戏的模型化成为可能，否则数学对对我们玩的个人心理站可无能为力。

在没有警察的游戏中，规则比较简单，有一个结论是杀手的数量应该是 $\sqrt{C}$ 量级的，大概是 $M=0.643\sqrt{C}$ 时，游戏才会平衡，其中C是平民数...不过这都要是C比较大的时候，否则怎么叫作"理论分析"呢

但当有警察的时候，哪怕只有一个，杀手数需要和平民保持线形的关系，游戏才会平衡。

休息时间：来大斗智力吧，你选哪边？

扑克牌大战

关于mafia game, 杀人, 概率, 游戏 »

摸箱子问题以及在Static data structure problems上的应用以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆...
取硬币游戏 $$n$$枚硬币排成一排，两人轮流取，每人每次可取其中一枚或者相邻的两枚。取到最后一枚硬币的赢得游戏。分析游戏策略。取到最后一枚硬币的算...
Tower Defense游戏盘点 PS1：Work hard, play hard PS2：星际争霸里有一类block的RPG游戏，差不多是诸多RPG里面最流行的。Tow Defense可以视作block RPG游戏的网页版，玩起来更方便。正...
来活跃活跃大脑多做思维游戏有助于保持和提高智商选钱袋现在有两个人，"酷毙"与"帅呆"，正在花园里一边喝着酒，一边讨论关于精灵的神话。正好有个精灵从此...
Windows游戏中的NP完全问题上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌...
空当接龙中最难的关空当接龙可说是最耐玩的Windows小游戏之一，尤其在办公一族中长盛不衰。Win98中的空当接龙有32000局，在XP里面则增加到了 1000000关，不过前32000关与Win9...
硬币游戏 Alice和Bob两人玩一种硬币游戏。游戏在一个$$2\times2$$的棋盘上进行，棋盘上每个格子上都有一枚硬币。在每一回合，Alice可以决定选择翻转某两枚或者一...
"完美"的洗牌次数 - 7次在大家玩牌的时候，每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌，但多少次洗牌才是正当的呢？就我多次打牌的观察，...
三门问题及相关写篇三门问题的终结版。欢迎补充材料。三门问题，亦称为蒙特霍问题（英文：Monty Hall problem），最初的表述形式：参赛者会看见三扇关闭了的门，...
帽子游戏二这个题目听说是MSRA的面试题。在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参...

44条留言 -> 跳到留言表格

At 2007.11.10 14:40, 老豆豉 said:

我选多
出牌数序：
1、3+4+5+6+7
2、3条Q+5+4
3、3条K+7+6
4、2
5、99

[Reply]
At 2007.11.10 14:40, 老豆豉 said:

错了啊，没看清题目。

[Reply]
At 2007.11.10 14:56, 虫子 said:

呵呵，

先出方块同花顺和 3\4\5\6\7

过后必胜

[Reply]
At 2007.11.10 15:55, lost said:

选多的赢

先出3,对方拆j的话,我就拆k,q都可以,如果对方拆A,那么我先不出,等对方出牌,最后牌多的赢.

[Reply]
- At 2008.02.06 13:58, 聦 said:
  
  若对方什么都不出呢？
  
  [Reply]
  - At 2009.04.22 03:08, hi said:
    
    那就出K，
    a.下A，就上2，。。。
    b.不下，出单4，若下J，出Q，下A出2，不下继续单。。。。
    
    [Reply]
At 2007.11.10 16:15, kun said:

選多~先出方塊457QK
再出34567
這時剩下62一張同9QK個一對
出單張6，此時只要另到對方出單張A就勝出

[Reply]
- At 2007.11.27 10:57, kend said:
  
  你这里假设了你出6时候，对家一定要出牌，若对家不出A。
  6-》J（你只能挑Q,K,2否则输）-》Q，K（对家不出），出Q，K（这里如果拆开两个单排必输）对家不出，假设剩下2，一对9和一对K，因为对家有一对A，拆开K必输，所以必须拆9，9-》J，之后就不用说了必输。
  
  那你就输定了。
  
  [Reply]
  - At 2008.05.21 15:30, am said:
    
    剩下2、对9和对K，你剩下J和对A，为什么我拆开K必输？
    就拆开K挑你，你拆A还是不拆？你拆了就用2打住，然后出对9，你只有一个J和一个A了，怎么让我必输？你不拆A，再出剩下的K挑死你！你拆不拆A都是死定了，还怎么让我必输？
    
    [Reply]
    - At 2008.06.28 09:05, ALIST said:
      
      怎么是一个J应该是两个J
      
      [Reply]
At 2007.11.12 20:31, 苗苗 said:

哪要那么麻烦，出单张。
只要将对方A对拆开就赢。

[Reply]
- At 2007.11.14 08:42, 虫子 said:
  
  直接拆单张肯定是有问题的。
  
  如果拆比 J小的，对方直接拆JJ。
  
  如果是必J大，比A小的，第一个对方不要，第二个，对方出一个A，
  
  这样，无论用2与否，对方的A，将会占优势。
  
  [Reply]
  - At 2008.06.27 22:07, Jack said:
    
    直接拆单张似乎可以
    直接出3，对方是否出Jack？分支A：
    A1：不出Jack就继续出4；是否继续跟Jack？当然还是不出……子子孙孙无穷匮也……出完了……
    A2：出Jack就跟进Queen，是否跟进Ace？出现选择B
    B1：是。我2大，我出牌。此时对方一个Ace，一个Jack，我手中没有Single，赢了
    B2：否。我出牌，重新出4，此时一个2，tripleKing，doubleQueen，下面一手double，加一个4，对方是否继续跟进那个Jack？出现选择C
    C1：否。这种可能性不大，对方手中是一个singleJack 和 doubleAce。不出的话就让我一张张直接出到tripleKing……
    C2：跟进。我手中doubleQueen不能拆，出King，你是否跟进Ace？此时你手中只有doubleAce。我手中是(5 to 9)*2，Queen&King doubled,一个2,single4.只要先出single4，对方无法跟进A,因为我手中都是2，且下面的牌都是Double，然后把所有的Double都拆分成Single依次放出……和上面的一样了。
    
    [Reply]
At 2007.11.13 12:24, zhiqiang said:

我也觉得似乎没有什么好选择的，牌多的一方有好几种方法获胜。但真就这么简单么？这是街头真实拍摄下来的呢。

高中的时候我遇到一次，象棋残局，任选一方，和棋就算赢，5块棋一次。当时也以为很简单，5块钱上去赌了一次，结果没走几步就被人弄死了。

[Reply]
At 2007.11.26 18:16, rainfiel said:

牌多的输

[Reply]
At 2007.11.28 20:35, rainfiel said:

哦看错条件了, 居然还讲同花, 有点不伦不类, 还以为是斗地主的规则呢, 不讲同花还有点玩头

[Reply]
At 2008.02.06 21:10, 聦 said:

终于想到了...
我们要想赢，必选多的那副，否则肯定被摆摊主打赢...

我们首先出3（梅）4（梅）5（黑）6（黑）7（红心），然后出QQ ，这里出现分支。
1.若你出11，那我不出，然后你只能出J（规定不能连对），我再出2，然后出KK，再来个方块同花顺，顺带99，最后出6，赢了。

2.若你不出。那我出6，那么就有三种情况。
你不出---我和刚才那样出---你输
---你不出--我出K---你输
你出J---我出K
---你出1---我出2---你输
你出1---我出2---KK---还是你输

[Reply]
- At 2008.07.23 19:03, v0u0yeah said:
  
  所谓连对是指不能出5566这样的吧？谁会规定我出了一对A后不能出一对j这种“连对”的。
  这题恐怕要编程算了.....
  
  [Reply]
At 2008.02.06 21:11, 聦 said:

三种情况里可能有人看不懂..再来..
1.你不出---我和刚才那样出---你输
（分之2） ---你不出--我出K---你输
2.你出J---我出K
（分之2） ---你出1---我出2---你输
3.你出1---我出2---KK---还是你输

[Reply]
At 2008.03.31 15:28, 静 said:

更正：
其中C是平民数

我看了这篇论文，C是参与人数而不是平民数。
杀人游戏中，参与人数=好人方数+杀手人数
一般游戏中所指平民是没有特殊技能的好人。好人方=平民+警察（3.0规则下+医生+狙击）

根据作者结论，简化版9人二杀或10人二杀局最平衡。但是他的推导过程所用的R实在太大了，所以结论本身没有现实意义。笑~很多理论模型都是如此。

[Reply]
At 2008.04.03 21:32, lup said:

是不是必须3个带一对？这样就不是想象的那样简单了

[Reply]
At 2008.05.13 18:11, kilin said:

选牌多的，先出3，对方分A和J么？
不分就拆一对4，打单张4，对方分A我们就让他出，分J我们就用Q打他
如果我们用Q打他J，他必然让我们出，因为如果他A和J都分了，那他必输，因为我们都是一对，分拆的4可以最后打。
现在轮到我们出，我们还打4，他怎么打，如果他打J，我们就用Q打，他分A不？他如果分A还是他输，因为我们可以用2打他A，然后我们除了了单张Q都是一对，如果他不分A让我们出，很简单。先把单张Q打掉，他让我们出么？如果让就拆5.就这么继续。
牌多的肯定赢。

[Reply]
- At 2008.07.23 19:02, v0u0yeah said:
  
  你单打4,我出A，你敢让我出？我出一对J你怎么办？你必出对q或对k，那样你就有了4Q两张单牌，你怎么跑？
  
  [Reply]
At 2008.05.21 16:24, FightingMan said:

[Reply]
At 2008.06.14 13:53, 大道至简 said:

我们手上除２以外，绝对不能超过两个单牌，如果超过了两个单牌，那我们就输了．这是胜负的关键！所以出先出同色与顺子，那就注定输了！多方好像是打不过的．

[Reply]
At 2008.07.18 21:43, AAA said:

多牌一定输。

[Reply]
At 2008.07.23 18:56, v0u0yeah said:

终于想到了...
我们要想赢，必选多的那副，否则肯定被摆摊主打赢...

我们首先出3（梅）4（梅）5（黑）6（黑）7（红心），然后出QQ ，这里出现分支。
1.若你出11，那我不出，然后你只能出J（规定不能连对），我再出2，然后出KK，再来个方块同花顺，顺带99，最后出6，赢了。

2.若你不出。那我出6，那么就有三种情况。
你不出---我和刚才那样出---你输
---你不出--我出K---你输
你出J---我出K
---你出1---我出2---你输
你出1---我出2---KK---还是你输

所谓连对是指不能出5566这样的吧？谁会规定我出了一对A后不能出一对j这种“连对”的。
这题恐怕要编程算了.....

[Reply]
At 2008.07.24 19:56, 再现盛唐 said:

应该是双方都有赢的机会，不存在必胜的模式吧，如果有，我倾向于牌多的一方。

博主所说的江湖象棋，一般不要下。江湖象棋棋局往往有很大诱惑性，实际上一般都是和棋。很多有名的江湖棋局如八大棋局之“小征东”“野马操田”等，变换很多，有一百多年的历史，是很难的，否则，摆摊的怎么赚钱？赚的就是那些不知道天高地厚的，呵呵。解答江湖棋局至少要参加市区比赛的水平。

[Reply]
- At 2008.07.24 21:47, zhiqiang said:
  
  任何轮流进行的游戏都必有一方有不败策略。因为打牌没有和局，所以肯定有一方有必胜策略。
  
  [Reply]
At 2008.09.02 11:45, seth said:

多牌一方一张一张出，从最小的单3开始，如果对方上J，就用K或者Q压一下，如果对方上A，多牌方不出，知道对方剩1张牌，此时上2.
然后打对，多牌方胜。

不可打对子和顺子，也不可上2，除非对方就剩1张牌

[Reply]
At 2008.09.02 11:50, seth said:

补充：对方上第一张J时用Q压，上第二张J时用K压，一定要保证2打出后只有一张单牌，剩下都是对子。

[Reply]
At 2008.09.17 16:25, wilderwein said:

看了那么多讨论，有没有正确答案啊

[Reply]
At 2008.09.24 01:31, 无壳蜗牛 said:

我来答：选牌多
1、先出单6（花色随便），有以下情况，
一种：对方是要，对方出单J，我出单Q（红桃），(对方拆A要.我就上2，方法基本同下），我再出3、4(梅花）、5（黑桃）、6、7（红桃），然后，再出方块同花4、5、7、Q、K,现在我的牌是K一对，单2，单Q，9一对，对方有一对A，单J。我再出单Q，对方拆A，马上就输，如对方不要，我再出单K，对方还不要，对方如拆A，我就上2，我再出单K,单2，对9，结束。
二种：对方不要，我就再出单6，对方如果要，我就出Q，（对方如果拆A要，我就出2，然后打对子，最后出3，因为对方只有一对J和单A，我只要打对子，对方出对J，我就对Q收回，我只单一个3的单牌，对方输定）,如果对方还不要，我就再出3，对方要我就出Q，按照上面的方法，保持我方单一张牌，对方就输定了。

[Reply]
- At 2008.10.21 13:36, sigepluto said:
  
  这样也不行啊。如果你出第二张六，对方出A，你2打，然后对方剩一张A，一对J，你出对的话，对方对J打，你对Q打过后，还剩3，和Q2张单牌，你怎么出啊？
  
  [Reply]
At 2008.10.21 13:38, sigepluto said:

这个牌不可能和局的。表面看来，规则利于多牌方，咋一看是多牌剩，但我直觉还剩少牌方胜。

[Reply]
At 2008.10.30 18:43, 白痴 said:

4楼是对的。出单牌，由小牌出起，对方不出的话，就一直出单牌，对方出J的话用K或Q打，直到对方出A的时候就赢了。

[Reply]
- At 2008.10.31 12:02, milu said:
  
  出单张是要输的，比如你出3，我不要，再出4，我就出A，你要不要
  1，要，就得用2，你再出单张（我用A，胜），出一对（我一对jj，你再要就会出现两个单张）
  2，不要，我还是出jj，又造成你两张单的情况。
  
  所以多牌想赢得靠同花什么的，单靠直接打是不行的
  
  [Reply]
At 2008.11.04 13:09, NjuBee said:

这个出牌规则叫做锄大地, 我是广东人的, 经常玩.
这个江湖局经常出现在街头, 正确答案是
3,P,K,P,4, 之后小牌单挑

上面有人说单挑已经对了20%
大家都没看见(也是很难发现的) QK 中的一张在单挑过程中本质上是单牌.

[Reply]
- At 2009.04.22 02:55, hi said:
  
  没错！！！这个就是正确答案！！！
  
  [Reply]
At 2009.01.09 17:26, 红色警戒 said:

少牌赢

如果你打单，我可以不要，一直到你出第一张6的时候，我出J，你出Q，然后你再出6，我再出J，因为你如果出K的话，就会形成对7，对9，对Q，对K四对。所以你会继续出Q。这时，你剩下1个2，3个K，1个Q，对9，对7. 当你再出一个7的时候，我下A。此时，你有1张Q，一张7共2个单牌，但你只有一个2, 顶多大我一手。

所以少牌必赢

其他的组合都会有这样那样的单牌问题。因为你只有一个2,单牌只能大一手。

[Reply]
At 2009.01.09 17:38, 红色警戒 said:

上面的错了，是多牌赢。当形成对7，对9，对Q，对K, 一个2时，继续打单牌就可以了。只要少牌敢拆对A，用2打后，发对子就可以了。

这样打，反过来证明了是多牌赢

[Reply]
At 2009.02.23 10:26, everest said:

先出3：J；
　　K：不出；（出A用2毕全对胜）
　　4：J；
　　Q：A；（不出，继续单张）
　　2：不出；
　　全双一单4必胜

[Reply]
At 2009.02.23 12:07, everest said:

单出少胜；同花+顺子出法也是少胜；少必胜局！！！有人要出招吗？

[Reply]
- At 2009.06.11 03:00, Chaney said:
  
  我出招了，我出3，你出什么？
  
  [Reply]

« 用Web Picasa API搭建站内相册

加速blog：序 »

杀人的理论分析

阅微堂