KeyTo9_Fans 发表于 2018-6-15 21:28:14

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

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

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

每轮游戏,庄家都会从没亮过的牌里随机选一张牌亮出来(每张牌被选中的概率相等)。

在亮牌前,玩家可以选择买红或者不买。

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

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

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

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

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

玩家希望每局游戏得分之和的期望值尽可能大。

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

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

.·.·. 发表于 2018-6-18 03:18:32

……不知为何firefox发不了图片(准确地说是打不开附件那个框)
或许该重装了……
以及图片画得很渣
题目很有趣,也很难,给出了一个编程计算的方法
然而没编程序

思想的核心是,利用国际象棋的残局进行枚举
不妨记终点(图片的右下角)为0,因为在这个点我们已经无利可图了。
然后,画格子,假设在终点,每向左边走一个格子,庄家手里就多一张红牌,每向上走一个格子,庄家手里就多一张黑牌
首先走一步,我们可以发现,从残局格子开始,往左数第i个格子的值应该是i(因为玩家知道庄家手里只有红牌了,于是玩家会选择买买买……)往上(直着往上不拐弯)的全部格子都是0
然后,假设现在在格子A=A(p,q)(有p张红牌和q张黑牌的格子)
EA(p,q)=max(在这个格子买的收益,在这个格子不操作的收益)
$E(A(p,q))=\frac{p}{p+q}E(A(p-1,q))+\frac{q}{p+q}E(A(p,q-1))+max(0,\frac{p}{p+q}-\frac{q}{p+q})$
然后,用动态规划或者递归
反正是一个二维的问题,并不麻烦

mathe 发表于 2018-6-20 08:02:10

我们如果使用楼上的公式递推下去,除了继续包含E(A(.,.))的项,还会产生很多常数项。
其中每个常数项都是由某个E(A(x,y))产生($x>y$),这一项产生的值是E(A(x,y))本身的系数再乘上${x-y}/{x+y}$
而如果我们从某个E(A(p,q))出发利用上面公式反复递推到E(A(x,y)),在棋盘上相当于需要遍历所有从点(p,q)到(x,y)的最短路径
其中,每次从其中一个(u,v)移动到下一个(u-1,v)或(u,v-1),产生的系数的分母都是u+v,而对应分子如果横坐标变化就是u,纵坐标变化就是v
由于乘法可以交换,而所有从(p,q)到(x,y)的路径都需要变化所有p->x的横坐标和q->y的纵坐标,所以每条(p,q)到(x,y)的最短路径都需要产生相同的系数
$\frac{p!q!(x+y)!}{(p+q)!x!y!}=\frac{C_{x+y}^x}{C_{p+q}^p}$,而所有这样的路径的数目有$C_{p+q-x-y}^{p-x}$
所以E(A(x,y))前面的系数是$\frac{C_{p+q-x-y}^{p-x}C_{x+y}^x}{C_{p+q}^p}$
需要注意上面的递推式对于$p=0$或$q=0$也都是成立的,由此我们得出
\(E(A(p,q))=\frac1{C_{p+q}^p}\sum_{x=1}^p\sum_{y=0}^{\min\{q,x-1\}} C_{p+q-x-y}^{p-x}C_{x+y}^x\frac{x-y}{x+y}\)
于是
\(E(A(p,p))=\frac1{C_{2p}^p}\sum_{x=1}^p\sum_{y=0}^{x-1} C_{2p-x-y}^{p-x}C_{x+y}^x\frac{x-y}{x+y}\)
\(E(A(p,p))=\sum_{x=1}^p\sum_{y=0}^{x-1} \frac{C_p^xC_p^y}{C_{2p}^{x+y}}\frac{x-y}{x+y}=\sum_{s=1}^{2p-1}\frac{1}{C_{2p}^s}\sum_{y=0}^{\lfloor\frac {s-1}2\rfloor}C_p^{s-y}C_p^y\frac{s-2y}s\)


mathe 发表于 2018-6-20 16:39:18

这个比较难估算其近似值,计算机计算表明大概在$0.875\sqrt(p)$,而模型2中是$\sqrt(p/\pi)~=0.564\sqrt(p)$

mathe 发表于 2018-6-20 18:58:37

我们可以先计算
\(\sum_{t=0}^sC_p^tC_p^{s-t}(s-2t)^2=s^2C_{2p}^s-4p(s-1)C_{2p-1}^{s-1}+4p(p-1)C_{2p-2}^{s-2}\)
\(\frac1{C_{2p}^s}\sum_{t=0}^sC_p^tC_p^{s-t}(s-2t)^2=s^2-4p(s-1)\frac{s}{2p}+4p(p-1)\frac{(s-1)s}{(2p-1)2p}\)
\(\frac1{C_{2p}^s}\sum_{t=0}^sC_p^tC_p^{s-t}(s-2t)^2=\frac{2ps-s^2}{2p-1}\)
所以\(\frac1{C_{2p}^s}\sum_{t=0}^sC_p^tC_p^{s-t}|s-2t|\le\sqrt{\frac1{C_{2p}^s}\sum_{t=0}^sC_p^tC_p^{s-t}(s-2t)^2}=\sqrt{\frac{2ps-s^2}{2p-1}}\)
\(E(A(p,p))=\sum_{s=1}^{2p-1}\frac{1}{C_{2p}^s}\sum_{y=0}^{\lfloor\frac {s-1}2\rfloor}C_p^{s-y}C_p^y\frac{s-2y}s\le \sum_{s=1}^{2p-1}\frac{1}{2}\sqrt{\frac{2p-s}{s(2p-1)}}\)
所以\(E(A(p,p))\le \sum_{s=1}^{2p-1}\frac{1}{2}\sqrt{\frac{2p-s}{s(2p-1)}}\le\sum_{s=1}^{2p-1}\frac{1}{2\sqrt{s}}\le\int_1^{2p}\frac{dx}{2\sqrt{x}}=\sqrt{2p}-1\)
于是结合策略(2)中结论,我们有\(\sqrt{\frac{p}{\pi}}\le E(A(p,p))\le\sqrt{2p}-1\)
还可以利用Beta函数,有更加精确一点的估计:
\
页: [1]
查看完整版本: 红黑牌游戏的最佳策略(1)