记$f(i,j)$为当玩家二行动时，玩家一、二分别还需至少i,j分才能获胜的局面下玩家二获胜的最大概率，那么有边界值$f(i,0)=1$。
假设玩家二选择了次数T，则他有$a=1/2^T$的机会得$p=2^{T-1}$分，也有$b=1-a$的机会不得分。
考虑抛掷的结果共四种情况，可得
$$f(i,j)=\frac{1}{2}\left(af(i-1,j-p)+bf(i-1,j)\right)+\frac{1}{2}\left(af(i,j-p)+bf(i,j)\right),$$
移项后得递推公式
$$f(i,j)=\frac{0.5\left(af(i-1,j-p)+bf(i-1,j)+af(i,j-p)\right)}{1-0.5bf(i,j)},$$
递推计算即得结果$0.83648556$。
f=[[0]*101 for i in range(101)]
for i in range(101):
f[i][0]=1
for i in range(1,101):
for j in range(1,101):
for k in [1,2,4,8,16,32,64,128]:
p=max(j-k,0)
a=0.5/k
b=1-a
f[i][j]=max(f[i][j],(0.5*a*(f[i-1][p]+f[i][p])+0.5*b*f[i-1][j])/(1-0.5*b))
print "%.8f" %(0.5*(f[100][100]+f[99][100]))
|
