找回密码
 欢迎注册
查看: 15368|回复: 6

[原创] 红黑牌游戏的最佳策略(1)

[复制链接]
发表于 2018-6-15 21:28:14 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
一副牌有$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})$
然后,用动态规划或者递归
反正是一个二维的问题,并不麻烦

点评

不只是这一个论坛……所有论坛都有问题……  发表于 2018-6-20 01:35
非 firefox 的问题,而是论坛的代码对它兼容有问题,请换一个浏览器上传附件。  发表于 2018-6-19 07:56
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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\)


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-20 16:39:18 | 显示全部楼层
这个比较难估算其近似值,计算机计算表明大概在$0.875\sqrt(p)$,而模型2中是$\sqrt(p/\pi)~=0.564\sqrt(p)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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函数,有更加精确一点的估计:
\[E(A(p,p))\le \sum_{s=1}^{2p-1}\frac{1}{2}\sqrt{\frac{2p-s}{s(2p-1)}}\le\int_0^{2p-1}\sqrt{\frac{2p-x}{x(2p-1)}}\frac{dx}2<\frac{p}{\sqrt{2p-1}}\int_0^1\sqrt{\frac{1-y}{y}}dy=\frac{p}{\sqrt{2p-1}}\int_0^1(1-y)^{\frac1 2}y^{-\frac1 2}dy=\frac{B(\frac1 2, \frac 3 2)p}{\sqrt{2p-1}}=\frac{\Gamma(\frac1 2)\Gamma(\frac3 2)p}{\Gamma(2)\sqrt{2p-1}}=\frac{\pi p}{2\sqrt{2p-1}}\]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 06:49 , Processed in 0.043836 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表