Project Euler 227

题目

The Chase

The Chase is a game played with two dice and an even number of players.

The players sit around a table; the game begins with two opposite players having one die each. On each turn, the two players with a die roll it.

If a player rolls a $1$, he passes the die to his neighbour on the left; if he rolls a $6$, he passes the die to his neighbour on the right; otherwise, he keeps the die for the next turn.

The game ends when one player has both dice after they have been rolled and passed; that player has then lost.

In a game with $100$ players, what is the expected number of turns the game lasts?

Give your answer rounded to ten significant digits.

解决方案

令 $N=100$，注意 $N$ 必须是偶数，并令 $M={\displaystyle \frac{N}{2}}$。不难发现，当前游戏的状态并不取决于是哪两个人拿着骰子，而只取决于拿着骰子的两个人的距离（注意这个距离是指比较短的那段距离，也就是两个人在圆上的劣弧长度）。

那么，令 $d_N(x)=min(x\mathrm{\%}N,(-x)\mathrm{\%}N)$，其中 $x$ 是两人在优弧或者劣弧上的距离，$d_N(x)$ 用于求出两人在劣弧上的距离。

根据题意，两人同时抛骰子，那么两个人距离的变化值的分布律可以写出：

$d$	$-2$	$-1$	$0$	$1$	$2$
$p(d)$	${\displaystyle \frac{1}{36}}$	${\displaystyle \frac{2}{9}}$	${\displaystyle \frac{1}{2}}$	${\displaystyle \frac{2}{9}}$	${\displaystyle \frac{1}{36}}$

那么，令状态 $f(i)(0\le i\le M)$ 表示从游戏一开始后，两个骰子之间的距离第一次达到 $i$ 的期望游戏轮数。对于 $\mathrm{\forall }i,0\le i<M$，可以写出：

$$f(i)=1+\sum _{d=-2}^{2}f(d_N(i+d))\cdot p(d)(1)$$

由于游戏的初始状态是 $M$，因此 $f(M)=0$。

这是一个有后效性的动态规划方程，因为状态之间形成了循环的依赖（状态 $i$ 依赖于自身）。不过，这种情况下消除后效性很简单。右边有一个项也是 $f(i)$，只需要挪到左边消除就可以完成消除后效性，从而正确计算结果。

那么，将 $f$ 中的每一个值全部当成是未知数，那么方程 $(1)$ 和 $f(M)=0$ 构成了一个 $M+1$ 元的线性方程组，解这个方程组即可，最终 $f(0)$ 即为答案。

代码

import numpy as np

N = 100
con = [1, 8, -18, 8, 1]
M = N >> 1
b = [-36] * M + [0]
a = []
for i in range(M):
    t = [0 for _ in range(M + 1)]
    for j in range(5):
        x = i + j - 2
        t[min(x % N, -x % N)] += con[j]
    a.append(t)
a.append([0] * M + [1])
x = np.linalg.solve(a, b)
ans = x[0]
print("{:.6f}".format(ans))