最优答题策略

lsr314

某xxqg软件有一个挑战答题，每次挑战可重复进行多轮答题，直到某轮连续答对5题或者前6题答对5题则挑战成功，后者是因为每轮有一个复活机会。
答错时亦可以选择不复活而放弃本轮，直接开始新一轮答题。
最终挑战成功时，系统会给出本次挑战多轮答题的总题数。
例如，某人某次挑战的过程和结果如下：
轮次      过程                    题数
第1轮    110110                  6
第2轮    111010                  6
第3轮    1100                     4
第4轮    10（放弃）            2
第5轮    111011（成功）     6
结果本次挑战总题数 = 24
假定他进行了10次挑战试验，各次的答题总数为24，22，20，20，21，24，23，25，21，20
则他这10次的各次答题总数期望值为（24+22+19+20+21+24+23+25+21+20）/10=22题

假如不考虑借助搜索引擎，某人答题的正确率是p，每轮应该在连续答对多少题后失败时选择复活，才能使得完成挑战的答题总数的期望值最少？

lsr314

测试了几个数据，结果显示：最佳策略是：答对一题以后使用复活，所用答题总数的平均值最少。即如果第一题就答错了，那么本次挑战放弃，不使用复活而直接进入下一轮挑战，如果第一题答对了，那么后面不管第几题答错了，都使用复活，直到挑战成功或者答错进入下一轮。
不过，也有很多数据表明答对两次以后才使用复活，总次数会比答对一次就用要少，不过结果比较接近，不好判断。

mathe

我计算结果和p相关，比如p<0.5187900636758842219074538,
那么只有前4个都猜对了才值得复活
而如果0.5187900636758842219074538<p<0.7412709105660020537067863,
那么前3个都猜对了复活
如果0.7412709105660020537067863<p<0.8881796675853100182508273
那么前2个都猜对了复活
如果p>0.8881796675853100182508273
那么第一个猜对就值得复活了

lsr314

mathe 发表于 2020-12-23 13:01
我计算结果和p相关，比如p

我试了p=1/3,答对0~4题后复活平均答题次数分别是166、130、133、160、219，在测试10万次后取平均数，每个数字在±3范围内波动。所以答对一题和答对两题后复活结果接近，但是明显优于其他方案。

mathe

你模拟的应该有问题：
计算后平均答题次数:
? getA(1.0/3.0)
%6 = [[283.00000000000000000000000000000000018, 280.00000000000000000000000000000000018, 271.00000000000000000000000000000000018, 244.00000000000000000000000000000000018, 163.00000000000000000000000000000000017]~, 4]
也就是说4题答对后才复活结果最优，答对0～4题后（还有复活机会）还平均需要回答上面次数才可以。

模拟结果
\$ ./testc 2 0.333333333333
regret at 2 try and probability is 0.333333
Average try 336.740347 times

\$./testc 3 0.333333333333
regret at 3 try and probability is 0.333333
Average try 308.719644 times

\$./testc 4 0.333333333333
regret at 4 try and probability is 0.333333
Average try 282.619372 times


另外比如
\$ ./testc 2 0.7
regret at 2 try and probability is 0.700000
Average try 12.555739 times

\$ ./testc 3 0.7
regret at 3 try and probability is 0.700000
Average try 12.353519 times

\$ ./testc 4 0.7
regret at 4 try and probability is 0.700000
Average try 13.336981 times

? getA(0.7)
%7 = [[12.368768965312072350806211697506991135, 10.940197536740643779377640268935562563, 8.8993812102100315344796810852620931754, 5.9839293151662997560540251085857083358, 2.7849705479859582316891771285773784732]~, 3]

lsr314

mathe 发表于 2020-12-23 17:21
你模拟的应该有问题：
计算后平均答题次数:
? getA(1.0/3.0)

能否贴一下代码，或者给一个p=1/2单次挑战成功的数据，用1表示答对，0表示答错，-1表示重新开始答题，看看算法是不是和实际的规则一致。
比如以下是一组测试数据：{1, 1, 0, 0, -1, 1, 0, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 1, 1, 0, 0, -1, 0, -1, 1, 1, 1, 1, 0, 0, -1, 0, -1, 0, -1, 1, 1, 1, 1, 1}
里面0和1的个数是33，表示总共答了33题，-1的个数是15，重启了15轮答题，总共答了16轮。

lsr314

mathe 发表于 2020-12-23 13:01
我计算结果和p相关，比如p

