简化的三国杀游戏

KeyTo9_Fans

三国杀是多个玩家（至少$4$个）参与的一种卡牌游戏。

玩家有$4$种身份：主公、忠臣、内奸、反贼。

我们首先考虑只有$1$名主公、$1$名忠臣、$1$名内奸和$1$名反贼的简单情形，并且将游戏规则简化如下：

=====

所有玩家的身份都是公开的；

每个玩家都拥有一定点数的初始体力；

在每个回合里面，所有活着的玩家，从主公开始，轮流出击；

玩家出击时，只需要指定一个玩家作为攻击目标，被攻击的玩家即刻扣除$1$点体力；

玩家的体力降至$0$即刻死亡，已经死亡的玩家不能出击；

内奸和反贼死亡，则主公和忠臣获胜（无论忠臣存活与否）；

主公死亡，如果此时只剩下内奸$1$人存活，则内奸获胜，否则反贼获胜（无论反贼存活与否）。

=====

我们假设所有的玩家都采取最佳策略出击，最佳策略的定义如下：

$1$、如果只剩下二人进行PK，出击时攻击对方即可；

例如：

只剩下主公和内奸进行PK，那么出击时攻击对方即可，结果体力大的一方获胜（体力一样大则先出击获胜）；

$2$、如果有多个攻击目标可供选择，那么选择【攻击之后，自己的获胜概率最大】的目标进行攻击；

例如：

主公、忠臣和反贼各剩余$1$点体力，内奸已死亡，轮到反贼出击，那么反贼有多个攻击目标可供选择：

如果攻击忠臣，反贼会被主公杀死，获胜概率为$0$；

如果攻击主公，则直接获得胜利，获胜概率为$1$；

所以反贼的最佳策略是攻击主公，获胜概率为$1$。

$3$、如果存在多个目标，使得攻击之后，自己的获胜概率都是并列最大的，那么就从这些并列最大的目标中，随机等概率地选择一个目标进行攻击。

例如：

主公、忠臣和内奸各剩余$1$点体力，反贼已死亡，轮到内奸出击，那么内奸有多个攻击目标可供选择：

如果攻击忠臣，内奸会被主公杀死，获胜概率为$0$；

如果攻击主公，则反贼获胜，内奸的获胜概率仍然为$0$；

所以内奸的最佳策略是以$0.5$的概率攻击忠臣，$0.5$的概率攻击主公，

结果内奸的获胜概率为$0$，主公和忠臣的获胜概率为$0.5$，反贼的获胜概率为$0.5$。

$4$、主公和忠臣永远不会把对方列为攻击目标之一。

例如：

主公和忠臣各剩余$2$点体力，反贼剩余$1$点体力，内奸已死亡，轮到主公出击，那么：

主公攻击反贼，则直接获得胜利，胜利概率为$1$；

虽然主公攻击忠臣后，胜利概率仍然为$1$，但主公不会攻击忠臣。

=====

问题$1$：

是否存在一组初始体力和轮候顺序，使得每个玩家的获胜概率均为$1/3$？

如果存在，请列出这组初始体力和轮候顺序；

如果不存在，请找出一组初始体力和轮候顺序，使得每个玩家的获胜概率最接近$1/3$。

问题$2$：

是否存在这样的奇葩情况：【某个玩家突然不按套路出牌了，轮到他出击时，他自损$1$点体力（或者是主公攻击忠臣、忠臣攻击主公），结果他的获胜概率反而比伤害其他人$1$点体力后的获胜概率更大】？

如果存在，请列出此时每个玩家的体力和轮候顺序，以及不按套路出牌的玩家。

问题$3$：

是否存在这样的情况：【某个玩家突然不按套路出牌了，轮到他出击时，他放空枪，结果他的获胜概率反而比伤害别人或者自残$1$点体力后的获胜概率更大】？

如果存在，请列出此时每个玩家的体力和轮候顺序，以及不按套路出牌的玩家。

问题$4$：

如果允许自损$1$点体力（即所有的玩家都把自己列为攻击目标之一，主公和忠臣互相把对方列为攻击目标之一），

也允许放空枪（如果放空枪后，己方的胜利概率比伤害任何一人都大，就放空枪；如果放空枪与否，胜利概率都一样大，则不放空枪），

