CF98E

首先，最优策略不一定是每次去问自己没有的牌，而是来问自己拥有的牌来让对手认为这张是桌上那张牌。

所以说，两个人在每个回合都有三种操作

1. 去猜一张自己没有的牌。
2. 去猜一张自己拥有的牌，以此来混淆对手
3. 去猜桌子上的牌。

对于它的对手来说，如果它的对手选择了猜，且自己并没有猜的牌。

那么他也有两种选择，一种是相信没有的牌就是桌子上的牌，然后直接猜桌子上的牌是什么，还有一种就是继续以上的三种操作（但要注意此时第一个人应该还有牌）。

否则还是正常游戏。

令$P(m,n)$表示第一个人有$m$张牌，第二个人有$n$张牌的赢得游戏的概率。

可以列出表格（其中左边的列是第一个人的操作，上面的行是第二个玩家的操作）

稍微解释一下里面的东西如何得到：

首先就是第一个人猜自己没有的牌，那么有$\frac{1}{n+1}$的概率猜到桌子上的牌，此时第二个人可以直接相信并取得胜利，或者在下一个回合自己胜利。有$\frac{n}{n+1}$的可能猜到第二个人的牌，此时游戏继续，此时第二个人有$P(n-1,m)$的可能性第二个人获胜。那么这样获胜的总概率为$\frac{n}{n+1}\times (1-P(n-1,m))$。

其他还是比较显然的… 然后算出所有的P的就可以解决问题，答案即$P(m,n)$。

以及注意当$m,n\ge 1$且游戏没有鞍点是，直接猜测桌子上的牌是不优的。

然后是纳什平衡（直接开始搬了）：

混合策略的纳什均衡采用随机化来对抗对手的策略，也就是说在这个策略下无论对手采用什么样的策略都不会改变期望收益，否则一定可以通过调整概率来达到跟好的均衡。

这题就是 $$ p\times( \frac{n}{(n+1)}\times (1-P(n-1,m)))+ (1-p)\times( \frac{1}{n+1}+\frac{n}{(n+1)}\times (1-P(n-1,m)))=p +((1-p) \times 1-P(n,m-1)) $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

double P[2222][2222];
inline double f(int n,int m)
{
	if(!n) return 1.0/(1.0+m);
	if(!m) return 1.0;
	if(P[n][m]) return P[n][m];
	double A=1.0*m/(m+1.0)*(1.0-f(m-1,n));
	double B=1.0;
	double C=1.0/(m+1.0)+A;
	double D=1.0-f(m,n-1.0);
	double p=(D-B)/(A-B-C+D);
	return P[n][m]=p*A+(1.0-p)*B;
}
signed main()
{
	int a=read(),b=read();
	printf("%.18lf %.18lf\n",f(a,b),1.0-f(a,b));
}