ガチャのひみつ（重み付き乱択アルゴリズム）

PHP,アルゴリズム,ソーシャルゲーム,ガチャ,プログラミング初心者

確率ってなんだっけ？

　確率とは何なのだろう。学校で習った確率は、起こりうるすべてのパターンの中から、ある一つの出来事が起こる可能性の高さ（あるいは低さ）を計算で求めたり、それをパーセントで表したりするものであった。

　例えばサイコロを振って、１の目が出る確率、２の目が出る確率、３の目がでる確率、４の目がでる確率、５の目が出る確率、６の目が出る確率。これらがすべて６分の１の確率なのは、起こりうる出来事のパターンが６パターンあるが、実際にサイコロを振ったときにでる目は６パターンのうちの１パターンだからというわけだ。

<?php
$dice = array(
    "1の目"    => 1,
    "2の目"    => 2,
    "3の目"    => 3,
    "4の目"    => 4,
    "5の目"    => 5,
    "6の目"    => 6
);

$result = rand(1, 6);
echo array_search($result, $dice);

　プログラムで表すと、このような感じである。乱数を生成する関数がどのような言語にもあるから、それを使って1～6の範囲で乱数を生成すればよい。サイコロの目を出すプログラムであれば、これでいい。なぜならどの目も同じ確率で出るからである。

ガチャやくじ引きはサイコロとどう違うか

　今度はガチャやくじ引きについて考えてみよう。これはサイコロとは異なり、１個しかない１等や、膨大な数の６等といったものまで出る確率が様々に異なるものの中から１つの結果が抽選される。

　物事の確率というのは、0%～100%の間に納まっている必要がある。非常に珍しいものは0.0000000000001%で出るとか、そういう希少性を持つものもあるだろう。一方99.999997%で出るようなハズレみたいなものもあったりするだろう。そして、商品は後から新しいものが足されたり、誰かが獲得したことによってなくなってしまったりする。そのたびにすべての商品の抽選確率は変化していなければならないように思えてくる。そんな複雑なことを一体どうやって実装できるのだろうか？

重み付き乱択アルゴリズム

　そこで登場するのが重み付き乱択アルゴリズムである。仰々しい名前なので、自分にはとても理解できそうもないと身構えてしまいそうになるのをこらえて、読んでみてほしい。

　こんな感じの図を考えてみよう。Aに1、Bに2～4、Cには5～10、Dは11～20、Eに21～130と書いてある。なんだこれはと思うだろう。これは商品Aは1、商品Bは2～4、商品Cは5～10・・・というような意味だ。で、下にはそれぞれの商品の数字の幅を合計した計算が書いてある。数字の幅はその商品の出やすさ、出にくさで狭くとったり広くとったりする。商品Aはめったに出ない。商品Eはかなり出やすい。この図の状態で、合計値である130までの乱数を一つ出すと、その値はこの図の中のどれかの範囲に収まる。驚くほどわかりやすい。それぞれの商品の確率を計算したければ計算することもできる。たとえばこうなる。

　重み付き乱択の基本的な理屈は、たったこれだけのことだ。しかし、実装上ちょっと困った事がある。2～4とか、5～10などといった範囲を持った値を扱うのが面倒だという事である。だから大抵はこういう風に逆に考える。

　プログラムで書き表すと、このような感じである。

<?php

$dice = array(
    "商品A"    => 1,
    "商品B"    => 3,
    "商品C"    => 6,
    "商品D"    => 10,
    "商品E"    => 110
);

$sum  = array_sum($dice);
$rand = rand(0, $sum);

foreach($dice as $key => $probability)
{
    if (($sum -= $probability) < $rand)
    {
        echo $key . "がでました。";
        break;
    }
}