那么是否存在这样的奇葩情况：【突然间，所有的玩家都不敢伤害别人（或者自己）了，纷纷放出空枪，结果游戏无限循环，永不终止。因为任何一个玩家如果不放空枪而伤害别人或者自残，他的胜利概率反而更小了】？

如果存在，请列出此时每个玩家的体力和轮候顺序。

KeyTo9_Fans

由于无人回答，楼主开始陆续公布答案。

问题$1.1$：

是否存在一组初始体力和轮候顺序，使得每个玩家的获胜概率均为$1/3$？

答案是不存在。

问题$1.2$：如果不存在，请找出一组初始体力和轮候顺序，使得每个玩家的获胜概率最接近$1/3$。

最接近$1/3$的获胜概率是：

主公和忠臣$3/8$，内奸$5/16$，反贼$5/16$。

具有此获胜概率的初始体力和轮候顺序只有$2$组解：

第$1$组解：主公体力$10$，反贼体力$8$，忠臣体力$6$，内奸体力$11$；
第$2$组解：主公体力$10$，反贼体力$10$，忠臣体力$8$，内奸体力$11$；

其余的初始体力和轮候顺序的胜率都没有这两组接近$1/3$。

KeyTo9_Fans

由于无人回答，楼主继续公布答案。

问题$2.1$：

是否存在这样的奇葩情况：【某个玩家突然不按套路出牌了，轮到他出击时，他自损$1$点体力，结果他的获胜概率反而比伤害其他人$1$点体力后的获胜概率更大】？

答：假设整局游戏就只有这一次没按套路出牌，之后都按套路出牌，那么答案是存在的。

问题$2.2$：

如果存在，请列出此时每个玩家的体力和轮候顺序，以及不按套路出牌的玩家。

答：当初始体力和轮候顺序如下时：

主公体力$2$，忠臣体力$1$，内奸体力$2$，反贼体力$5$，

那么主公和忠臣的最佳策略是攻击反贼，然后进入如下局面：

内奸体力$2$，反贼体力$3$、主公体力$2$，忠臣体力$1$，轮到内奸

那么此时内奸无论是攻击反贼、攻击主公、还是攻击忠臣，最终的获胜概率都为$0$；

但是如果内奸自损$1$点体力，那么最终的获胜概率反而有$0.25$，大于$0$。

具体分析如下：

如果内奸攻击主公，那么内奸体力$2$，反贼体力$3$、主公体力$1$，忠臣体力$1$，轮到反贼，于是反贼攻击主公，反贼获胜。

如果内奸攻击忠臣，那么内奸体力$2$，反贼体力$3$、主公体力$2$，忠臣死了，轮到反贼，于是反贼攻击主公，主公体力剩$1$，无力回天，还是反贼获胜。

如果内奸攻击反贼，那么内奸体力$2$，反贼体力$2$、主公体力$2$，忠臣体力$1$，轮到反贼。

　　于是反贼的最佳策略是攻击主公（攻击主公之后，获胜概率为$2/3$；如果攻击忠臣，胜率只有$0.5$；如果攻击内奸，胜率为$0$）

　　结果内奸体力$2$，反贼体力$2$、主公体力$1$，忠臣体力$1$，轮到主公和忠臣。

　　于是主公和忠臣的最佳策略是分别攻击内奸和反贼（否则的话：如果都攻击内奸，则反贼获胜；如果都攻击反贼，则内奸获胜）

　　结果内奸体力$1$，反贼体力$1$、主公体力$1$，忠臣体力$1$，轮到内奸。

　　结果无论内奸如何出击，都无法获胜，胜率为$0$。

综上所述，内奸无论是攻击反贼、攻击主公、还是攻击忠臣，最终的获胜概率都为$0$；

如果内奸自损$1$点体力，那么内奸体力$1$，反贼体力$3$、主公体力$2$，忠臣体力$1$，轮到反贼。

　　于是反贼的最佳策略是攻击忠臣（攻击忠臣之后，获胜概率为$0.75$；如果攻击主公，胜率只有$2/3$；如果攻击内奸，胜率为$0$）

　　结果内奸体力$1$，反贼体力$3$、主公体力$2$，忠臣死了，轮到主公。

