ゲーム「hades」のあるクエストの試行回数の期待値を計算してみた

何をやったのか

ゲーム「hades」でなかなか終わらないクエスト（ゲーム内では「運命の書」）があったので，試行回数の期待値を計算してみた。

クエストの内容は「ダイダロスの槌で全12種すべてのアップグレードを出す」というもので，武器ごとに6つのクエストがある。名称は次の通り。だいたいどれも最後の1個がなかなか出なくてヤキモキ，というかイライラしてしまった。

• 「忘却の剣」
• 「心追いの弓」
• 「混沌の盾」
• 「永遠の長槍」
• 「双拳」
• 「アダマント電磁砲」

入試問題っぽく言い換えて解く

このクエストを大学入試の問題っぽく言い換えるとこうなる。

「12枚」を一般化して「$n$枚」で考える。
$k$個の数字がノートに書いてある状態からスタートして，すべての数字が出揃うまでの試行回数の期待値を$E(k)$とする。
また，$k$個の数字がノートに書いてあるとき，次の試行の3枚がすべて既出の確率を$p_k$とする。
$$p_k=\frac{\binom{k}{3}}{\binom{n}{3}}\tag{1}$$

この試行の後の結果，既出の数の個数は次のように変化する。

• 確率$p_k$で$k$個のまま
• 確率$1-p_k$で$k+1$個に増える

これを漸化式で表す。

$$ \begin{align*} &E(k)=p_k \left\{1+E(k)\right\}+(1-p_k)\left\{1+E(k+1)\right\}\\ &\therefore E(k)=E(k+1)+\frac{1}{1-p_k}\tag{2} \end{align*} $$

この漸化式と「全部揃ったら終了」の$E(n)=0$を使うと一般項が求められる。

$$E(0)=E(n)+\sum_{k=0}^{n-1}\frac{1}{1-p_k}=\sum_{k=0}^{n-1} \frac{\binom{n}{3}}{\binom{n}{3}-\binom{k}{3}}\tag{3}$$

計算結果とその吟味

(3)は手計算は向かない形なので mathematica で計算した。
6 つのクエストを全部終えるのに必要な回数の期待値$6E(0)$は約105回だった。

      In[]:= Clear["Global`*"];
AbsoluteTiming[
 n = 12;
 p[k_] := Binomial[k, 3]/Binomial[n, 3];
 e[n] := 0;
 e[k_] := e[k] = e[k + 1] + 1/(1 - p[k]);
 ans = N[6*e@0, 5]]

Out[]= {0.0000935, 105.11}
    

私がこれらのクエストを終えるのにかかった回数はちょうど80回。
なかなか終わらなくて結構イライラしたが，実は運がよかったのかもしれない。

ただ，もう少し考えると，この2つの数字を単純に比較するのはおかしい。

• 私の80回はゲームの周回数
• 計算で求めた105回はダイダロスの槌の試行回数

1回のゲームでダイダロスの槌が出る回数は体感では$1+\alpha\ (0\lt \alpha \lt 1)$回といったところで，この分の補正を考えると自分の「80回」は普通の数字だったのかなと思う。

$105/80 \approx 1.31$から推測される$\alpha \approx 0.31$は直感的には妥当な結果に思える。