【报数拆区间】游戏的最佳策略
【报数拆区间】游戏是一个有裁判参与的多玩家混战游戏。游戏开始前，由随机数发生器产生一个$1$到$100$的随机数。
（产生$1$到$100$之间的任何一个数的概率均等，均为$1/100$）。
这个数只有裁判知道是多少，其余所有的玩家都不知道这个数是多少。
这个数生成后，所有玩家排成一圈，然后裁判转动转盘。
待转盘指针稳定后，指针指到的玩家开始报一个数。
所报之数必须是已知区间里的一个数。
该已知区间一开始是$$。
假设所报之数是$y$，随机数发生器产生的数是$x$。
如果$y=x$，则游戏结束，报数的玩家输，接受惩罚（一般是头上的气球爆炸，或者是一个冰桶盖下来）。
如果$y\ne x$，则游戏继续，分两种情况讨论。
情况$1$、$y>x$，则已知区间缩小为$$。
情况$2$、$y<x$，则已知区间缩小为$$。
也就是说，已知区间被$y$劈成了两半，缩小后的已知区间是包含$x$的那一半。
然后游戏继续，由第二个玩家在新的已知区间内报一个数，重复上述流程。
直到某个玩家所报之数等于$x$为止，该玩家输，接受惩罚。
以下是所有玩家都具备的无穷阶公共知识：
$1$、最小化自己输的概率。
$2$、若存在多种方案使得自己输的概率最小，则最大化对面玩家输的概率（城中失火，殃及池鱼：旁边的玩家输，自己也遭殃。因此让离自己最远的玩家输，即让对面的玩家输，自己受到的伤害最小）。
$3$、若存在$2$个距离相等的【对面玩家】，则无所谓了，抛硬币决定让谁输的概率大。
$4$、在自己输的概率最小化，对面玩家输的概率之和最大化的前提下，还存在多种并列方案，则最大化第二远玩家输的概率之和，然后最大化第三远玩家输的概率之和，依次类推。
$5$、若还存在并列，就无所谓了，掷骰子决定报哪个数吧。
问这个游戏的最佳策略。
#####
郑重声明：
这个游戏是有策略可言的。举个简单的例子：$3$个数$\{1,2,3\}$，$2$个玩家。问先行报数的玩家报几？答案是$2$。因为报$2$只有$1/3$的概率输；若报$1$或$3$，输的概率均为$2/3$。 为啥是100个数而不限制玩家数量
比如如果有101个玩家呢（……） 两个玩家应该还是挺简单的，稍微多一些玩家就会比较复杂了。
但是我觉得很有可能每次挑选最中间就可以了，思路很简单，尽快结束游戏，降低下一轮还轮到自己的概率。当然在无法改变命运时，开始会为了欺负紧跟着自己的小弟而选择边上的数字了。
比如两个人，可以简单逆推。由于这时遇到多种方案概率相等时，怎么选择都不影响最终结果，所以
如果面对的区间只有一个数字了，那就100%失败，p=1
如果面对的区间有两个数字，那么选哪个都一样，50%失败，p=1
而对于$n>=3$个数字,挑选第k个失败的概率是$1/n+(k-1)/n*(1-p)+(n-k)*(1-p)$
计算结果在选择k为$[(n+1)/2]$时最小，概率为$1/2+{cos((n-1)*pi/2)}/{2n}$,而如果要证明结论，也很简单，数学归纳法即可 三个玩家玩游戏时，除了计算各种方案下当前玩家输掉的概率，还需要记录其它玩家输掉的概率，所以计算相对要复杂一些。
如果只有1个或2个数，第一个显然选择第一个数即可（怎么选择都没有区别），自己输的概率分别是1或1/2
而如果三个数时，第一个选手怎么选择失败的概率都是1/3，所以为了害小弟，会选择数字2，让小弟有2/3概率输掉。
而如果四个数时，选择第一个数时，无论选择哪个数，自己失败概率为1/4（选择1号时，由于小弟的助攻，还是可以无恙），所以还是选择了2号迫害小弟，导致失败概率为1/4，但是小弟失败概率为1/2，而三号选手有1/4的概率失败。
但是如果五个数时，情况稍微有点变化了，如果选择第一个数，失败的概率就是1/5+4/5*1/4=2/5了，但是选择第二个数和第三个数的失败概率都为1/5。但是同样选择第二个数可以更好的害小弟，所以选了2号。依次类推下去，计算结果表示3个人时，总是要选择第一个或第二数来迫害小弟。应该是模6为周期，分别选择1,1,2,2,2,2。前提是相信无论你如何迫害小弟，他还是爱你依旧。 mathe 发表于 2019-3-11 14:14
三个玩家玩游戏时，除了计算各种方案下当前玩家输掉的概率，还需要记录其它玩家输掉的概率，所以计算相对要 ...
三个人情况前面算错了，结果很复杂，没有明显的规律 改一下游戏规则
猜到与裁判一样的数为赢家
不管裁判的数多大,至多猜10次,就可以猜中裁判的数 mathe 发表于 2019-3-11 14:35
三个人情况前面算错了，结果很复杂，没有明显的规律
算4个人的就好
1-4，自己输掉的概率为1,1/2,1/3,1/4
为了更好地害小弟，大家不约而同地选择最边上的数字
5，我们可以知道，之后的人都是选择最边上的数字，所以这时候不能选靠边的数字(选最边上的数字，则在更靠后的时候有概率轮到自己，这样会增大自己输的概率)
5-8，为了更好地关爱小弟，选中间的数字
……果然好麻烦 两个玩家时选择方案给的不正确。
事实上两个玩家时，面对n个数，如果n是偶数，最有方案是平局，面对n=4k+1,先手输的概率略大，为${2k+1}/{4k+1}$.面对n=4k+3时，先手输的概率略小为${2k+1}/{4k+3}$。所以任何时候，玩家的对策是尽量产生4k+1型的局面。
比如如果面对的局面是$n=2m$,可以分拆为$2m=(4h+1)+1+(2(m-1-2h))$,得出输的概率为
$1/{2m}+{4h+1}/{2m}*{2h}/{4h+1}+{2(m-1-2h)}/{2m}*1/2={1+2h+m-1-2h}/{2m}=1/2$
如果$n=4m+3$,那么可以拆分为$4m+3=(4a+1)+1+(4(m-a)+1)$,得出输得概率为$1/{4m+3}+{4a+1}/{4m+3}{2a}/{4a+1}+{4(m-a)+1}/{4m+3}{2(m-a)}/{4(m-a)+1}={1+2a+2(m-a)}/{4m+3}={2m+1}/{4m+3}$
而如果$n=4m+1$时，那么去掉一个后，怎么选择都结果一样。
但是切换到3个人以后好像就完全没有规律了，n个数时3人输的概率分别为
而选择的对称在3个数是选中间，4个数也是选中间两个，但是5个数只要不选两边就可以。6，7，8个数还是选中间，9个数选中间3个，10个数选中间4个，11个数选两边各两个(1,2,10,11),12~18个数时都神奇的选择了12号数（或对称的数，比如12个数时1，12对称，18个数时，7，18对称）。
19个数时选择方案较多有(1,2,8,12,18,19),20个数时可以选择(1,2,9,12,19,20)，21个数选(2,10,12,20),22个数选(11,12), 23个数只能选12，24个数可以选(2,3,4,12,13,21,22,23), 25个数选(3,4,12,14,22,23)
(需要注意神奇的12还没有退出）
但是26个数时，12号数终于退出最优选择，需要选(4,23)
27个数，选(5,23),
但是到了28~34个数，神奇的12又回归了（只能选12以及对称数）
而35个数可以选(4,12,13,14,...)
总体上来说，12号数是很受欢迎的
比如前500个数里面找出编号最小的最优选择，结果如下（也就是如果还有比12更小的最优选择，12就不会被显示）
而如果换成4个选手好像48号数比较受欢迎，但是受欢迎程度和3个选手时的12完全不能相比
sor(n,k)={
local(a,b,c,d,p);
a=matrix(k,n);
a=1;
for(u=2,k,a=0);
b=vector(k);c=vector(k);
d=vector(n);d=1;
for(u=2,n,
b=1/u+(u-1)/u*a;d=1;
for(v=2,k,
b=(u-1)/u*a
);
for(h=2,floor((u+1)/2),
c=1/u+(h-1)/u*a+(u-h)/u*a;
if(c>b, next());
for(v=2,k,
c=(h-1)/u*a+(u-h)/u*a
);
p=0;
if(c<b,p=1);
for(v=2,k,
if(c<b,break());
if(c>b,p=1;break())
);
if(p,
for(v=1,k,b=c);d=h
)
);
for(v=1,k,a=b)
);
}
输入参数k表示人数,n代表数字数目，比如sor(100,3)就给出了100个数3个人时的结果。输出结果中a是k个人的输的概率。d给出了编号最小的最优选择策略。
页:
[1]
2