红黑牌游戏的最佳策略(2)

KeyTo9_Fans

一副牌有$54$张，其中红色牌和黑色牌各有$27$张。

玩家的初始得分是$0$，一局游戏有$54$轮。

每轮游戏，庄家都会从没亮过的牌里选定一张牌。

庄家选好牌后，玩家选择买红或者不买，然后庄家把所选的牌亮出来。

如果买红且庄家亮出了红色牌，那么玩家得$1$分；

如果买红且庄家亮出了黑色牌，那么玩家得$-1$分；

如果不买，那么亮牌后玩家的得分保持不变。

庄家亮过的牌会一直展示给玩家看，

因此玩家在每次亮牌前都可以根据庄家之前亮过的牌做决定。

玩家会采取最佳的买牌策略使得每局游戏得分之和的期望值尽可能大，

庄家会采取最佳的选牌策略使得玩家每局游戏得分之和的期望值尽可能小。

问每局游戏玩家得分之和的期望值是多少？

如果红色牌和黑色牌各有$n$张，那么每局游戏玩家得分之和的期望值是多少？

.·.·.

这个题真的有解吗？
比如n=1时候
庄家和玩家的第二步是确定的，只需要考虑双方的第一步是什么
红/买，+1
红/不买，0
黑/买，-1
黑/不买，1
于是需要引入纳什均衡，当大家都随机操作
……问题来了，如果n=2，纳什均衡会膨胀成什么样子
n=27呢……
……
不太会算纳什均衡
不过感觉如果用1的思路，外加如果这个纳什均衡能算而且不会出什么鬼差错，2其实不难

补充内容 (2018-6-21 01:48):
黑/买，-1这一行应该为黑/买，0，因为玩家第二次一定会选择继续买，从而填平损失

mathe

这题的确比另外一个容易计算。庄家会以50%概率出红色

mathe

纳什均衡的关键在于一方做了选择后，另外一方无论如何选择，得出最优概率都是一样
所以假设面对u红牌，v黑牌的局面，玩家最优期望得分为$E_{u,v}$,那么
假设庄家最优选择为以$p$的概率出红牌，$1-p$的概率出黑牌，而玩家以$q$的概率买红,$1-q$的概率不买红
于是有得分表

得分情况, 概率	买红	不买红
出红	$E_{u-1,v}+1, pq$	$E_{u-1,v},p(1-q)$
出黑	$E_{u,v-1}-1, (1-p)q$	$E_{u,v-1}, (1-p)(1-q)$

于是得出期望得分为$pq(E_{u-1,v}+1)+p(1-q)E_{u-1,v}+(1-p)q(E_{u,v-1}-1)+(1-p)(1-q)E_{u,v-1}=pE_{u-1,v}+(1-p)E_{u,v-1}+(2p-1)q$
所以在选择$p=1/2$时，得出结果和对方选择无关，也就是锁定了最优期望概率。
于是我们得出递推式$E_{u,v}={E_{u-1,v}+E_{u,v-1}}/2$,而特别的有初始条件$E_{u,0}=u, E_{0,v}=0$

mathe

设\(\begin{cases}E_{u,k}=u-k+\frac{f_k(u+k)}{2^{u+k}}&u\ge k\\E_{k,v}=\frac{g_k(v+k)}{2^{v+k}}&v\ge k\end{cases}\)
于是我们可以得出初始条件
\(\begin{cases}f_0(u)=0\\g_0(v)=0\end{cases}\)
以及边界条件\(f_k(2k)=g_k(2k)\)
代入递推式我们有
\(\begin{cases}f_k(x+1)-f_k(x)=f_{k-1}(x)\\g_k(y+1)-g_k(y)=g_{k-1}(y)\end{cases}\)
于是容易归纳假设得$f_k(u)=g_k(u)$
\(f_k(2k)=2^{2k-1}+2f_{k-1}(2k-1)\)
记\(\Delta f(x)\)代表\(f(x)\)的差分函数，即\(\Delta f(x)=f(x+1)-f(x)\), 而\(\Delta^{(0)}f(x)=f(x),\Delta^{(n+1)}f(x)=\Delta\Delta^{(n)}f(x)\)
于是容易看出对于n次多项式f(x),\(\Delta f(x)\)是n-1次多项式，而\(\Delta^{(n)}f(x)\)是常数而\(\Delta^{(n+1)}f(x)=0\)
显然对于本题，我们现在有\(f_{k-1}(x)=\Delta f_k(x)\)
显然$f_k(u)=g_k(u)$是u的k-1次多项式

接下去可以递推计算
$f_0(x)=0$
所以$f_1(2)=2^1+2f_0(1)=2$
$f_1(h)=2+\sum_{t=2}^{h-1} f_1(t)=2$
所以$f_1(x)=2$
由于$f_2(4)=2^3+2f_1(3)=12$
所以$f_2(h)=12+\sum_{t=4}^{h-1} f_2(t)=12+2(h-4)=2h+4$
所以得出$f_2(x)=2x+4$
...
另外我们容易得出$f_k(x) ~= {2x^{k-1}}/{(k-1)!}$

mathe

另外一种比较方便的计算方法可以设$f_k(x)=\sum_{i=0}^{k-1} a_{k-1-i} C_x^i$
利用$f_k(2k)=2^{2k-1}+2f_{k-1}(2k-1)$,我们就可以得出$a_k$的递推式
$a_{k-1}=2^{2k-1}+\sum_{i=0}^{k-2}a_{k-2-i}(2C_{2k-1}^i-C_{2k}^{i+1})=2^{2k-1}-\sum_{i=0}^{k-2}a_{k-2-i}(C_{2k-1}^{i+1}-C_{2k-1}^i)$
而根据$f_1(x)=2$有$a_0=2$
于是$a_1=2^3-2(C_3^1-C_3^0)=4$,所以$f_2(x)=2C_x^1+4=2x+4$
$a_2=2^5-a_1(C_5^1-C_5^0)-a_0(C_5^2-C_5^1)=32-4*4-2*5=6$,所以$f_3(x)=2C_x^2+4C_x^1+6=x^2+3x+6$

mathe

进一步推导有$a_{k-1}=2k$
所以$f_k(2k)=\sum_{i=1}^k 2iC_{2k}^{k-i}=2\sum_{i=1}^k kC_{2k}^{k-i} -2\sum_{i=1}^k (k-i)C_{2k}^{k-i}$
由于$(k-i)C_{2k}^{k-i}=\frac{(2k)!}{(k-i-1)!(k+i)!}=2kC_{2k-1}^{k-i-1}$
所以$f_k(2k)=2k\sum_{i=1}^k (C_{2k}^{k-i} - 2C_{2k-1}^{k-i-1})=2k\sum_{i=1}^k (C_{2k-1}^{k-i}-C_{2k-1}^{k-i-1})=2kC_{2k-1}^{k-1}$
于是
$E_{k,k}=\frac{2kC_{2k-1}^{k-1}}{2^{2k}}=\frac{(2k)!}{2^{2k}(k-1)!k!}~=\frac{k^k}{e\sqrt{\pi}(k-1)^{k-1/2}}~=\sqrt{k/\pi}$
比如本题中扑克牌例子就是计算$E_{27,27}=2.918$,而最后的采用近似结果是$2.932$