コンプガチャの数理 -コンプに必要な期待回数の計算方法について-

4. 『コンプガチャの数理 -ガイドラインに基づいたゲームデザインその2-』

目的

コンプガチャのコンプに必要な回数を求める問題は「The Coupon Collector's Problem」と呼ばれる数学モデルの枠組みに沿った美しい問題である事を述べ，いくつかの有用な結果を示す。

※ あくまで個人研究のつもりで書いたので，色々不備があるかもしれません。その際は一言頂けると助かります。

定義

コンプガチャ問題を Coupon Collector's Problem に準じた形で書くと以下の様になる：

「全部で n 種類のアイテムがあって，1つのガチャの中にアイテムが1つ入っているけれども，ガチャを空けるまではその中身はわからない。今，アイテム集めに関しては他の人と協力しない（トレードや売買をしない）という前提の元で，n 種類のアイテムを全部コンプリートするのにいったいいくつのガチャを買わないといけないだろうか？」

※ 例えば n 種類の中の特定の m 種類（レアガチャ）を集めれば良いといった問題は今回は対象としていない。

結果

1. 全アイテムの出現確率が等確率の場合

全アイテムの出現確率が等確率，つまり 1/n の場合は大学学部レベルの数学でこの問題を解くことができる。

今， $X_{i}$ を新たなガチャが出るまでに買わないといけない数であるとする。n 種類のガチャを全て得るための回数をとすると，本問題におけるゴールはの期待値 E[X] を求める事に等しい。

$X=\Sigma_{i=1}^{n} X_{i}$ であるから期待値の線形性より $E[X]=\Sigma_{i=1}^{n} E[X_{i}]$ であるので， E[X] を求めるには任意の i において E[X_i] を計算できれば良いことになる。さて， E[X_i] の計算は任意の i で X_i が幾何分布に従っているという事実から簡単に求めることができる。

※ 幾何分布とは「確率 p で表が出るコイン投げを行ったとき，n 回目に初めて表が出る確率」を表現するものであり，

$p(X=n)=(1-p)^{n-1}p$

と表現される。p は幾何分布のパラメータと呼ばれる。この期待値 E[X]=1/p である。これは例えば p=1/2 のコイン投げにおいて、初めて表が出る期待回数は 2 回という事を示している。

今，既に i-1 種類のガチャを集めているとする。この時新しいアイテムが得られる確率は 1 から現在持っている i-1 種類のガチャが選ばれる確率を引けば良いので,

$p_{i}=1-\frac{i-1}{n} = -\frac{1}{n}i + \frac{n+1}{n}$

である。当たり前だが，この確率の示すところは，i （既に集めているアイテムの数）が大きくなれば p_i （新しいアイテムが得られる確率）が小さくなっていくことである。

ところで、 X_i はパラメータ p_i を持った幾何分布であるので，

$E[X_i]=\frac{1}{p_i} = \frac{n}{n-i+1}$

である。よって

$E[X]=\Sigma_{i=1}^{n} E[X_i]=\Sigma_{i=1}^{n}\frac{n}{n-i+1}= n\Sigma_{i=1}^{n}\frac{1}{i}$

となる。ここで $\Sigma\frac{1}{i}$ は Harmonic Number: H(n) と呼ばれる。

∴ n 種類全てのアイテムをコンプするために必要な期待回数は nH(n) 回である。

$ln(n) \leq H(n) \leq ln(n) + 1$

であるので，期待回数はまた $n\ln(n)+\Theta(n)$ とも書ける。

$e=2.72,\quad e^{2}=7.39,\quad e^{3}=20.09,\quad e^{4}=54.60,\quad e^{5}=148.41$

であるので，n=3 で 2n+α，n=8 で 3n+α，n=20 で 4n+α，n=150 で 5n+α n=3 で n+α，n=8 で 2n+α，n=20 で 3n+α，n=55 で 4n+α，n=150 で 5n+α 程度の回数を必要とする。

例

AKB48「ポスター44種類コンプでイベント招待」企画，「独禁法違反」のおそれで中止

解: 今44種類のポスターを全てコンプするのに必要な期待回数は 44*H(44) である。

Rでは H(n) を以下の様に定義することができる:

つまり44枚のポスターを全部コンプするのに必要なCDは192枚ということになる。CDは1250円であったらしいので、全部コンプするのに 1250*192 = 240,000（24万円！）かかることになる。

また、n を1から50まで動かした時の期待回数は以下の通り。

今求めているのはあくまで期待値であるので実際はこの期待値まわりの値にばらつく。

そのばらつき具合は Y がパラメータ p を持つ幾何分布であるとき，その分散が

$Var[X]=\frac{1-p}{p^2}\lt\frac{1}{p^2}$

であることを利用して、

$Var[X]=\Sigma_{i=1}^{n}Var[X_i]\leq\Sigma_{i=1}^{n}\left(\frac{n}{n-i+1}\right)^2= n^2\Sigma_{i=1}^{n}\left(\frac{1}{i}\right)^2\leq\frac{\pi^{2}n^{2}}{6}$

となる。この結果に Chebychev の不等式を適用することで（導出省略）以下のさらに強い結果を言うことができる：

「2nln(n) 回ガチャを回してもまだアイテムをコンプできていない確率は 1/n 以下である」

