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=\dfrac{N}{2}$。不难发现，当前游戏的状态并不取决于是哪两个人拿着骰子，而只取决于拿着骰子的两个人的距离（注意这个距离是指比较短的那段距离，也就是两个人在圆上的劣弧长度）。

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

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

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

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

$$f(i)=1+\sum_{d=-2}^2f(d_N(i+d))\cdot p(d)\qquad(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))