　　此时无论主公攻击内奸，还是攻击反贼，胜率都为$0$，所以主公以$0.5$的概率攻击内奸，以$0.5$的概率攻击反贼。

　　如果主公攻击内奸，则反贼获胜；

　　如果主公攻击反贼，那么内奸体力$1$，反贼体力$2$、主公体力$2$，轮到内奸。

　　　　此时内奸的最佳策略是攻击反贼（如果攻击主公，则反贼获胜）

　　　　结果内奸体力$1$，反贼体力$1$、主公体力$2$，轮到反贼。

　　　　此时反贼的最佳策略是攻击主公（如果攻击内奸，则主公获胜）

　　　　结果内奸体力$1$，反贼体力$1$、主公体力$1$，轮到主公，此时由于主公无法获胜，因此随机出击，结果内奸和反贼的胜率各为$0.5$。

综上所述，如果内奸自损$1$点体力，那么主公的胜率为$0$，反贼的胜率为$0.75$，内奸的胜率为$0.25$，大于$0$。

因此内奸就【不按套路出牌了，轮到他出击时，他自损$1$点体力，结果他的获胜概率反而比伤害其他人$1$点体力后的获胜概率更大】。

.·.·.

最后一问
先写递推好了
只剩1人，剩的就是赢家
剩2人，主内，（血量高的）赢；主忠，主忠赢；主反，（血量高的）赢；忠内，反赢；忠反，反赢；内反，反赢；
这里（血量高的）人指的是，按先出手的人血量+0.5进行比较
剩3人，cyc(忠，内，反)，cyc(忠，反，内)，反赢；
cyc（主，忠，反），cyc（主，反，忠），反的最优策略是杀死主公/先杀忠再杀主，主忠的最优策略是杀死反，比较血量可以得到胜利结果
cyc（主，忠，内），cyc（主，内，忠），内的最优策略是先杀忠再杀主，主忠的最优策略是杀死内，比较血量可以得到胜利结果
cyc（主，反，内），cyc（主，内，反）：：
  当主剩体力1的时候：
  主1，反X，内Y
    当X=1，主砍哪个都会被补刀，不操作也会被杀：若Y=1，反的胜率为0.5（可能被主杀，此时内的胜率为0.5）；否则反赢
    当X>=2，反赢
  反X，内Y，主1，反赢
  内Y，主1，反X：：
    X=1，Y=1:不操作，到“主1，反1，内Y”状态，反胜率0.5，内胜率0.5
      杀反，主赢（X）
      杀主，反赢（X）
    X=1，Y>=2:杀反，主杀内，内杀主，内赢
      不操作，到“主1，反1，内Y”状态，反胜率0.5，内胜率0.5（X）
      杀主，反赢（X）
    X=2，Y=1:杀反，到“主1，反1，内1”状态，反胜率0.5，内胜率0.5
      不操作，“主1，反2，内1”状态，反赢（X）
      杀主，反赢（X）
    X>=3，反赢
……
我想到了一个绝妙的方法
但是服务器太小放不下……

.·.·.

KeyTo9_Fans 发表于 2018-12-13 20:48
由于无人回答，楼主继续公布答案。

问题$2.1$：

想到了第四问存在一个不严谨的地方：
事实上，我们并不能确定“放空枪”的胜率

因为我们确定概率的方法只有一种，就是递推
一旦我们确定了“放空枪”的胜率，这就代表，放空枪之后，存在一条通向“某方获胜”的路径

而我们并没有排除“大家都在放空枪”这种情况
事实上，当某种状态下，大家都没有必胜策略的时候，由于谁都没办法确定放空枪的胜率是不是高于现存的胜率最大的方法
于是……突然间所有玩家都死机了……

staticfield

.·.·. 发表于 2018-12-16 20:46
想到了第四问存在一个不严谨的地方：
事实上，我们并不能确定“放空枪”的胜率

存在死机的情况，并不代表不存在都放空枪的情况。

比如三人混战局，从A开始按ABC方向依次行动，A,B,C初始为1,1,1，就是都放空枪。

A,B,C初始为1,2,2，则1,2,2永远保持，或者1,1,2然后1,1,1之后永远保持。所以A开始到底时空枪还是攻击C就算不出来死机。

