多轮猜数游戏的最佳策略
单轮猜数游戏单轮猜数游戏有$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$的期望值是多少？
多轮猜数游戏
$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$，结果是怎样的呢？ 把$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$项或者更多，就可以扩充这个数列。
对于扩充数列的编辑者，该网站也会有记录。
感兴趣的有空人士不妨一试。
页:
[1]