超难的问题求解：开枪决斗博弈

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

两人决斗，相距100米，以1米/秒速度接近，每人有3发子弹，每相距整数米时可以开1枪，没子弹了也必须接着走，每人中1枪死，击中概率是（100-距离）/100。
请问双方的最优策略？


是乎要用到混合策略，超级难求。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏2 回帖

关键词：问题求解 混合策略 最优策略

1米/秒是两个人一起走的，还是就一个人？

flumer 发表于 2012-8-4 22:06
1米/秒是两个人一起走的，还是就一个人？

这题我是转贴的，原文就这样了，目前还没有解决。我理解为：两人一起走，每人的速度都是0.5米/秒。
@死狗方舟子

小三真子的圣衣 发表于 2012-8-5 12:58
这题我是转贴的，原文就这样了，目前还没有解决。我理解为：两人一起走，每人的速度都是0.5米/秒。
@死 ...

说实话，这题目可以找个懂ACM的人拿计算机算一下。
我想了个枚举算法要有两个小时出结果，但是不太懂编程了。

好好学习天天向上

网易公开课，《博弈论》有类似讲解。其实三发子弹跟一发子弹是一样的，都是看自己最后一颗子弹的命中率。因为两个人的命中率相等。画出二人的概率曲线，然后照着课程讲得方法分析应该就可以了吧？

msesilver 发表于 2012-8-6 13:43
网易公开课，《博弈论》有类似讲解。其实三发子弹跟一发子弹是一样的，都是看自己最后一颗子弹的命中率。因 ...

网易公开课讲的是几发子弹？一颗子弹很简单，三颗子弹就难了。

我有个思路大家一起讨论。

根据题意，如果双方的目的是在保命的基础上，尽可能杀死对方。

以下分析先不考虑“每相距整数米时可以开1枪”的要求。假设随时可以开枪。

①甲1颗子弹对乙1颗子弹的局面：

当的击中概率（指击中对方概率，以下同）等于50%时，双方同时开枪。即当距离一旦小于50米，双方同时开枪。

②甲1颗对乙2颗：

设：开第一枪时的距离是s米

如果甲先开枪，甲的存活率是（100-s）/100，乙的存活率是1-（100-s）/100

如果乙先开枪，乙的存活率是（100-s）/100 + 0.5[1-（100-s）/100]

甲的存活率是0.5[1-（100-s）/100]

思路：当 甲先开枪甲的存活率 > 乙先开枪甲的存活率 时，甲会开枪。

（100-s）/100 ＞ 0.5[1-（100-s）/100]

解得：s ＜ 200/3

甲的存活率＞1/3

当 乙先开枪乙的存活率 ＞ 甲先开枪乙的存活率 时，甲会开枪。

（100-s）/100 + 0.5[1-（100-s）/100] ＞ 1-（100-s）/100

解得：s ＜ 200/3

乙的存活率＞2/3

即距离一旦小于200/3米，双方都会开枪。

极限下去，双方在距离200/3米处同时开枪。

但是，如果此时双方同时开枪：

甲的存活率是：（100-s）/100 * [1-（100-s）/100] = 2/9

乙的存活率是：1-（100-s）/100 = 2/3

由于同时开枪时甲的存活率变小，甲会选择在距离200/3米之前开枪（无限接近于200/3米）。

乙的理想策略则是与甲同时开枪。

因此，双方无纯策略均衡。MS双方在任何距离开枪都是可选策略。要在所有混合策略中找出最优混合策略是非常繁琐复杂的。

我猜测，甲的最优策略是66米和67米的混合策略。

算出②后，再逐步递推：

③甲1颗对乙3颗，

④甲2颗对乙2颗

⑤甲2颗对乙3颗

⑥甲3颗对乙3颗

MS每步都有混合策略，越到后面越难推算，极度繁琐复杂。