如果A,B,C初始为2,1,2，那么A结束2,1,1->B结束1,1,1；或者A结束2,1,2->B结束2,1,1->C结束1,1,1；或者A结束2,1,2->B结束2,1,2->C结束2,1,2，同样从A开始就死机。

2,2,2开局也是死机。

如果加上几种方案都会导致最终放空枪死循环，则在死循环时己方及队友减员最少的情况中随机选择一个方案，那么上述的几种情况，最终都会变成1,1,1。

所以原题是否可以加一个条件，胜利方所有人（无论是否存活）平分1收益，一轮下来均放空枪则平局，幸存者平分1收益，然后每一方所有人平分己方幸存者获得的收益。

还有一种方法就是加入天谴模式保证不会出现放空枪死循环，比如一个人连续两轮空枪则强制扣一点体力，或者每次放空枪，回合结束则天怒+1，一旦某人攻击或者自减体力则天怒清零，回合结束后天怒达到存活人数，则天谴刚刚放空枪的人强扣一点体力，然后天怒清零。也就是从你开始放空枪，一轮下来你继续放空枪则要减一点体力。 天谴需要的数值不等于场上存活人数也可以，可能计算更复杂一点。

复杂点可以再增加一个条件，一个队分配收益时存活者可以比阵亡者多分配收益，比如2:1的比例，在保证己方总收益最大，以及不能攻击己方队友的前提下，选择使自己的收益更大的策略，又会又什么样的结果呢？比如剩余主反忠2,1,1，主可以放空枪，则二分之一概率反攻击忠。又或者一个队共3人击杀数分别为2,3,1，则分配从1:1:1变为3:4:2呢？如果可以击杀队友，但此次击杀会导致被杀者分配权重+1，攻击者分配权重-1呢？

还是三人混战的天谴模式递推最简单了，1,1,1开局，A上来就只能随机选择一种方案了，因为即使放空，B,C都会等一轮。为了减少随机性，可以再加一个规则：每个人都需要1个单位的行动时间，阵亡的人也会被轮到，直接等待1个单位的行动时间然后轮到下一个。每个人如果推测自己必死，那么以自己确定能存活的时间最长为前提，随机选择自己可能存活时间最长的方案之一。比如至少活3个单位时间的3种，1种70%概率活6单位，2种时10%概率活10单位，则后两种随机选一个。

这种情况下1,1,1开局，A放空，B若放空，C放空后A一定会攻击B，所以B必死，为了多活一阵，B只能攻击C，然后被A击杀。明知必死则等死（突然可以不用死了还是要反抗的），或自杀，则结局又不一样。如果是现实生活中一个考验人性的"上帝"抓了三个足够聪明的人，他们不知道对方的策略，只知道"上帝"给他们规定了攻击和天谴等规则，最终只能活一个。那么就要揣摩人心了，人都想活下来，明知必死，是能多苟活一阵子也好，还是看谁不顺眼攻击谁，还是等死，自杀，随机等死自杀或攻击一个人？不过在三人互相不知道策略的情况下，A放空枪，BC肯定还是放空枪的。

.·.·.

staticfield 发表于 2018-12-24 16:22
存在死机的情况，并不代表不存在都放空枪的情况。

比如三人混战局，从A开始按ABC方向依次行动，A,B,C ...

你的推理存在问题，因为“A,B,C初始为1,1,1，就是都放空枪。”
这一句不成立
哪怕你明知A行动的话，A输掉的概率是100%
你也不能确定如果A不行动，A的胜率会大于0
（如果放空枪后，己方的胜利概率比伤害任何一人都大，就放空枪；如果放空枪与否，胜利概率都一样大，则不放空枪）
讲道理死循环应该算“胜利概率为0”（毕竟最终没有人能获胜），那么A不应该放空枪，所以A应该放枪
但如果A意识到B也会这样想，A就会发现，如果自己不放枪，B会觉得自己遇到了死循环，胜率为0所以B必须放枪
于是A死机了……

staticfield

.·.·. 发表于 2018-12-24 18:23
你的推理存在问题，因为“A,B,C初始为1,1,1，就是都放空枪。”
这一句不成立
哪怕你明知A行动的话，A输 ...