先ほどのAKB48の例では「CDを 2*44*ln(44)=333 枚（416,250円）買ったとしてもまだポスターをコンプできない人は 2.3% 程度に過ぎない」，つまり50万円を持っておけば準備はほぼ万全と言える。

(Q. 以上の結果を踏まえると，ポスターのコンプリートセットを販売するとするなら，いくらの値段設定が妥当であろうか？例えば10万円なら本気でコンプリートしたい人には安い設定となる)

2. 出現確率が互いに異なる確率の場合

ここで考える問題は，全 3 種類のコンプガチャゲームがあったとき，その3種類の出現確率が ( p_1,p_2,p_3 ) = (1/6, 1/3, 1/2) と異なって設定されている場合である。

一般にはこちらの状況の方が多いが，式の導出はなかなかのハイレベルなので結果のみを示すことにする。詳細は http://algo.inria.fr/flajolet/Publications/FlGaTh92.pdf を参照。

∴n 種類のアイテムをコンプするのに必要な期待回数は，

$E[X]=\Sigma_{i=0}^{n-1}(-1)^{n-1-i} \Sigma_{|J|=i}\frac{1}{1-P_j},\qquad\qquad\qquad\left(P_j=\Sigma_{j \in J}p_j\right)$

である。

(ただし $\Sigma_{i=1}^{n}p_i=1$ ）この結果より，以下の事がわかる：

等確率の設定よりもコンプに必要な回数は遙かに多くなる
出現確率のばらつきによってもコンプに必要な回数は変動する
300円ガチャであれば10種類のアイテム数でもコンプまでに10万円以上かかる設定が可能である

以下が主な数値結果。

# 3種類

(1/3,1/3,1/3) -> 5.5回
(1/6,1/3,1/2) -> 7.3回
(1/10,4/10,5/10) -> 10.7回

# 20種類（括弧内は確率ではなくそれぞれのアイテムの重み）

(1,1,...,1) [等確率] -> 72回，21,586円
(1,1,1,1,1,10,...,10) [5個のレアイテムと15個のアイテム] -> 354回，106,195円

# 10種類（括弧内は確率ではなくそれぞれのアイテムの重み）

(1,1,...,1) [等確率] -> 29回，8,787円
(1,1,1,30,...,30) [3個の超レアイテムと7個のアイテム] -> 390回, 117,152円

R コードは本文の最後に記載。

感想

ソーシャルゲームのコンプガチャやAKBのポスター購入戦略のすごいところは，数学モデルのレールに沿った仕組みを実世界で提供することにより，物事を有利に進められる点である。例えばあるイベントにおいては本イベント期間での売上目標を x 円と定めたとすると，この目標は以下の具体的なアクションスキームまで落とし込むことができる：

アイテムを n 種類用意する
確率テーブルを (p_1, p_2,...) に設定する
以下の様な見込みセグメントにおいて，ユーザー数 a, b,...人と期待金額 x_1, x_2,...円に設定する

コンプするユーザー a 人 --(計算)--> x_1 円
3/4種類集めるユーザー b 人 --(計算)--> x_2 円
半分種類集めるユーザー c 人 --(計算)--> x_3 円
...

（以上のパラメータは全て事前に定める事ができる。）

後はイベントにおいて，各セグメントを達成するユーザー数が a, b, c,... となるように工夫をしていけば良い。

データマイニングがデータ（結果）から数学モデルを見いだし，調節可能なパラメータを見いだしそれを変更することで改善を図る戦略なのに対し，上記の戦略は数学理論に沿ったデザインを初めから提供することで調節可能なパラメータを初めから握っておくという対照的なものであると言える。

また，今後コンプガチャに代わるデザインを考える場合にも数学モデルに基づいたものを検討するのは有効な戦略と考える。「Coupon Collector's Problem」にも色々な派生があり，またより大きな視点で見れば Coupon Collector's Problem は「Balls and Bins Problem」の一部であると考えることができる。つまりこれらのモデルをうまくデザインすることができれば，それはまたコンプガチャと同じように結果が予測可能で具体的なアクションに落とし込むことができるゲームを作ることができるかもしれない。以下の問題と結果は，次のデザインを生み出すヒントになるかもしれない。

a. Birthday Paradox

「全 n 種類のアイテムの出現確率の等しいガチャがある。ゲームのルールを同じアイテムが 2 個揃った（つまり重複した）時点でユーザーにご褒美がもらえるとする。このとき， $\Omega(\sqrt{n})$ 回で初めて重複する確率が 1/2 以上になる」

b. Balls and Bins Problem

「全 n 種類のアイテムの出現確率の等しいガチャがある。今ユーザーは n 回ガチャを回すチャンスがあり，どれかのアイテムが k 個以上重複していれば（これを最大内容量と呼ぶ）ユーザーにご褒美がもらえるとする。このとき最大容量 k が 3ln(n) / ln(ln(n)) より大きくなるのは 1/n でしか無い。」

c. Coupon Collector's Problem

「より優しいガチャコンプ問題を考える。1つのガチャからは1種類のアイテムが得られるのでは無く，ランダムに選ばれた d 種類のアイテムが掲載されたカタログが得られ，ユーザーはそこからどれか 1 つのアイテムを選択することができる。ユーザーは合理的な選択，つまり自分が今持っていないアイテムを選択するという過程のもとでは，コンプまでの期待回数は

$\Sigma_{i=0}^{n-1}\frac{1}{1- {i \choose d}/{n \choose d}}$