多轮猜数游戏的最佳策略

KeyTo9_Fans

单轮猜数游戏

单轮猜数游戏有$2$个玩家参与，

$2$个玩家先约定好数字范围$n$，

然后玩家$1$在$1$到$n$之间选定一个数写下来，

然后玩家$2$猜玩家$1$写下来的数字，

如果猜对了，则玩家$2$获胜，否则玩家$1$获胜。

这个游戏的策略很简单，

玩家$1$的最佳策略是以$1/n$的概率选$1$、以$1/n$的概率选$2$、……、以$1/n$的概率选$n$，

玩家$2$的最佳策略是以$1/n$的概率猜$1$、以$1/n$的概率猜$2$、……、以$1/n$的概率猜$n$，

于是玩家$1$的获胜概率是$(n-1)/n$，玩家$2$的获胜概率是$1/n$。

多轮猜数游戏

多轮猜数游戏在此基础上增加了难度。

$2$个玩家先约定好数字范围$n$，

然后玩家$1$在$1$到$n$之间选定一个数写下来，不妨设为$x$

然后玩家$2$猜玩家$1$写下来的数字，不妨设为$y$，

如果$x=y=1$，那么玩家$2$获胜；

如果$x=y>1$，那么双方进行下一轮游戏，数字范围缩小至$(x-1)$；

如果$x\ney$，那么玩家$1$获胜。

求双方的最佳策略和获胜概率。

提示大小的多轮猜数游戏

玩家$1$在$1$到$n$的范围里选一个整数$x$，让玩家$2$猜。

玩家$2$每猜一次，玩家$1$都要告诉玩家$2$是猜大了、猜小了、还是猜对了。

如果猜大了或者猜小了，那么玩家$2$继续猜，玩家$1$继续提示，直到玩家$2$猜对为止。

记玩家$2$猜对$x$所耗的次数为$k$。

玩家$1$希望$k$的期望值尽可能大，玩家$2$希望$k$的期望值尽可能小。

问：玩家$1$会如何选数，玩家$2$会如何猜数，纳什均衡时$k$的期望值是多少？

KeyTo9_Fans

多轮猜数游戏

$2$个玩家先约定好数字范围$n$，

然后玩家$1$在$1$到$n$之间选定一个数写下来，不妨设为$x$

然后玩家$2$猜玩家$1$写下来的数字，不妨设为$y$，

如果$x=y=1$，那么玩家$2$获胜；

如果$x=y>1$，那么双方进行下一轮游戏，数字范围缩小至$(x-1)$；

如果$x\ney$，那么玩家$1$获胜。

求双方的最佳策略和获胜概率。

-----

这个不难，相当于玩家$1$选一个首项不超过$n$的单调递减数列，并且该数列的最后一个数必须是$1$，然后由玩家$2$猜这个数列是什么。

例如，当$n=3$时，玩家$1$可以选择的数列有$4$个：

$3,2,1$
$3,1$
$2,1$
$1$

因此玩家$1$的胜率为$3/4$，玩家$2$的胜率为$1/4$。

又如，当$n=4$时，玩家$1$可以选择的数列有$8$个：

$4,3,2,1$
$4,3,1$
$4,2,1$
$4,1$
$3,2,1$
$3,1$
$2,1$
$1$

因此玩家$1$的胜率为$7/8$，玩家$2$的胜率为$1/8$。

再如，当$n=5$时，玩家$1$可以选择的数列有$16$个：

$5,4,3,2,1$
$5,4,3,1$
$5,4,2,1$
$5,4,1$
$5,3,2,1$
$5,3,1$
$5,2,1$
$5,1$
$4,3,2,1$
$4,3,1$
$4,2,1$
$4,1$
$3,2,1$
$3,1$
$2,1$
$1$

因此玩家$1$的胜率为$15/16$，玩家$2$的胜率为$1/16$。

根据上述例子不难找出规律：

玩家$1$可以选择的数列有$2^{n-1}$个，胜率为$(1-1/{2^{n-1}})$，玩家$2$的胜率为$1/{2^{n-1}}$。

#####

于是楼主的问题就只剩下【提示大小的多轮猜数游戏】了。

绝顶聪明的玩家$1$和玩家$2$又会怎么玩这个游戏呢？

-----

当$n=3$时，如果玩家$1$等概率选数，那么玩家$2$猜$2$，结果玩家$2$只需$5/3$次就猜对了。

玩家$1$的最佳策略是从以下$5$个小球里随便摸一个小球，让玩家$2$猜小球上的数字。

① ① ② ③ ③

于是：

如果玩家$2$猜$2$，那么只有$1$个球②是$1$次猜对的，而剩余的$4$个球①①③③都需要$2$次才能猜对，平均次数为$9/5$。

如果玩家$2$猜$1$，那么有$2$个球①①是$1$次猜对的，有$2$个球③③是$2$次猜对的，还有$1$个球②需要$3$次才能猜对，平均次数依然是$9/5$。

所以当$n=3$时，$k$的期望值是$9/5$。

-----

当$n=4$时，玩家$1$等概率选数即可，$k$的期望值是$2$。

-----

当$n=5$时，玩家$1$的最佳策略是在以下$18$个小球里等概率摸球：

①①①①① ②②② ③③ ④④④ ⑤⑤⑤⑤⑤

于是玩家$2$无论如何猜小球上的数字，所需的期望次数都不低于$20/9$。

所以当$n=5$时，$k$的期望值是$20/9$。

-----

对于更大的$n$，结果是怎样的呢？

KeyTo9_Fans

把$n=1$到$n=5$的结果列出来，得到$1$个分数数列：

$1$，$3/2$，$9/5$，$2$，$20/9$

把分子分母分开，就可以得到$2$个整数数列：

分子数列：$1,3,9,2,20$
分母数列：$1,2,5,1,9$

然后去【在线整数数列百科大全】上查询这两个整数数列，结果为：

分子数列：

https://oeis.org/A286676

分母数列：

https://oeis.org/A286677

该数列的定义是：

Nash equilibrium guesses for the number guessing game for n numbers.

翻译过来是：

$n$个数的猜数游戏在纳什均衡时的猜数次数。

因此该数列的定义与楼主所提的最后一个问题完全一致，而且已经有了$16$项数据：

分子数列：$1, 3, 9, 2, 20, 12, 23, 27, 31, 35, 187, 1461, 485, 105, 64, 69$
分母数列：$1, 2, 5, 1, 9, 5, 9, 10, 11, 12, 62, 470, 152, 32, 19, 20$

该数列是由 Lewis Chen 在 2017年5月12日 提交的。

楼主晚了半年才发现这个数列，因此无法成为这个数列的贡献者了，甚是可惜。

#####

尽管如此，如果能计算出这个数列的前$17$项或者更多，就可以扩充这个数列。

对于扩充数列的编辑者，该网站也会有记录。

感兴趣的有空人士不妨一试。