A攻击别人后的胜率为0，假设A放空枪后的胜率x也为0，那么A放空枪后，B的情形和A行动之前是一样的，那么可以推断出此时B攻击别人和放空枪的概率都为0，那么按照题设，B必定随机攻击A或C，从而B的胜率为0，A和C的胜率为50%，这和之前的假设A放空枪后胜率为0矛盾。所以x必然大于0。
所以A是不会死机的，因为可以推断出放空枪的胜率大于0。

staticfield

主反内的开局想了下，似乎不存在一直放空枪的情况。

主反内的行动次序，体力为2,1,2。
主杀反后2,0,2，必输
主杀内后2,1,1，则：反若放空枪2,1,1，内杀主1,1,1，反1/2概率赢；反杀主后1,1,1，内必放空枪1,1,1，反1/2概率赢。所以主杀内必输。
主放空枪后2,1,2，反杀主必输，反杀内，内杀主，又回到1,1,1。反放空枪，内必然放空枪，那么如何计算反放空枪的胜率？所以这时候反杀内还是放空枪？
只能推断：若反放空枪后的胜率为y>1/2，之后内放空枪后胜率要满足z>=1/2，否则内攻击主后1,1,2主必输，内有1/2胜率，与y>1/2矛盾。但是z>=1/2与y>1/2又矛盾，所以y<=1/2。若y<1/2，推断出反放空后，内不可能杀主，那么内一定会放空且z>1/2，若z=1/2，z不会放空, y=z=1/2，与y=1/2矛盾，然后主也只能放空。那么就意味着：反放空后的胜率小于1/2，且会演化成内主都放空又轮到自己行动，所以反放空后的胜率等于反放空前的胜率，但是反放空前有胜率1/2的选择，这本身时矛盾的。所以y<1/2也不对。那么就只有y=1/2，内必然攻击主，z=1/2。
那么推断出主放空也是必输，所以主随机选择攻击内反。

主反内2,2,2开局，主杀反2,1,2变成上述必输局，主杀内2,2,1，反若放空则内只能放空，轮到主还是只能放空，又转化成反杀主，内杀反后1,1,1必输局。主开局放空，反杀主内杀反，反杀内内放空，反放空内放空或杀反，最终都演变成1,1,1的主必输局。主2体力不能在行动后让内反一死，一体力，就输定了。

主结束后3,1,1必然被打成1,1,1，所以3,1,2和3,2,1也是主的无解局。3,2,2开局主不放空，也是最终1,1,1无解局。开局放空也是无解。4,2,2->2,1,2还是无解。5,2,2主必赢。6,3,2主必赢。对于X,Y,Z，且如果X>=MIN(Y,Z)+Y+Z-1，那么主盯着体力少的人攻击就必赢。X<MIN(Y,Z)+Y+Z，X>Y, X>Z，那么主必输，反内会让主永远保持X<MIN(Y,Z)+Y+Z，同时反和内也不会让对方的体力占据绝对优势。

对于反来说的绝对优势为，轮到反行动时，Y>=2X-1，或Y>2(Z-1)+X。对于内的绝对优势为，轮到内行动时：Y<2X，且Z>2(Y-1)+X。开局几种情况：1. 主绝对优势 2.反绝对优势：就是主攻击反后，到反依然反绝对优势，3. 内绝对优势：就是主反都攻击内后，到内依然绝对优势。4. 反差一步绝对优势，之后只要有一次主随机攻击的不是反，反就占据了绝对优势 5. 内差一步绝对优势，只要主有一次随机攻击的不是内，内就占据了绝对优势。6. 主反内都没有明显优势。

不存在轮到每一个人时，攻击任意一人都会造成另一人的绝对优势。所以要推算胜率的改变去寻找一直放空枪的情况。

.·.·.

staticfield 发表于 2018-12-25 10:27
主反内的开局想了下，似乎不存在一直放空枪的情况。

主反内的行动次序，体力为2,1,2。

主放空枪后2,1,2，反杀主必输，反杀内，内杀主，又回到1,1,1。

你可能没有理解这款游戏
如果是111的话，主可以放空枪，但反一定会杀主
因为反杀主的胜率为100%
反的胜利条件不需要杀掉全部在场玩家