問題

500個入りのボックスガチャがあり、これを1個ずつ引いていく。1個あるティアラを引くと中身をリセットすることができる。
この中に2つあるスタドリがなるべく多く欲しいので、効率を最大化する戦略を考えたい。いつリセットするのが適切だろうか？

いくつかの戦略を考えてみる。

箱を全部開けるとき

スタドリ率は $\frac{2}{500} = 0.4\%$ 。それはそう。

リセットアイテムが出たら即リセするとき

この場合は全部回す場合に同じ。ざっくり考えて、リセット基準がスタドリを引いたかどうかに依存しないので、上がりも下がりもしない。

スタドリが全部出るまで回してからリセットするとき

要はスタドリとリセットアイテムの全てを引いた場合にリセットなので、次の問題を考えれば良い。

500個のくじにあたり3つがあり、全てが出るまで引き続ける。引いた個数の期待値はいくらか？

アイテムの配置は ${}_{500}\mathrm{C}_3$ 通り、k 回目でちょうどあたりが3つ揃う場合は ${}_{k-1} \mathrm{C}_2$ 通りであるから、期待値は次のように計算できる。

\begin{aligned} E &= \sum_{k=3}^{500} k \cdot \frac{{}_{k-1} \mathrm{C}_2}{{}_{500} \mathrm{C}_3} \\ &= \frac{1}{{}_{500} \mathrm{C}_3}\sum_{k=3}^{500} \frac{k \cdot k - 1 \cdot k-2}{2!} \\ &= \frac{1}{{}_{500} \mathrm{C}_3} \frac{1}{2!} \cdot \frac{1}{4} \sum_{k=3}^{500} {}_{k+1} \mathrm{P}_4 - {}_{k} \mathrm{P}_4 \\ &= \frac{1}{2!}\frac{1}{4} \frac{3!}{{}_{500} \mathrm{P}_3} ({}_{501} \mathrm{P}_4 - 0)\\ &= \frac{3}{4} \cdot 501 \end{aligned}

したがってこの場合のスタドリ率は $\frac{4}{3} \cdot \frac{2}{501} = 0.532\%$ となる。大体1.33倍ほど効率が良い。

常に期待値を計算する場合

ある箱において、スタドリの割合(スタドリの数/総数)を最大化したい。そうすると、まだスタドリが残っていても利確する戦略が考えられる。
すなわち、リセットの権利がある場合に、引き続けた場合と現状で確定してリセットする場合の期待値をそれぞれ計算し、良い方の選択を取りたい。
以下、計算のために全回数をm回し、n回目の試行終了後にティアラが出ている場合を考える。出たスタドリの個数で場合分けする。

スタドリが2個出ている場合

これ以上スタドリが出ることはなく、即座にリセットするべき。

スタドリが0個出ている場合

スタドリが1個も出ていないので、引き続けて損する場合がない。少なくともスタドリが1個出るまで引き続けるべきである。

スタドリが1個出ている場合

n回目でスタドリが1個とティアラが出た場合を考える。
この場合、ここでリセットすれば確率は $\frac{1}{n}$ ,2個目が出るまで引く場合、確率の期待値は $\sum_{k=n+1}^{m} \frac{1}{m-n} \frac{2}{k}$ である。

m=500としてこれを計算すると、n<=142までは引き直したほうが得、n>=143以降はリセットしたほうが得という結果になる。

142という数がどこから来たか見るために、別の方法でこの式を考える。

f(n) = \frac{1}{n}-\frac{1}{m-n} \sum_{k=n+1}^{m} \frac{1}{k}

なる $f(n)$ を考える。これが $>0$ ならリセットが得、 $<0$ なら引き続けるのが得となる。
$\sum \frac{1}{k}$ をlogで乱暴に近似すれば、

f(n) = \frac{1}{n}-\frac{2}{m-n}(\log m - \log n)

と表せる。 $t=m/n$ を導入してf(n)を変形すると

f(t) = \frac{t}{m(t-1)}(t-2\log t-1)

となる。 $t-2\log t-1$ は解析的に解けないが、増減を調べると $1 < t < \alpha$ で $<0$ , $t > \alpha$ で $>0$ となる。ただし、 $\alpha = 3.513...$ 。
nに直すと、 $n < m / \alpha$ で>0, $n > m/ \alpha$ で<0。 $m=500$ を代入して $n$ を計算すると $142.33$ となり、先程の結果にほぼ一致する。

実証(シミュレーション)

メダル10億枚(試行1億回)でシミュレーションさせた。使用したコードは最後に記載。結果は以下。

全部引く場合：ガチャ回数100000000, スタドリ数532241, 割合0.5322%
期待値を考慮する場合：ガチャ回数100000000, スタドリ数535686, 割合0.5357%

何回か回したが、多めに見積もって0.004%ほど差がある結果になった。メダル10万枚でおおよそスタドリ0.4本分。メダル25万枚あって1本差が出るかどうかである。

結論

最適を求めるなら、142回目までにスタドリ1個とティアラが1個出ればリセット。それ以外は出るまで回せ。

とはいえ、結局誤差だし、そんなことのために10連ずつ(あるいは1連ずつ)結果の確認なんてしてられないので、自動ストップを使ってひたすらぶん回したほうがいい。

考察

chatGPTに試行させたこちらの結果とも概ね一致する結果に見える。素朴に考えれば、リセットのしきい値は250回になるような気もするのだが、それとは異なるのが意外だった。

使用したコード

少し重たいので実行の際はを気をつけてください。

import random

#全て出るまで試行する。nmaxは引けるガチャの回数の最大値
def all(nmax):
    [t, s1, s2] = random.sample(range(1,501), 3)
    
    #ティアラ、スタドリのうち一番後ろにあるものを返す。
    n = max(t,s1,s2)
    if n <= nmax:
        return (n, 2)
    else:
        #引ききれない場合の処理
        d = 0
        if nmax <= s1:
            d+=1
        if nmax <= s2:
            d+=1
        return (nmax, d)

threshold = 143
        
#指定回数で1コスタドリが出てたらやめる。nmaxは引けるガチャの回数の最大値
def expectation(nmax):
    [t, s1, s2] = random.sample(range(1,501), 3)
    
    flg = False
    d = 0
    for i in range(1, 501):
        if i == t:
            flg = True
        if i == s1 or i == s2:
            d += 1

        if i == nmax:
            return (i, d)
        if flg:
            if d == 2:
                return (i, d)
            elif d == 1 and i < threshold:
                return (i, d)



LEFT = 100_000_000

left = LEFT
drink = 0
while left > 0:
    n, d = all(left)
    left -= n
    drink += d
print(f"全部引く場合：ガチャ回数{LEFT}, スタドリ数{drink}, 割合{(drink * 100 / LEFT):.4f}%")

left = LEFT
drink = 0
while left > 0:
    n, d = expectation(left)
    left -= n
    drink += d
print(f"期待値を考慮する場合：ガチャ回数{LEFT}, スタドリ数{drink}, 割合{(drink * 100 / LEFT):.4f}%")

日記