p=1/2的时候，如果已经答对三个了，第四个答错了复活的话，只要再答对2个就成功了，概率是1/4.如果不复活，下次连续答对三个的概率只有1/8，也就是大约8次重新答题（少说也要再答十几道题）才能到达现在的状态，感觉不符合直觉，放弃似乎不划算。

mathe

则本次挑战失败，重新答题，前面答对的清零，依然可以有一次复活机会
===
看来是我规则理解不对，也就是每次清零后可以重新复活了，我理解成每次开始挑战，直到挑战成功只有一次复活机会

lsr314

mathe 发表于 2020-12-23 19:13
则本次挑战失败，重新答题，前面答对的清零，依然可以有一次复活机会
===
看来是我规则理解不对，也就是 ...

对，每次可以重新复活，情况更复杂一点

mathe

用A0,A1,A2,A3,A4分别代表还没有使用掉复活机会，而且当前已经连续答对0,1,2,3,4道题时的状态
用B1,B2,B3,B4分别代表已经使用掉复活机会，而且当前已经连续大队1,2,3,4道题时的状态。
用a0,a1,a2,a3,a4,b1,b2,b3,b4代表在对应状态下，需要挑战成功的平均答题次数。
于是，如果至少一道答对就使用复活机会，得出

\(q=1-p, \begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_1\\b_2\\b_3\\b_4\end{pmatrix}=\begin{bmatrix}q&p&0&0&0&0&0&0&0\\0&0&p&0&0&q&0&0&0\\0&0&0&p&0&0&q&0&0\\0&0&0&0&p&0&0&q&0\\0&0&0&0&0&0&0&0&q\\q&0&0&0&0&0&p&0&0\\q&0&0&0&0&0&0&p&0\\q&0&0&0&0&0&0&0&p\\q&0&0&0&0&0&0&0&0\end{bmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_1\\b_2\\b_3\\b_4\end{pmatrix}+\begin{pmatrix}1\\1\\1\\1\\1\\1\\1\\1\\1\end{pmatrix}\)

而如果需要答对两道题目以上才会使用复活机会，那么得出
\(\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_2\\b_3\\b_4\end{pmatrix}=\begin{bmatrix}q&p&0&0&0&0&0&0\\q&0&p&0&0&0&0&0\\0&0&0&p&0&q&0&0\\0&0&0&0&p&0&q&0\\0&0&0&0&0&0&0&q\\q&0&0&0&0&0&p&0\\q&0&0&0&0&0&0&p\\q&0&0&0&0&0&0&0\end{bmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_2\\b_3\\b_4\end{pmatrix}+\begin{pmatrix}1\\1\\1\\1\\1\\1\\1\\1\end{pmatrix}\)

而如果需要答对三道题目以上才会使用复活机会，那么得出
\(\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_3\\b_4\end{pmatrix}=\begin{bmatrix}q&p&0&0&0&0&0\\q&0&p&0&0&0&0\\q&0&0&p&0&0&0\\0&0&0&0&p&q&0\\0&0&0&0&0&0&q\\q&0&0&0&0&0&p\\q&0&0&0&0&0&0\end{bmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_3\\b_4\end{pmatrix}+\begin{pmatrix}1\\1\\1\\1\\1\\1\\1\end{pmatrix}\)

而如果需要答对四道题目以上才会使用复活机会，那么得出
\(\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_4\end{pmatrix}=\begin{bmatrix}q&p&0&0&0&0\\q&0&p&0&0&0\\q&0&0&p&0&0\\q&0&0&0&p&0\\0&0&0&0&0&q\\q&0&0&0&0&0\end{bmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_4\end{pmatrix}+\begin{pmatrix}1\\1\\1\\1\\1\\1\end{pmatrix}\)

得到四个$a_0$对应的结果好像分别为
${4p^5 - 2p^4 - 2p^3 - 2p^2 - 2p - 1}/{4p^6 - 5p^5}, {3p^5 - 2p^4 - 2p^3 - 2p^2 - p - 1}/{3p^6 - 4p^5}, {2p^5 - 2p^4 - 2p^3 - p^2 - p - 1}/{2p^6 - 3p^5}, {p^5 - 2p^4 - p^3 - p^2 - p - 1}/{p^6 - 2p^5}$
结果显示不总是第二个最优
而是0.43691112721451127690774683642557996857<p<0.71973996370820249294954144847181472770时第二种方案最优
其余情况第一种方案最优